Gibt es in einem Ressourcenauswahlspiel immer ein reines Nash-Gleichgewicht?

Bezeichne . $[r]\triangleq\{1,2,\ldots,r\}$

Betrachten Sie ein Spiel mit Spielern, , jeder hat Strategien, . $n$ $[n]$ $m$ $[m]$

Jedem Spieler ist eine Auszahlungsfunktion zugeordnet, die nur seine ausgewählte Strategie berücksichtigt, und die Anzahl der Spieler, die dieselbe Strategie ausgewählt haben: $i$

{U.}_{ich} :: [m]] \times [n]] \to [0, 1]]

$U_i:[m]\times[n]\to[0,1]$

Darüber hinaus nimmt die Utility-Funktion in der Anzahl der Spieler, die dieselbe Strategie gewählt haben, monoton ab, dh

\forall ich \in [n]], j \in [m]], k \in [n - - 1]] :: {U.}_{ich} (j, k) \geq {U.}_{ich} (j, k + 1)

$\forall i\in[n],j\in[m],k\in[n-1]:U_i(j,k)\geq U_i(j,k+1)$

Hat dieses Spiel immer ein reines Nash-Gleichgewicht?

Können wir es (rechnerisch) effizient finden?

Beachten Sie, dass im Sonderfall , in dem alle Spieler symmetrisch sind ( ), das Spiel auf ein genaues potenzielles Spiel reduziert wird und daher garantiert ein reines Nash-Gleichgewicht aufweist . $\forall i,j\in[n]: U_i\equiv U_j\equiv U$

Die mögliche Funktion für den symmetrischen Fall wäre bei einem Strategieprofil : $s$

ϕ (s) = \sum_{j \in [m]]} \sum_{k = 1}^{#_{j} (s)} U. (j, k)

$\phi(s) = \sum_{j\in[m]}\sum_{k=1}^{\#_j(s)} U(j,k)$

Wobei die Anzahl der Spieler in Spielstrategie . $\#_j(s)$ $s$ $j$

Antworten:

Ja, es gibt immer ein reines Nash-Gleichgewicht. Sehen:

I Milchtaich (1996). Überlastungsspiele mit spielerspezifischen Auszahlungsfunktionen. Spiele und wirtschaftliches Verhalten 13 (1), 111-124.

Sie interessieren sich für den Sonderfall von Singleton- Überlastungsspielen mit spielerspezifischen Auszahlungsfunktionen.

Und ja, sie können in Polynomzeit berechnet werden. Siehe Folgerung 7 in:

Heiner Ackermann, Heiko Röglin, Berthold Vöcking (2009). Reine Nash-Gleichgewichte in spielerspezifischen und gewichteten Überlastungsspielen. Theoretical Computer Science 410 (17), 1552-1563.

Rahul Savani
quelle

Danke für die Antwort Rahul. Nicht überzeugt von der Härte, da dies ein Sonderfall des Stauspiels und nicht des allgemeinen Spiels ist.

Entschuldigung, ich habe Ihre Definition falsch verstanden. Sie interessieren sich für Singleton- Überlastungsspiele mit spielerspezifischen Auszahlungen. Meine Antwort würde für asymmetrische Netzwerküberlastungsspiele gelten. Ich habe es bearbeitet.

Rahul Savani

Danke Rahul! Wenn Sie interessiert sind, habe ich eine verwandte Frage zu mathoverflow , bei der die Auszahlung an den Spieler von der Anzahl der Spieler abhängt, die dieselbe Strategie wählen. Sie kann jedoch auf 0 fallen, wenn einige Spieler denselben Singleton auswählen. Danke noch einmal.