Énoncés mathématiques liés à la détermination des prix et à la nomination des gagnants lors d’enchères combinatoires au cadran pour services mobiles à large bande (SMLB) — bande de 700 MHz

Affiché sur le site Web d'Industrie Canada : le 5 novembre 2012
(mis à jour janvier 2014)

 

Avis émis par Industrie Canada : Ce document a été rédigé par Power Auctions LLC pour Industrie Canada. Son contenu définit clairement le processus de fixation des prix et de nomination des gagnants tel que décrit dans le document DGSA-001-13, Cadre de délivrance des licences pour services mobiles è large bande (SMLB) – bande de 700 MHz.

Mai 2013
Des précisions ont été incluses aux paragraphes 33 et 34.

Décembre 2013
Des précisions ont été incluses aux paragraphes 8, 38, 42 et 43.

Janvier 2014
Une modification a été effectuée à l’équation 16 au paragraphe 34

 

Table des matières

1. Objet

1. Le présent document formule de manière concise les problèmes de processus et d'optimisation qui ont été résolus aux étapes de l'attribution et de l'assignation lors d'enchères combinatoires au cadran (ECC). Un aperçu de ces sujets est présenté aux annexes B et E du document DGSA-001-13, Cadre de délivrance des licences pour services mobiles è large bande (SMLB) — bande de 700 MHzNote de bas de page 1. La notation est basée sur le document intitulé Quadratic Core-Selecting Payment Rules for Combinatorial Auctions de R.W. Day et P. CramtonNote de bas de page 2.

2. L’optimisation est utilisée avec le processus des ECC dans les exemples suivants : pour déterminer les soumissions retenues et les prix è payer è la fin de l’étape de l’attribution et è la fin de chaque ronde d’assignation. La manière de déterminer les gagnants è la fin de l’étape de l’attributionNote de bas de page 3 et è la fin de chaque ronde d’assignationNote de bas de page 4 est expliqué è l'annexe B du document DGSA-001-13. Le processus de détermination des prix è la fin de l’étape de l’attributionNote de bas de page 5 et è la fin de chaque ronde d’assignationNote de bas de page 6 est expliqué è l'annexe E du même document, et donne aussi un exemple illustrant le processus de détermination des prixNote de bas de page 7.

2. Détermination des soumissions retenues à l'étape de l'attribution

3. Toutes les soumissions valides reçues lors des rondes au cadran et de la ronde supplémentaire sont examinées en vue de la détermination des soumissions retenues à la fin de l'étape de l'attribution. De plus, une mise à prix pour chaque licence, au prix de départ, sera incluse dans la détermination des soumissionnaires retenus à la fin de l'étape de l'attribution. Lors de ce processus, Industrie Canada agira comme s'il était soumissionnaire pendant les enchères en faisant une soumission pour chaque licence au prix de départ. L'inclusion d'une mise à prix pour chaque licence a pour but de garantir que la valeur supplémentaire qu'un soumissionnaire serait prêt à payer pour une licence additionnelle est au moins égale au prix de départ de la licence. Les mises à prix ne seront pas traitées de façon globale, mais plutôt comme ayant été faites par différents soumissionnaires, de manière que tout nombre de mise à prix puisse être sélectionné à partir de la combinaison retenue.

4. Un algorithme sera utilisé pour déterminer la combinaison de soumissions valides qui a la plus haute valeur, sous réserve que chaque soumissionnaire ne gagne qu'un de ses ensembles et que chaque licence ne soit attribuée qu'une seule fois.

2.1 Définitions préliminaires

  • Soit \(N\), un groupe de soumissionnaires.
  • Soit l'offre \(M\), un vecteur d'application entre produits et quantités. Ainsi, pour chaque produit \(i\), \( M_{i} \in \{1, 2,...\}\). Si \(i\) est un produit comportant une seule licence, alors \(M_{i} = 1\). Si \(i\) est un produit associé à plusieurs licences génériques, alors \(M_{i} > 1\).
  • Soit \(S\), un ensemble (vecteur) de produits. Pour chaque produit \(i, S_{i} \;(S_{i} \in \{0,1,...,M_{i},\})\) précise le nombre d'unités du produit \(i\) qui sont incluses dans l'ensemble \(S\).
  • Définissons une relation de sous-offre \( \subseteq \) tel que \( S \subseteq M \) si, et seulement si, \(S_{i} \leq M_{i}\) pour chaque produit \(i\).
  • Soit \(o(S)\), le prix de départ pour un ensemble \(S\).
  • Pour un soumissionnaire \(j\) et un ensemble \(S\), définissons \(b_{j}(S)\) comme le montant de la soumission de \(j\) pour \(S\). Ainsi, \(b\) représente un groupe de soumissions.
  • Définissons de la façon habituelle les opérations binaires sur les vecteurs de prix. Par exemple, pour les deux vecteurs de prix \(p\) et \(q\) , définissons \(p − q\) de telle sorte que \( (p − q)_{j} = p_{j} − q_{j}\).

2.2 Détermination des soumissionnaires retenus à l'étape de l'attribution

5. Si nous avons un groupe de soumissionnaires et de soumissions \(b\) , la désignation des soumissionnaires retenus à l'étape de l'attribution détermine la combinaison de soumissions valides qui a la plus haute valeur tout en permettant à chaque soumissionnaire de ne gagner qu'un de ses ensembles et de n'attribuer que l'offre disponible. Ainsi, la détermination des soumissionnaires retenus correspond à l'optimisation binaire suivante :

\[wd(N,b)=\max\sum_{j \in N} \sum_{S \subseteq M}b_{j}(S)\cdot x_{j}(S)\]
\[ \text {(1) }\]
\[ \text{subordonnée è } \;\; \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 { tel que}\;\; b_{j}(S) \;\;\text {est défini}\]
\[ \text {(4) }\]

où :

  • \( x_{j}(S)=1\) indique que le soumissionnaire \(j\) gagne l'ensemble \(S\);
  • \(x_{j}(S)=0\) indique que le soumissionnaire \(j\) ne gagne pas l'ensemble \(S\).

6. La première contrainte \[ \sum_{S \subseteq M} x_{j}(S) \leq 1 \] exige que pour chaque soumissionnaire \(j\), le nombre total de ses soumissions gagnantes soit égal à 0 ou à 1, ce qui signifie que le soumissionnaire \(j\) ne peut gagner qu'une seule de ses offres globales. La seconde contrainte \[ \sum_{j \in N} \sum_{S \subseteq M} \;S_{i}\cdot x_{j}(S)\leq M_{i}\;\] exige que pour chaque produit \(i\) , le nombre total d'unités du produit \(i\) contenues dans les soumissions gagnantes de tous les soumissionnaires soit inférieur ou égal à l'offre du produit \(i\). Autrement dit, que chaque licence générique de chaque produit ne puisse être attribuée qu'une seule fois. La troisième contrainte \[ x_{j}(S) \in \{0,1\}\;\] exige que \(x_{j}(S) \) soit binaire, ce qui signifie que si un soumissionnaire obtient ou non la totalité de son ensemble; il n'est pas possible qu'il ne gagne qu'une seule partie de son offre globale.

7. Soit \(W(N,b)\), l'ensemble des soumissionnaires retenus déterminé par \(N\) et \(b\):

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

où :

  • \(j \in W(N,b)\) représente un soumissionnaire gagnant donné;
  • \(S_{j}\) est l'ensemble unique que le soumissionnaire \(j \in W(N,b) \) gagne (c.-à-d. \(x_{j}(S_{j})=1)\).

8. Si une seule combinaison de soumissions valides produit la combinaison ayant la plus haute valeur, cette combinaison constitue le résultat qui détermine les offres globales retenues et les soumissionnaires gagnants. Dans le cas contraire, des règles sont appliquées pour briser l'égalité et garantir qu'une solution unique soit trouvée. Une fois que la valeur objective optimale a été trouvée, c'est-à-dire une fois que la combinaison de soumissions ayant la plus haute valeur a été déterminée, il faut remplacer l'objectif de l'équation (1) par l'objectif de bris d'égalité et introduire une contrainte garantissant que la valeur objective optimale sera atteinte. Cette opération est effectuée dans l'ordre pour chaque règle de bris d'égalité. Les règles de bris d'égalité sont les suivantes :

  • minimiser le nombre de licences perdues (les licences perdues sont celles qui font partie de l’ensemble du soumissionnaire è la ronde finale au cadran, mais qui n’ont pas été gagnées par le soumissionnaire dans une combinaison de soumissions donnée);
  • maximiser la quantité de spectre attribuée et mesurée d’après les points d’admissibilité;
  • maximiser la somme des produits formant l'admissibilité totale et les nombres aléatoires associés à chaque soumission gagnante.

9. En plus de déterminer les soumissions gagnantes, le processus de désignation des gagnants décrit dans les équations (1), (2), (3) et (4) est utilisé à plusieurs reprises pour déterminer les prix Vickrey et les prix de base.

3. Détermination des prix de base à l'étape de l'attribution

10. Cette section correspond à l'annexe B, paragraphes 52-54 et à l'annexe E, paragraphes 2-9 du document DGSA-001-13.

11. Le prix de base représente la somme minimum que les soumissionnaires retenus paieront pour leurs ensembles génériques gagnants; il ne comprend pas la somme additionnelle ou supplémentaire que paieront éventuellement les soumissionnaires retenus pour les licences particulières accordées à l'étape de l'assignation, s'il y avait des licences génériques incluses dans leur ensemble gagnant à l'étape de l'attribution. Le prix de base est déterminé en utilisant toutes les soumissions valides faites par tous les soumissionnaires à l'étape de l'attribution. Un prix de base distinct est établi pour chaque soumissionnaire gagnant.

12. Industrie Canada utilisera une règle du deuxième prix pour calculer les prix de base, de manière que le prix de base pour un soumissionnaire gagnant soit au moins égal à la somme des prix de départ, sans être supérieur au montant réel de la soumission. Les deuxièmes prix sont souvent appelés prix Vickrey et représentent le coût d'opportunité pour l'ensemble du soumissionnaire gagnant. Plus précisément, Industrie Canada appliquera les prix de base optimaux pour les soumissionnaires et utilisera la « méthode Vickrey de calcul du deuxième prix » pour déterminer les prix de base.

13. Le prix Vickrey pour chaque soumissionnaire \(j\) retenu se calcule comme suit. Premièrement, la soumission gagnante \(j\) du soumissionnaire (valeur A) est soustraite de la valeur de la combinaison gagnante d'ensemblesNote de bas de page 8. Ensuite, la valeur de la combinaison gagnante d'ensembles est recalculée selon l'hypothèse où toutes les soumissions du soumissionnaire \(j\) seraient exclues, comme si le soumissionnaire \(j\) n'avait pas participé aux enchères (valeur B). Le prix Vickrey pour le soumissionnaire \(j\) se définit comme étant la valeur de la combinaison gagnante d'ensembles une fois que toutes les soumissions du soumissionnaire \(j\) ont été exclues (valeur B), moins le total des soumissions gagnantes à l'étape de l'attribution pour tous les soumissionnaires sauf pour le soumissionnaire \(j\) (valeur A), c'est-à-dire B−A.

14. Parfois, un paiement en sus du prix Vickrey est exigé par suite d'éléments complémentaires. Si un paiement additionnel est requis, ce dernier sera ajusté proportionnellement à la taille de l'ensemble du soumissionnaire, telle que mesurée par l'ensemble du soumissionnaire gagnant évalué aux prix de départ.

15. L'ensemble des prix de base pour les soumissions gagnantes à l'étape de l'attribution doit satisfaire aux quatre conditions suivantes :

  • a) Première condition : Le prix de base pour gagner une soumission à l'étape de l'attribution doit être supérieur ou égal aux prix de départ des licences incluses dans l'ensemble associé à la soumission retenue, mais pas plus élevé que le montant en dollars de la soumission gagnante.
  • b) Deuxième condition : Le groupe des prix de base doit être suffisamment élevé pour qu'aucun autre soumissionnaire ou groupe de soumissionnaires ne soit prêt à payer davantage que tout soumissionnaire gagnant ou groupe de soumissionnaires gagnants. Si un seul groupe de prix de base satisfait à la première et à la deuxième condition, c'est ce groupe qui détermine les prix de base pour l'étape de l'attribution.
  • c) Troisième condition : Si plusieurs groupes de prix de base satisfont à la première et à la deuxième condition, le ou les groupe(s) de prix de base qui minimise(nt) la somme des prix de base pour toutes les soumissions gagnantes est(sont) choisi(s). Si un seul groupe de prix de base satisfait aux trois conditions, c'est ce groupe qui détermine les prix de base pour l'étape de l'attribution.
  • d) Quatrième condition : Si plus d'un groupe de prix de base satisfont aux trois premières conditions, le groupe de prix de base qui réduit la somme pondérée des carrés des différences entre les prix de base et les prix Vickrey est sélectionné. La pondération est basée sur le prix de l'ensemble du soumissionnaire évalué aux prix de départ. Cette méthode pour choisir entre des groupes de prix de base qui minimisent la somme des prix de base concernant toutes les soumissions gagnantes s'appelle la « méthode Vickrey de calcul du deuxième prix ».

3.1 Définitions préliminaires

16. Soit \(b_{j}^*=b_{j}(S_{j})\), signifiant le montant de la soumission gagnante du soumissionnaire gagnant \(j \in W(N,b)\).

17. Soit \( p = p(N,b)\), signifiant un vecteur de prix génériques pour les soumissionnaires gagnants dans \(W(N,b)\), où \(N\) est l'ensemble complet des soumissionnaires \(b\) l'ensemble initial des soumissions présentées. De plus, soit l'équation \[ \left \vert p \right \vert = \sum_{j \in W(N,b)} p_{j}(N,b), \] servant à calculer la somme des prix pour les gagnants dans \(W(N,b)\).

18. Les prix Vickrey retranchent de chaque soumission gagnante la somme que le soumissionnaire gagnant contribue à la valeur totale de la combinaison gagnante. Pour un soumissionnaire gagnant donné, cette contribution est déterminée au moyen d'une détermination hypothétique des gagnants après exclusion du soumissionnaire. La différence entre la valeur totale de la combinaison gagnante incluant le soumissionnaire \(j\) et la valeur totale de la combinaison gagnante excluant toutes les soumissions du soumissionnaire \(j\) correspond à la contribution du soumissionnaire \(j\) à la valeur totale de la combinaison gagnante, et c'est cette contribution qui sert à déterminer la valeur à retrancher pour établir les prix Vickrey.

19. Chaque soumissionnaire gagnant \(j\) bénéficie de la réduction suivante sur la valeur de ses soumissions gagnantes :

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

20. Les prix Vickrey \(p^0\) se calculent en appliquant la réduction à la valeur des soumissions gagnantes de chaque soumissionnaire gagnant, comme suit :

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

où :

  • \(d_{j}\) est la réduction que le soumissionnaire gagnant \(j\) reçoit de sa soumission gagnante;
  • \(wd(N \setminus \{j\},b)\) est la valeur de la combinaison gagnante une fois que toutes les soumissions du soumissionnaire \(j\) ont été exclues.

21. Le prix Vickrey pour chaque soumissionnaire gagnant \(j\) peut également se calculer comme suit. Premièrement, on soustrait la soumission gagnante du soumissionnaire \(j\) de la valeur de la combinaison d'ensembles gagnante, c'est-à-dire \((wd(N,b) − b_{j}^*)\). Ensuite, on recalcule la combinaison d'ensembles gagnante dans la situation hypothétique où toutes les soumissions du soumissionnaire \(j\) ont été exclues, comme si le soumissionnaire \(j\) n'avait pas participé aux enchères, c'est-à-dire \(wd(N\setminus\{j\},b)\). Le prix Vickrey pour le soumissionnaire \(j\) se définit comme la valeur maximum du montant de la soumission une fois que les soumissions du soumissionnaire \(j\) ont été retirées, moins la valeur des soumissions gagnantes à l'étape de l'attribution pour tous les soumissionnaires autres que le soumissionnaire \(j\). Cette méthode de calcul équivaut à celle décrite dans les équations (6) et (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 Ajustement sélectif des prix de base

22. Un paiement en sus du prix Vickrey est parfois exigé dû à des complémentarités, et ce, pour satisfaire à la seconde condition selon laquelle les prix de base doivent être suffisamment élevés pour qu'il n'y ait pas d'autres soumissionnaires ou d'autres groupes de soumissionnaires qui soient prêts à payer davantage que l'un des soumissionnaires ou des groupes de soumissionnaires gagnants. On appelle coalition de blocage tout soumissionnaire ou groupe de soumissionnaires qui est prêt à payer davantage que tout soumissionnaire ou groupes de soumissionnaires gagnants. Le groupe qui est prêt à payer le montant le plus élevé constitue la première coalition de blocage. Pour dissoudre une coalition de blocage, il suffit d'augmenter les prix de base de sorte que la somme totale payée par les soumissionnaires gagnants ne soit pas inférieure à la somme totale que la coalition de blocage est prête à payer. Si d'autres coalitions de blocage se forment une fois que les prix de base ont été ajustés pour dissoudre la première coalition, les autres coalitions qui pourraient surgir sont dissoutes à tour de rôle du fait de l'augmentation des prix de base jusqu'à ce qu'il n'y ait plus de soumissionnaires individuels ou de groupes de soumissionnaires qui soient prêts à renchérir.

23. Le calcul des prix de base peut se faire itérativement grâce à un ajustement sélectif. L'ajustement sélectif consiste à prendre les prix Vickrey comme point de départ et à ajuster itérativement les prix de base jusqu'à ce qu'il n'y ait plus de soumissionnaires ou de groupes de soumissionnaires qui soient prêts à payer davantage que le groupe de prix de base existant. Pour cela, on regroupe les contraintes de prix qui s'appliquent à chaque coalition de blocage et on cherche à respecter les contraintes de prix en sélectionnant les prix de base qui réduisent l'écart pondéré entre les prix de départ et les prix Vickrey.

24. Soit \(p^n\), désignant le vecteur de prix défini pour l'itération \(n\) de l'ajustement sélectif des prix de base. Les prix Vickrey sont représentés par \(p^0\) dans cet algorithme. Étant donné le vecteur de prix \(p^n\) de l'itération \(n\) et l'ensemble initial des soumissions déposées \(b\), il est possible d'obtenir comme suit un ensemble réduit de soumissions \(b^n\), en soustrayant le surplus existant du soumissionnaire \(j\) de chaque offre \(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. Lorsqu'un soumissionnaire \(j\) est perdant, mais qu'il est toujours prêt à payer la valeur totale de ses soumissions (puisque le surplus de tout soumissionnaire perdant est nul) afin de faire partie d'une coalition de blocage, alors : \(b_{j}^n(S)=b_{j}(S)\) pour tous les \(S\). Un soumissionnaire \(j\) gagnant, quant à lui, ne paiera sa soumission gagnante \(S_{j}\) ni plus cher ni moins cher que son prix de l'itération \(n\) pour faire partie de la coalition de blocage \(b_{j}^n(S_{j})=p_{j}^n\).

26. Soit \(C^n = W(N,b^n)\), le groupe des gagnants dans la détermination hypothétique des gagnants comportant les soumissionnaires de l'ensemble \(N\) et un ensemble réduit de soumissions \(b^n\). Ces gagnants forment la coalition de blocage de l'itération \(n\). Parmi toutes les coalitions de blocage possibles de l'itération \(n\), \(C^n\) est celle qui a la plus haute valeur.

27. Soit \(\beta^n\), un vecteur indexé des coalitions de blocage pour lequel la valeur de chaque coalition est la somme des prix de base requis pour dissoudre la coalition :

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

où :

  • \(wd(C^n,b)\) est la valeur totale que les soumissionnaires de la coalition de blocage \(C^n\) peuvent atteindre sans faire appel à des soumissionnaires n'appartenant pas à la coalition, ou à \(N\setminus C^n\); \[\sum_{j\epsilon C^n}b_{j}^*\]
  • est la somme des soumissions gagnantes des premiers soumissionnaires gagnants de la coalition \(C^n\).

28. Soit \(A^n\), une matrice dans laquelle les colonnes sont indexées en fonction des coalitions de blocage et où chaque colonne \(a_{C^n}\) est le vecteur caractéristique de l'ensemble complémentaire des gagnants :

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

où :

  • \( a_{C^n,j}=0\) indique qu'un soumissionnaire donné \(j\) fait partie de la coalition \(C^n\);
  • \( a_{C^n,j}=1\) indique qu'un soumissionnaire donné \(j\) devrait faire ajuster son prix de base pour dissoudre la coalition.

29. Trouvons \(\mu^n\), le cumul minimum des prix de base requis pour dissoudre toutes les coalitions à l'itération \(n\) en optimisant le vecteur de prix \(p\) comme suit :

\[ \mu^n = min \left \vert p \right \vert \]
 
\[ \mbox { à condition que }\;\;\; pA^n \geq \beta^n \]
\[\text{(15)}\]
\[ p^0 \leq p \leq b^* \]
 

30. La première contrainte \(pA^n \geq \beta^n \) exige que toutes les coalitions soient dissoutes, c'est-à-dire que le cumul des prix de base payés par les soumissionnaires gagnants soit au moins égal à la somme des prix de base requise pour dissoudre les coalitions. La seconde contrainte \( p^0 \leq p \leq b^*\) exige que le prix payé par chaque soumissionnaire gagnant ne dépasse pas le prix soumissionné pour l'ensemble gagnant et ne soit pas inférieur au prix Vickrey.

31. Il reste maintenant à mettre à jour les prix que devront payer les soumissionnaires gagnants pour que leur somme soit égale à \(\mu^n\) (troisième condition), de manière que le prix payé collectivement par les soumissionnaires gagnants soit assez élevé pour qu'aucun autre soumissionnaire ou groupe de soumissionnaires ne veuille renchérir.

32. S'il y a plus d'un groupe de prix de base dont la somme est égale à \(\mu^n\), l'algorithme sélectionne le groupe de prix de base qui réduit la somme pondérée des carrés des écarts entre les prix de base et les prix Vickrey. La pondération est basée sur le prix de l'ensemble du soumissionnaire qui a été évalué aux prix de départ (quatrième condition).

33. Soit \(o(S_{j})\), le prix de l'ensemble de chaque soumissionnaire gagnant évalué aux prix de départ. :

34. Trouvons ensuite les prix révisés \(p^{n+1}\) comme solution optimale de :

\[\min \sum_{j \notin C^n} \frac {( p^{n+1}_j − p^0_{j})^2} {o(S_{j})}\]
\[\text{(16)}\]
\[ \text{à condition que }\;\;\; 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. Ce problème quadratique réduit la somme pondérée des carrés des écarts entre les prix de base révisés \(p^{n+1}\), où les prix révisés sont ceux dont la somme est égale à \(\mu^n\), et les prix Vickrey \(p^0\)(quatrième condition). La première contrainte \(p^{n+1}A^n \geq \beta^n \) exige que chacune des coalitions soit dissoute, c'est-à-dire que les prix de base totaux payés par les soumissionnaires gagnants soient au moins égaux à la somme des prix de base requis pour dissoudre les coalitions. La seconde contrainte \( p^0 \leq p^{n+1} \leq b^*\) exige qu'aucun soumissionnaire ne paie au-delà de la valeur de sa soumission gagnante et qu'il paie au moins la valeur de son prix Vickrey. La troisième contrainte \( \left \vert p^{n+1} \right \vert = \mu^n\) garantit que les prix ne seront ni plus ni moins élevés que la somme minimale des prix de base permettant de dissoudre toutes les coalitions.

36. Soit \(p^*=p^n\), où \(n\) est la plus petite valeur de sorte que la valeur de la coalition ne dépasse pas la somme des prix de base : \(wd(N,b^n) \leq \left \vert p^n \right \vert \) . À l'itération \(p^*\), il n'y aura plus de coalitions de blocage.

4. Détermination des soumissions retenues à la fin de chaque ronde d'assignation

37. Les licences génériques sont des blocs de spectre qui sont de valeur comparable et se ressemblent suffisamment pour être offertes dans une seule catégorie. À chaque ronde d'assignation, les soumissionnaires gagnants font des soumissions additionnelles, exprimant ainsi leurs préférences pour certaines fréquences particulières parmi les licences génériques qu'ils ont gagnées.

38. Un algorithme servira à déterminer la combinaison d'assignations particulières de licences qui produit la valeur de soumission la plus élevée. En cas d'égalité, c'est à-dire si au moins deux assignations données produisent la même valeur totale, l'égalité sera brisée en choisissant l'assignation qui maximise la somme des produits formant l'admissibilité totale et le nombre aléatoire associé à chaque soumission gagnante.

39. Le mode de détermination des gagnants des rondes d'assignation diffère de celui de l'étape de l'attribution car chaque soumissionnaire doit gagner un seul ensemble. De plus, tous les produits sont uniques en raison de la nature du problème d'assignation.

\[ wd'(N,b)=\max\sum_{j \in N} \sum_{S \subseteq M}b_{j}(S)\cdot x_{j}(S) \]
\[\text{(20)}\]
\[ \text {à condition que} \;\; \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 {tel que} \;\;b_{j}(S) \text { est défini }\]
\[\text{(23)}\]

(Le signe d'égalité à l'équation (21) est la seule différence entre la formule de \(wd\) et celle de \(wd'\).)

5. Détermination des prix à l'étape de l'assignation

40. Les prix de base à l'étape de l'attribution sont simplement \(\hat{p}^*\), où \(N\) est le groupe complet des soumissionnaires \(\hat{N}\) , \(M\) est l'offre de licences, \(o\) est le vecteur des prix de départ, et \(b\) est l'ensemble des soumissions à l'étape de l'attribution \(\hat{b}\).

41. À l'étape de l'assignation, pour respecter la règle selon laquelle chaque soumissionnaire ne gagne précisément qu'un seul ensemble, la réduction Vickrey est calculée en mettant à zéro toutes les soumissions \(j\) du soumissionnaire plutôt que de les supprimer :

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

où :

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

42. Comme la modification à la détermination des gagnants des rondes d'assignation exige que chaque soumissionnaire ne gagne qu'un seul ensemble, les modifications suivantes sont nécessaires afin d'effectuer la détermination des prix lors de l'étape de l'assignation : les prix d'assignation deviennent \(\hat{p}'^*\) lorsque \(N\) est le sous-groupe des soumissionnaires auxquels des licences ont été assignées pendant la ronde, \(M\) est l'offre des licences assignées, et \(b\) est l'ensemble des soumissions à l'étape de l'assignation.

43. Comme à l'étape de l'attribution, les prix d'assignation doivent respecter des conditions similaires à celles énoncées au paragraphe 15 ci-dessus en notant que pour la première condition, les prix d'assignation doivent être supérieurs ou égaux à zéro, et ne doivent pas dépasser le montant en dollars de la soumission gagnante à l'étape de l'assignation.

44. Les prix finaux lors des ECC correspondent à la somme des prix de base des licences génériques établis à l'étape de l'attribution, plus les prix des fréquences particulières établis à l'étape de l'assignation.