The generalized second-price auction (GSP) is a non-truthful auction mechanism for multiple items. Each bidder places a bid. The highest bidder gets the first slot, the second-highest, the second slot and so on, but the highest bidder pays the price bid by the second-highest bidder, the second-highest pays the price bid by the third-highest, and so on. First conceived as a natural extension of the Vickrey auction, it conserves some of the desirable properties of the Vickrey auction. It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction basis. The first analyses of GSP are in the economics literature by Edelman, Ostrovsky, and Schwarz [1] and by Varian. [2] It is used by Google's AdWords technology and Facebook.
Suppose that there are bidders and slots. Each slot has a probability of being clicked of . We can assume that top slots have a larger probability of being clicked, so:
We can think of additional virtual slots with click-through-rate zero, so, for . Now, each bidder submits a bid indicating the maximum they are willing to pay for a slot. Each bidder also has an intrinsic value for buying a slot . Notice that a player's bid doesn't need to be the same as their true valuation. We order the bidders by their bid, let's say:
and charge each bidder a price . The price will be 0 if they didn't win a slot. Slots are sold in a pay-per-click model, so a bidder just pays for a slot if the user actually clicks in that slot. We say the utility of bidder who is allocated to slot is . The total social welfare from owning or selling all slots is given by: The expected total revenue is given by:
To specify a mechanism we need to define the allocation rule (who gets which slot) and the prices paid by each bidder. In a generalized second-price auction we order the bidders by their bid and give the top slot to the highest bidder, the second top slot to the second highest bidder and so on. Then, assuming the bids are listed in decreasing order the bidder bidding gets slot for . Each bidder winning a slot pays the bid of the next highest bidder, so: .
There are cases where bidding the true valuation is not a Nash equilibrium. For example, consider two slots with and and three bidders with valuations , and and bids , and respectively. Thus, , and . The utility for bidder is This set of bids is not a Nash equilibrium, since the first bidder could lower their bid to 5 and get the second slot for the price of 1, increasing their utility to .
Edelman, Ostrovsky and Schwarz, [1] working under complete information, show that GSP (in the model presented above) always has an efficient locally-envy free equilibrium, i.e., an equilibrium maximizing social welfare, which is measured as where bidder is allocated slot according to the decreasing bid vector . Further, the expected total revenue in any locally-envy free equilibrium is at least as high as in the (truthful) VCG outcome.
Bounds on the welfare at Nash equilibrium are given by Caragiannis et al., [3] proving a price of anarchy bound of . Dütting et al. [4] and Lucier at al. prove [5] that any Nash equilibrium extracts at least one half of the truthful VCG revenue from all slots but the first. Computational analysis of this game have been performed by Thompson and Leyton-Brown. [6]
The classical results due to Edelman, Ostrovsky and Schwarz [1] and Varian [2] hold in the full information setting – when there is no uncertainty involved. Recent results as Gomes and Sweeney [7] and Caragiannis et al. [3] and also empirically by Athey and Nekipelov [8] discuss the Bayesian version of the game - where players have beliefs about the other players but do not necessarily know the other players' valuations.
Gomes and Sweeney [7] prove that an efficient equilibrium might not exist in the partial information setting. Caragiannis et al. [3] consider the welfare loss at Bayes–Nash equilibrium and prove a price of anarchy bound of 2.927. Bounds on the revenue in Bayes–Nash equilibrium are given by Lucier et al. [5] and Caragiannis et al. [9]
The effect of budget constraints in the sponsored search or position auction model is discussed in Ashlagi et al. [10] and in the more general assignment problem by Aggarwal et al. [11] and Dütting et al. [12]
A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. Bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins but the price paid is the second-highest bid. This type of auction is strategically similar to an English auction and gives bidders an incentive to bid their true value. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893. In 1797 Johann Wolfgang von Goethe sold a manuscript using a sealed-bid, second-price auction.
The principle of detailed balance can be used in kinetic systems which are decomposed into elementary processes. It states that at equilibrium, each elementary process is in equilibrium with its reverse process.
In game theory, the war of attrition is a dynamic timing game in which players choose a time to stop, and fundamentally trade off the strategic gains from outlasting other players and the real costs expended with the passage of time. Its precise opposite is the pre-emption game, in which players elect a time to stop, and fundamentally trade off the strategic costs from outlasting other players and the real gains occasioned by the passage of time. The model was originally formulated by John Maynard Smith; a mixed evolutionarily stable strategy (ESS) was determined by Bishop & Cannings. An example is a second price all-pay auction, in which the prize goes to the player with the highest bid and each player pays the loser's low bid.
In mathematics and economics, the envelope theorem is a major result about the differentiability properties of the value function of a parameterized optimization problem. As we change parameters of the objective, the envelope theorem shows that, in a certain sense, changes in the optimizer of the objective do not contribute to the change in the objective function. The envelope theorem is an important tool for comparative statics of optimization models.
A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.
A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction. In this type of auction, all bidders simultaneously submit sealed bids so that no bidder knows the bid of any other participant. The highest bidder pays the price that was submitted.
Revenue equivalence is a concept in auction theory that states that given certain conditions, any mechanism that results in the same outcomes also has the same expected revenue.
The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Here, efficiency means the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases.
Market design is an interdisciplinary engineering-driven approach to economics and a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In market design, the focus is on the rules of exchange-- meaning who gets allocated what and by what procedure. Market design is concerned with the workings of particular markets in order to fix them when they are broken or to build markets when they are missing. Market design principles have been implemented in auction theory and matching theory.
A sponsored search auction (SSA), also known as a keyword auction, is an indispensable part of the business model of modern web hosts. It refers to results from a search engine that are not output by the main search algorithm, but rather clearly separate advertisements paid for by third parties. These advertisements are typically related to the terms for which the user searched. They come in the form of a link and some information, with the hope that a search user will click on the link and buy something from the advertiser. In sponsored search auctions, there are typically some fixed number of slots for advertisements and more advertisers that want these slots than there are slots. The advertisers have different valuations for these slots and slots are a scarce resource, so an auction is done to determine how the slots will be assigned.
In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear -ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
The generalized first-price auction (GFP) is a non-truthful auction mechanism for sponsored search. In sponsored search n bidders compete for the assignment of k slots. Each slot has an associate click-through rate, the click-through rates are decreasing from top to bottom. The GFP mechanism asks each bidder for a bid. Then the highest bidder gets the first slot, the second-highest, the second slot and so on. On each click the highest bidder pays his bid on the first slot, the second highest bidder pays his bid on the second slot, and so on.
In mechanism design and auction theory, a profit extraction mechanism is a truthful mechanism whose goal is to win a pre-specified amount of profit, if it is possible.
A sequential auction is an auction in which several items are sold, one after the other, to the same group of potential buyers. In a sequential first-price auction (SAFP), each individual item is sold using a first price auction, while in a sequential second-price auction (SASP), each individual item is sold using a second price auction.
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.
The Prize in Game Theory and Computer Science in Honour of Ehud Kalai is an award given by the Game Theory Society. The prize is awarded for outstanding articles at the interface of game theory and computer science. Following the eligibility rules of the Gödel Prize, preference is given to authors who are 45 years old or younger at the time of the award. It was established in 2008 by a donation from Yoav Shoham in honor of the Ehud Kalai's contributions in bridging these two fields.
The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.
A set function is called fractionally subadditive, or XOS, if it is the maximum of several additive set functions. This valuation class was defined, and termed XOS, by Noam Nisan, in the context of combinatorial auctions. The term fractionally subadditive was given by Uriel Feige.
When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.