Double auction

• Order the buyers in decreasing order of their bid: b₁≥b₂≥...≥b_n.
• Order the sellers in increasing order of their bid: s₁≤s₂≤...≤s_n.
• Let k be the largest index such that b_k≥s_k (the "breakeven index").

Every price in the range [max(s_k,b_k+1),min(b_k,s_k+1)] is an equilibrium price, since both demand and supply are 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):

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

• Order the buyers and sellers in the Natural ordering and find the breakeven index k.
• Set the price at the average of the kth values: p=(b_k+s_k)/2.
• Let the first k sellers sell the good to the first k buyers.

This mechanism is:

• IR - because by the ordering, the first k players value each item as at least p and the first k sellers value each item as at most p.
• BB - because all monetary transfers are between buyers and sellers.
• EE - because the n items are held by the n players who value them the most.
• Not TF - because buyer k has an incentive to report a lower value and seller k has an incentive to report a higher value.

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:

• If b≤s then no trade is done and the product remains with the seller;
• If b>s then the product goes to the buyer, the buyer pays s and the seller receives b.

This mechanism is:

• IR, since the buyer pays less than his value and the seller receives more than his value.
• TF, since the price paid by the buyer is determined by the seller and vice versa. Any attempt to misreport will make the utility of the misreporter either zero or negative.
• EE, because the product goes to the one who values it the most.
• Not BB, because the auctioneer has to pay 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_k+1), and each seller receives the highest equilibrium price min(b_k,s_k+1), as in the following table:

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[3] 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.

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

• Order the buyers and sellers in the Natural ordering and find the breakeven index k.
• The first k-1 sellers give the item and receive s_k from the auctioneer;
• The first k-1 buyers receive the item and pay b_k to the auctioneer.

This mechanism is:

• IR, as before.
• TF: the first k-1 buyers and sellers have no incentive to change their declaration since this will have no effect on their price; the kth buyer and seller have no incentive to change since they don't trade anyway, and if they do enter the trading (e.g. b_k increases his declaration above b_k-1), their profit from trading will be negative.
• Not BB, because the auctioneer is left with a surplus of (k-1)(b_k-s_k). (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).
• Not EE, because b_k and s_k don't trade, although buyer k values the item more than seller k.

If we tried to make this mechanism efficient by letting the kth 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 ${\displaystyle 1-1/k}$ of the optimum.

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.[5]

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

• Order the buyers and sellers in the Natural ordering and find the breakeven index k.
• Calculate: p=(b_k+1+s_k+1)/2.
• If b_k≥p≥s_k, then the first k buyers and sellers trade the good in price p.
• Otherwise, the first k-1 sellers trade for s_k and the first k-1 buyers trade for b_k as in the trade-reduction mechanism.

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).[4]

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.[6] 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:

• The loss of gain-from-trade is either 0 (achieved by VCG) or 1/k (achieved by trade-reduction); hence the expected loss in gain-from-trade is at most: p/k.
• The auctioneer surplus is either negative (in case of VCG) or positive (in case of trade-reduction); hence the expected surplus is 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,[6] 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 ${\displaystyle pb_{k}+(1-p)\max {(b_{k+1},s_{k})}}$ and each seller receives ${\displaystyle ps_{k}+(1-p)\min {(s_{k+1},b_{k})}}$. Then, with probability p, buyer k pays ${\displaystyle \max {(b_{k+1},s_{k})}}$ and buys the good from seller k who receives ${\displaystyle \min {(s_{k+1},b_{k})}}$. Like the first variant, this variant is IR and has the same expected efficiency and surplus. Its advantage is that it "hides" its randomized character from almost all traders. The downside is that now the mechanism is truthful only ex-ante; i.e., a risk-neutral trader cannot gain in expectation by misreporting his value, but after he knows the results of the lot, he might feel regret for not reporting otherwise.

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