Top 5 Arxiv Papers Today in Computer Science And Game Theory


2.001 Mikeys
#1. Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros A. Voudouris
Aggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitarian social choice setting, where the agents have explicit numerical values for the alternatives, yet they only report their linear orderings over them. To compare different aggregation mechanisms, Procaccia and Rosenschein introduced the notion of distortion, which quantifies the inefficiency of using only ordinal information when trying to maximize the social welfare, i.e., the sum of the underlying values of the agents for the chosen outcome. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a...
more | pdf | html
Figures
None.
Tweets
DO: Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries. https://t.co/4saSdXMAXg
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 17774
Unqiue Words: 2629

2.001 Mikeys
#2. Envy, Regret, and Social Welfare Loss
Riccardo Colini-Baldeschi, Stefano Leonardi, Okke Schrijvers, Eric Sodomka
Incentive compatibility (IC) is one of the most fundamental properties of an auction mechanism, including those used for online advertising. Recent methods by Feng et al. and Lahaie et al. show that counterfactual runs of the auction mechanism with different bids can be used to determine whether an auction is IC. In this paper we show that a similar result can be obtained by looking at the advertisers' envy, which can be computed with one single execution of the auction. We introduce two metrics to evaluate the incentive-compatibility of an auction: IC-Regret and IC-Envy. For position auction environments, we show that for a large class of pricing schemes (which includes e.g. VCG and GSP), IC-Envy $\ge$ IC-Regret (and IC-Envy = IC-Regret when bids are distinct). We consider non-separable discounts in the Ad Types environment of Colini-Baldeschi et al. where we show that for a generalization of GSP also IC-Envy $\ge$ IC-Regret. Our final theoretical result is that in all these settings IC-Envy be used to bound the loss in social...
more | pdf | html
Figures
Tweets
DO: Envy, Regret, and Social Welfare Loss. https://t.co/WjjpcAURNG
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 10775
Unqiue Words: 2532

2.001 Mikeys
#3. Optimal Bi-level Lottery Design for Multi-agent Systems
Hunmin Kim, Minghui Zhu
We consider a bi-level lottery where a social planner at the high level selects a reward first and, sequentially, a set of players at the low level jointly determine a Nash equilibrium given the reward. The social planner is faced with efficiency losses where a Nash equilibrium of the lottery game may not coincide with the social optimum. We propose an optimal bi-level lottery design problem as finding least reward and perturbations such that the induced Nash equilibrium produces the socially optimal payoff. We formally characterize the price of anarchy as well as the behavior of public goods and Nash equilibrium with respect to the reward and perturbations. We relax the optimal bi-level lottery design problem via a convex approximation and identify mild sufficient conditions under which the approximation is exact. A case study on demand response in the smart grid is conducted to demonstrate the results.
more | pdf | html
Figures
None.
Tweets
DO: Optimal Bi-level Lottery Design for Multi-agent Systems. https://t.co/n8cb9c8AKy
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

1.997 Mikeys
#4. A substitute for the classical Neumann--Morgenstern characteristic function in cooperative differential games
Ekaterina Gromova, Ekaterina Marova, Dmitry Gromov
In this paper, we present a systematic overview of different endogenous optimization-based characteristic functions and discuss their properties. Furthermore, we define and analyze in detail a new, $\eta$-characteristic function. This characteristic function has a substantial advantage over other characteristic functions in that it can be obtained with a minimal computational effort and has a reasonable economic interpretation. In particular, the new characteristic function can be seen as a reduced version of the classical Neumann-Morgenstern characteristic function, where the players both from the coalition and from the complementary coalition use their previously computed strategies instead of solving respective optimization problems. Our finding are illustrated by a pollution control game with $n$ non-identical players. For the considered game, we compute all characteristic functions and compare their properties. Quite surprisingly, it turns out that both the characteristic functions and the resulting cooperative...
more | pdf | html
Figures
None.
Tweets
DO: A substitute for the classical Neumann--Morgenstern characteristic function in cooperative differential games. https://t.co/QLz9PekqI3
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8523
Unqiue Words: 1900

1.997 Mikeys
#5. Convergence and Hardness of Strategic Schelling Segregation
Hagen Echzell, Tobias Friedrich, Pascal Lenzner, Louise Molitor, Marcus Pappik, Friedrich Schöne, Fabian Sommer, David Stangl
The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least $\tau$, for some $0<\tau<1$. Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak...
more | pdf | html
Figures
Tweets
DO: Convergence and Hardness of Strategic Schelling Segregation. https://t.co/lUJZBzEkp1
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 8
Total Words: 12425
Unqiue Words: 2239

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 160,434 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 160,434 papers.