Double Auction

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.

Index	1	2	3	4	5
Buyer prices b	100	90	80	70	60
Seller prices s	80	85	95	100	110

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

b₂ = 90

s₂ = 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 > bi	si+1 <= bi
bi+1 < si	1 Every buyer pays si Every seller receives bi	3 Every buyer pays si Every seller receives bi+1
bi+1 >= si	2 Every buyer pays bi+1 Every seller receives bi	4 Every buyer pays bi+1 Every seller receives si

To make this clearer, we have four numerical examples.

Case 1:

Break-even index: 2

• s_i+1 > b_i
• b_i+1 < s_i

Index	1	2	3
b	75	70	65
s	60	69	80

b = 69

s = 70

Case 2:

Break-even index: 2

• s_i+1 > b_i
• b_i+1 >= s_i

Index	1	2	3
b	75	73	70
s	60	69	80

b = 70

s = 73

Case 3:

Break-even index: 2

• s_i+1 <= b_i
• b_i+1 < s_i

Index	1	2	3
b	75	70	65
s	60	67	69

b = 65

s = 69

Case 4:

Break-even index: 2

• s_i+1 <= b_i
• b_i+1 >= s_i

Index	1	2	3
b	75	70	65
s	60	64	69

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 s_i.

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

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 s_i and b_i.

Numerical Example

Index	1	2	3	4	5
bi	100	90	80	70	65
si	50	70	75	80	85

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 = (b_i+1+s_i+1)/2. If b_i>=p>=s_i 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

Index	1	2	3	4	5
bi	100	90	80	70	65
si	50	70	75	80	85

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

Index	1	2	3	4	5
bi	100	90	80	70	65
si	50	70	76	80	85

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.