Computer Science – Computer Science and Game Theory
Scientific paper
2010-11-14
Computer Science
Computer Science and Game Theory
Scientific paper
The Generalized Second Price auction is the primary method by which sponsered search advertisements are sold. We study the performance of this auction under various equilibrium concepts. In particular, we demonstrate that the Bayesian Price of Anarchy is at most $2(1-1/e)^{-1} \approx 3.16$, significantly improving upon previously known bounds. Our techniques are intuitively straightforward and extend in a number of ways. For one, our result extends to a bound on the performance of GSP at coarse correlated equilibria, which captures (for example) a repeated-auction setting in which agents apply regret-minimizing bidding strategies. In addition, our analysis is robust against the presence of byzantine agents who cannot be assumed to participate rationally. Additionally, we present tight bounds for the social welfare obtained at pure NE for the special case of an auction for 3 slots, and discuss potential methods for extending this analysis to an arbitrary number of slots.
Leme Renato Paes
Lucier Brendan
No associations
LandOfFree
Improved Social Welfare Bounds for GSP at Equilibrium does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Social Welfare Bounds for GSP at Equilibrium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Social Welfare Bounds for GSP at Equilibrium will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-297792