Spot auction mechanics

How Mithril allocates spot compute

Mithril allocates spot instances through a blind second-price auction to ensure fair and efficient distribution. This article provides a deep dive into the mechanics of this auction and how it handles allocation in various cases.

Second-price auction overview

In a second-price auction, all participants submit sealed bids noting the maximum price (known as the limit price) they are willing to pay for the item without knowing the value of the other bids. Those who win the auction do not pay their limit price but the limit price of the highest losing bid. This mechanism encourages participants to bid their true valuation for the item because overbidding does not increase the price they pay if they win.

Consider a simple example where there are 3 (identical) spot instances available in a hypothetical region-a and 6 bids, each for a single instance:

Bid	Bid limit price ($/instance/hr)	Price paid ($/instance/hr)
A ✅	$23.00	$13.00
B ✅	$21.00	$13.00
C ✅	$16.00	$13.00
D ❌	$13.00	--
E ❌	$12.00	--
F ❌	$8.00	--

In this example, bids A, B, and C are allocated, and they each pay $13.00/instance/hr, the limit price of the highest losing bid, as long as their instance remains allocated.

It is important to note that in this case, $13.01 becomes the spot price for region-a, but a new bid (X) with a limit price of $13.01 would not be successful:

Bid	Bid limit price ($/instance/hr)	Price paid ($/instance/hr)
A ✅	$23.00	$13.01
B ✅	$21.00	$13.01
C ✅	$16.00	$13.01
X ❌	$13.01	--
D ❌	$13.00	--
E ❌	$12.00	--
F ❌	$8.00	--

Although bid X is higher than the previous spot price of $13.00, it is not higher than the lowest winning bid, C, at $16.00. Because of this, bid X is not allocated, but it does raise the current spot price to $13.01, since it becomes the highest losing bid.

Multi-instance allocation logic

To support distributed workloads, a single bid can request multiple instances. Bids for multiple instances are all-or-nothing, meaning the bid will not be successful if there aren't enough spot instances remaining to allocate the entire bid. In certain cases, this can mean bids with lower limit prices will be allocated even when higher bids are not. To demonstrate, let's again consider an example where 3 spot instances are available:

Bid	# of instances	Bid limit price	Price paid	Instances remaining
--	--	--	--	3
A ✅	2	$23.00	$13.00	1
B ❌	2	$21.00	--	1
C ✅	1	$16.00	$13.00	0
D ❌	1	$13.00	--	0
E ❌	1	$12.00	--	0
F ❌	1	$8.00	--	0

In this case, bid B is unsuccessful because it requests 2 instances, but there is only 1 instance remaining in the spot pool after all higher bids are allocated (bid A, in this case). Bid C is then allocated because it only requests 1 instance.

Although bid B is unsuccessful, it does not qualify as the "highest losing bid" for the purposes of setting the spot price because there are successful bids below it.

Tied bids

In the case of tied bids (bids at the same limit price), the spot auction preferentially allocates older bids first. The age of a bid is based on the bid's creation time or, if the bid was ever paused, based on when the bid was last resumed.

Preemption & price change scenarios

The Mithril spot auction is fully dynamic, meaning that allocation and prices can change in real time based supply and demand. Concretely, changes are triggered when:

1. Capacity is added or removed from the spot pool (supply)
2. Bids are created or canceled (demand)

Consider the table below as the initial state of the spot market in a specific region:

Bid	# of instances	Bid limit price	Price paid	Instances remaining
--	--	--	--	3
A ✅	1	$23.00	$13.00	2
B ✅	1	$21.00	$13.00	1
C ✅	1	$16.00	$13.00	0
D ❌	1	$13.00	--	0
E ❌	1	$12.00	--	0
F ❌	1	$8.00	--	0

Each of the sections below introduces a change to the market and examines how it would affect allocation and spot prices.

Instances added to the spot pool

Two additional instances are added to the spot pool.

Bid	# of instances	Bid limit price	Price paid	Instances remaining
--	--	--	--	5
A ✅	1	$23.00	$8.00	4
B ✅	1	$21.00	$8.00	3
C ✅	1	$16.00	$8.00	2
D ✅	1	$13.00	$8.00	1
E ✅	1	$12.00	$8.00	0
F ❌	1	$8.00	--	0

Outcome(s):

• Bids D and E are allocated
• The spot price decreases from $13.00 to $8.00

Instances removed from the spot pool

One instance is removed from the spot pool. (Capacity reduced from 3 instances to 2)

Bid	# of instances	Bid limit price	Price paid	Instances remaining
--	--	--	--	2
A ✅	1	$23.00	$16.00	1
B ✅	1	$21.00	$16.00	0
C ❌	1	$16.00	--	0
D ❌	1	$13.00	--	0
E ❌	1	$12.00	--	0
F ❌	1	$8.00	--	0

Outcome(s):

• Bid C is preempted (with a 5-minute warning)
• The spot price increases from $13.00 to $16.00

Bids created

Bids X and Y are created.

Bid	# of instances	Bid limit price	Price paid	Instances remaining
--	--	--	--	3
A ✅	1	$23.00	$16.00	2
X ✅	1	$22.00	$16.00	1
B ✅	1	$21.00	$16.00	0
C ❌	1	$16.00	--	0
D ❌	1	$13.00	--	0
Y ❌	1	$12.00	--	0
E ❌	1	$12.00	--	0
F ❌	1	$8.00	--	0

Outcome(s):

• Bid C is preempted (with a 5-minute warning)
• Bid X is allocated
• The spot price increases from $13.00 to $16.00

Bids canceled

Bids A and C are canceled.

Bid	# of instances	Bid limit price	Price paid	Instances remaining
--	--	--	--	3
B ✅	1	$21.00	$8.00	2
D ✅	1	$13.00	$8.00	1
E ✅	1	$12.00	$8.00	0
F ❌	1	$8.00	--	0

Outcome(s):

• Bids D and E are allocated
• The spot price decreases from $13.00 to $8.00

FAQs

Q: My bid was preempted but the spot price is still below my limit price

A: This can occur on rare occasions for multi-instance bids when the number of spot instances in the spot pool is reduced, and there are no longer enough instances to fulfill your bid. In this case, because multi-instance bids are all-or-nothing, your bid will be preempted, but bids requesting fewer instances at a lower limit price may then be filled.

Q: What is "Win price"?

A: "Win price" displayed in the spot auction UI is the current lowest allocated bid. "Spot market" price is the highest losing bid. Bidding above the win price providers higher chance for your bid to be allocated, but does not guarantee it, for example due to other market participants bidding up in response to preemption, or due to considerations regarding bid instance size.