Potentielt spil

Et potentielt spil  er et spil i normal form , hvor udbetalingsfunktionerne har en særlig egenskab. Når en spiller ændrer sine strategier, er forskellen i hans udbetalinger lig med forskellen i værdierne af den potentielle funktion. Dette gør det muligt at finde Nash-ligevægten som en løsning på et eller andet optimeringsproblem. Potentielle spil blev introduceret af Monderer og Shapley .

Potentiel funktion

Overvej et spil med ansigter i normal form , hvor  er sættet af spillere,  er sættet af strategier og  er udbetalingsfunktionen for den th spiller, . Antag, at der eksisterer en funktion sådan , at for evt

H jeg ( x − jeg , x jeg " ) − H jeg ( x − jeg , x jeg ) = P ( x − jeg , x jeg " ) − P ( x − jeg , x jeg ) {\displaystyle H_{i}(x_{-i},x_{i}')-H_{i}(x_{-i},x_{i})=P(x_{-i},x_{i} ')-P(x_{-i},x_{i})}

for vilkårlige og eventuelle strategier . Hvis en sådan funktion eksisterer, vil vi kalde det potentialet i spillet , og spillet selv - potentialet .

Ligevægt i rene strategier

Lad spillet med ansigter give mulighed for potentiale . Så er Nash-ligevægten i spillet Nash-ligevægten i spillet , og omvendt. Derudover har spillet altid mindst én ligevægt i rene strategier.

Optimal løsning

Eksistensen af ​​potentialet letter i høj grad at finde Nash-ligevægten. Lad os vælge som en situation i rene strategier, der leverer et maksimum på sættet . Så på dette tidspunkt, for enhver , gælder uligheden , især, og for hvert argument, dvs.

P ( x − jeg ∗ , x jeg ) ≤ P ( x ∗ ) , ∀ x jeg . {\displaystyle P(x_{-i}^{*},x_{i})\leq P(x^{*}),\forall x_{i}.}

Dette indebærer, at Nash-ligevægten i spillet og dermed i spillet .

Cournot oligopol

Overvej Cournot-oligopolet, hvor spillernes udbetalingsfunktioner har formen

H jeg ( x en , . . . , x n ) = ( s − b ∑ j = en n x j ) x jeg − c jeg x jeg , jeg = en , . . . , n . {\displaystyle H_{i}(x_{1},...,x_{n})=(pb\sum _{j=1}^{n}x_{j})x_{i}-c_{i }x_{i},\,\,\,i=1,...,n.}

Dette spil er også potentielt. Potentialet er funktionen

P ( x en , . . . , x n ) = ∑ j = en n ( s − c j ) x j − b ( ∑ j = en n x j 2 + ∑ en ≤ jeg < j ≤ n x jeg x j ) . {\displaystyle P(x_{1},...,x_{n})=\sum _{j=1}^{n}(p-c_{j})x_{j}-b\left(\ sum _{j=1}^{n}x_{j}^{2}+\sum _{1\leq i<j\leq n}x_{i}x_{j}\right).}

Funktionens globale maksimum giver Nash-ligevægten:

x jeg = s − c jeg b − n s − ∑ j = en n c j n + en , jeg = en , . . . , n . {\displaystyle x_{i}={\frac {p-c_{i}}{b}}-{\frac {np-\sum _{j=1}^{n}c_{j}}{n+ 1 }},\quad i=1,...,n.}

Routing

Potentielle spil spiller en vigtig rolle i routing -spillene (congestion games), som først blev overvejet af Rosenthal. De har fået deres navn, fordi udbetalingsfunktionen i dem kun afhænger af antallet af spillere, der har valgt de samme strategier. I disse spil er der et potentiale, hvis maksimum giver optimale ruter i et vilkårligt netværk.

Litteratur