This last week on Monday the Israeli Ministry of Communication auctioned 8 bands (each band of 5 mega-herz) for the use of fourth-generation cellular communication. The auction was interesting from a game theoretic perspective, and so I share it with the blog’s readers.

The rules of the auction are as follows:

  1. The auction is conducted on the internet, and each participant sits in his office.
  2. The minimum bid is 2,000,000 NIS per mega-herz (meaning 10M per band).
  3. Bids must be multiples of 100,000.
  4. No two bids can be the same: if a participant makes a bid that was already made by another participant, the e-system notifies the participant that his bid is illegal.

The auction is conducted in round.
In the first round:

  1. Each bidder makes a bid, which consists of the number of bands it asks for and the price he is willing to pay for each mega-herz. As mentioned above, no two participants can offer the same price.
  2. The e-system allocates the 8 band between the participants according to the bids: the bidder with the highest bid gets the number of bands it asked for, then the bidder with the second highest bid, and so on, until the 8 bands are exhausted.
  3. Each participant is told the number of bands it was allocated.
  4. The price in which the 8th band was allocated is called the threshold and posted publicly.
  5. The minimum price for the next round is the threshold + 200,000 NIS.

In each subsequent round:

  1. Each participant that got 0 bands in the previous round, as well as any participant who got strictly less bands than the number of bands it bid for (there is at most one bidder that can satisfy this latter condition), can submit a new bid. A participant cannot increase the number of bands it asks for, so if a bidder asked for 2 bands in a certain round, it can bid for 0, 1, or 2 bands in the following round. A participant may choose not to submit any bid, but it can do that only once in a row: a participant who does not submit a bid for two consecutive rounds cannot submit any bid in any subsequent round.
  2. The new threshold and minimum price are calculated as above.

Along the auction, the bidders know
a) Their own bids.
b) The list of thresholds (or, equivalently, minimum prices).
In particular, the number of participants and their identities is not known, so that nobody knows if and when a participant left the auction.

One feature (or bug) of the system was that the process of submitting a bid had two steps: the participant first submits the bid and is told whether it is legal or not (that is, whether it was already made by another participant), and only if it is legal the participant is asked to confirm it. This allows the participants to know the number of participants that are still in the auction, simply by checking which prices are already taken (except of the price “threshold+100,000”, which cannot be verified).
Important information the participants do not have is the number of bands that each other participant ask for. As we will see, this was the key issue in the actual auction.

The participants and the relations between them

There were six participants: three large service providers, Pelephone, Cellcom, and Partner, and three newcomers, Exphone, Golan, and Hot. To construct a viable network one needs at least 4 bands; 4 bands are enough to meet current demand, yet in few years, when the demand for fourth-generation communication will increase, a fifth band will be needed. Consequently, no participant was allowed to bid for more than 4 bands. In addition, each of Cellcom and Partner already owns two bands, which can be used for fourth-generation communication. Consequently, these two participants were allowed to bid for at most two bands. Simple math shows that the 8 new bands, together with the 4 existing bands, are sufficient to create three viable networks, one for each large service provider.
The license of the newcomers requires them to get at least one band each. To be able to provide service, each newcomer planned to join one large service provider: Cellcom had an agreement with Golan for a joint network. Similarly, Partner had an agreement with Hot. Pelephone and Exphone tried to reach an agreement, but failed to do so before the auction began.
To encourage newcomers, the Ministry of Communication gave 50% discount to each one of the three newcomers.
The situation then is as follows:

Large firm #bands in possession Maximal  #bands it can bid %discount Small firm #bands in possession Maximal  #bands it can bid %discount
Pelephone 0 4 0% Exphone 0 4 50%
Cellcom 2 2 0% Golan 0 4 50%
Partner 2 2 0% Hot 0 4 50%

Presumably, the auction is very simple and should end after the first round at a price that is close to the minimum price: Cellcom, Partner, Golan, and Hot each bids for one band; Pelephone and Exphone together bid for 4 bands, most likely Exphone bids for 1 band and Pelephone for 3 bands. In fact, each large firm wanted its smaller partner to get 1 band, because this way they get a band for their network without paying its cost.

Unfortunately for the participants, it is illegal to coordinate bids, and knowledge is not common knowledge. Some concerns that participants may have are:

  1. A partnership (of a large service provider and a newcomer) that has only 3 bands will not be able to provide a viable network. This situation should be avoided at all cost.
  2. Pelephone was not able to sign an agreement with Exphone before the auction started. Suppose that Exphone wins a band; will it then join Pelephone, or maybe it will prefer joining one of the other large service providers?
  3. The price of 2,000,000 NIS is low, and at that price, firms may be willing to purchase more bands than they need, just to be on the safe side, or to have 5 bands to meet future demand for fourth-generation communication.
  4. The newcomers have smaller pockets than the large service providers. If some participant decides to bid more than the numbers I mentioned above (e.g., Hot bids on 2 bands, or Pelephone on 4 bands) then someone will have to drop out. This is likely to be one of the newcomers. But then its larger partner will be left with 3 bands, a situation which, as mentioned above, should be avoided.

The uncertainty described above increases the probability that there will be over-demand for bands, and that prices will soar.

Optimal Behavior

How should one bid in this auction?
A newcomer, who needs one band, should go all the way up to its private value.
A large firm that believes that its smaller party will not leave the auction should similarly ask for 1 (Partner and Cellcom) or 3 (Pelephone) bands.
A large firm who believes that its smaller partner may leave the auction should ask for 2 (Partner and Cellcom) or 4 (Pelephone) bands.

If there is over-demand of 1, then exactly one firm overbid. In this case the firm that made the overbid should ask for one fewer band and end the auction.
But what does one do if there is over-demand of 2 (or more) bands? Maybe some small firm asks for 2 bands? Maybe Pelephone asks for 4 bands? A large firm that bid for one additional band than the number it was supposed to bid, cannot give up this additional band, and therefore has to stick to overbidding.

The actual auction

After several rounds, the information available to the participants (that is, the list of thresholds as well as their own bids) allowed them to infer that there is an over-demand of 2 bands. Pelephone, for example, could deduce this information as follows: when the threshold was equal to Pelephone’s offer, it got 2 out of the 3 or 4 bands that it bid for, which implies that there is an over-demand of at least two bands. The threshold in the previous round allowed them to deduce that the over-demand is exactly 2).

An overbid of two bands can occur in two scenarios:
Scenario 1: Pelephone bid 4, one firm bid 2, four firms bid 1.
Scenario 2: Pelephone bid 3, two firms bid 2, three firms bid 1.

Why is it important to distinguish between the two scenarios?
Suppose that Hot bid for 2 bands. If the true scenario is the first one, Hot knows that once it gives up a band, Pelephone may follow suit. If, on the other hand, the true scenario is the second one, then Hot does not know which other firm bid for 2 bands. If it is Cellcom or Partner, then once Hot gives up a band, Cellcom or Partner may do the same. If, on the other hand, it is Golan or Exphone, then both Hot and Golan/Exphone try to get an extra band for a low price, and then even if Hot gives up a band, Golan may stay in, in which case prices will go up.

After several more rounds all participants could infer the actual bids, though they could not know which firm made which bid. The true scenario happened to be the first one. It was quite clear that Pelephone asks for 4 bands. But who bids for 2 bands?
Pelephone feared that Golan or Hot attempts to buy 2 bands, which might cause Exphone to withdraw, so that if they go down to 3 bands, they will end up with 3 bands – a disaster. The participant who bid for 2 bands, call it firm X, could be either a large service provider or a newcomer. If it was a large provider, it feared that Pelephone will go all the way with 4 bands, which means that its small partner may withdraw, so that if they (firm X) give up a band, then they might end up with 3 bands (the new 1 band + the two they already have) – a disaster. If firm X is a newcomer, then they may wish to get a second band for a cheap price. Since a newcomer has a discount of 50%, if the price of a band turns out to be P, then the newcomer will have to pay P for 2 bands, while Pelephone will pay 4P for its 4 bands. There is no way to avoid a price war. Will Pelephone be able to survive it?

Unfortunately for the government that wants to have a high final price, and fortunately for the participants, rational thinking can be useful. The only participants whose strategy is not clear are firm X itself and Pelephone. Consider the point of view of firm X. Suppose that it (firm X) decides to stick to 2 bands.

  1. If Pelephone sticks to 4 bands whatever happens, the price will increase, and the participants will reach the same situation they have now, but with higher prices. If firm X is a large firm, this will increase the probability that its small partner will drop out, and firm X will have to purchase 2 bands at a high price.
  2. If Pelephone ask for 4 bands out of fear that Exphone will drop out, then the moment that firm X asks for 1 band only, Pelephone will follow suit. Will they know that firm X asks for only 1 band? Yes, because once firm X does it, the threshold will increase by 100,000 NIS per round, and there will be no round in which the threshold increases by 200,000 NIS. Moreover, whenever the threshold is equal to Pelephone’s bid, it will get 3 out of the 4 bands it asked for, rather than 2 out of the 4 it got so far.
  3. Because Pelephone does not know who asks for 2 bands, a large firm who is afraid that its small partner will drop out or a small firm that tries to get 2 bands for a low price, at present they cannot allow themselves to give up a band, and therefore if firm X sticks to asking for 2 bands, firm X will never know whether Pelephone plans to stick to 4 bands or whether they will give up a band once firm X does it.

The conclusion that firm X could reach is that they should give up a band, and that this is the optimal course of action, whatever is Pelephone’s reaction. And indeed, firm X gave up a band, in a subsequent round (the first round in which it could do it) Pelephone gave up a band, and the auction was over.

What I find interesting in this auction is

  1. Even though the rules dictate that the bids are not known, and all a participant knows is the sequence of thresholds, nevertheless the number of bands that the participants asked for could have been deduced by the participants during the first rounds of the auction.
  2. Since the identity of the participant that made each bid could not be deduced, a price war could have ensued.
  3. Firm X was the only one who could stop a price war. Luckily for the other participants, it did it, and made all participants profit from a low price.
  4. Even though monitoring was incomplete, the auction was efficient: the outcome was the scenario that would have been realized if the participants could have coordinated their bids. Moreover, the final price of a band was not high, so the firms did not pay much to learn the missing data.
  5. There are many instances of auctions in which the deep theory that we develop is not helpful at all. However, strategic thinking can be useful and save hundreds of millions of dollars.