Top 10 Arxiv Papers Today in Computer Science And Game Theory


2.103 Mikeys
#1. Incentivizing Exploration with Unbiased Histories
Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, Zhiwei Steven Wu
In a social learning setting, there is a set of actions, each of which has a payoff that depends on a hidden state of the world. A sequence of agents each chooses an action with the goal of maximizing payoff given estimates of the state of the world. A disclosure policy tries to coordinate the choices of the agents by sending messages about the history of past actions. The goal of the algorithm is to minimize the regret of the action sequence. In this paper, we study a particular class of disclosure policies that use messages, called unbiased subhistories, consisting of the actions and rewards from by a subsequence of past agents, where the subsequence is chosen ahead of time. One trivial message of this form contains the full history; a disclosure policy that chooses to use such messages risks inducing herding behavior among the agents and thus has regret linear in the number of rounds. Our main result is a disclosure policy using unbiased subhistories that obtains regret $\tilde{O}(\sqrt{T})$. We also exhibit simpler policies...
more | pdf | html
Figures
None.
Tweets
BrundageBot: Incentivizing Exploration with Unbiased Histories. Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu https://t.co/Nkhi2dJkMc
arxivml: "Incentivizing Exploration with Unbiased Histories", Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, Zhiwei Ste… https://t.co/d2SvaelKC0
DO: Incentivizing Exploration with Unbiased Histories. https://t.co/llYr8gwX5Y
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 14696
Unqiue Words: 2644

2.008 Mikeys
#2. Cooperation Enforcement and Collusion Resistance in Repeated Public Goods Games
Kai Li, Dong Hao
Enforcing cooperation among substantial agents is one of the main objectives for multi-agent systems. However, due to the existence of inherent social dilemmas in many scenarios, the free-rider problem may arise during agents' long-run interactions and things become even severer when self-interested agents work in collusion with each other to get extra benefits. It is commonly accepted that in such social dilemmas, there exists no simple strategy for an agent whereby she can simultaneously manipulate on the utility of each of her opponents and further promote mutual cooperation among all agents. Here, we show that such strategies do exist. Under the conventional repeated public goods game, we novelly identify them and find that, when confronted with such strategies, a single opponent can maximize his utility only via global cooperation and any colluding alliance cannot get the upper hand. Since a full cooperation is individually optimal for any single opponent, a stable cooperation among all players can be achieved. Moreover, we...
more | pdf | html
Figures
Tweets
DO: Cooperation Enforcement and Collusion Resistance in Repeated Public Goods Games. https://t.co/hQWvjFM6vo
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7000
Unqiue Words: 1900

2.001 Mikeys
#3. Heuristic Voting as Ordinal Dominance Strategies
Omer Lev, Reshef Meir, Svetlana Obraztsova, Maria Polukarov
Decision making under uncertainty is a key component of many AI settings, and in particular of voting scenarios where strategic agents are trying to reach a joint decision. The common approach to handle uncertainty is by maximizing expected utility, which requires a cardinal utility function as well as detailed probabilistic information. However, often such probabilities are not easy to estimate or apply. To this end, we present a framework that allows "shades of gray" of likelihood without probabilities. Specifically, we create a hierarchy of sets of world states based on a prospective poll, with inner sets contain more likely outcomes. This hierarchy of likelihoods allows us to define what we term ordinally-dominated strategies. We use this approach to justify various known voting heuristics as bounded-rational strategies.
more | pdf | html
Figures
None.
Tweets
DO: Heuristic Voting as Ordinal Dominance Strategies. https://t.co/0xm2BXNQh0
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 8155
Unqiue Words: 2053

2.001 Mikeys
#4. A Game Theoretic Approach for Dynamic Information Flow Tracking to Detect Multi-Stage Advanced Persistent Threats
Shana Moothedath, Dinuka Sahabandu, Joey Allen, Andrew Clark, Linda Bushnell, Wenke Lee, Radha Poovendran
Advanced Persistent Threats (APTs) infiltrate cyber systems and compromise specifically targeted data and/or resources through a sequence of stealthy attacks consisting of multiple stages. Dynamic information flow tracking has been proposed to detect APTs. In this paper, we develop a dynamic information flow tracking game for resource-efficient detection of APTs via multi-stage dynamic games. The game evolves on an information flow graph, whose nodes are processes and objects (e.g. file, network endpoints) in the system and the edges capture the interaction between different processes and objects. Each stage of the game has pre-specified targets which are characterized by a set of nodes of the graph and the goal of the APT is to evade detection and reach a target node of that stage. The goal of the defender is to maximize the detection probability while minimizing performance overhead on the system. The resource costs of the players are different and the information structure is asymmetric resulting in a nonzero-sum imperfect...
more | pdf | html
Figures
Tweets
DO: A Game Theoretic Approach for Dynamic Information Flow Tracking to Detect Multi-Stage Advanced Persistent Threats. https://t.co/0FGuqL2x2H
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 7
Total Words: 16718
Unqiue Words: 2747

0.0 Mikeys
#5. Truthful Peer Grading with Limited Effort from Teaching Staff
Jatin Jindal, Swaprava Nath
Massive open online courses pose a massive challenge for grading the answerscripts at a high accuracy. Peer grading is often viewed as a scalable solution to this challenge, which largely depends on the altruism of the peer graders. Some approaches in the literature treat peer grading as a 'best-effort service' of the graders, and statistically correct their inaccuracies before awarding the final scores, but ignore graders' strategic behavior. Few other approaches incentivize non-manipulative actions of the peer graders but do not make use of certain additional information that is potentially available in a peer grading setting, e.g., the true grade can eventually be observed at an additional cost. This cost can be thought of as an additional effort from the teaching staff if they had to finally take a look at the corrected papers post peer grading. In this paper, we use such additional information and introduce a mechanism, TRUPEQA, that (a) uses a constant number of instructor-graded answerscripts to quantitatively measure the...
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11630
Unqiue Words: 2453

0.0 Mikeys
#6. The Complexity of Sequential Routing Games
Anisse Ismaili
We study routing games where every agent sequentially decides her next edge when she obtains the green light at each vertex. Because every edge only has capacity to let out one agent per round, an edge acts as a FIFO waiting queue that causes congestion on agents who enter. Given $n$ agents over $|V|$ vertices, we show that for one agent, approximating a winning strategy within $n^{1-\varepsilon}$ of the optimum for any $\varepsilon>0$, or within any polynomial of $|V|$, are PSPACE-hard. Under perfect information, computing a subgame perfect equilibrium (SPE) is PSPACE-hard and in FPSPACE. Under imperfect information, deciding SPE existence is PSPACE-complete.
more | pdf | html
Figures
None.
Tweets
WhalezEye: RT @DO: The Complexity of Sequential Routing Games. https://t.co/p9gCI3lRRa
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 7611
Unqiue Words: 2016

0.0 Mikeys
#7. Almost Envy Freeness and Welfare Efficiency in Fair Division with Goods or Bads
Martin Aleksandrov
We consider two models of fair division with indivisible items: one for goods and one for bads. For both models, we study four generalized envy freeness proxies (EF1 and EFX for goods, and 1EF and XEF for bads) and three common welfare (utilitarian, egalitarian and Nash) efficiency notions. We revealed a close relation between these properties that allow us to use for bads a few existing algorithms for goods. However, most existing algorithms for goods do not work for bads. We thus propose several new algorithms for the model with bads. Our new algorithms exhibit many nice properties. For example, with goods and additive valuations, Nash efficiency and EF1 can be achieved simultaneously. With bads, the problem was unresolved. In response, we propose a new negative Nash welfare and an algorithm for it that is further 1EF. We also give simple cases when these envy freeness proxies and welfare efficiency are attainable.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 11935
Unqiue Words: 1719

0.0 Mikeys
#8. On the Inducibility of Stackelberg Equilibrium for Security Games
Qingyu Guo, Jiarui Gan, Fei Fang, Long Tran-Thanh, Milind Tambe, Bo An
Strong Stackelberg equilibrium (SSE) is the standard solution concept of Stackelberg security games. As opposed to the weak Stackelberg equilibrium (WSE), the SSE assumes that the follower breaks ties in favor of the leader and this is widely acknowledged and justified by the assertion that the defender can often induce the attacker to choose a preferred action by making an infinitesimal adjustment to her strategy. Unfortunately, in security games with resource assignment constraints, the assertion might not be valid; it is possible that the defender cannot induce the desired outcome. As a result, many results claimed in the literature may be overly optimistic. To remedy, we first formally define the utility guarantee of a defender strategy and provide examples to show that the utility of SSE can be higher than its utility guarantee. Second, inspired by the analysis of leader's payoff by Von Stengel and Zamir (2004), we provide the solution concept called the inducible Stackelberg equilibrium (ISE), which owns the highest utility...
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 6
Total Words: 9756
Unqiue Words: 2283

0.0 Mikeys
#9. Dealing with the Dimensionality Curse in Dynamic Pricing Competition: Using Frequent Repricing to Compensate Imperfect Market Anticipations
Rainer Schlosser, Martin Boissier
Most sales applications are characterized by competition and limited demand information. For successful pricing strategies, frequent price adjustments as well as anticipation of market dynamics are crucial. Both effects are challenging as competitive markets are complex and computations of optimized pricing adjustments can be time-consuming. We analyze stochastic dynamic pricing models under oligopoly competition for the sale of perishable goods. To circumvent the curse of dimensionality, we propose a heuristic approach to efficiently compute price adjustments. To demonstrate our strategy's applicability even if the number of competitors is large and their strategies are unknown, we consider different competitive settings in which competitors frequently and strategically adjust their prices. For all settings, we verify that our heuristic strategy yields promising results. We compare the performance of our heuristic against upper bounds, which are obtained by optimal strategies that take advantage of perfect price anticipations. We...
more | pdf | html
Figures
None.
Tweets
saeedamenfx: Dealing with the Dimensionality Curse in Dynamic Pricing Competition: Using Frequent Repricing to Compensate Imperfect Market Anticipations https://t.co/NJ7JqYvGfd #QuantLinkADay
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 15116
Unqiue Words: 3094

0.0 Mikeys
#10. Strategic Availability and Cost Effective UAV-based Flying Access Networks: S-Modular Game Analysis
Sara Handouf, Essaid Sabir
Telecommunication service providers deploy UAVs to provide flying network access in remote rural areas, disaster-affected areas or massive-attended events (sport venues, festivals, etc.) where full set-up to provide temporary wireless coverage would be very expensive. Of course, a UAV is battery-powered which means limited energy budget for both mobility aspect and communication aspect. An efficient solution is to allow UAVs switching their radio modules to sleep mode in order to extend battery lifetime. This results in temporary unavailability of communication feature. Within such a situation, the ultimate deal for a UAV operator is to provide a cost effective service with acceptable availability. This would allow to meet some target Quality of Service while having a good market share granting satisfactory benefits. We construct a duopoly model to capture the adversarial behavior of service providers in terms of their pricing policies and their respective availability probabilities. Optimal periodic beaconing (small messages...
more | pdf | html
Figures
Tweets
arxiv_org: Strategic Availability and Cost Effective UAV-based Flying Access Networks: S-Modular Gam... https://t.co/x4deUb8w8N https://t.co/IT9GIXq2JS
DO: Strategic Availability and Cost Effective UAV-based Flying Access Networks: S-Modular Game Analysis. https://t.co/PLrOggmsZO
Github
None.
Youtube
None.
Other stats
Sample Sizes : [50]
Authors: 2
Total Words: 7153
Unqiue Words: 2156

About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 57,756 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 57,756 papers.