Double Auction

Published by Mario Oettler on

A double auction is a mechanism to sell or buy goods to or from multiple sellers or buyers.

The standard mechanism is that each buyer or seller only requests or sells one item. The workflow is as follows:

  • All buyers submit a bid for their maximum buy price.
  • All sellers submit a bid for their minimum sales price.
  • Auctioneer finds a price p that clears the market.
  • All sellers that ask for p or less can sell their items. All buyers that offered p or higher can buy an item.

Basic Example

We order all sales ascending and all buy prices descending.

Index12345
Buyer prices b10090807060
Seller prices s808595100110

The index where the market is cleared is 2. This index is called the break-even index. At the break-even index, the buyer price is still higher or the same as the seller price. Buyer 1 and buyer 2 receive an item, and seller 1 and seller 2 sell their item.

The possible price span of p is between 85 and 90.

There are different mechanisms to determine the actual price p.

  • Average mechanism
  • VCG mechanism (Vickrey Clarke Groves mechanism)
  • Trade reduction mechanism
  • McAfee’s mechanism
  • Probabilistic reduction mechanism

Average Mechanism

The clearing price is the average of seller price and buyer price at the break-even index.

In our example

b2 = 90

s2 = 85

p = (90 + 85)/2 = 87.5

The first i buyers receive the item. So, everybody who wants to buy at the clearing price can buy and everybody who wants to sell at the clearing price can sell. This is called efficient. We have a balanced budget. However, buyer i has an incentive to state a lower price and seller i has the incentive a higher price.

VCG Mechanism

In the VCG mechanism, we need to distinguish four different cases.

 si+1 > bisi+1 <= bi
bi+1 < si1 Every buyer pays si Every seller receives bi3 Every buyer pays si Every seller receives bi+1
bi+1 >= si2 Every buyer pays bi+1 Every seller receives bi4 Every buyer pays bi+1 Every seller receives si

To make this clearer, we have four numerical examples.

Case 1:

Break-even index: 2

  • si+1 > bi
  • bi+1 < si
Index123
b757065
s606980

b = 69

s = 70

Case 2:

Break-even index: 2

  • si+1 > bi
  • bi+1 >= si
Index123
b757370
s606980

b = 70

s = 73

Case 3:

Break-even index: 2

  • si+1 <= bi
  • bi+1 < si
Index123
b757065
s606769

b = 65

s = 69

Case 4:

Break-even index: 2

  • si+1 <= bi
  • bi+1 >= si
Index123
b757065
s606469

b = 65

s = 69

This means that we don’t have a balanced budget. The auctioneer subsidizes the trade. But it reveals the willingness to pay truthfully and it is efficient.

Trade Reduction Mechanism

With the trade reduction mechanism, the first i-1 seller can sell their items. They receive the price si.

The first i-1 buyers receive an item and pay bi.

The problem with this approach is that not everyone can buy or sell. The budget is not balanced since the auctioneer receives the difference between si and bi.

Numerical Example

Index12345
bi10090807065
si5070758085

Break-even index i is 3.

Buyer 1 and buyer 2 can buy an item and pay 80.

Seller 1 and seller 2 sell an item and receive 75.

Auctioneer receives the difference of 80 – 75 = 5.

McAfee Mechanism

With the McAfee mechanism, we calculate p = (bi+1+si+1)/2. If bi>=p>=si the clearing price is p. Otherwise, we determine the price like in trade reduction.

In the second case, the mechanism is inefficient and has no balanced budget.

Numerical Example 1

Index12345
bi10090807065
si5070758085

Break -even index i = 3

p = (70+80)/2=75

80 > 75 >=75

Buyer 1, 2, and 3 pay p

Seller 1, 2, and 3 receive p

Numerical Example 2

Index12345
bi10090807065
si5070768085

Break -even index i = 3

p = (70+80)/2=75

80 > 75 <76: Now trade reduction

Buyer 1 and 2 pay 80

Seller 1 and 2 receive 75

Probabilistic Reduction

This mechanism uses trade reduction with the probability p and VCG mechanism with 1-p. 0<=p<=1

The properties depend on p.

Categories: