Mathematical Formulations for Winner and Price Determination for the Combinatorial Clock Auction in the 600 MHz Band

1. This document provides a concise formalization of the process and optimization problems solved in the allocation and assignment stages of the combinatorial clock auction (CCA). An overview of these topics is presented in annex C and annex F of SLPB-002-18, Technical, Policy and Licensing Framework in the 600 MHz Band, hereinafter referred to as the 600 MHz Framework. The notation is based on Quadratic Core-Selecting Payment Rules for Combinatorial Auctions, by R.W. Day and P. Cramton.^{Footnote 1}

2. Optimization is used in the CCA format in the following instances: to determine the winning bids at the end of the allocation stage and at the end of each assignment round, and to determine prices to be paid at the end of the allocation stage and at the end of each assignment round. Annex C of the 600 MHz Framework provides explanations of how winners are determined at the end of the allocation stage (see paragraphs 43-47) and at the end of each assignment round (see paragraphs 53-63). Annex F of the 600 MHz Framework gives explanations of the price determination process at the end of the allocation stage (see paragraphs 1-8) and at the end of each assignment round (see paragraphs 19-24), and it provides an example illustrating the price determination process (see paragraph 10-18).

3. All valid bids received from bidders in the clock and supplementary rounds are considered for the determination of winning packages at the end of the allocation stage. In addition, a reserve bid for every licence, at the opening bid price, will be included in the determination of winning bidders at the end of the allocation stage. In this process, it is as if ISED is a bidder in the auction, placing a bid on every licence at the opening bid price. The purpose of including a reserve bid for every licence is to ensure that the incremental price that a bidder will pay for an additional licence is at least the opening bid price of that licence. The reserve bids will not be treated as a package, but rather as having been placed by different bidders, so that any number of reserve bids can be selected in the winning combination. Specifically, in each service area there will be seven separate reserve bids, each for one set-aside licence.

4. An algorithm will be used to identify the highest-value combination of valid bids, subject to the requirements that each bidder wins no more than one of its packages, the quantity of open blocks allocated in a service area must not exceed four, and the sum of the quantities of open and set-aside blocks allocated in a service area must not exceed seven. Note that it is possible to assign more than three blocks to set-aside-eligible bidders in a service area.

• Let \(A\) be the set of service areas.
• Let \(N\) be the full set of bidders.
• Let \(D_{i}\) be the set of bidders that are set-aside-ineligible in service area \(i\).
• Let \(S\) be a package (vector) that specifies quantity of blocks in each service area. For each service area \(i\), \(S_{i}\) specifies the number of blocks in service area \(i\) included in the package \(S\). For a set-aside-ineligible bidder, \(S_{i}\) represents the number of open blocks in service area \(i\). For a set-aside-eligible bidder, \(S_{i}\) represents the number of set-aside blocks in service area \(i\).
• Let \(F_{j}\) be the set of non-zero feasible packages for bidder \(j\). That is, package \(S\in\ F_{j}\) if \(S_{i}\leq\ 4\) for every service area \(i\) in which bidder \(j\) is set-aside-ineligible, \(S_{i}\leq\ 7\) for every service area \(i\) in which bidder \(j\) is set-aside-eligible, and \(S_{i}\ >\ 0\) for at least one service area.
• Given a bidder \(j\) and a package \(S\), let \(b_{j}\ (S)\) be the dollar amount bid by \(j\) for \(S\). The complete collection of bids (including packages and dollar amounts) from all bidders is denoted by \(b\).

5. Given a set of bidders \(N\) and bids \(b\), winner determination in the allocation stage identifies the highest-value combination of valid bids, allowing each bidder to win no more than one of its package bids, allowing the quantity of open blocks allocated in a service area to be at most four, and allowing the sum of the quantities of open and set-aside blocks allocated in a service area to be at most seven. Thus, winner determination (wd) is the binary optimization:

\[wd(N,b)=max\sum_{j\in N}\sum_{S\in F_{j}}b_{j} (S)\cdot x_{j} (S)\]

subject to

where:

• \(x_{j}(S)= 1\) indicates that bidder \(j\) wins package \(S\); and
• \(x_{j}(S)= 0\) indicates that bidder \(j\) does not win package \(S\).

6. The objective function is to maximize the value (i.e., the total dollar amount) of winning bids.

7. Constraint (1) requires that for each bidder \(j\), the total number of its winning bids is 0 or 1; that is, each bidder \(j\), wins no more than one of its packages.

8. Constraint (2) requires that, for each service area \(i\), the quantity of open blocks allocated does not exceed four (the maximum amount of the open blocks in a service area).

9. Constraint (3) requires that, for each service area \(i\), the sum of the quantities of open and set-aside blocks allocated does not exceed seven, or in other words, that each block in a service area is allocated at most once.

10. Constraint (4) requires that \(x_{j}(S)\) be binary in that bidder \(j\) either wins package \(S\) or does not; it is not possible for a bidder to win only part of a package.

11. Let \(W(N,b)\) be the set of winning bidders determined by \(N\) and \(b\):

where:

• \(j \in W(N,b)\) represents a given winning bidder; and
• \(S_{j}\) is the unique non-zero package that bidder \(j \in W(N,b)\) wins (i.e. \(x_{j}(S_{j})=1\)).

12. If there is only one combination of valid bids that produces the highest value, this combination will be the outcome that determines the winning packages and winning bidders. If the same highest value is produced by more than one set of valid bids, then tie-breaking rules will be applied to ensure that a unique solution is found. Once the optimal objective value (i.e. the value of the highest-value combination of bids) is found, the objective function is replaced with the tie-breaking objective function, and a new constraint, that of attaining the optimal objective value, is introduced. These steps are applied to each tie-breaking rule in sequence. The tie-breaking rules are as follows:

• minimize the number of licences that are part of a bidder’s final clock package but not won by the bidder in a given combination of bids;
• maximize the quantity of allocated spectrum measured in eligibility points; and
• maximize the sum of the products of the total eligibility and the random number associated with each winning bid.

13. In addition to determining winning bids, the winner determination process described in paragraph 5 applied to a modified collection of bids is used multiple times for determining Vickrey prices and base prices.

14. This section corresponds to annex C (paragraphs 48-50) and annex F (paragraphs 2-9) of the 600 MHz Framework.

15. The base price is the minimum amount that a winning bidder will pay for its package of generic blocks. The base price does not include the additional, incremental amount that a winning bidder may pay for specific licences in the assignment stage. The base price is determined using all valid bids submitted by all bidders during the allocation stage. A separate base price is determined for each winning bidder.

16. ISED will use a second-price rule to calculate base prices such that the base price for a winning bidder will be at least the sum of the opening bid prices, but no higher than the actual amount of the bid. Second prices are often referred to as Vickrey prices and represent the opportunity cost of the bidder winning the package. More specifically, ISED will apply bidder-optimal core prices and use the “nearest Vickrey” approach in determining base prices.

17. The Vickrey price for each winning bidder j is calculated as follows. First, from the value of the winning combination of packages, subtract bidder j’s winning bid (value A). Next, recalculate the winning combination of packages for the hypothetical situation in which all of bidder j’s bids are excluded, as if bidder j had not participated in the auction (value B). The Vickrey price for bidder j is defined as the value of the winning combination of packages with all bidder j’s bids excluded (value B) minus the sum of the winning allocation stage bids for all bidders other than bidder j (value A); that is, B  A.

18. An extra payment beyond the Vickrey prices is sometimes required as a result of bidder complementarities. In the event that an extra payment is required, the payment to be made will be adjusted so that it is proportionate to the size of the bidder’s package, as measured by the bidder’s winning package evaluated at the opening bid prices. The procedure for calculation of this extra payment is called a core-selection adjustment.

19. The set of base prices for the winning allocation stage bids must satisfy the following conditions:

1. First condition: The base price for a winning allocation stage bid must be greater than or equal to the opening bid prices for the licences included in the package associated with the winning bid, but not more than the dollar amount of the winning bid.
2. Second condition: The set of base prices must be sufficiently high that there is no alternative bidder, or group of bidders, prepared to pay more than any winning bidder or group of winning bidders. If there is only one set of base prices that meets the first and second conditions, this set determines the base prices for the allocation stage.
3. Third condition: If there is more than one set of base prices that fulfills the first and second conditions, the set (or sets) minimizing the sum of base prices across the winning bidders is (are) selected. If there is only one set of base prices satisfying these three conditions, this set determines the base prices for the allocation stage.
4. Fourth condition: If there is more than one set of base prices that satisfy the first three conditions, the set of base prices that minimizes the weighted sum of squares of differences between the base prices and the Vickrey prices will be selected. The weighting is relative to the price of the bidder’s package evaluated at the opening prices. This approach for selecting among sets of base prices that minimize the sum of base prices across winning bidders is referred to as the “nearest Vickrey” approach.

20. Let b_j*=b_j(S_j) denote the amount of the winning bid of the winning bidder \(j \in W(N,b)\) and b* is the vector that is composed of winning bid amounts.

21. Let p = p(N,b) denote a generic price vector for winning bidders in W(N,b) where N is the full set of bidders and b is the original set of submitted bids. In addition, let

\[|p|= \sum_{j \in W(N,b)} p_{j}(N,b)\]

denote a sum of prices for winning bidders in W(N,b).

22. Vickrey prices discount each winning bid by the amount that the winning bidder contributes to the total value of the winning combination. For a given winning bidder, the contribution is determined by performing a counterfactual winner determination with the bidder excluded. The difference between the total value of the winning combination with bidder j and the total value of the winning combination, excluding all bidder j’s bids, is the contribution of bidder j to the total value of the winning combination, which is used as the discount for Vickrey prices.

23. Each winning bidder j receives the following discount from its winning bid amount:

where wd(N\{j},b) represents the value of the winning combination with all of bidder j’s bids excluded.

24. Vickrey prices p⁰ are found by applying the discount to the winning bid amount of each winning bidder:

where \(p^0_{j}\) is the Vickrey price of winning bidder j and d_j is the discount winning bidder j receives from its winning bid amount \(b^*_{j}\).

25. The Vickrey price for each winning bidder j can also be calculated as follows. First, from the value of the winning combination of packages, subtract bidder j’s winning bid \( (wd(N,b)-b^\ast_{j}) \). Next, recalculate the winning combination of packages for a hypothetical situation in which all bidder j’s bids are excluded, as if bidder j had not participated in the auction; that is, \(wd(N\backslash\{j\},b)\). The Vickrey price for bidder j is defined to be the maximum bid value with bidder j’s bids removed minus the sum of the winning allocation stage bids for all bidders other than bidder j. This method of calculating Vickrey prices is equivalent to the method described in equations (6) and (7).

26. An extra payment beyond the Vickrey prices is sometimes required as a result of bidder complementarities to satisfy the second condition (paragraph 19-b), that the set of base prices must be sufficiently high that there is no alternative bidder, or group of bidders, prepared to pay more than any winning bidder or group of winning bidders. A bidder or group of bidders willing to pay more than any winning bidder or group of winning bidders is referred to as a blocking coalition of bidders. The group that is willing to pay the most forms the first blocking coalition. A blocking coalition is unblocked by increasing base prices so that the total amount paid by winning bidders is no less than the total amount that the blocking coalition is willing to pay. After the base prices are adjusted to unblock the first blocking coalition, there may be additional blocking coalitions, each of which is unblocked by increasing the base prices until there is no alternative bidder or group of bidders willing to pay more.

27. Base prices can be calculated iteratively through a core-selection adjustment. Core selection operates by starting with Vickrey prices and then by iteratively adjusting base prices until there is no bidder or group of bidders willing to pay more than the current set of base prices. It does so by gathering pricing constraints from each blocking coalition and then by satisfying the pricing constraints by selecting base prices that minimize the opening bid price weighted distance from Vickrey prices.

28. Let pⁿ denote the price vector for core-selection iteration n whose component \(p^n_j\) is the updated price after the iteration n for winning bidder j. The Vickrey prices are p⁰ under this scheme. Given the price vector pⁿ from an iteration n and the original set of submitted bids b, calculate a set of reduced bids bⁿ by deducting the current surplus of bidder j from each bid b_j:

29. A losing bidder j is always willing to pay the full amount it bid (since a surplus of a losing bidder is zero) to be a part of a blocking coalition: \(b^n_{j}(S)=b_{j}(S)\) for all S. A winning bidder j will pay no more or less for its winning bid S_j than its price in iteration n to be part of a blocking coalition \(b^n_{j}(S_{j})=p^n_{j}\).

30. Let Cⁿ= W(N,bⁿ) be one of the sets of winners of the counterfactual winner determination with bidders in N and a set of reduced bids bⁿ. These winners form the blocking coalition for iteration n. Among all potentially blocking coalitions for iteration n, Cⁿ is the one with the highest value.

31. Let \(\beta^n\) be a blocking coalition indexed vector whose components are denoted \(\beta^n_{C^n}\) For each coalition this vector represents the sum of base prices required to unblock the coalition:

where:

• wd(Cⁿ,b) is the total value that bidders forming a blocking coalition Cⁿ can achieve without including bidders outside the coalition, or N\Cⁿ; and
• \(\sum_{j \in C^n}b^\ast_j\)is the sum of winning bids from the original winners that are present in the coalition Cⁿ.

32. Let Hⁿ be a matrix where columns are indexed by blocking coalitions and each column \(h_{C^n}\) is the characteristic vector of the complementary set of winners:

where:

• \(h_{C^n,j}=0\) indicates that a specific bidder j is part of the coalition Cⁿ; and
• \(h_{C^n,j}=1\) indicates that a specific bidder j should have its base price adjusted to unblock the coalition.

33. Find \(\mu^n\), the minimal aggregate of base prices required to unblock all coalitions as of iteration n, by optimizing a price vector p:

34. The first constraint, \(pH^n \geq\beta^n\), requires that all coalitions be unblocked; that is, in aggregate, the base prices paid by winning bidders must be at least the sum of base prices required to unblock the coalitions. The second constraint, \(p^0\leq p\leq b^\ast\), requires that the price paid by each winning bidder be no more than the price the winner bid for its winning package and no less than the Vickrey price.

35. The remaining task is to update the prices to be paid by the winning bidders so that they sum up to \(\mu^n\)(the third condition); that is, the winning bidders are collectively paying enough to ensure that no other bidder or group of bidders is willing to pay more.

36. If there is more than one set of base prices that sum up to \(\mu^n\), the set of base prices that minimizes the weighted sum of squares of differences between the base prices and the Vickrey prices will be selected. The weighting is relative to the price of the bidder’s package evaluated at the opening bid prices (the fourth condition).

37. Let o(S_j) be the price of each winning bidder’s package evaluated at opening bid prices.

38. Then find the updated prices pⁿ⁺¹ as the optimal solution to:

39. This quadratic problem minimizes the weighted sum of squares of differences between the updated base prices pⁿ⁺¹, where the updated prices are those that sum to \(\mu^n\), and the Vickrey prices p⁰(the fourth condition). The first two constraints are identical to the previous optimization problem (15). The third constraint, \(|p^{n+1}|=\mu^n\), ensures that the prices are equal to the minimal sum of base prices needed in order to unblock all the coalitions.

40. Let p^*=pⁿ for the smallest n such that the value of the coalition does not exceed the sum of base prices: \(wd(N,b^n)\leq |p^n|\). At p^*, there are no more blocking coalitions. Then, the base prices are given by p^*.

41. Generic licences are blocks of spectrum that are similar enough and of comparable value such that they can be offered in a single category. In each assignment round, winning bidders make additional bids to express their preferences for specific frequencies among the generic licences that they have won.

42. An algorithm will be used to identify the combination of specific assignments of licences that result in the highest bid amount. In the event of a tied outcome with more than one specific assignment producing the same total value, the tie will be broken by selecting the assignment that maximizes the sum of the random numbers associated with the winning bids.

• Let L be the set of frequency-specific blocks to be assigned in the assignment round. That is, L consists of blocks A, B, C, D, E, F, and G.
• Let N be the set of bidders that won one or more generic licenses during the allocation stage in the service area(s) to be assigned in the assignment round.
• Let S be a package (vector) of blocks. For each block \(i\in L\), \(S_{i}=1\) if block i is included in the package S, and \(S_{i}=0\) if block i is not included in the package S. Note that each bidding option in the assignment round can be represented as a package of blocks.
• Let \(F_{j}\) be the set of all contiguous bidding options that are consistent with the allocation stage winnings of bidder j.
• Given a bidder j and a package S, let \(b_{j}(S)\) be the amount bid by j for S. Thus, b represents a collection of bids. The bid amount is equal to 0 for every bidding option \(S\in F_{j}\) for which bidder j did not submit a bid in the assignment round.

43. Winner determination in the assignment rounds differs from the winner determination in the allocation stage in that it requires that every bidder win exactly one package and in that it does not distinguish between bidder types (set-aside-eligible or set-aside-ineligible).

\[wd'(N,b)=\textrm{ max }\sum_{j\in N}\sum_{S\in F_{j}}b_{j}(S)\cdot x_{j}(S)\]

44. Constraint (20) requires that each bidder j is assigned exactly one of its bidding options.

45. Constraint (21) requires that each block in a service area is assigned at most once.

46. Constraint (22) requires that \(x_j(S)\) be binary in that bidder j either wins package S or does not.

47. ISED will apply bidder-optimal core prices and use the “nearest Vickrey” approach to determine assignment prices. In the event that an additional payment above Vickrey prices is required, the calculation of the additional payment to be paid by each winning bidder will be weighted based on the relative size of the package that is being assigned in the given assignment round, evaluated at the opening prices. The assignment prices must satisfy the conditions given in paragraph 24 of annex F of the 600 MHz Framework.

48. To accommodate an outcome in which every bidder wins exactly one package in the assignment stage, the Vickrey discount is determined by zeroing all of bidder j’s bids instead of by removing all of bidder j’s bids:

where

49. The final prices in the CCA are the sum of base prices for generic licences found in the allocation stage plus the assignment prices for specific licence frequencies found in the assignment stage.