A deferred-acceptance auction (DAA) is an

auction An auction is usually a process of buying and selling goods or services by offering them up for bids, taking bids, and then selling the item to the highest bidder or buying the item from the lowest bidder. Some exceptions to this definition e ...

in which the allocation is chosen by repeatedly rejecting the least attractive bids. It is a

truthful mechanism 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 ...

with strategic properties that make it particularly suitable to complex auctions such as the

radio spectrum The radio spectrum is the part of the electromagnetic spectrum with frequencies from 0 Hz to 3,000 GHz (3 THz). Electromagnetic waves in this frequency range, called radio waves, are widely used in modern technology, particul ...

reallocation auction.

Example

Suppose the government wants to sell broadcasting rights in two areas: North and South. Three agents compete on these rights: * Alice needs both areas, and values them (together) as $3M. * Bob needs only the North, and values it as $1M. * Carl needs only the South, and values it as $1M. 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

in order to induce the agents to reveal their true valuations. We compare two types of truthful mechanisms.

Vickrey–Clarke–Groves solution

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.

Deferred-acceptance auction solution

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

coalition A coalition is a group formed when two or more people or groups temporarily work together to achieve a common goal. The term is most frequently used to denote a formation of power in political or economical spaces. Formation According to ''A Gui ...

s. 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).

References

{{reflist Types of auction

Example

Vickrey–Clarke–Groves solution

Deferred-acceptance auction solution

See also

Related articles

References