Fetching the paper…

Reading the bibliography…

2012

Bayesian Games and the Smoothness Framework

Syrgkanis, Vasilis

Original
PDF
Post on X

Understand

We consider a general class of Bayesian Games where each players utility depends on his type (possibly multidimensional) and on the strategy profile and where players' types are distributed independently.

We show that if their full information version for any fixed instance of the type profile is a smooth game then the Price of Anarchy bound implied by the smoothness property, carries over to the Bayes-Nash Price of Anarchy.
We show how some proofs from the literature (item bidding auctions, greedy auctions) can be cast as smoothness proofs or be simplified using smoothness.
For first price item bidding with fractionally subadditive bidders we actually manage to improve by much the existing result \cite{Hassidim2011a} from 4 to $\frac{e}{e-1}\approx 1.58$.

Bayesian Games and the Smoothness Framework · Around

Built on

Worst-case equilibria
E. Koutsoupias and C. H. Papadimitriou · 1999
Earlier work this paper cites.
Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions
Original
A. Vetta · 2002
Earlier work this paper cites.
Intrinsic robustness of the price of anarchy
T. Roughgarden · 2009
Earlier work this paper cites.
Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness
K. Bhawalkar and M. Gairing · 2010
Earlier work this paper cites.
Bayesian combinatorial auctions
G. Christodoulou, A. Kovács, and M. Schapira · 2010
Earlier work this paper cites.

Similar

Price of anarchy for greedy auctions
B. Lucier and A. Borodin · 2010
Cited alongside, same era.
Pure and Bayes-Nash price of anarchy for generalized second price auction
R. Paes Leme and E. Tardos · 2010
Cited alongside, same era.
Efficiency and the Redistribution of Welfare
Y. Bachrach, V. Syrgkanis, and M. Vojnovi \ \backslash ’c · 2011
Cited alongside, same era.
Welfare Guarantees for Combinatorial Auctions with Item Bidding
K. Bhawalkar and T. Roughgarden · 2011
Cited alongside, same era.

Then

On the Efficiency of Equilibria in Generalized Second Price Auctions
I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou · 2011
Later among the works it cites.
Non-price equilibria in markets of discrete goods
A. Hassidim, H. Kaplan, Y. Mansour, and N. Nisan · 2011
Later among the works it cites.
GSP auctions with correlated types
B. Lucier and R. Leme · 2011
Later among the works it cites.
Local smoothness and the price of anarchy in atomic splittable congestion games
T. Roughgarden and F. Schoppmann · 2011
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…