Batch Auction

In a batch auction, one seller sells multiple items to more than one buyer.

• The seller determines the number of items available.
• The seller sets a minimum price.
• Each buyer submits his bid containing the price per item and the number of items he wants to buy.
• All bids are ordered descending
• The auction ends at a certain date

Now, the algorithm goes from the highest bid towards the lowest one and looks if enough items are available to fulfill the order. The clearing price is determined by the last bid that adds up the number of available items while offering a higher price than the minimum price. All bidders that offer higher prices have to pay only the clearing price.

Example

The seller wants to sell 100 Tokens. His minimum price is 50 Coins per piece. The ordered bids are as shown in the table:

Buyer	1	2	3	4	5	6	7
Bid price	80	75	70	60	55	50	45
Bid amount	20	25	30	35	20	30	15

We can ignore buyer number 7 since he offers less than the minimum price set by the seller.

The following table shows the accumulated amounts.

Buyer	1	2	3	4	5	6	7
Accumulated amount	20	45	75	110	130	160	175

We can see that with buyer 4 more items are requested than available (110 > 100). This means that the clearing price per item is the bid price of buyer 4. This is 60 Coins. All successful buyers have to pay 60 Coins per token.

Buyers 1 till 3 receive their full amount. But buyer 4 falls 10 tokens short and can only receive 25 instead of 35 tokens.