### Top 10 Arxiv Papers Today in Computer Science And Game Theory

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 14696
Unqiue Words: 2644

##### #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
###### Tweets
DO: Cooperation Enforcement and Collusion Resistance in Repeated Public Goods Games. https://t.co/hQWvjFM6vo
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7000
Unqiue Words: 1900

##### #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
None.
###### Tweets
DO: Heuristic Voting as Ordinal Dominance Strategies. https://t.co/0xm2BXNQh0
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 8155
Unqiue Words: 2053

##### #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
###### Tweets
DO: A Game Theoretic Approach for Dynamic Information Flow Tracking to Detect Multi-Stage Advanced Persistent Threats. https://t.co/0FGuqL2x2H
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 7
Total Words: 16718
Unqiue Words: 2747

##### #5. Truthful Peer Grading with Limited Effort from Teaching Staff
###### Jatin Jindal, Swaprava Nath
more | pdf | html
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11630
Unqiue Words: 2453

##### #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
None.
###### Tweets
WhalezEye: RT @DO: The Complexity of Sequential Routing Games. https://t.co/p9gCI3lRRa
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 7611
Unqiue Words: 2016

##### #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
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 11935
Unqiue Words: 1719

##### #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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 6
Total Words: 9756
Unqiue Words: 2283

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 15116
Unqiue Words: 3094

##### #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
###### 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
None.
None.
###### Other stats
Sample Sizes : [50]
Authors: 2
Total Words: 7153
Unqiue Words: 2156

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
Online
###### Stats
Tracking 57,756 papers.