Do core-selecting Combinatorial Clock Auctions always lead to high efficiency? An experimental analysis of spectrum auction designs

Abstract

For many years the Simultaneous Multi-Round Auction (SMRA) has been the primary auction design for spectrum sales worldwide. Recently, the core-selecting Combinatorial Clock Auction (CCA) has been used as an alternative to the SMRA in a number of countries promising strong incentives for truthful bidding and high efficiency as a result. We analyze the efficiency and auctioneer revenue of the CCA in comparison to SMRA and examine bidding behavior in both formats. The experiments are based on two value models, which resemble single- and multiband spectrum sales in the field. Such applications often allow for thousands of possible bundles. Bidders in the CCA submitted bids for only a fraction of all bundles with a positive valuation. Bundles were selected based on synergies and payoff after the primary bid rounds. As a consequence, we found efficiency of the CCA to be significantly lower than that of SMRA in the multi-band value model and auctioneer revenue of the CCA to be lower in both value models. In addition, we characterize several properties of the auction format, which result from the two-stage design and the payment and activity rules.

Appendix

1.1 A.1 CCA activity rules

The primary bid rounds help reducing value uncertainty in the market. Activity rules should provide incentives for bidders to reveal their preferences truthfully and bid straightforwardly in the primary bid rounds. Bidders should not be able to shade their bids and then provide large jump bids in the supplementary bids round. We will describe the activity rules and derive some useful propositions.

An eligibility points rule is used to enforce activity in the primary bid rounds. The number of bidder’s eligibility points is non-increasing between rounds, and it limits the number of blocks the bidder can bid on in subsequent rounds. In the supplementary bids round, the following rules apply:¹²

• There is no limit on the supplementary bid that can be made for the bundle bid in the final primary bid round.

• The supplementary bid for any other bundle A is subject to a cap determined in the following way:

  • 1. First, we determine the last primary bid round in which the bidder would have been eligible to bid for bundle A. Call this round the anchor round n. This will either be the final round or some round in which the bidder dropped its eligibility to bid (by reducing the number of blocks bid for) and gave up the opportunity to bid for bundle A in later primary bid rounds.

  • 2. Suppose that the bidder bids for bundle B in round n; The supplementary bid for bundle A cannot exceed the bid for bundle B (i.e., the supplementary bid for this bundle, if one is made, or otherwise the primary round bid) plus the price difference between bundles A and B that applied after round n.

Since the bidder had the opportunity to choose between A and B back in round n, and to opt for B, the bidder revealed the relative value between these two bundles. In the supplementary bids round, the bidder cannot reverse this reported preference by submitting a high bid on A. If a bidder bids on a bundle C⊂B in the supplementary bids round, the bundle price is also bounded by the supplementary bid for B minus the price difference between the bundles B and C after round n. In other words, this is a revealed preference constraint. This constraint is applied to the supplementary bids phase and with respect to the last primary bid round, where the bidder had sufficient eligibility points to submit a bid, which is different to his standing bid after the primary bid rounds. Also, all supplementary bids must satisfy the revealed preference limit with respect to the final clock round regardless of whether the supplementary bid package is larger or smaller than the final clock package. A formalization of the revealed preference constraint will be provided for the proofs of the Propositions 3 and 4 below.

Proposition 1

If a bidder follows a straightforward bidding strategy in the primary bid rounds of a CCA with an anchor activity rule, then the activity rule will not restrict him to bid his maximum valuation on every bundle in the supplementary bids round.

Proof

Let’s assume, a bidder bids straightforward, i.e., he submits a bid on his payoff maximizing bundle in every round. Throughout the primary bid rounds he might have switched from a bundle A to a bundle B in a round n, when v(B)−p _n (B)>v(A)−p _n (A), where p _n (A) is the price of bundle A in round n. For the bundle A the bidder did not necessarily bid up to his true valuation in the primary bids round. Based on the anchor rule, in the supplementary bids round s the bidder can submit a maximum bid of $p_{s}^{max}(A) = v(B)+p_{n}(A)-p_{n}(B)$, if he bid his true valuation p _s (B)=v(B). As a result of adding both inequalities $p_{s}^{max}(A) > v(A)$ such that the bidder can bid up to his true valuation on A in the supplementary bids phase. Note that the same argument applies for bundle bids, which were submitted in the primary bid rounds before A, after the bidder has revealed his true valuation v(A) in the supplementary bids round. The proof also applies to bundles C, on which the bidder has never submitted a bid in the primary bid rounds, as long as v(B)−p _n (B)>v(C)−p _n (C) in a round n, where the bidder had sufficient eligibility points to bid on this bundle. □

Unfortunately, bidding straightforward is not always possible.

Proposition 2

If valuations for at least two bundles A and B are full substitutes with v(A∪B)=max(v(A),v(B)) and the bundle of higher valuation A requires less bid rights than the lower valued bundle B, straightforward bidding is not possible due to the activity rule in the primary bid rounds.

Proof

Suppose there are two different bundles A and B with |A|<|B| and v(A∪B)=max(v(A),v(B)). The activity rule in the primary bid rounds does not allow to increase the number of bid rights in later rounds. We assume the number of bid rights required to be proportional to the size of the bundle. If v(A)>v(B) and prices in A rise such that the payoff of A becomes smaller than that of B, a bidder would not be able to switch to bundle B, and would therefore not be able to bid straightforward on his payoff maximizing bundle at the prices. □

The proposed rules for spectrum auctions to be organized in the future have been improved to cure problems like this and also apply the revealed preference constraint to the primary bid rounds. Also, the constraint needs to be satisfied with respect to any eligibility-reducing primary bid round after the one, where the bidder could submit a bid on bundle C for the last time including the last primary bid round, and we will draw on those rules for the remainder.

1.2 A.2 Safe supplementary bids

We first introduce some additional notation. Let q=(q ₁,…,q _d ,…,q _D ) denote the supply of blocks in D bands, and $b^{p}_{j}(q^{j}) \in B$ the standing bid of bidder j∈J on bundle $q^{j} = (q^{j}_{1}, q^{j}_{2}, \ldots, q^{j}_{D})$ after the primary bid phase. In addition, let r ^s(q) denote the revenue of the optimal allocation after the supplementary bids phase including all bids B in both phases. r ^p(q) describes the value with only standing bids in the last round of the primary bids phase. $r^{s}_{-b^{p}_{j}(q^{j})}(q)$ denotes the auctioneer revenue in the optimal allocation without all bids of bidder j∈J on bundle q ^j. q ^−j=q−q ^j is the set of blocks complementary to q ^j. We refer to π as the ask price vector in the last primary bid round. Supplementary bids q ^j′ on packages different to the standing bid q ^j of bidder j are restricted by a revealed preference rule such that bids with additional blocks are restricted by the prices after the anchor round. As prices in the primary bid rounds are increasing monotonously, the highest such price is π, such that $b^{s}_{j}(q^{j'})-q^{j'}\pi\leq b^{s}_{j}(q^{j}) - q^{j}\pi$ or $b^{s}_{j}(q^{j'}) \leq b^{s}_{j}(q^{j}) + (q^{j'}-q^{j})\pi$.

Proposition 3

If demand equals supply in the final primary bid round, a supplementary bid $b^{s}_{j}(q^{j})>b^{p}_{j}(q^{j})$ cannot become losing.

Proof

In the last primary bid round, there is a demand of exactly q blocks, if demand equals supply. Bidder j∈J submits a bid $b^{p}_{j}(q^{j})$ in the last primary bids round, his standing bid after the primary bid rounds. Let $b^{s}_{j}(q^{j}) > r^{s}_{-b^{p}_{j}(q^{j})}(q) - r^{s}(q^{-j})$ be the bid price that bidder j needs to submit, in order to win q ^j after the supplementary bid round. Due to the anchor rule, j’s competitors k∈J with k≠j can only increase his bid without limits on bundles q ^k≤q ^−j, his standing bid which was submitted in the last primary bids round. Any high supplementary bid $b^{s}_{k}(q^{k})$ on a bundle q ^k from k’s standing bid after the primary bid rounds, will increase $r^{s}_{-b^{p}_{j}(q^{j})}(q)$ as well as r ^s(q ^−j) and cannot impact $b^{s}_{j}(q^{j})$, such that $b^{s}_{j}(q^{j}) > r^{p}_{-b^{p}_{j}(q^{j})}(q) - r^{p}(q^{-j})$ is sufficient. This difference cannot be higher than q ^j π. Supplementary bids on packages different to the standing bid q ^k′ of bidder k are restricted, such that $b^{s}_{k}(q^{k'}) \leq b^{s}_{k}(q^{k}) + (q^{k'}-q^{k})\pi$. So, if blocks are added to the standing bid of a competing bidder k, the price of additional blocks can not exceed π. Also, if a bidder k bids on less blocks in a band m than in his standing bid $q^{k'}_{d}-q^{k}_{d} < 0$, the bid price must be reduced by $(q^{k'}_{d}-q^{k}_{d})\pi_{d}$. As a result, any supplementary bid $b^{s}_{j}(q^{j}) > b^{p}_{j}(q^{j}) = q^{j}\pi$ must be winning. □

If there is excess supply in the last round of the primary bid phase, a last primary round bid $b^{p}_{j}(q^{j})$ can become losing, because even if no supplementary bids were submitted, the auctioneer conducts an optimization with all bids submitted at the end, which might displace $b^{p}_{j}(q^{j})$. This raises the question for the safe supplementary bid $b^{s}_{j}(q^{j}_{p})$, which ensures that the bidder j wins the bundle $q^{j}_{p}$ of his standing bid from the primary round after the supplementary bids phase.¹³

Proposition 4

If bundle q ^u is unallocated after the last primary bid round, a supplementary bid $b^{s}_{j}(q^{j}) > b^{p}_{j}(q^{j}) + q^{u}\pi$ of a standing bidder j cannot become losing if all his supplementary bids contain q ^j.

Proof

Let’s first assume a specific situation with bidder j bidding on a bundle q ^j in the last primary bid round and two other competitors, who bid on a bundle with all blocks q in the previous to last round of the primary bid phase. In the last round the two competitors reduce demand to zero so that q ^−j blocks have zero demand after the last primary bid round. Now, at least one of the competitors k submits a supplementary bid on the bundle q at the prices of the last primary round qπ. Now, bidder j can win bundle q ^j only, if he increases his bid to $b^{s}_{j}(q^{j}) > b^{p}_{j}(q^{j}) + q^{-j}\pi= q\pi$, the safe supplementary bid. Supplementary bids of bidders k are restricted, such that $b^{s}_{k}(q^{k'}) \leq b^{s}_{k}(q^{k}) + (q^{k'}-q^{k})\pi$. Consequently, no combination of bids of competitors can exceed qπ.

Similarly, if the competitors k reduce their demand such that a package q ^u with q ^u<q ^−j blocks remain unsold after the primary bid rounds, bidder j has to increase his standing bid by more than q ^u π to become winning after the supplementary bid round with certainty. Again, this is due to the revealed preference rule, because j can leverage the standing bid on q ^k and supplementary bids $b^{s}_{k}(q^{k})$ of another bidder k. If blocks are added to the standing bid of the competing bidder k, the price of additional blocks can not exceed π. Also, if a bidder k bids on less blocks in a band m than in his standing bid $q^{k'}_{d}-q^{k}_{d} < 0$, the bid price must be reduced by $(q^{k'}_{d}-q^{k}_{d})\pi_{d}$.

Note, that if bidder j also bids on packages q ^j′≤q ^j, then his safe supplementary bid on q ^j is not safe any more. To see this, look at a simple example with three items {α,β,γ} and two bidders 1 and 2. Bidder 1 has a standing bid on the bundle {α,β} after the primary bid rounds, while {γ} is unsold. Prices for all three items in the last primary bid round are $10. Bidder 1 bids $40 on {α,β} in the supplementary bids round, and $30 for {α}. Bidder 2 bid $ 18 in the previous to last primary bid round on {β,γ}. Even though bidder 1 submitted a safe bid on {α,β}, his new bid on {α} together with the last primary round bid of bidder 2 would become winning. □

1.3 A.3 Spiteful bidding

In the following, we will provide a brief example of a CCA, in which a bidder can submit a spiteful bid, which increases the payments of other bidders with little risk of winning such a bid. If excess supply is known and the bidder submits a safe supplementary bid as described in the last section, such bids would not stand a chance of winning.

Consider one region in which 3 blocks A (1 unit) and B (2 units), and one region in which 3 blocks C (1 unit) and D (2 unites) are up for auction among one national and several regional bidders. Start prices are $1 for all blocks and prices for overdemanded blocks are increased by $1 per round. Each block corresponds to one eligibility point.

The national bidder N is only interested in winning block A and C in each of the two regions for at most $40, i.e. he is not willing to switch to other packages. Regional bidder R ₁₁ is only interested in obtaining block A in his region. Regional bidder R ₂₁ prefers AB over 2B. He is willing to switch from AB to 2B, if prices differ by at least $15. Regional bidders R ₁₂ and R ₂₂ would like to obtain CD. Bidder R ₂₂ is weaker and willing to bid on D after if he is overbid.

Table 10 illustrates the primary bid rounds, while Table 11 describes the payments if no supplementary round bid was submitted. Finally, Table 12 illustrates the payments if bidder R ₂₁ submitted a spiteful bid on AB for $ 22, the package price in the final round for which he would still be eligible according to the activity rule. This is round 41, where the price for A is $21 and for B is $1. Let’s assume bidder R ₁₁ increases his bid on block A by 1 in the supplementary round to be safe. The payments of R ₁₁ for his winning bid on A are (22−(66−(16+42)))=$14 without the spiteful bid, and (22−(66−(22+42)))=$20 with the spiteful bid. Consequently, the payment of the regional competitor increases by $6 with both, a VCG and a core-selecting payment rule. Such bids are possible due to the initial eligibility points rule, which might not reflect the proportion of clock prices after the clock auction.

Table 10 Bids in the primary bid rounds. Standing bids are marked with a star

Table 11 Payments after the supplementary bids round without additional supplementary bids

Table 12 Payments after the supplementary bids round with an additional supplementary bid by bidder R ₂₁ on AB for $22