In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategize in order to maximize their utilities. A number of results indicate that high welfare can be achieved this way, giving bounds on the welfare at equilibrium. Recently, however, criticism has been raised that equilibria are hard to compute and therefore unlikely to be attained. In this paper, we take a different perspective. We study simple best-response dynamics. That is, agents are activated one after the other and each activated agent updates his strategy myopically to a best response against the other agents' current strategies. Often these dynamics may take exponentially long before they converge or they may not converge at all. However, as we show, convergence is not even necessary for good welfare guarantees. Given that agents' bid updates are aggressive enough but not too aggressive, the game will remain in states of good welfare after each agent has updated his bid at least once. In more detail, we show that if agents have fractionally subadditive valuations, natural dynamics reach and remain in a state that provides a @math approximation to the optimal welfare after each agent has updated his bid at least once. For subadditive valuations, we can guarantee an @math approximation in case of @math items that applies after each agent has updated his bid at least once and at any point after that. The latter bound is complemented by a negative result, showing that no kind of best-response dynamics can guarantee more than an @math fraction of the optimal social welfare.
The study of the Price of Anarchy in combinatorial auctions with item bidding was initiated by @cite_10 , and subsequently refined and improved upon in @cite_0 @cite_21 @cite_2 @cite_15 @cite_13 . Some of these bounds are based on mechanism smoothness, others are not. They provide welfare guarantees for a broad range of equilibrium concepts ranging from pure Nash equilibria, over (coarse) correlated equilibria, to Bayes-Nash equilibria. For fractionally subadditive valuations there is a smoothness-based proof that shows that the Price of Anarchy with respect to pure Nash equilibria is at most @math @cite_10 @cite_2 . For subadditive valuations the Price of Anarchy with respect to pure Nash equilibria is also at most @math @cite_0 , but the best smoothness-based proof gives a bound of @math @cite_0 @cite_2 . In fact, as shown by Roughgarden @cite_12 , combinatorial auctions with item bidding achieve (near-)optimal Price of Anarchy among a broad class of simple'' mechanisms.
@cite_13 @cite_21 @cite_0 @cite_2 @cite_15 @cite_10 @cite_12
2022890659 1967821428 2294025081 2133243407
The Generalized Second Price Auction has been the main mechanism used by search companies to auction positions for advertisements on search pages. In this paper we study the social welfare of the Nash equilibria of this game in various models. In the full information setting, socially optimal Nash equilibria are known to exist (i.e., the Price of Stability is 1). This paper is the first to prove bounds on the price of anarchy, and to give any bounds in the Bayesian setting. Our main result is to show that the price of anarchy is small assuming that all bidders play un-dominated strategies. In the full information setting we prove a bound of 1.618 for the price of anarchy for pure Nash equilibria, and a bound of 4 for mixed Nash equilibria. We also prove a bound of 8 for the price of anarchy in the Bayesian setting, when valuations are drawn independently, and the valuation is known only to the bidder and only the distributions used are common knowledge. Our proof exhibits a combinatorial structure of Nash equilibria and uses this structure to bound the price of anarchy. While establishing the structure is simple in the case of pure and mixed Nash equilibria, the extension to the Bayesian setting requires the use of novel combinatorial techniques that can be of independent interest. 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. The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known for a wide range of application domains. However, such bounds are meaningful only if a game's participants successfully reach a Nash equilibrium. This drawback motivates inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash equilibria and correlated equilibria, and to sequences of outcomes generated by natural experimentation strategies, such as successive best responses and simultaneous regret-minimization. We establish a general and fundamental connection between the price of anarchy and its seemingly more general relatives. First, we identify a “canonical sufficient condition” for an upper bound on the price of anarchy of pure Nash equilibria, which we call a smoothness argument. Second, we prove an “extension theorem”: every bound on the price of anarchy that is derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of every outcome sequence generated by no-regret learners. Smoothness arguments also have automatic implications for the inefficiency of approximate equilibria, for bicriteria bounds, and, under additional assumptions, for polynomial-length best-response sequences. Third, we prove that in congestion games, smoothness arguments are “complete” in a proof-theoretic sense: despite their automatic generality, they are guaranteed to produce optimal worst-case upper bounds on the price of anarchy. The price of anarchy (POA) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a game and that of an optimal outcome. This measure implicitly assumes that players successfully reach some Nash equilibrium. This drawback motivates the search for inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash and correlated equilibria; or to sequences of outcomes generated by natural experimentation strategies, such as successive best responses or simultaneous regret-minimization. We prove a general and fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective. First, we identify a "canonical sufficient condition" for an upper bound of the POA for pure Nash equilibria, which we call a smoothness argument. Second, we show that every bound derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of regret-minimizing players (or "price of total anarchy"). Smoothness arguments also have automatic implications for the inefficiency of approximate and Bayesian-Nash equilibria and, under mild additional assumptions, for bicriteria bounds and for polynomial-length best-response sequences. We also identify classes of games --- most notably, congestion games with cost functions restricted to an arbitrary fixed set --- that are tight, in the sense that smoothness arguments are guaranteed to produce an optimal worst-case upper bound on the POA, even for the smallest set of interest (pure Nash equilibria). Byproducts of our proof of this result include the first tight bounds on the POA in congestion games with non-polynomial cost functions, and the first structural characterization of atomic congestion games that are universal worst-case examples for the POA.