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 Hassidim2011a from 4 to @math . This also shows a very interesting separation between first and second price item bidding since second price item bidding has PoA at least 2 even under complete information. For a larger class of Bayesian Games where the strategy space of a player also changes with his type we are able to show that a slightly stronger definition of smoothness also implies a Bayes-Nash PoA bound. We show how weighted congestion games actually satisfy this stronger definition of smoothness. This allows us to show that the inefficiency bounds of weighted congestion games known in the literature carry over to incomplete versions where the weights of the players are private information. We also show how an incomplete version of a natural class of monotone valid utility games, called effort market games are universally @math -smooth. Hence, we show that incomplete versions of effort market games where the abilities of the players and their budgets are private information has Bayes-Nash PoA at most 2.
There have also been several works on quantifying the inefficiency of incomplete information games, mainly in the context of auctions. A series of papers by Paes Leme and Tardos @cite_3 , Lucier and Paes Leme @cite_11 and @cite_12 studied the ineffficiency of Bayes-Nash equilibria of the generalized second price auction. Lucier and Borodin studied Bayes-Nash Equilibria of non-truthful auctions that are based on greedy allocation algorithms @cite_9 . A series of three papers, Christodoulou, Kovacs and Schapira @cite_2 , Bhawalkar and Roughgarden @cite_7 and Hassidim, Kaplan, Mansour, Nisan @cite_1 , studied the inefficiency of Bayes-Nash equilibria of non-truthful combinatorial auctions that are based on running simultaneous separate item auctions for each item. However, many of the results in this line of work where specific to the context and a unifying framework doesn't exist. Lucier and Paes Leme @cite_11 introduced the concept of semi-smoothness and showed that their proof for the inefficiency of the generalized second price auction falls into this category. However, semi-smoothness is a much more restrictive notion of smoothness than just requiring that every complete information instance of the game to be smooth.
@cite_7 @cite_9 @cite_1 @cite_3 @cite_2 @cite_12 @cite_11
1967821428 2022890659 2404718321 2072113937
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 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. We consider the problem of maximizing revenue in prior-free auctions for general single parameter settings. The setting is modeled by an arbitrary downward-closed set system, which captures many special cases such as single item, digital goods and single-minded combinatorial auctions. We relax the truthfulness requirement by the solution concept of Nash equilibria. Implementation by Nash equilibria is a natural and relevant framework in many applications of computer science, where auctions are run repeatedly and bidders can observe others’ strategies, but the auctioneer needs to design a mechanism in advance and cannot use any information on the bidders’ private valuations. We introduce a worst-case revenue benchmark which generalizes the second price of single item auction and the F2 benchmark, introduced by , for digital goods. We design a mechanism whose Nash equilibria obtains at least a constant factor of this benchmark and prove that no truthful mechanisms can achieve a constant approximation. In the traffic assignment problem, first proposed by Wardrop in 1952, commuters select the shortest available path to travel from their origins to their destinations. We study a generalization of this problem in which competitors, who may control a nonnegligible fraction of the total flow, ship goods across a network. This type of games, usually referred to as atomic games, readily applies to situations in which the competing freight companies have market power. Other applications include intelligent transportation systems, competition among telecommunication network service providers, and scheduling with flexible machines. Our goal is to determine to what extent these systems can benefit from some form of coordination or regulation. We measure the quality of the outcome of the game without centralized control by computing the worst-case inefficiency of Nash equilibria. The main conclusion is that although self-interested competitors will not achieve a fully efficient solution from the system's point of view, the loss is not too severe. We show how to compute several bounds for the worst-case inefficiency that depend on the characteristics of cost functions and on the market structure in the game. In addition, building upon the work of Catoni and Pallotino, we show examples in which market aggregation (or collusion) adversely impacts the aggregated competitors, even though their market power increases. For example, Nash equilibria of atomic network games may be less efficient than the corresponding Wardrop equilibria. When competitors are completely symmetric, we provide a characterization of the Nash equilibrium using a potential function, and prove that this counterintuitive phenomenon does not arise. Finally, we study a pricing mechanism that elicits more coordination from the players by reducing the worst-case inefficiency of Nash equilibria.