A **double auction** is a process of buying and selling goods when potential buyers submit their bids and potential sellers simultaneously submit their ask prices to an auctioneer, and then an auctioneer 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.

## Contents

- Economic analysis
- Natural ordering
- Game theoretic analysis
- Mechanism design
- Average mechanism
- VCG mechanism
- Trade reduction mechanism
- McAfees mechanism
- Probabilistic reduction mechanisms
- Comparison
- Double auctions in a supply chain
- Modular approach
- References

As well as their direct interest, double auctions are reminiscent of Walrasian auction and have been used as a tool to study the determination of prices in ordinary markets.

A simple example of a double auction is a *bilateral trade* scenario, in which there is a single seller who values his product as *S* (e.g. the cost of producing the product), and a single buyer who values that product as *B*.

## Economic analysis

From an economist's perspective, the interesting problem is to find a competitive equilibrium - a situation in which the supply equals the demand.

In the simple bilateral trade scenario, if *B*≥*S* then any price in the range [*S*,*B*] is an equilibrium price, since both the supply and the demand equal 1. Any price below *S* is not an equilibrium price since there is an excess demand, and any price above *B* is not an equilibrium price since there is an excess supply. When *B*<*S*, any price in the range (*B*,*S*) is an equilibrium price, since both the supply and the demand equal 0 (the price is too high for the buyer and too low for the seller).

In a more general double auction, in which there are many sellers each of whom holds a single unit and many buyers each of whom wants a single unit, an equilibrium price can be found using the natural ordering of the buyers and sellers:

## Natural ordering

*b1*≥

*b2*≥...≥

*b*.

_{n}*s1*≤

*s2*≤...≤

*s*.

_{n}*k*be the largest index such that

*b*≥

_{k}*s*(the "breakeven index").

_{k}Every price in the range [max(*s _{k}*,

*b*),min(

_{k+1}*b*,

_{k}*s*)] is an equilibrium price, since both demand and supply are

_{k+1}*k*. It is easier to see this by considering the range of equilibrium prices in each of the 4 possible cases (note that by definition of

*k*,

*b*<

_{k+1}*s*):

_{k+1}## Game-theoretic analysis

A double auction can be analyzed as a game. Players are buyers and sellers. Their strategies are bids for buyers and ask prices for sellers (that depend on the valuations of buyers and sellers). Payoffs depend on the price of the transaction (determined by the auctioneer) and the valuation of a player. The interesting problem is to find a Nash equilibrium - a situation in which no trader has an incentive to unilaterally change their bid/ask price.

Consider the bilateral trade scenario, in which the buyer submits a bid of *b* and the seller submits *s*.

Suppose an auctioneer sets the price in the following way:

*s*>

*b*then no trade occurs (the seller wants more than the buyer pays);

*s*≤

*b*then

*p*=(

*b*+

*s*)/2.

The utility of the buyer is:

*s*>

*b*;

*B-p*if

*s*≤

*b*(where

*B*is the true value of the buyer).

The utility of the seller is:

*s*>

*b*;

*p-S*if

*s*≤

*b*(where

*S*is the true value of the seller).

In a *complete information* (symmetric information) case when the valuations are common knowledge, it can be shown that the continuum of pure strategy efficient Nash equilibriums exists with
*B>S*, there will be *no* equilibrium in which both players declare their true values: either the buyer will be able to gain by declaring a lower value, or the seller will be able to gain by declaring a higher value.

In an *incomplete information* (asymmetric information) case a buyer and a seller know only their own valuations. Suppose that these valuations are uniformly distributed over the same interval. Then it can be shown that such a game has a Bayesian Nash equilibrium with linear strategies. That is, there is an equilibrium when both players' bids are some linear functions of their valuations. It is also brings higher expected gains for the players than any other Bayesian Nash equilibrium (see Myerson–Satterthwaite theorem).

## Mechanism design

How should the auctioneer determine the trading price? An ideal mechanism would satisfy the following properties:

1. **Individual Rationality** (IR): no person should lose from joining the auction. In particular, for every trading buyer: *p ≤ B*, and for every trading seller: *p ≥ S*.

2. **Balanced Budget** (BB) comes in two flavors:

3. **Truthfulness** (TF), also called **Incentive compatibility** (IC) or *strategy-proofness*: also comes in two flavors:

4. **Economic efficiency** (EE): the total social welfare (the sum of the values of all players) should be the best possible. In particular, this means that, after all trading has completed, the items should be in the hands of those that value them the most.

Unfortunately, it is not possible to achieve all these requirements in the same mechanism (see Myerson–Satterthwaite theorem). But there are mechanisms that satisfy some of them.

## Average mechanism

The mechanism described in the previous section can be generalized to *n* players in the following way.

*k*.

*k*th values:

*p*=(

*bk*+

*sk*)/2.

*k*sellers sell the good to the first

*k*buyers.

This mechanism is:

*k*players value each item as at least

*p*and the first

*k*sellers value each item as at most

*p*.

*n*items are held by the

*n*players who value them the most.[citation needed]

*k*has an incentive to report a lower value and seller

*k*has an incentive to report a higher value.

## VCG mechanism

A VCG mechanism is a generic mechanism which optimizes the social welfare while achieving truthfulness. It does so by making each agent pay for the "damage" that his desires cause to society.

In the simple bilateral trade setting, this translates to the following mechanism:

*b*≤

*s*then no trade is done and the product remains with the seller;

*b*>

*s*then the product goes to the buyer, the buyer pays

*s*and the seller receives

*b*.

This mechanism is:

*b*-

*s*. The auctioneer actually has to subsidize the trade.

In the general double auction setting, the mechanism orders the buyers and sellers in the #Natural ordering and finds the breakeven index *k*. Then the first *k* sellers give the item to the first *k* buyers. Each buyer pays the lowest equilibrium price max(*s _{k}*,

*b*), and each seller receives the highest equilibrium price min(

_{k+1}*b*,

_{k}*s*), as in the following table:

_{k+1}Similar to the bilateral trade scenario, the mechanism is IR, TF and EE (optimizes the social welfare), but it is not BB - the auctioneer subsidizes the trade.

The uniqueness-of-prices theorem implies that this subsidy problem is inevitable - *any* truthful mechanism that optimizes the social welfare will have the same prices (up to a function independent of the ask/bid prices of each trader). If we want to keep the mechanism truthful while not having to subsidize the trade, we must compromise on efficiency and implement a less-than-optimal social welfare function.

## Trade reduction mechanism

The following mechanism gives up a single deal in order to maintain truthfulness:

*k*.

*k*-1 sellers give the item and receive

*sk*from the auctioneer;

*k*-1 buyers receive the item and pay

*bk*to the auctioneer.

This mechanism is:

*k*-1 buyers and sellers have no incentive to change their declaration since this will have no effect on their price; the

*k*th buyer and seller have no incentive to change since they don't trade anyway, and if they do enter the trading (e.g.

*bk*increases his declaration above

*b*

_{k-1}), their profit from trading will be negative.

*k*-1)(

*bk*-

*sk*). (however, it is considered

*weakly budget balanced*, since the auctioneer at least doesn't have to subsidize the trade but is rather left with a surplus).

*bk*and

*sk*don't trade, although buyer

*k*values the item more than seller

*k*.

If we tried to make this mechanism efficient by letting the *k*th buyer and seller trade, this would make it untruthful because then they will have an incentive to change their prices.

Although the social welfare is not optimal, it is near-optimal, since the forbidden deal is the least favorable deal. Hence the gain-from-trade is at least

Note that in the bilateral trade setting, *k*=1 and we give up the only efficient deal, so there is no trade at all and the gain-from-trade is 0. This is in accordance with the Myerson-Satterthwaite theorem.

The trade reduction mechanism can be generalized to a market that is *spatially-distributed*, i.e. the buyers and sellers are in several different locations, and some units of the good may have to be transported between these locations. The cost of transport is thus added to the cost of production of the sellers.

## McAfee's mechanism

The following mechanism is a variation on the trade-reduction mechanism:

*k*.

*p*=(

*b*

_{k+1}+

*s*

_{k+1})/2.

*b*≥

_{k}*p*≥

*s*, then the first

_{k}*k*buyers and sellers trade the good in price

*p*.

*k*-1 sellers trade for

*s*and the first

_{k}*k*-1 buyers trade for

*b*as in the trade-reduction mechanism.

_{k}Similarly to the trade-reduction mechanism, this mechanism is IR, TF, not BB (in the second case) and not EE (in the second case). Assuming that the values of the buyers and sellers are all bounded above zero, it is possible to prove that the loss of trade efficiency is bounded by 1/min(num-of-buyers,num-of-sellers).

## Probabilistic reduction mechanisms

Given a *p*∈[0,1], after the bids are submitted, use the #Trade reduction mechanism with probability *p* and the #VCG mechanism with probability 1-*p*. This mechanism inherits all the properties of its parents, i.e. it is IR and TF. The parameter *p* controls the tradeoff between EE and BB:

*k*(achieved by trade-reduction); hence the expected loss in gain-from-trade is at most:

*p*/

*k*.

*p**(surplus-in-trade-reduction)-(1-

*p*)*(deficit-in-VCG). If the values of the traders come from known distribution,

*p*can be selected such that the expected surplus will be 0, i.e. the mechanism is BB ex-ante.

In a variant of this mechanism, after the bids are submitted, the *k*-1 cheap sellers trade with the *k*-1 expensive buyers; each of them receives/pays the expected payment of the original mechanism, i.e. each buyer pays
*p*, buyer *k* pays
*k* who receives

## Comparison

(chapter 4) provide both a theoretic comparison and an empirical comparison of the various mechanisms.

## Double auctions in a supply chain

The basic double auction model involves a single market. It can be extended to handle a supply chain - a chain of markets, in which the buyers in one market become sellers in the next market. E.g., farmers sell fruits in the fruit market; juice makers buy fruits in the fruit market, make juice and sell it in the juice market to consumers.

The model can be further extended to handle markets in an arbitrary directed acyclic graph.

## Modular approach

A modular approach to the design of double auctions was recently proposed by Dütting, Roughgarden and Talgam-Cohen. This framework views double auctions as being composed of ranking algorithms for each side of the market and a composition rule, and can be applied to complex markets. An immediate consequence of this framework is that classic double auction mechanisms such as the trade reduction mechanism are not only strategyproof but also weakly group-strategyproof (meaning that no group of buyers and sellers can benefit by a joint misreport of their preferences).