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

##### #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
None.
###### Tweets
DO: Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries. https://t.co/4saSdXMAXg
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 17774
Unqiue Words: 2629

##### #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
###### Tweets
DO: Envy, Regret, and Social Welfare Loss. https://t.co/WjjpcAURNG
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 10775
Unqiue Words: 2532

##### #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
None.
###### Tweets
DO: Optimal Bi-level Lottery Design for Multi-agent Systems. https://t.co/n8cb9c8AKy
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
DO: A substitute for the classical Neumann--Morgenstern characteristic function in cooperative differential games. https://t.co/QLz9PekqI3
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8523
Unqiue Words: 1900

##### #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
###### Tweets
DO: Convergence and Hardness of Strategic Schelling Segregation. https://t.co/lUJZBzEkp1
None.
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
Online
###### Stats
Tracking 160,434 papers.