Mathematical Formulations for Winner and Price Determination in the Combinatorial Clock Auction for Mobile Broadband Services (MBS) — 700 MHz Band

Posted on Industry Canada website: November 5, 2012
(modified January 2014)


Industry Canada Notice: This document has been prepared by Power Auctions LLC for Industry Canada. This material represents the winner and price determination processes described in DGSA-001-13, Licensing Framework for Mobile Broadband Services (MBS) — 700 MHz Band.

May 2013
Clarification has been added to paragraphs 33 and 34.

December 2013
Clarification has been added to paragraphs 8, 38, 42 and 43.

January 2014
A modification has been made to equation 16, paragraph 34.


Contents

1. Purpose

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 B and Annex E of DGSA-001-13, Licensing Framework for Mobile Broadband Services (MBS) — 700 MHz Band.Footnote 1 The notation is based on Quadratic Core-Selecting Payment Rules for Combinatorial Auctions, by R.W. Day and P. Cramton.Footnote 2

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 B of DGSA-001-13 provides explanations of how winners are determined at the end of the allocation stageFootnote 3 and at the end of each assignment round.Footnote 4 Annex E of DGSA-001-13 gives explanations of the price determination process at the end of the allocation stageFootnote 5 and at the end of each assignment round,Footnote 6 and it provides an example illustrating the price determination process.Footnote 7

2. Determining the Winning Packages in the Allocation Stage

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 Industry Canada 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 value that a bidder would be prepared to 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.

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 and that each licence is allocated no more than once.

2.1 Preliminary Definitions

  • Let \(N\) be a set of bidders.
  • Let a supply \(M\) be a vector mapping products to quantities, so that for each product \(i\), \( M_{i} \in \{1, 2,...\}\). If \(i\) is a product with a single specific licence, then \(M_{i} = 1\). If \(i\) is a product with multiple generic licences, then \(M_{i} > 1\).
  • Let \(S\) be a package (vector) of products. For each product \(i, S_{i} \;(S_{i} \in \{0,1,...,M_{i},\})\) specifies the number of units of product \(i\) included in the package \(S\).
  • Define a sub-supply relation \( \subseteq \) such that \( S \subseteq M \) if and only if \(S_{i} \leq M_{i}\) for every product \(i\).
  • Let \(o(S)\) be the opening bid price for a package \(S\).
  • 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.
  • Define binary operations over price vectors in the regular way. For example, given two price vectors \(p\) and \(q\), define \(p − q \) such that \( (p − q)_{j} = p_{j} − q_{j}\).

2.2 Winner Determination in the Allocation Stage

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 and allocating no more than the available supply. Thus, winner determination is the binary optimization:

\[wd(N,b)=\max\sum_{j \in N} \sum_{S \subseteq M}b_{j}(S)\cdot x_{j}(S)\] \[\text {(1) }\]
\[ \text{subject to} \;\; \sum_{S \subseteq M}x_{j}(S) \leq 1 \;\;\;\;\;\;\;\;\;\; \forall {j \in N}\] \[ \text {(2) }\]
\[\sum_{j \in N} \sum_{S \subseteq M}S_{i}\cdot x_{j}(S)\leq M_{i} \;\;\;\;\;\;\;\;\; \forall {i \in M} \] \[\text {(3) }\]
\[ x_{j}(S) \in \{0,1\},\;\;\;\;\;\;\ \forall S,j \;\;\text {such that}\;\; b_{j}(S) \;\;\text {is defined}\] \[ \text {(4) }\]

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 first constraint,

\[ \sum_{S \subseteq M} x_{j}(S) \leq 1, \]
requires that for each bidder \(j\), the total number of its winning bids is 0 or 1; that is, bidder \(j\) can win at most one of its package bids. The second constraint,
\[ \sum_{j \in N} \sum_{S \subseteq M} \;S_{i}\cdot x_{j}(S)\leq M_{i}\;,\]
requires that for each product \(i\), the total number of units of product \(i\) contained in winning packages across all bidders is less than or equal to the supply of product \(i\), or in other words, that each generic licence of each product can be allocated at most once. The third constraint,
\[ x_{j}(S) \in \{0,1\},\;\]
requires that \(x_{j}(S) \) be binary in that a bidder either wins its package or does not; it is not possible for a bidder to win only part of a package.


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

\[ W(N,b)=\{j \in N \; | \; \exists \;S_{j} \subseteq M, x_{j}(S_{j})=1\}\] \[ \text {(5) }\]

where:

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

8. 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 (equation 1) 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 lost licences (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.

9. In addition to determining winning bids, the winner determination process described in equations (1) to (4) is used multiple times in determining Vickrey prices and base prices.

3. Determining the Base Prices in the Allocation Stage

10. This section corresponds to Annex B (paragraphs 52-54) and Annex E (paragraphs 2-9) of DGSA-001-13.

11. The base price is the minimum amount that the winning bidders will pay for their generic winning packages; it does not include the additional, incremental amount that winning bidders may pay for specific licences in the assignment stage if generic licences are included in their winning allocation stage package. 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.

12. Industry Canada 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, Industry Canada will apply bidder‑optimal core prices and use the "nearest Vickrey" approach in determining base prices.

13. The Vickrey price for each winning bidder j is calculated as follows. First, from the value of the winning combination of packages,Footnote 8 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.

14. An extra payment beyond the Vickrey prices is sometimes required as a result of 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.

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

  • (a) 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.
  • (b) 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.
  • (c) 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.
  • (d) 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.

3.1 Preliminary Definitions

16. Let \(b_{j}^*=b_{j}(S_{j})\) denote the amount of the winning bid of the winning bidder \(j \in W(N,b)\).

17. 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

\[ \left \vert p \right \vert = \sum_{j \in W(N,b)} p_{j}(N,b) \]
denote a sum of prices for winning bidders in \(W(N,b)\).

18. 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.

19. Each winning bidder \(j\) receives the following discount from its winning bid amount:

\[ d_{j}= wd(N,b)-wd(N \setminus \{j\},b) \] \[\text {(6) }\]

20. Vickery prices \(p^0\) are found by applying the discount to the winning bid amount of each winning bidder:

\[ p_{j}^0=b_{j}^*-d_{j} \] \[\text {(7) }\]

where:

  • \(d_{j}\) is the discount winning bidder \(j\) receives from its winning bid amount \(b_{j}^*\); and
  • \(wd(N \setminus \{j\},b)\) represents the value of the winning combination with all of bidder \(j\)'s bids excluded.

21. 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_{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\setminus\{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).

\[p_{j}^0=b_{j}^*-d_{j}\] \[\text{(8)}\]
\[p_{j}^0=b_{j}^*-(wd(N,b)-wd(N \setminus\{j\},b))\] \[\text{(9)}\]
\[p_{j}^0=wd(N \setminus\{j\},b)-wd(N,b)+b_{j}^*\] \[\text{(10)}\]
\[p_{j}^0=wd(N\setminus\{j\},b)-(wd(N,b)−b_{j}^*)\] \[\text{(11)}\]

3.2 Core-Selection Adjustment

22. An extra payment beyond the Vickrey prices is sometimes required as a result of complementarities to satisfy the second condition, 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 are unblocked by increasing the base prices until there is no alternative bidder or group of bidders willing to pay more.

23. 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.

24. Let \(p^n\) denote the price vector for core-selection iteration \(n\). The Vickrey prices are \(p^0\) under this scheme. Given the price vector \(p^n\) from an iteration \(n\) and the original set of submitted bids \(b\), calculate a reduced set of bids \(b^n\) by deducting the current surplus of bidder \(j\) from each bid \(b_{j}\):

\[b_{j}^n(S)=b_{j}(S)-(b_{j}^*-p_{j}^n)=b_{j}(S)-b_{j}^*+p_{j}^n\] \[\text{(12)}\]

25. A losing bidder \(j\) is always willing to pay the full amount it bids (since a surplus of a losing bidder is zero) to be a part of a blocking coalition: \(b_{j}^n(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_{j}^n(S_{j})=p_{j}^n\).

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

27. Let \(\beta^n\) be a blocking coalition indexed vector where the value for each coalition is the sum of base prices required to unblock the coalition:

\[\beta_{C^n}^n=wd(C^n,b)-\sum_{j\epsilon C^n}b_{j}^*\] \[\text{(13)}\]

where:

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

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

\[ a_{C^n,j}= \begin{cases} 0 & \mbox{ if \(j \in C^n\) } \\ 1 & \mbox{ otherwise} \end{cases} \] \[\text{(14)}\]

where:

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

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

\[ \mu^n = min \left \vert p \right \vert \]
\[ \mbox { subject to }\;\;\; pA^n \geq \beta^n \] \[\text{(15)}\]

\[ p^0 \leq p \leq b^* \]

30. The first constraint, \(pA^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^*\), 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.

31. The remaining task is to update 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 are willing to pay more.

32. 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).

33. Let \(o(S_{j})\) be the price of each winning bidder’s package evaluated at opening bid prices.:

34. Then find the updated prices \(p^{n+1}\) as the optimal solution to:

\[\min \sum_{j \notin C^n} \frac {( p^{n+1}_j − p^0_{j})^2} {o(S_{j})}\] \[\text{(16)}\]
\[ \text{subject to }\;\;\; p^{n+1}A^n \geq \beta^n\] \[\text{(17)}\]
\[ p^0 \leq p^{n+1} \leq b^*\] \[\text{(18)}\]
\[ \left \vert p^{n+1} \right \vert = \mu^n\] \[\text{(19)}\]

35. This quadratic problem minimizes the weighted sum of squares of differences between the updated base prices \(p^{n+1}\), where the updated prices are those that sum up to \(\mu^n\), and the Vickrey prices \(p^0\) (the fourth condition). The first constraint, \(p^{n+1}A^n \geq \beta^n \), requires that each individual coalition is unblocked; that is, the base prices paid in aggregate by winning bidders must be at least the sum of base prices required to unblock the coalitions. The second constraint, \( p^0 \leq p^{n+1} \leq b^*\), requires that no bidder pay more than its winning bid amount and no less than its Vickrey price. The third constraint, \( \left \vert p^{n+1} \right \vert = \mu^n\), ensures that the prices are no higher or lower than the minimal sum of base prices needed in order to unblock all the coalitions.

36. Let \(p^*=p^n\) for the smallest \(n\) such that value of the coalition does not exceed the sum of base prices: \(wd(N,b^n) \leq \left \vert p^n \right \vert \) . At \(p^*\), there are no more blocking coalitions.

4. Determining Winning Bids at the End of Each Assignment Round

37. 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.

38. 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 products of the total eligibility and the random number associated with each winning bid.

39. 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. Also, all products are unique because of the nature of the assignment problem.

\[ wd'(N,b)=\max\sum_{j \in N} \sum_{S \subseteq M}b_{j}(S)\cdot x_{j}(S) \] \[\text{(20)}\]
\[ \text {subject to} \;\; \sum_{S \subseteq M}x_{j}(S) \;\; = \;\;1 \;\;\;\;\;\;\;\;\;\; \forall {j \in N} \] \[\text{(21)}\]
\[\sum_{j \in N} \sum_{S \subseteq M}S_{i}\cdot x_{j}(S)\leq M_{i} \;\;\;\;\;\;\;\;\;\;\;\; \forall {i \in M} \] \[\text{(22)}\]
\[ x_{j}(S) \in \{0,1\},\;\;\;\;\;\;\ \forall S,j \;\; \text {such that} \;\;b_{j}(S) \text { is defined }\] \[\text{(23)}\]

(The equals sign in equation (21) is the only difference between \(wd\) and \(wd'\) .)

5. Determining the Assignment Prices in the Assignment Stage

40. Base prices for the allocation stage are just \(\hat{p}^*\) where \(N\) is the full set of bidders \(\hat{N}\) , \(M\) is the supply of licences, \(o\) is the opening price vector, and \(b\) is the set of allocation bids \(\hat{b}\) .

41. 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 :

\[ d'_{j} = wd'(N,b) − wd'(N,b[j\rightarrow 0])\] \[\text{(24)}\]

where:

\[ b[j\rightarrow 0]_k (S) = \begin{cases} 0 & \mbox{ if \(k = j\) } \\ b_k (S) & \mbox{ otherwise} \end{cases}\] \[\text{(25)}\]

42. Given the modification to winner determination in the assignment rounds, that every bidder must win exactly one package, the following modifications are necessary for price determination in the assignment stage: assignment prices are \(\hat{p}'^*\) where \(N\) is the subset of bidders having licences assigned in the round, \(M\) is the supply of licences being assigned and \(b\) is the set of assignment bids.

43. As in the allocation stage, the assignment prices must satisfy conditions similar to those outlined in paragraph 15 above, noting that for the first condition, the assignment prices must be greater than or equal to zero, and not more than the dollar amount of the winning assignment stage bid.

44. 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.

Date modified: