We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multi-parameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show for a variety of equilibrium concepts, including Bayes-Nash equilibrium and correlated equilibrium, the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.
The BNE solution concept was recently applied to submodular combinatorial auctions @cite_12 , where it was shown that a randomized mechanism can attain a @math -approximation at any mixed equilibrium assuming that bidders are ex-post individually rational. Pure equilibria of first-price mechanisms have also been studied for path procurement auctions @cite_1 . Performance at Nash equilibrium has been extensively studied in the economics literature (see Jackson @cite_13 for a survey) and recently in work on Internet advertising slot auctions @cite_8 @cite_23 . In that line of research the goal is often revenue maximization, rather than social welfare maximization, and traditionally one wishes to implement a particular optimal allocation rule, rather than guarantee a given approximation ratio.
@cite_8 @cite_1 @cite_23 @cite_13 @cite_12
2127595535 1975392791 1977483205 1489333206
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the designer has flexibility in specifying remaining details. We assume edges are independent agents with fixed capacities and costs, and their objective is to maximize their profit. We characterize all strong e-Nash equilibria of a first-price auction, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves mechanism. We then present a randomized version of the first-price auction for which the equilibrium condition can be relaxed to e-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known. For this model, we show that a simple ex ante first-price auction may not have any e-Nash equilibria. We then present a modified mechanism with 2-parameter bids which does have an e-Nash equilibrium. For a randomized version of this 2-parameter mechanism we characterize the set of all eNEs and prove a bound on the total payment in any eNE. We investigate the "generalized second price" auction (GSP), a new mechanism which is used by search engines to sell online advertising that most Internet users encounter daily. GSP is tailored to its unique environment, and neither the mechanism nor the environment have previously been studied in the mechanism design literature. Although GSP looks similar to the Vickrey-Clarke-Groves (VCG) mechanism, its properties are very different. In particular, unlike the VCG mechanism, GSP generally does not have an equilibrium in dominant strategies, and truth-telling is not an equilibrium of GSP. To analyze the properties of GSP in a dynamic environment, we describe the generalized English auction that corresponds to the GSP and show that it has a unique equilibrium. This is an ex post equilibrium that results in the same payoffs to all players as the dominant strategy equilibrium of VCG. This paper is meant to familiarize the audience with some of the fundamental results in the theory of implementation and provide a quick progression to some open questions in the literature. We study the following Bayesian setting: mitems are sold to nselfish bidders in mindependent second-price auctions. Each bidder has a privatevaluation function that expresses complex preferences over allsubsets of items. Bidders only have beliefsabout the valuation functions of the other bidders, in the form of probability distributions. The objective is to allocate the items to the bidders in a way that provides a good approximation to the optimal social welfare value. We show that if bidders have submodular valuation functions, then every Bayesian Nash equilibrium of the resulting game provides a 2-approximation to the optimal social welfare. Moreover, we show that in the full-information game a pure Nash always exists and can be found in time that is polynomial in both mand n.