Własność podmodularności w grach z zatorami?

Niech będzie -players i -elements gra przekrwienie . $G$ $n$ $m$

Dla równowagi oznaczamy $e$

S U P (e) ≜< s u p_{1} (e), s u p_{2} (e), \dots, s u p_{n} (e) >

$SUP(e)\triangleq<sup_1(e),sup_2(e),\ldots, sup_n(e)>$

Gdzie $sup_i(e)$ zawiera wsparcie $i$ „th gracz gry $e$ (zbiór strategii $i$ grać z dodatnim prawdopodobieństwem).

Mówimy również, że $SUP(e)\subseteq SUP(e')$ iff $\forall i\in[n]: sup_i(e)\subseteq sup_i(e')$ , to znaczy, że każdy gracz w $e$ losuje swoją akcję na podzbiorze działań, które mógł wybrać grając $e'$ .

Ostatnią definicją jest koszt społeczny, $SC(e)$ który jest definiowany jako suma kosztów dla graczy.

Niech dwa (ewentualnie mieszane) equilibriums dla . $e,e'$ $G$

Czy oznacza ?
$S U P (e) \subseteq S U P (e^{'})$ $SUP(e)\subseteq SUP(e')$ $S C (e) \leq S C (e^{'})$ $SC(e) \leq SC(e')$

game-theory nash-equilibrium congestion-games

— RB
źródło

Czy miałeś na myśli ? Intuicyjnie można by pomyśleć, że skoncentrowanie gry równowagi wokół mniejszej liczby elementów doprowadziłoby do większego przeciążenia każdego elementu.

S C (e) \geq S C (e^{'})

$SC(e)\geq SC(e')$

— Wszechobecny

@ Wszechobecny - myślę, że jest zupełnie odwrotnie. Każdy gracz koncentruje się na mniejszej liczbie elementów, co oznacza, że mniej graczy wykorzystuje każdy element. Fakt, że każdy gracz wybiera teraz podzbiór elementów i jest to nadal równowaga , może oznaczać, że społeczeństwo zyskuje na tym (w przeciwnym razie wydaje się, że gracz prawdopodobnie wróci do korzystania z większej liczby elementów).

— RB

Zależy od funkcji kosztu (opóźnienie). Gra w pytaniu jest niepełna, ponieważ wypłaty (koszty) są nieobecne.

— Sander Heinsalu

Twierdzenie to na ogół nie jest prawdziwe . Można wykazać, że jest to prawdą w przypadku i . Tutaj pokazuję przeciwny przykład, gdy i . $n=2$ $m=2$ $n=3$ $m=2$

Krótki komentarz. Możemy ponownie sformułować pytanie słowem: czy równowaga Nasha, która jest „bardziej losowa” ( versus ), jest mniej wydajna? Intuicyjnie, gdy rozgrywane są bardziej mieszane strategie, osiągnięty wynik jest bardziej losowy i może być bardzo nieefektywny z powodu braku koordynacji między agentami. Kiedy agenci grają w czyste strategie, możemy myśleć, że zmniejszamy problem koordynacji, biorąc pod uwagę, że rozważamy równowagę Nasha. Ta intuicja nie ma zastosowania, jeśli twierdzenie jest fałszywe, co pokażę, gdy i . $e'$ $e$ $n=3$ $m=2$

Oznacz i dwie możliwe czynności. Funkcje opóźnienia są zdefiniowane następująco: , , i , , . Oznacza to, że kiedy $A$ $B$ $d_A(1)=5$ $d_A(2)=7$ $d_A(3)=10$ $d_B(1)=1$ $d_B(2)=6$ $d_B(3)=7$ agenci grają (lub ), otrzymują wypłatę (odpowiednio ). Jest to (symetryczna) gra z przeciążeniem, o ile zwiększają się funkcje opóźnienia. $x$ $A$ $B$ $-d_A(x)$ $-d_B(x)$

Określić w równowadze gdy jeden środek odgrywa i 2 odgrywają czynniki . Określić w stanie równowagi, gdy jeden środek zawsze odgrywa , a pozostałe 2 odgrywa z prawdopodobieństwem i z prawdopodobieństwem . Spełnia właściwość . $e$ $A$ $B$ $e'$ $B$ $A$ $\mu=2/3$ $B$ $1-\mu=1/3$ $sup(e) \subseteq sup(e')$

Po pierwsze, pokazujemy, że jest równowagą Nasha. Agent, który gra maksymalizuje wypłatę, biorąc pod uwagę strategię dwóch innych graczy, wybierając jest lepszy niż wybór , (tj. ). Obaj agenci, którzy grają w grają optymalnie, jeśli (tj. ). $e$ $A$ $A$ $B$ $d_A(1)<d_B(3)$ $5<7$ $B$ $d_B(2)<d_A(2)$ $6<7$ $e$ jest zatem równowagą Nasha, a jej koszt społeczny wynosi . $d_A(1)+2d_B(2)=17=\frac{153}{9}$

Po drugie, pokazujemy, że jest równowagą Nasha. Z jednej strony agent, który gra w maksymalizuje swoją wypłatę, gdy dwaj pozostali grają strategią mieszaną, jeśli lepiej gra w niż , $e'$ $B$ $B$ $A$ tj.

(1 - μ)^{2)} {re}_{b} (3)) + 2) μ (1 - μ) {re}_{b} (2)) + μ^{2)} {re}_{b} (1) < (1 - μ)^{2)} {re}_{ZA} (1) + 2) μ (1 - μ) {re}_{ZA} (2)) + μ^{2)} {re}_{ZA} (3))

$(1-\mu)^2d_B(3)+2\mu(1-\mu)d_B(2)+\mu^2d_B(1)<(1-\mu)^2d_A(1)+2\mu(1-\mu)d_A(2)+\mu^2d_A(3)$

, co jest prawdą. Z drugiej strony, każdy z agentów grających strategią mieszaną jest obojętny między wyborem

lub

jeżeli

tj.

\frac{1}{9} 5 + \frac{4}{9} 7 + \frac{4}{9} 10 < \frac{1}{9} 7 + \frac{4}{9} 6 + \frac{4}{9} 1

$\frac{1}{9}5+\frac{4}{9}7+\frac{4}{9}10<\frac{1}{9}7+\frac{4}{9}6+\frac{4}{9}1$

A

$A$

B

$B$

μ {re}_{ZA} (2)) + (1 - μ) {re}_{ZA} (1) = μ {re}_{b} (2)) + (1 - μ) {re}_{b} (3))

$\mu d_A(2)+(1-\mu)d_A(1)=\mu d_B(2)+(1-\mu)d_B(3)$

jest wtedy równowagą Nasha, a jej koszt społeczny wynosi

\frac{19}{3} = \frac{19}{3}

$\frac{19}{3}=\frac{19}{3}$

e^{'}

$e'$

co jest równe

(1 - μ)^{2)} [3) {re}_{b} (3))] + 2) μ (1 - μ) [{re}_{ZA} (1) + 2) {re}_{b} (2))] + μ^{2)} [2) {re}_{ZA} (2)) + {re}_{b} (1)]

$(1-\mu)^2 [3d_B(3)]+2\mu(1-\mu)[d_A(1)+2d_B(2)]+\mu^2[2d_A(2)+d_B(1)]$

\frac{1}{9} 21 + \frac{4}{9} 17 + \frac{4}{9} 15 = \frac{149}{9}

$\frac{1}{9}21+\frac{4}{9}17+\frac{4}{9}15=\frac{149}{9}$

Wreszcie wykazaliśmy, że ale . Równowaga Nasha o mieszanej strategii powoduje niższe koszty społeczne niż ta o czystej strategii. $sup(e) \subseteq sup(e')$ $SC(e) > SC(e')$

— GuiWil
źródło