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

##### #1. Relating Metric Distortion and Fairness of Social Choice Rules
###### Ashish Goel, Reyna Hulett, Anilesh K. Krishnaswamy
One way of evaluating social choice (voting) rules is through a utilitarian distortion framework. In this model, we assume that agents submit full rankings over the alternatives, and these rankings are generated from underlying, but unknown, quantitative costs. The \emph{distortion} of a social choice rule is then the ratio of the total social cost of the chosen alternative to the optimal social cost of any alternative; since the true costs are unknown, we consider the worst-case distortion over all possible underlying costs. Analogously, we can consider the worst-case \emph{fairness ratio} of a social choice rule by comparing a useful notion of fairness (based on approximate majorization) for the chosen alternative to that of the optimal alternative. With an additional metric assumption -- that the costs equal the agent-alternative distances in some metric space -- it is known that the Copeland rule achieves both a distortion and fairness ratio of at most 5. For other rules, only bounds on the distortion are known, e.g., the...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8741
Unqiue Words: 1822

##### #2. The Temporary Exchange Problem
###### Haris Aziz, Edward Lee
We formalize an allocation model under ordinal preferences that is more general than the well-studied Shapley-Scarf housing market. In our model, the agents do not just care which house or resource they get but also care about who gets their own resource. This assumption is especially important when considering temporary exchanges in which each resource is eventually returned to the owner. We show that several positive axiomatic and computational results that hold for housing markets do not extend to the more general setting. We then identify natural restrictions on the preferences of agents for which several positive results do hold. One of our central results is a general class of algorithms that return any allocation that is individually rational and Pareto optimal with respect to the responsive set extension.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 5809
Unqiue Words: 1241

##### #3. Stochastic Stability in Schelling's Segregation Model with Markovian Asynchronous Update
###### Gabriel Istrate
We investigate the dependence of steady-state properties of Schelling's segregation model on the agents' activation order. Our basic formalism is the Pollicott-Weiss version of Schelling's segregation model. Our main result modifies this baseline scenario by incorporating contagion in the decision to move: (pairs of) agents are connected by a second, agent influence network. Pair activation is specified by a random walk on this network. The considered schedulers choose the next pair nonadaptively. We can complement this result by an example of adaptive scheduler (even one that is quite fair) that is able to preclude maximal segregation. Thus scheduler nonadaptiveness seems to be required for the validity of the original result under arbitrary asynchronous scheduling. The analysis (and our result) are part of an adversarial scheduling approach we are advocating to evolutionary games and social simulations.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5461
Unqiue Words: 1694

##### #4. A Mathematical Model for Optimal Decisions in a Representative Democracy
###### Malik Magdon-Ismail, Lirong Xia
Direct democracy is a special case of an ensemble of classifiers, where every person (classifier) votes on every issue. This fails when the average voter competence (classifier accuracy) falls below 50%, which can happen in noisy settings where voters have only limited information, or when there are multiple topics and the average voter competence may not be high enough for some topics. Representative democracy, where voters choose representatives to vote, can be an elixir in both these situations. Representative democracy is a specific way to improve the ensemble of classifiers. We introduce a mathematical model for studying representative democracy, in particular understanding the parameters of a representative democracy that gives maximum decision making capability. Our main result states that under general and natural conditions, 1. Representative democracy can make the correct decisions simultaneously for multiple noisy issues. 2. When the cost of voting is fixed, the optimal representative democracy requires that...
more | pdf | html
None.
###### Tweets
k1ito: #質問箱一個につき論文一個紹介する https://t.co/mwJhyEdJ3j 間接民主主義を機械学習的・数理モデル的に解析する論文。 考え・解析は面白いけど別に使い道もなさそうなので深くは読んでないのですが、誰か教えて下さいという意味で紹介。
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 12539
Unqiue Words: 2628

##### #5. Markets Beyond Nash Welfare for Leontief Utilities
###### Ashish Goel, Reyna Hulett, Benjamin Plaut
We study the allocation of divisible goods to competing agents via a market mechanism, focusing on agents with Leontief utilities. The majority of the economics and mechanism design literature has focused on \emph{linear} prices, meaning that the cost of a good is proportional to the quantity purchased. Equilibria for linear prices are known to be exactly the maximum Nash welfare allocations. \emph{Price curves} allow the cost of a good to be any (increasing) function of the quantity purchased. We show that price curve equilibria are not limited to maximum Nash welfare allocations with two main results. First, we show that an allocation can be supported by strictly increasing price curves if and only if it is \emph{group-domination-free}. A similarly characterization holds for weakly increasing price curves. We use this to show that given any allocation, we can compute strictly (or weakly) increasing price curves that support it (or show that none exist) in polynomial time. These results involve a connection to the...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 20146
Unqiue Words: 2884

##### #6. Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries
###### Paul W. Goldberg, Francisco J. Marmolejo-Cossío
Suppose that an $m$-simplex is partitioned into $n$ convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance $\epsilon$ from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant $m$ uses $poly(n, \log \left( \frac{1}{\epsilon} \right))$ queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant $n$ uses $poly(m, \log \left( \frac{1}{\epsilon} \right))$ queries. We show via Kakutani's fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 21144
Unqiue Words: 3243

##### #7. Jamming in multiple independent Gaussian channels as a game
###### Michail Fasoulakis, Apostolos Traganitis, Anthony Ephremides
We study the problem of \emph{jamming} in multiple independent \emph{Gaussian channels} as a zero-sum game. We show that in the unique Nash equilibrium of the game the best-response strategy of the transmitter is the \emph{waterfilling} to the sum of the jamming and the noise power in each channel and the best-response strategy of the jammer is the \emph{waterfilling} only to the noise power.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 2340
Unqiue Words: 629

##### #8. Fair allocation of combinations of indivisible goods and chores
###### Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi
We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are "goods" i.e., they yield positive utility for the agents. There is also some work where the items are "chores" that yield negative utility for the agents. In this work, we consider more general scenarios where for any item, an agent may have negative or positive utility for it. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties as well as the computational complexity of computing such allocations.
more | pdf | html
None.
###### Tweets
DO: Fair allocation of combinations of indivisible goods and chores. https://t.co/fgHCmql7Wh
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8523
Unqiue Words: 1781

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

##### #10. 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

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 72,893 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 72,893 papers.