Double auction
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.
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 double auction is also possible without any exchange of currency in barter trade. A barter double auction is an auction, where every participant has a demand and an offer consisting of multiple attributes and no money is involved. For the mathematical modelling of satisfaction level Euclidean distance is used, where the offer and demand are treated as vectors.
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, 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 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 is an equilibrium price, since both the supply and the demand equal 0.
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]
- Order the buyers in decreasing order of their bid: b1≥b2≥...≥bn.
- Order the sellers in increasing order of their bid: s1≤s2≤...≤sn.
- Let k be the largest index such that bk≥sk.
| sk+1 > bk | sk+1 ≤ bk | |
| bk+1 < sk | ||
| bk+1 ≥ sk |
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. Payoffs depend on the price of the transaction 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:
- If s>b then no trade occurs ;
- If s≤b then p=/2.
- 0 if s>b;
- B-p if s≤b.
- 0 if s>b;
- p-S if s≤b.
In an incomplete 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.
Mechanism design
How should the auctioneer determine the trading price? An ideal mechanism would satisfy the following properties:
1. Individual Rationality : 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 comes in two flavors:
- Strong balanced budget : all monetary transfers must be done between buyers and sellers; the auctioneer should not lose or gain money.
- Weak balanced budget : the auctioneer should not lose money, but may gain money.
- The stronger notion is dominant-strategy-incentive-compatibility, which means that reporting the true value should be a dominant strategy for all players. I.e, a player should not be able to gain by spying over other players and trying to find an 'optimal' declaration which is different from his true value, regardless of how the other players play.
- The weaker notion is Nash-equilibrium-incentive-compatibility, which means that there exists a Nash equilibrium in which all players report their true valuations. I.e, if all players but one are truthful, it is best for the remaining player to also be truthful.
Unfortunately, it is not possible to achieve all these requirements in the same mechanism. 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.- 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=/2.
- Let the first k sellers sell the good to the first k buyers.
- 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.
VCG mechanism
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.
- 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.
| sk+1 > bk | sk+1 ≤ bk | |
| bk+1 < sk | Each buyer pays sk and each seller gets bk | Each buyer pays sk and each seller gets sk+1 |
| bk+1 ≥ sk | Each buyer pays bk+1 and each seller gets bk | Each buyer pays bk+1 and each seller gets sk+1 |
Similar to the bilateral trade scenario, the mechanism is IR, TF and EE, 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. 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:- 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 sk from the auctioneer;
- The first k-1 buyers receive the item and pay bk to the auctioneer.
- 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, their profit from trading will be negative.
- Not BB, because the auctioneer is left with a surplus of..
- Not EE, because bk and sk don't trade, although buyer k values the item more than seller k.
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 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.
McAfee's mechanism
The following mechanism 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=/2.
- If bk≥p≥sk, then the first k buyers and sellers trade the good in price p.
- Otherwise, the first k-1 sellers trade for sk and the first k-1 buyers trade for bk as in the trade-reduction mechanism.
Probabilistic reduction mechanisms
Given a p∈, 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:- The loss of gain-from-trade is either 0 or 1/k ; hence the expected loss in gain-from-trade is at most: p/k.
- The auctioneer surplus is either negative or positive ; hence the expected surplus is p*-*. 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.
Comparison
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.