Top 10 Arxiv Papers Today in Computer Science And Game Theory


0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8741
Unqiue Words: 1822

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 5809
Unqiue Words: 1241

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5461
Unqiue Words: 1694

0.0 Mikeys
#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
Figures
None.
Tweets
k1ito: #質問箱一個につき論文一個紹介する https://t.co/mwJhyEdJ3j 間接民主主義を機械学習的・数理モデル的に解析する論文。 考え・解析は面白いけど別に使い道もなさそうなので深くは読んでないのですが、誰か教えて下さいという意味で紹介。
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 12539
Unqiue Words: 2628

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 20146
Unqiue Words: 2884

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 21144
Unqiue Words: 3243

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 2340
Unqiue Words: 629

0.0 Mikeys
#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
Figures
None.
Tweets
DO: Fair allocation of combinations of indivisible goods and chores. https://t.co/fgHCmql7Wh
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8523
Unqiue Words: 1781

0.0 Mikeys
#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
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11630
Unqiue Words: 2453

0.0 Mikeys
#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
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 6
Total Words: 9756
Unqiue Words: 2283

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