Abstract | In sponsored search auctions, advertisers compete for a number
of available advertisement slots of different quality. The
auctioneer decides the allocation of advertisers to slots using
bids provided by them. Since the advertisers may act
strategically and submit their bids in order to maximize their
individual objectives, such an auction naturally defines a
strategic game among the advertisers. In order to quantify
the efficiency of outcomes in generalized second price auctions,
we study the corresponding games and present new
bounds on their price of anarchy, improving the recent results
of Paes Leme and Tardos [16] and Lucier and Paes
Leme [13]. For the full information setting, we prove a surprisingly
low upper bound of 1.282 on the price of anarchy
over pure Nash equilibria. Given the existing lower bounds,
this bound denotes that the number of advertisers has almost
no impact on the price of anarchy. The proof exploits
the equilibrium conditions developed in [16] and follows by
a detailed reasoning about the structure of equilibria and a
novel relation of the price of anarchy to the objective value
of a compact mathematical program. For more general equilibrium
classes (i.e., mixed Nash, correlated, and coarse correlated
equilibria), we present an upper bound of 2.310 on
the price of anarchy. We also consider the setting where
advertisers have incomplete information about their competitors
and prove a price of anarchy upper bound of 3.037
over Bayes-Nash equilibria. In order to obtain the last two
bounds, we adapt techniques of Lucier and Paes Leme [13]
and significantly extend them with new arguments |