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.

DO:
Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries. https://t.co/4saSdXMAXg

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 17774

Unqiue Words: 2629

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
DO:
Envy, Regret, and Social Welfare Loss. https://t.co/WjjpcAURNG

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 10775

Unqiue Words: 2532

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.

DO:
Optimal Bi-level Lottery Design for Multi-agent Systems. https://t.co/n8cb9c8AKy

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

DO:
A substitute for the classical Neumann--Morgenstern characteristic function in cooperative differential games. https://t.co/QLz9PekqI3

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 8523

Unqiue Words: 1900

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
DO:
Convergence and Hardness of Strategic Schelling Segregation. https://t.co/lUJZBzEkp1

None.

None.

Sample Sizes : None.

Authors: 8

Total Words: 12425

Unqiue Words: 2239

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible