مسابقة دكتوراه 2022 — Université Abderrahmane Mira - Béjaïa — الموضوع 02

1.

Le gain total est $\sum_{k=1}^3 z_k(x_k) = 8(x_1+x_2+x_3) - (x_1^2 + 2x_2^2 + 3x_3^2)$, sous la contrainte d'utilisation totale et de positivité :

$(P):\quad \max\ f(x) = 8(x_1+x_2+x_3) - (x_1^2+2x_2^2+3x_3^2)\quad \text{s.c.}\quad x_1+x_2+x_3 = d,\ x_k\ge 0.$

2.

Oui, $(P)$ est quadratique : $f(x) = c^\top x - x^\top D x$ avec

$c = (8,8,8)^\top,\qquad D = \operatorname{diag}(1,2,3),\qquad \nabla^2 f = -2D = \operatorname{diag}(-2,-4,-6).$

La matrice hessienne est constante, ce qui caractérise un programme quadratique.

3.

La hessienne $\nabla^2 f = \operatorname{diag}(-2,-4,-6)$ est définie négative, donc $f$ est strictement concave. On maximise une fonction concave sur un ensemble convexe (hyperplan $\sum x_k = d$ intersecté avec l'orthant positif). C'est donc un problème convexe (maximisation concave).

$\boxed{\ (P)\ \text{est convexe : } f\ \text{strictement concave, domaine convexe}\ }$

4.

Lagrangien avec multiplicateur $\lambda$ (égalité) et $\mu_k\ge 0$ (contraintes $x_k\ge 0$) :

$\frac{\partial f}{\partial x_k} - \lambda + \mu_k = 0,\qquad 8 - 2k x_k - \lambda + \mu_k = 0,$

$\mu_k \ge 0,\quad x_k\ge 0,\quad \mu_k x_k = 0\ (k=1,2,3),\qquad x_1+x_2+x_3 = d.$

5.

Cherchons la solution intérieure $x_k>0$, donc $\mu_k = 0$ et $8 - 2k x_k - \lambda = 0$, soit $x_k = \dfrac{8-\lambda}{2k}$. La contrainte donne

$\frac{8-\lambda}{2}\left(1 + \tfrac12 + \tfrac13\right) = d\ \Longrightarrow\ \frac{8-\lambda}{2}\cdot\frac{11}{6} = d\ \Longrightarrow\ 8-\lambda = \frac{12d}{11}.$

D'où $\lambda = 8 - \dfrac{12d}{11}$ et

$\boxed{\ x^0 = \left(\tfrac{6d}{11},\ \tfrac{3d}{11},\ \tfrac{2d}{11}\right),\qquad f(x^0) = 8d - \tfrac{6d^2}{11}\ }$

Ces valeurs sont positives pour $d>0$ et $\mu_k=0\ge0$ : les conditions KKT sont satisfaites.

6.

$f$ étant strictement concave et le domaine convexe, tout point KKT est l'unique maximum global. Donc $x^0$ est le maximum global (et unique).

$\boxed{\ x^0\ \text{est l'optimum global unique de } (P)\ }$

Partie 2.

Les poids des variables $x_1, x_3, x_4$ dans la contrainte sont respectivement $3, 3, 4$. La somme des deux plus petits vaut $3+3 = 6 > 5$ : deux quelconques de ces trois variables mises à $1$ dépassent déjà la capacité $5$. Donc dans toute solution admissible $x\in\{0,1\}^4$, au plus une des variables $x_1,x_3,x_4$ peut valoir $1$. Formellement, $\{x_1,x_3,x_4\}$ forme une couverture minimale (tout sous-ensemble de taille $2$ viole la contrainte), d'où l'inégalité de couverture

$\boxed{\ x_1 + x_3 + x_4 \le 1\ \text{(valide pour } (Q))\ }$

Partie 1 — 1.

Le jeu $\Gamma$ est un jeu statique à information complète à la Bertrand (prix) différencié :

$\Gamma = \big(\{1,2\},\ (S_i)_{i},\ (\pi_i)_i\big),\quad S_i = [0,+\infty)\ (\text{prix } p_i\ge 0),$

$\pi_i(p_i,p_j) = p_i\,q_i = p_i\,(100 - 2p_i + p_j).$

Caractéristiques : 2 joueurs, stratégies continues (prix), jeu non coopératif à coups simultanés, information complète, fonctions de gain (profits) $\pi_i$.

Partie 1 — 2.

Le concept de solution est l'équilibre de Nash : un profil $(p_1^*,p_2^*)$ tel que pour chaque $i$, $p_i^*$ maximise $\pi_i(p_i,p_j^*)$ étant donné $p_j^*$ :

$\pi_i(p_i^*,p_j^*)\ge \pi_i(p_i,p_j^*)\quad \forall p_i\ge 0,\ \forall i.$

Partie 1 — 3.

Condition du premier ordre (fonction de meilleure réponse) :

$\frac{\partial \pi_i}{\partial p_i} = 100 - 4p_i + p_j = 0\ \Longrightarrow\ p_i = \frac{100 + p_j}{4}.$

Par symétrie $p_1^* = p_2^* = p^*$, d'où $4p^* = 100 + p^*$, soit $p^* = \tfrac{100}{3}$. Alors $q_i = 100 - 2\cdot\tfrac{100}{3} + \tfrac{100}{3} = \tfrac{200}{3}$ et

$\boxed{\ p^* = \tfrac{100}{3}\approx 33{,}33,\qquad \pi^N = \tfrac{100}{3}\cdot\tfrac{200}{3} = \tfrac{20000}{9}\approx 2222{,}2\ }$

Partie 2 — 4.

On maximise $\pi_1+\pi_2$. Par symétrie $p_1=p_2=p$ donne $q_i = 100 - p$ et $\pi_1+\pi_2 = 2p(100-p)$, maximal en

$\frac{d}{dp}\,2p(100-p) = 200 - 4p = 0\ \Longrightarrow\ p^c = 50.$

(On vérifie l'optimum sans symétrie : $\partial(\pi_1+\pi_2)/\partial p_1 = 100 - 4p_1 + 2p_2 = 0$ donne aussi $p=50$.) Alors $q_i = 50$ et

$\boxed{\ p^c = 50,\qquad \pi^c = 50\cdot 50 = 2500\ \text{par entreprise}\ }$

Partie 2 — 5.

Si la firme $j$ reste à $p_j = 50$, la meilleure réponse de $i$ est $p_i = \dfrac{100 + 50}{4} = 37{,}5$. Alors $q_i = 100 - 75 + 50 = 75$ et

$\boxed{\ p_i^{d} = 37{,}5,\qquad \pi_i^{d} = 37{,}5\cdot 75 = 2812{,}5\ }$

(la firme loyale obtient alors $\pi_j = 50\cdot 37{,}5 = 1875$).

Partie 2 — 6.

Comparaison des profits par entreprise :

$\pi^N = 2222{,}2\ \lt\ \pi^c = 2500\ \lt\ \pi^{d} = 2812{,}5.$

La coopération domine la concurrence ($2500 > 2222$), donc collectivement le comportement le plus favorable est de coopérer. Mais chaque firme est individuellement tentée de dévier ($2812{,}5 > 2500$) : c'est une structure de dilemme du prisonnier, et l'unique équilibre du jeu à un coup reste la concurrence.

Partie 3.

Avec la stratégie déclic (« grim trigger »), coopérer à jamais rapporte

$V_C = \frac{\pi^c}{1-\delta} = \frac{2500}{1-\delta}.$

Dévier une fois (gain $\pi^d = 2812{,}5$) puis subir l'équilibre de Nash à jamais rapporte

$V_D = \pi^d + \frac{\delta\,\pi^N}{1-\delta}.$

La coopération est un équilibre parfait en sous-jeu ssi $V_C\ge V_D$, c'est-à-dire $\pi^c - \pi^d \ge \delta(\pi^N - \pi^d)$, soit

$\delta \ge \frac{\pi^d - \pi^c}{\pi^d - \pi^N} = \frac{2812{,}5 - 2500}{2812{,}5 - 2222{,}2} = \frac{625/2}{10625/18} = \frac{9}{17}.$

$\boxed{\ \text{Coopération soutenable en EPSJ}\iff \delta \ge \tfrac{9}{17}\approx 0{,}53\ }$