A deferred-acceptance auction (DAA) is an auction in which the allocation is chosen by repeatedly rejecting the least attractive bids. It is a truthful mechanism with strategic properties that make it particularly suitable to complex auctions such as the radio spectrum reallocation auction. [1] An important advantage of DAA over the more famous VCG auction is that DAA is immune to manipulations by coalitions of bidders, while VCG is immune to manipulations only by individual bidders.
Suppose the government wants to sell broadcasting rights in two areas: North and South. Three agents compete on these rights:
The government wants to maximize the social welfare. In this case, there are two feasible allocations: either give all rights to Alice (welfare=3), or give the North to Bob and the South to Carl (welfare=2). Since the valuations are private information of the agents, the government needs to use a truthful mechanism in order to induce the agents to reveal their true valuations. We compare two types of truthful mechanisms.
The Vickrey–Clarke–Groves (VCG) algorithm finds the socially-optimal allocation, which is to give both areas to Alice. Alice should pay a price determined by the externalities it imposes on the other agents. In this case, Alice pays $2M, since without her, the welfare of Bob and Carl would have been $2M. Bob and Carl receive nothing and pay nothing.
The deferred-acceptance auction iteratively rejects the lowest-valued agent that can be rejected while keeping an optimal set of active agents. So, Carl is rejected first, then Bob. Alice remains and she is accepted. She pays the threshold value which is $1M.
Both auction types are truthful - no single agent could gain by reporting a different value. However, they differ when agents can form coalitions. Suppose that Bob and Carl together increase their bid to $4M. Now, the VCG auction will accept Bob and Carl, and charge each of them a price of 0 (since each of them alone has no effect on the allocation to Alice)! In contrast, the DAA will reject Alice, then accept Bob and Carl, and charge each of them his threshold price, which is $3M - so they do not gain anything from their misreport (in fact, they lose $2M).
The performance of deferred-acceptance auctions was analyzed by Dütting et al. in 2014. They focused on knapsack auctions and on auctions for single-minded bidders. [2] An application of this idea in a double auction setting was outlined by then-Stanford computer science researchers including Tim Roughgarden in 2014 that same year. [3]
In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful.
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.
A Japanese auction is a dynamic auction format. It proceeds in the following way.
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.
The revelation principle is a fundamental principle in mechanism design. It states that if a social choice function can be implemented by an arbitrary mechanism, then the same function can be implemented by an incentive-compatible-direct-mechanism with the same equilibrium outcome (payoffs).
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.
A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other bidders. The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders. It gives bidders an incentive to bid their true valuations, by ensuring that the optimal strategy for each bidder is to bid their true valuations of the items; it can be undermined by bidder collusion and in particular in some circumstances by a single bidder making multiple bids under different names. It is a generalization of a Vickrey auction for multiple items.
Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.
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 and by Varian. It is used by Google's AdWords technology and Facebook.
In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.
A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms.
A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of these variables.
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.
A Prior-independent mechanism (PIM) is a mechanism in which the designer knows that the agents' valuations are drawn from some probability distribution, but does not know the distribution.
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.
In economics and mechanism design, a cost-sharing mechanism is a process by which several agents decide on the scope of a public product or service, and how much each agent should pay for it. Cost-sharing is easy when the marginal cost is constant: in this case, each agent who wants the service just pays its marginal cost. Cost-sharing becomes more interesting when the marginal cost is not constant. With increasing marginal costs, the agents impose a negative externality on each other; with decreasing marginal costs, the agents impose a positive externality on each other. The goal of a cost-sharing mechanism is to divide this externality among the agents.
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.
Regularity, sometimes called Myerson's regularity, is a property of probability distributions used in auction theory and revenue management. Examples of distributions that satisfy this condition include Gaussian, uniform, and exponential; some power law distributions also satisfy regularity. Distributions that satisfy the regularity condition are often referred to as "regular distributions".
Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.
A knapsack auction is an auction in which several identical items are sold, and there are several bidders with different valuations, who are interested in different amounts of items. The goal is to choose a subset of the bidders, with a total demand that is at most the number of items, and subject to that, a maximum total value. Finding this set of bidders requires to solve an instance of the knapsack problem, which explains the term "knapsack auction".
