Spillteori

I kapittel 6 og 7 trakk spillerne etter tur. Mange situasjoner med flere agenter er annerledes: alle velger samtidig, eller uten å se hva de andre har valgt. Et spill på normalform (normal form) har tre deler: spillerne, strategiene hver av dem kan velge, og en utbyttefunksjon som gir hver spiller en nytte for hver kombinasjon av strategier. En ren strategi (pure strategy) er ett bestemt valg, for eksempel «sett høy pris».

Med to spillere skrives spillet som en utbyttematrise (payoff matrix). Radspilleren velger rad, kolonnespilleren velger kolonne, og cellen inneholder et par: (radspillerens nytte, kolonnespillerens nytte). Konvensjonen er alltid rad først. Si den høyt når du leser en celle, for byttes de to tallene, blir nesten alt som kommer etterpå feil.

Kaffebar Nord velger rad og Sør kolonne. Setter Nord høy pris og Sør lav, havner spillet i cellen (2, 7): Nord får 2 og Sør 7. Ingen av dem har et valg som er best uansett. Nord vil helst gjøre det samme som Sør, mens Sør helst vil gjøre det motsatte av Nord.

Resten av kapitlet bygger på tre antakelser: hver spiller velger det som gir høyest forventet nytte, alle vet at de andre gjør det samme, og alle kjenner hele matrisen. Holder ikke antakelsene, kan de stabile utfallene vi finner, være dårlige prognoser for hva som faktisk skjer.

Noen strategier kan strykes uten å vite noe om motspilleren. Strategien $s^{\prime }$ dominerer $s$ strengt når $s^{\prime }$ gir strengt høyere nytte enn $s$ mot hver eneste strategi motspilleren kan velge. Det er streng dominans (strict dominance), og en rasjonell spiller velger aldri en strengt dominert strategi: uansett hva motspilleren gjør, finnes det noe bedre. En strategi som strengt dominerer alle spillerens andre strategier, er en dominant strategi (dominant strategy).

Vet begge at den andre er rasjonell, kan de stryke de dominerte strategiene og se på det mindre spillet som er igjen. Der kan nye strategier ha blitt dominert, fordi motstrategien som reddet dem, er borte. Gjentar du dette til ingenting mer kan strykes, har du gjort iterert eliminering av strengt dominerte strategier (IESDS). Resultatet avhenger ikke av rekkefølgen, og ingen Nash-likevekt forsvinner underveis. Ofte står flere strategier igjen; IESDS løser bare spillet helt når én celle er igjen.

Sammenlign med riktige tall: rader sammenlignes på radspillerens nytte (første tall i cellene), kolonner på kolonnespillerens nytte (andre tall).

To strømselskap velger her mellom tre tariffer. Matrisen er større, men ingen tariff er best i alle situasjoner fra start.

Ofte er en strategi like god som en annen mot noen motstrategier og bedre mot resten. Vi bruker denne definisjonen av svak dominans (weak dominance): $s^{\prime }$ dominerer $s$ svakt når $s^{\prime }$ er minst like god mot alle motspillerens strategier og strengt bedre mot minst én. Kravet om «strengt bedre mot minst én» betyr at to strategier som er helt like, ikke dominerer hverandre.

Iterert eliminering av svakt dominerte strategier, iterert eliminering av svakt dominerte strategier (IEWDS), går fram som IESDS, men har to svakheter. Den kan stryke Nash-likevekter, og resultatet kan avhenge av rekkefølgen. Å stryke én svakt dominert strategi kan nemlig fjerne den eneste motstrategien der en annen strategi var strengt bedre, og dermed redde den andre. Oppgaver om IEWDS må derfor oppgi rekkefølgen. Standarden i dette faget er én strategi om gangen, radspilleren først, og blant flere dominerte strategier den med lavest indeks først.

To bakerier i samme gate velger åpningstid. Begge har valg som bare er svakt dårligere enn et annet.

Hvorfor bruke IEWDS i det hele tatt? Den løser ofte spill der IESDS står fast, og det er sjelden fornuftig å velge en strategi som aldri er bedre og noen ganger verre enn en annen. Men resultatet er et forslag til utfall, ikke en garanti for at det er den eneste rimelige likevekten.

Dominans løser få spill helt. Et svakere, men mer generelt krav er stabilitet. Et beste svar (best response) er en strategi som gir høyest nytte mot en gitt strategi hos motspilleren. En Nash-likevekt (Nash equilibrium) er et strategipar der begge spiller et beste svar på den andre, slik at ingen tjener på å bytte strategi alene. Det er ƒNash-betingelsen:

Ulikheten gjelder for alle strategier $s_i$ og alle spillere $i$, og $s_{-i}^{\ast }$ står for strategiene til alle de andre. Likevekten sier ingenting om at utfallet er godt, bare at ingen angrer alene.

For hånd finner du likevektene ved å markere. Hold kolonnespillerens valg fast, én kolonne om gangen, og marker den høyeste radspiller-nytten i kolonnen. Hold så radspillerens valg fast, én rad om gangen, og marker den høyeste kolonnespiller-nytten i raden. Celler der begge tallene er markert, er rene Nash-likevekter. Et spill kan ha ingen, én eller flere slike celler. Har begge spillerne en dominant strategi, er paret av dem en likevekt i dominante strategier (dominant strategy equilibrium), og den er alltid en Nash-likevekt.

To kaffebarer planlegger ukas kampanje: ingen kampanje, billig kaffe eller billig bakst. Tallene er ukeoverskudd i tusen kroner.

Når et spill har flere rene likevekter, sier teorien ikke hvilken som blir spilt. I kampanjespillet tjener begge kaffebarene på å velge ulike kampanjer, men de må på en eller annen måte bli enige om hvem som tar hva. Slike koordineringsproblemer løses i praksis ofte av vaner, av at spillerne snakker sammen, eller av at én av dem får velge først.

Koden under finner beste svar og rene likevekter i et 2 × 3-spill der én av radspillerens nytter kan endres.

a = 3  # @param -5..10

rader, kolonner = ["Opp", "Ned"], ["Venstre", "Midt", "Høyre"]
# Celle (r, k) = (radspillerens nytte, kolonnespillerens nytte). a er radspillerens nytte i (Ned, Høyre).
u = [[(4, 2), (1, 3), (2, 1)],
     [(3, 1), (2, 2), (a, 4)]]
beste_rad = {k: [r for r in range(2) if u[r][k][0] == max(u[x][k][0] for x in range(2))] for k in range(3)}
beste_kol = {r: [k for k in range(3) if u[r][k][1] == max(u[r][y][1] for y in range(3))] for r in range(2)}
nash = [(r, k) for r in range(2) for k in range(3) if r in beste_rad[k] and k in beste_kol[r]]

print("Beste svar for rad: " + ", ".join(f"mot {kolonner[k]} {'/'.join(rader[r] for r in v)}" for k, v in beste_rad.items()))
print("Beste svar for kolonne: " + ", ".join(f"mot {rader[r]} {'/'.join(kolonner[k] for k in v)}" for r, v in beste_kol.items()))
print("Rene Nash-likevekter: " + (", ".join(f"({rader[r]}, {kolonner[k]})" for r, k in nash) or "ingen"))
print("Velferd i likevekten: " + (", ".join(str(sum(u[r][k])) for r, k in nash) or "ingen likevekt"))

Noen spill har ingen ren likevekt. På et straffespark vil skytteren skyte dit keeperen ikke kaster seg, og keeperen vil kaste seg dit skytteren skyter. Er valget forutsigbart, kan det utnyttes. Løsningen er en blandet strategi (mixed strategy): en sannsynlighetsfordeling over de rene strategiene. Nash' teorem (Nash's theorem) sier at hvert spill med endelig mange spillere og strategier har minst én Nash-likevekt når blandede strategier er tillatt.

I et 2 × 2-spill finner du den blandede likevekten med indifferensprinsippet. Blander kolonnespilleren, må hun være indifferent mellom kolonnene; ellers ville hun spilt den beste rent. Det er altså radspillerens blanding $p$ som gjør kolonnespilleren indifferent, og kolonnespillerens blanding $q$ som gjør radspilleren indifferent. Med radspillerens nytter $a,b$ i rad 1 og $c,d$ i rad 2 gir det ƒindifferensbetingelsen:

For $p$ sammenligner du kolonnene, med kolonnespillerens nytter $a^{\prime },b^{\prime }$ i rad 1 og $c^{\prime },d^{\prime }$ i rad 2:

Forventet utbytte regnes ut med ƒforventet utbytte:

I likevekten gir begge radene samme forventning, så du kan sette $q$ inn i den ene siden av indifferenslikningen.

Tallene i figuren er skytterens sjanse for mål i tideler, og keeperen får det motsatte.

En blandet strategi kan tolkes på to måter. Enten trekker spilleren faktisk lodd før hvert valg, som en keeper som med vilje varierer side. Eller blandingen beskriver en hel gruppe spillere, der en andel alltid gjør det ene og resten alltid det andre. Regningen er den samme.

Koden under regner ut likevekten i et nullsumspill der to av radspillerens nytter kan endres.

from fractions import Fraction

a = 3  # @param -5..5
d = 2  # @param -5..5

# Nullsumspill: radspillerens nytte står i matrisen, kolonnespilleren får det motsatte.
u = [[a, -1],
     [1, d]]
nevner = u[0][0] - u[0][1] - u[1][0] + u[1][1]
p = Fraction(u[1][1] - u[1][0], nevner) if nevner != 0 else None  # P(rad 1): gjør kolonnespilleren indifferent
q = Fraction(u[1][1] - u[0][1], nevner) if nevner != 0 else None  # P(kolonne 1): gjør radspilleren indifferent

if p is None:
    print("Radspillerens blanding p: ingen indre blandet likevekt (nevneren er 0)")
elif not (0 < p < 1 and 0 < q < 1):
    print(f"Radspillerens blanding p: ingen indre blandet likevekt (likningene gir p = {p}, q = {q})")
else:
    print(f"Radspillerens blanding p: {p}")
    print(f"Kolonnespillerens blanding q: {q}")
    print(f"Forventet utbytte for rad: {q * u[0][0] + (1 - q) * u[0][1]}")

En likevekt er stabil, men er den bra? To mål vurderer utfallet utenfra. Et utfall er Pareto-optimal (Pareto optimal) når ingen andre utfall gjør noen bedre stilt uten å gjøre noen dårligere stilt. Utfallet $s$ Pareto-dominerer $s^{\prime }$ når ƒPareto-dominans holder:

Sosial velferd (social welfare) er summen av nyttene, $W(s)={\sum }_i{u}_i(s)$ (ƒsosial velferd). Utfallet med høyest velferd er alltid Pareto-optimalt, men ikke omvendt.

Fangens dilemma (prisoner's dilemma) viser at likevekt og effektivitet kan trekke hver sin vei. Hver spiller kan samarbeide eller svikte, og nyttene oppfyller ƒfangens dilemma: $T>R>P>S$. Her er $T$ fristelsen (svikte mens den andre samarbeider), $R$ belønningen for felles samarbeid, $P$ straffen for felles svik og $S$ nytten for den som blir sviktet. Svik er dominant for begge, så felles svik er eneste likevekt, selv om felles samarbeid gir begge mer. I figuren kan to naboer bidra på vegdugnaden eller snylte på den andres innsats.

I et nullsumspill er den enes gevinst den andres tap. En maximin-strategi (maximin) velger strategien som gir best resultat i verste fall. I rene strategier kan radspillerens maximin-verdi være lavere enn minimax-verdien kolonnespilleren kan holde henne på. Med blandede strategier er de to like, og den felles verdien er spillets verdi.

I et gjentatt spill (repeated game) spilles samme spill mange ganger, og strategier som lik for lik (samarbeid først, gjør så det motspilleren gjorde sist) kan holde samarbeidet oppe. Vet begge nøyaktig når siste runde er, faller det sammen: i siste runde er det ingen framtid å beskytte, så begge svikter, og da gjelder det samme i nest siste runde. Baklengs induksjon gir svik i alle runder.

Koden under spiller et fangens dilemma med andre tall enn dugnaden over, mange runder og med tre enkle strategier.

runder = 10  # @param 1..50

R, T, P, S = 4, 6, 1, 0  # begge bidrar, fristelse, begge snylter, lurt (T > R > P > S)
utbytte = {("B", "B"): (R, R), ("B", "S"): (S, T), ("S", "B"): (T, S), ("S", "S"): (P, P)}

def spill(strategi1, strategi2):
    sum1 = sum2 = 0
    forrige1 = forrige2 = "B"  # ingen har sviktet før første runde
    for runde in range(1, runder + 1):
        trekk1, trekk2 = strategi1(forrige2, runde), strategi2(forrige1, runde)
        x, y = utbytte[(trekk1, trekk2)]
        sum1, sum2 = sum1 + x, sum2 + y
        forrige1, forrige2 = trekk1, trekk2
    return sum1, sum2

lik_for_lik = lambda motpart_forrige, runde: motpart_forrige  # gjør det motparten gjorde sist
alltid_svik = lambda motpart_forrige, runde: "S"
svik_til_slutt = lambda motpart_forrige, runde: "S" if runde == runder else motpart_forrige

x, y = spill(lik_for_lik, lik_for_lik)
print(f"Lik for lik mot lik for lik: {x} og {y} poeng")
x, y = spill(alltid_svik, lik_for_lik)
print(f"Alltid svik mot lik for lik: {x} og {y} poeng")
x, y = spill(svik_til_slutt, lik_for_lik)
print(f"Lik for lik, men svik i siste runde, mot lik for lik: {x} og {y} poeng")