Rozdział 1

Gry niekooperacyjne w postaci
strategicznej

1.1

Gry dwuosobowe o sumie zerowej

Większość teorii matematycznych powstała do opisu pewnych konkretnych elementów rze-
czywistości i nie inaczej jest z teorią gier. Ją stworzono dla opisu sytuacji konfliktowych i
sposobów z nich wychodzenia, bądź przez współzawodnictwo, bądź przez kooperację. Oczy-
wiście w założeniu taka teoria powinna dawać odpowiedź na pytanie: jak w danej sytuacji
ludzie postąpią – niestety, jak w każdej teorii, teoria gier ma swoje założenia, w które lu-
dzie, głupi, nie chcą się wpasować. Wniosek z tego taki, że teoria gier nie jest najlepszym
narzędziem przewidywania przyszłości – do tego wciąż najlepsza jest szklana kula – może
nam natomiast dać odpowiedź na pytanie, jak powinni postąpić, jeśli byliby racjonalni. I
od paru słów na temat tego, jak opisać sytuację konfliktu, oraz tego, co będziemy rozumieć
pod pojęciem racjonalności, zaczniemy.

Zastanowimy się nad tym na prostym przykładzie sytuacji, w której mamy dwóch po-

dejmujących decyzje i ich interesy są całkowicie przeciwstawne, więc nie ma mowy o ja-
kiejkolwiek kooperacji, i dzięki temu można w miarę jasno wyekstrahować istotę tego, jakie
działanie możemy rozumieć jako racjonalne. Większość przykładów, które będą się pojawia-
ły na tym wykładzie, będzie jakimś uproszczeniem sytuacji z życia wziętych, ewentualnie
będzie opisywało jakieś zjawiska ekonomiczne – tyle że tam bardzo trudno o sytuacje, w
których interesy poszczególnych stron są całkowicie przeciwstawne – stąd przykład będzie
z dziedziny „gier wojennych”, czyli w praktyce takiej zabawy w żołnierzyki dla dużych
chłopców.

Przykład: Rozważamy następującą sytuację: dwóch dowódców armii przeciwnych państw
– A i B walczy o dwa forty (miasta) na terenie państwa A, każdy ma przy tym do dyspozycji
po dwa oddziały. Zadaniem każdego z dowódców jest rozmieszczenie swoich oddziałów
w poszczególnych fortach (ewent. jako atakujących poszczególne forty) – generał armii
A w ten sposób, żeby jak najwięcej fortów pozostało w rękach państwa A, generał B –
tak, żeby przejąć jak najwięcej fortów. Wiedzą przy tym, że armia posiadająca na danym
odcinku przeważającą siłę na pewno bitwę o dany fort wygra, a jeśli siły są równe, to z
prawdopodobieństwem

1
2

wygra jeden, i z prawdopodobieństwem

1
2

drugi. Jeśli o dany fort

nie toczy się walka, to zostaje on we władaniu państwa A. Taka bardzo prosta gra.

W naturalny sposób możemy to opisać tak, że wypiszemy wszystkie możliwe decyzje

jednego gracza, wszystkie możliwe decyzje drugiego, i w tabelce zapiszemy, co się w danym

1

przypadku dzieje:

20

11

02

20 fort 1 z pr.0.5 zdobyty przez B, fort 2 zostaje w A . . . . . .
11

. . .

. . . . . .

02

. . .

. . . . . .

Teraz co z informacji, które zawarliśmy w tabelce jest istotne - na co będą zwracać

uwagę podejmujący decyzje? Na to, ilu żołnierzy poległo, dostało się do niewoli, który
oddział wygrał, a który przegrał – nie! Istotny jest tylko efekt końcowy, czyli to, ile fortów
zdobyto, i (ewentualnie), czy efekt (pozytywny) operacji jest pewny, czy tylko z pewnym
prawdopodobieństwem. W takim razie po odrzuceniu nadmiarowej informacji dostajemy
taki opis gry:

20

11

02

20 −0.5 −1

−1

11

−1 −1

−1

02

−1 −1 −0.5

I w ten sposób dostaliśmy naturalny opis gry – przy pomocy zbiorów strategii dostęp-

nych poszczególnym graczom oraz macierzy tego, co wypłaca drugi gracz pierwszemu w
zależności od tego, jakie strategie stosują. Ogólnie:

Definicja 1.1 Grą dwuosobową o sumie zerowej nazwiemy trójkę (X, Y, u), gdzie: X –
zbiór strategii gracza 1., Y – zbiór strategii gracza 2., u : X × Y → R – ograniczona funkcja
wypłaty. Gra rozgrywana jest w następujący sposób: gracze niezależnie od siebie wybierają
x ∈ X oraz y ∈ Y , następnie gracz 2. płaci graczowi 1. kwotę u(x, y).

Drugim problemem, który postawiliśmy, było to, co będzie uważane za racjonalne w

grze. Wróćmy do naszego przykładu i zastanówmy się, jak postąpią gracze, i dlaczego?

↓

20

11

02

→ 20 −0.5

−1

−1

lub 11

−1

−1

−1

→ 02

−1

−1

−0.5

Drugi gracz (generał B) wybiera drugą kolumnę, bo wtedy powinien zdobyć jeden fort
niezależnie od tego, co zrobi pierwszy (generał A). Generał A natomiast wybierze jedną z
możliwości przy których może coś zyskać, czyli 1. lub 3. wiersz.

Na tej podstawie możemy zapisać, że za racjonalne będziemy uważać takie zachowania

jak:

1. Maksymalizowanie własnej wypłaty

2. Unikanie sytuacji, w których możemy więcej stracić, jeśli przeciwnik zagra dla nas

niekorzystnie

3. Odrzucanie decyzji, od których mamy lepsze

Zgodnie z tymi zasadami (przynajmniej z dwoma pierwszymi) gracz 1. będzie się starał

wybrać taką strategię, żeby zmaksymalizować swoją wypłatę przy założeniu, że przeciw-
nik będzie się starał mu jak najbardziej zaszkodzić. Podobnie – gracz 2. będzie wybierał
tak, żeby wypłacić graczowi 1. jak najmniej, zakładając, że ten będzie grał w najbardziej
dla siebie korzystny sposób. Patrząc na przykład, widzimy, że gracze właśnie tak robią.
Spróbujmy to teraz sformalizować.

2

Definicja 1.2 Wartość, którą gracz 1. może sobie zapewnić, nazywana wartością dolną
gry, jest równa

v = sup

x∈X

inf

y∈Y

u(x, y).

Wartość najmniejszej straty poniesionej przez gracza 2., którą może sobie zapewnić, nazy-
wana jest wartością górną gry i jest równa

v = inf

y∈Y

sup

x∈X

u(x, y).

Można udowodnić (i my to pokażemy na ćwiczeniach), że v

¬ v. W naszym przykładzie

mamy równość. Ale czy zawsze jest równość? Nie. Np. w grze z X = Y = {1, 2} oraz

u(x, y) =

(

1

gdy x = y

−1 gdy x 6= y

, v = −1, a v = 1.

Czym się zatem różnią dwa podane przez nas przykłady? Otóż w pierwszym z nich

istnieją takie strategie x

∗

∈ X, y

∗

∈ Y , że u(x

∗

, y

∗

) = sup

x∈X

u(x, y

∗

) = inf

y∈Y

u(x

∗

, y). Z

tego wynika, że

v = sup

x∈X

inf

y∈Y

u(x, y) ­ inf

y∈Y

u(x

∗

, y) = sup

x∈X

u(x, y

∗

) ­ inf

y∈Y

sup

x∈X

u(x, y) = v.

Czyli wartość górna jest równa wartości dolnej (i w dodatku równa wypłacie gracza 1., gdy
gracze używają strategii x

∗

i y

∗

).

Definicja 1.3 Jeśli v = v, to tę wspólną wartość nazywamy wartością gry i oznaczamy
przez v. Jeśli dodatkowo istnieją x

∗

∈ X, y

∗

∈ Y , takie że u(x

∗

, y

∗

) = sup

x∈X

u(x, y

∗

) =

inf

y∈Y

u(x

∗

, y), mówimy, że strategie x

∗

i y

∗

są optymalne dla graczy 1. i 2., lub że (x

∗

, y

∗

)

tworzą punkt siodłowy w grze.

Uwaga 1.1 Mówimy o strategiach optymalnych poszczególnych graczy, a nie tylko o opty-
malnej parze strategii, bo strategie optymalne danego gracza można między sobą wymieniać
(ten fakt udowodnimy sobie na ćwiczeniach).

Mamy zatem pewną koncepcję rozwiązania, przynajmniej dla pewnej klasy gier o su-

mie zerowej. Nie dla wszystkich jednak, a chcięlibyśmy mieć jakąś możliwość rozwiązania
możliwie jak najszerszej klasy gier. Na pewien pomysł, jak to zrobić, wpadł von Neumann,
i temu jego pomysłowi poświęcimy resztę wykładu. Ten sposób będzie skuteczny tylko dla
gier ze skończonymi zbiorami akcji graczy. Wypłaty dla takich gier (jak w przykładzie)
można zapisać przy pomocy macierzy, stąd będziemy je nazywać grami macierzowymi.

Gry macierzowe o sumie zerowej
X = {1, 2, . . . , m} – zbiór wierszy macierzy, Y = {1, 2, . . . , n} – zbiór kolumn macierzy
Wypłatę gracza 1. zapisujemy przy pomocy macierzy m × n A = [u(i, j)], i ∈ X, j ∈ Y .

Rozszerzenie mieszane gry macierzowej zdefiniowanej powyżej:

Zbiorami strategii graczy są P (X) i P (Y ) (gdzie P (A) oznacza zbiór rozkładów prawdopo-
dobieństwa o nośniku w zbiorze A). Elementy µ ∈ P (X) oraz σ ∈ P (Y ) będziemy nazywać
strategiami mieszanymi graczy (w odróżnieniu od elementów X i Y , które nazywamy stra-
tegiami czystymi), a wypłatę definiujemy następująco:

u(µ, σ) =

X

i

X

j

u(i, j)µ

i

σ

j

,

gdzie µ

i

to prawdopodobieństwo wylosowania i z rozkładu µ, a σ

j

– prawdopodobieństwo

wylosowania j z σ.

3

Oczywiście praktycznie rozszerzenie mieszane interpretuje się w ten sposób, że gracze,

zamiast wybrać jeden wiersz (jedną kolumnę) macierzy A, wybierają rozkład prawdopodo-
bieństwa, zgodnie z którym losują ten wiersz (tę kolumnę), a jako wypłaty graczy stosujemy
wartość oczekiwaną z ich wypłat.

Jeśli zastosujemy rozszerzenie mieszane, prawdziwe będzie następujące twierdzenie:

Twierdzenie 1.1 (von Neumann, 1928) W każdej grze macierzowej o sumie zerowej ist-
nieje para optymalnych strategii mieszanych tzn. µ

∗

∈ P (X), σ

∗

∈ P (Y ) takie że

u(µ, σ

∗

) ¬ u(µ

∗

, σ

∗

) ¬ u(µ

∗

, σ)

∀µ ∈ P (X), σ ∈ P (Y ).

Dowodu tego twierdzenia nie będę podawał, bo wynika z twierdzenia Nasha, które udo-
wodnimy za tydzień.

Wniosek 1.1 W strategiach mieszanych każda gra macierzowa posiada wartość.

Uwaga 1.2 To że u(µ, σ) = v nie oznacza, że µ i σ są optymalne. Np. w grze z macierzą
wypłat

A =

"

1 0
0 0

#

wybór pierwszej kolumny i drugiego wiersza nie jest optymalny, a wartość gry jest równa
0.

Niestety, trick z rozszerzeniem mieszanym nie działa już dla gier z większymi zbiorami

akcji graczy. Łatwo znaleźć przykład gry z przeliczalnymi zbiorami strategii czystych, dla
której gra nie posiada wartości w strategiach mieszanych.
Przykład: Niech X = Y = {1, 2, . . .} oraz u(x, y) = sgn(x − y). Rozważmy rozszerzenie
mieszane tej gry: P (X) = {µ : µ

i

­ 0,

P

∞
i=1

µ

i

= 1}, P (Y ) = {σ : σ

i

­ 0,

P

∞
i=1

σ

i

= 1},

u(µ, σ) =

P

∞
i=1

P

∞
j=1

u(i, j)µ

i

σ

j

.

W takiej grze v = −1, a v = 1.
Oba te fakty pokazuje się podobnie, więc udowodnię tylko pierwszy. Weźmy dowolne µ ∈
P (X) oraz ε > 0. Niech n

ε

będzie takie, że

P

∞
i=n

ε

+1

µ

i

< ε. Określmy teraz strategię gracza

2. jako σ

µ

= δ[n

ε

].

u(µ, σ

µ

) =

∞

X

i=1

u(i, n

ε

)µ

i

=

n

ε

−1

X

i=1

(−1)µ

i

+

∞

X

i=n

ε

+1

(1)µ

i

= −

∞

X

i=1

µ

i

− µ

n

ε

+ 2

∞

X

i=n

ε

+1

µ

i

< −1 + 2ε

Ponieważ ε było dowolne, dostajemy

inf

σ∈P (Y )

u(µ, σ) ¬ −1,

ale skoro dowolnie było też wybrane µ, to mamy

sup

µ∈P (X)

inf

σ∈P (Y )

u(µ, σ) ¬ −1.

Oczywiście w rzeczywistości mamy równość, bo w grze nie ma wypłat mniejszych niż -1.

4

1.2

Gry o sumie niezerowej

Na ostatnim wykładzie mówiłem o grach opisujących sytuację, gdy mamy dwóch graczy,
których interesy są całkowicie przeciwstawne – taką sytuację opisywały gry macierzowe, czy
ogólniej gry dwuosobowe o sumie zerowej. Dzisiaj uogólniamy tamten model. Zaczniemy
od sytuacji, gdy mamy dwóch graczy, których interesy nie są dokładnie przeciwne.

Gry dwumacierzowe
Niech X = {1, 2, . . . , m} – zbiór strategii (czystych) gracza 1., Y = {1, 2, . . . , n} – zbiór
strategii (czystych) gracza 2. Niech A = [a

ij

]

m×n

– macierz wypłat gracza 1., B = [b

ij

]

m×n

– macierz wypłat gracza 2. (Oczywiście, te wypłaty są czysto subiektywne, i mówią o tym,
co dany gracz myśli o danej sytuacji, a nie muszą oznaczać jakichś konkretnych wypłat,
które jeden z graczy wypłaca drugiemu, lub ktoś trzeci (Pan Bóg) wypłaca graczom). Jak
poprzednio, rozważamy od razu rozszerzenie mieszane takiej gry, czyli dowolny rozkład
prawdopodobieństwa na zbiorze X, µ = (µ

1

, . . . , µ

m

) jest strategią mieszaną gracza 1;

rozkład prawdopodobieństwa na zbiorze Y , σ = (σ

1

, . . . , σ

n

) – strategią mieszaną gracza

2., natomiast wypłatami poszczególnych graczy są odpowiednie wartości oczekiwane:

u

1

(µ, σ) =

X

i

X

j

a

ij

µ

i

σ

j

u

2

(µ, σ) =

X

i

X

j

b

ij

µ

i

σ

j

.

Jak pamiętają Państwo, w grach o sumie zerowej optymalnym zachowaniem było wybra-

nie przez gracza najkorzystniejszej dla siebie strategii przy założeniu, że przeciwnik będzie
grał najgorzej dla nas. Tam uzasadnieniem takiego zachowania było to, że interesy graczy
były dokładnie przeciwne, i wiedzieliśmy, że przeciwnik wybierze to, co dla nas najbardziej
niekorzystne, dlatego że to było jednocześnie najbardziej korzystne dla niego. Tutaj nie
mamy powodu, żeby oczekiwać, że przeciwnik będzie specjalnie działał na naszą niekorzyść
(nie wszyscy gracze są Polakami) – więc naturalnym jest, że każdy z graczy stara się zmak-
symalizować własną wypłatę, przy założeniu, że inni też starają się zmaksymalizować swoje
wypłaty. Autorem takiej koncepcji rozwiązania jest John Nash (stąd nazwa).

Definicja 1.4 Równowagą w sensie Nasha w grze dwumacierzowej nazwiemy taką parę
strategii µ

∗

∈ P (X), σ

∗

∈ P (Y ), że

u

1

(µ

∗

, σ

∗

) ­ u

1

(µ, σ

∗

)

∀µ ∈ P (X)

u

2

(µ

∗

, σ

∗

) ­ u

1

(µ

∗

, σ)

∀σ ∈ P (Y ),

czyli taką, że odstąpienie od równowagi przez pojedynczego gracza nie jest dla niego opła-
calne.

Uwaga 1.3 Oczywiście, jeśli B = −A, czyli u

1

= −u

2

, równowagą Nasha sprowadza się

do punktu siodłowego.

Równowaga w sensie Nasha wydaje się na tyle naturalnym uogólnieniem punktu siodło-

wego, że pewnie duża część z Państwa by ją wymyśliła, i aż narzuca się pytanie, dlaczego
von Neumann jej nie wymyślił. Jedna z możliwych odpowiedzi jest taka, że pewnie wymy-
ślił, ale uznał takie rozwiązanie za wadliwe. I teraz parę słów na temat tego, co w pojęciu
NE nie jest do końca udane.

Rozważmy taki przykład:

Przykład: Mamy dwoje małżonków, którzy właśnie wysłali dzieci do dziadków na wieczór,
i planują spędzić razem wieczór, tylko zastanawiają się jak. Kanoniczna wersja tej historyjki
jest taka , że Pani chce iść na balet, Pan na boks (co prawda niewielu znam facetów, którzy
chcieliby iść na boks, i jeszcze mniej kobiet, które chciałyby na balet, ale będę się trzymał

5

tej wersji). Jeśli każde z nich będzie obstawać przy swoim, nigdzie nie pójdą, w dodatku
pewnie się pokłucą i Pani będzie miała migrenę czy jakąś inną wymówkę, żeby już nic
razem znim nie robić tego wieczoru, a może obrazić się na następnych kilka dni, w drugą
stronę podobnie, w związku z tym taka sytuacja będzie ze wszech miar niekorzystna. W
związku z tym macierze wypłat graczy będą wyglądały tak:

A (Pani) =

"

4 0
0 1

#

B (Pan) =

"

1 0
0 4

#

.

Ta gra ma dwie równowagi w strategiach czystych: (boks,boks) i (balet, balet), oraz jedną
w strategiach mieszanych: µ = (.8, .2), σ = (.2, .8). W tej ostatniej wypłaty garczy są sobie
równe, i równe

4
5

.

Co z tego przykładu wynika?

1. Może istnieć wiele różnych równowag Nasha ze znacząco różnymi wypłatami. Może

się zdarzyć, że jedna równowaga jest bardziej opłacalna dla jednego z graczy, a inna
dla drugiego.

2. Strategii w różnych równowagach nie można między sobą wymieniać. Bez uzgodnie-

nia, która równowaga będzie grana, nie da się racjonalnie wybrać strategii
do gry.

3. Wiedząc, jaki jest zbiór równowag Nasha w danej grze, nie potrafimy po-

wiedzieć, jak będą zachowywać się gracze (nawet przy założeniu, że grają
racjonalnie.)

Kolejny przykład pokaże jeszcze jedną wadę rozwiązania Nasha.

Przykład: (dylemat więźnia – najbardziej znany przykład w teorii gier). Historyjka jest
taka: dwóch więźniów podejrzanych o jakieś przestępstwo, jest przesłuchiwanych w oddziel-
nych pokojach. Są winni, ale każdy z nich zastanawia się, czy się przyznać, czy nie. Jeśli się
przyzna (zrzucając przy okazji większość winy na drugiego), a drugi więzień będzie szedł w
zaparte, pierwszy może liczyć na to, że dostanie wyrok w zawiasach, ale kosztem wspólnika.
Jeśli żaden się nie przyzna, to głównej winy nikt im nie udowodni, ale przymkną ich na
rok za to, co są w stanie im udowodnić bez współpracy żadnego z nich. Jeśli przyznają się
obaj, sąd nie uwerzy w ich skruchę, ale odpowiedzialnością obarczy w tym samym stopniu,
i dostaną wyrok nieco niższy niż ten, który się nie przyzna, a cała wina zostanie jemu
przypisana. Macierze wypłat w tej grze wyglądają tak:

A =

"

−5

0

−10 −1

#

B =

"

−5 −10
0

−1

#

.

Ta gra posiada dokładnie jedną równowagę, i to w strategiach czystych – obaj się przyznają.
Problem w tym, że gdyby obaj odstąpili od równowagi, zyskaliby na tym.

Wniosek:

4. Równowaga nie musi dawać optymalnych wypłat w grze. Jeśli osiągnięcie takich wy-

płat wiąże się z kooperacją, nie będzie to równowaga.

Mimo tych wszystkich wad, równowaga Nasha ma jedną ważną zaletę – zawsze istnieje

(przynajmniej dla gier dwumacierzowych, dla bardziej skomplikowanych bytów niekoniecz-
nie, o czym później). Twierdzenie stwierdzające ten fakt sformułował John Nash.

Twierdzenie 1.2 (Nash, 1950) Każda gra dwumacierzowa posiada równowagę w sensie
Nasha.

6

I znowu, nie będziemy dowodzić tego twierdzenia. Udowodnimy twierdzenie trochę ogól-
niejsze, które za chwilkę podam. Żeby je podać, zdefiniuję ogólnie, co nazywamy grą nie-
kooperacyjną.

Definicja 1.5 n-osobową grą niekooperacyjną nazwiemy Γ = (X

1

, . . . , X

n

, u

1

, . . . , u

n

),

gdzie X

i

– (niepuste) zbiory strategii poszczególnych graczy, u

i

: X

1

× · · · × X

n

→ R

– ograniczone funkcje wypłaty poszczególnych graczy. Gracze wybierają niezależnie od sie-
bie odpowiednio x

1

∈ X

1

, x

2

∈ X

2

, . . . , x

n

∈ X

n

, w wyniku czego gracz k-ty otrzymuje

u

k

(x

1

, . . . , x

n

).

W powyższej definicji nie precyzujemy, czy X

i

są zbiorami strategii czystych, czy miesza-

nych. Pokażemy, że przy pewnych założeniach na te zbiory, oraz na funkcje wypłaty graczy,
gra będzie posiadała strategie należące wąśnie do tych zbiorów.

Definicja 1.6 Równowagą w sensie Nasha w grze Γ zdefiniowanej powyżej nazwiemy układ
strategii x

∗

= (x

∗
1

, . . . , x

∗
n

) takich, że dla każdego gracza i oraz y

i

∈ X

i

mamy

u

i

(x

∗

) ­ u

i

((x

∗
1

, . . . , x

∗
i−1

, y

i

, x

∗
i+1

, . . . , x

∗
n

)).

Oznacza to, jak poprzednio, że pojedynczemu graczowi nie opłaca się odstąpić od równo-
wagi, gdy inni pozostają przy swoich strategiach x

∗
i

.

Prawdziwe będzie następujące twierdzenie:

Twierdzenie 1.3 Załóżmy, że każdy ze zbiorów X

i

jest zwartym wypukłym podzbiorem R

k

.

Załóżmy ponadto, że dla każdego i funkcja u

i

jest ciągła na X

1

× · · · × X

n

oraz jest wklęsła

względem i-tej zmiennej, przy ustalonych pozostałych zmiennych. Wtedy gra Γ, określona
przez zbiory X

i

i funkcje u

i

, posiada równowagę Nasha.

Uwaga 1.4 Dla tych, którzy nie wiedzą – podzbiór przestrzeni metrycznej nazywamy
zwartym, jeśli każdy ciąg elementów tego zbioru posiada podciąg zbieżny. W R

k

zbiór

jest zwarty iff jest domknięty i ograniczony.

Zanim przejdziemy do dowodu tej uogólnionej wersji twierdzenia Nasha, sformułujemy

twierdzenie, które będzie punktem wyjściowym dla tego dowodu.

Twierdzenie 1.4 (Twierdzenie Kakutaniego o punkcie stałym) Niech S będzie zwartym
wypukłym podzbiorem R

k

i niech ψ będzie operatorem przyporządkowującym każdemu s ∈ S

zwarty, wypukły podzbiór S, o wykresie domkniętym, (tzn. jeśli x

n

∈ S, x

n

→ x

0

, y

n

∈

ψ(x

n

), y

n

→ y

0

, to y

0

∈ ψ(x

0

)). Istnieje wtedy takie x

∗

, że x

∗

∈ ψ(x

∗

) (punkt stały

multifunkcji ψ).

Tak naprawde chętnie przeprowadziłbym dowód też tego twierdzenia, żeby wychodzić od
faktów przez Państwa znanych, ale to wymagałoby wprowadzenia ileś dodatkowej teo-
rii (sympleks, współrzędne barycentryczne, podział symplicjalny, twierdzenie Brouwera o
punkcie stałym), w związku z tym twierdzenie Kakutaniego będę traktował jako punkt
wyjściowy, natomiast osobom zainteresowanym dowodem tego twierdzenia polecam prze-
czytanie XX rozdziału „Wstępu do teorii mnogości i topologii” Kuratowskiego [2] (Sympleks
i jego własności). Wtedy poniższy dowód powinien być zrozumiały.

Dowód tw Kakutaniego: Bez straty ogólności możemy założyć, że S jest sympleksem. Niech

{π

µ

} będzie ciągiem rozbić symplicjalnych sympleksu S, takich że średnica każdego sympleksu z

π

µ

nie przekracza δ

µ

i δ

µ

→ 0.

Zdefiniujmy ψ

µ

: S → S w następujący sposób: jeśli x jest wierzchołkiem sympleksu z π

µ

, to za

ψ

µ

(x) przyjmujemy dowolne s ∈ ψ(x), a następnie przedłużamy ψ

µ

liniowo na każdy z sympleksów

7

rozbicia, tzn. jeśli x =

P

k+1
j=1

λ

j

x

j

, λ

i

­ 0,

P

λ

j

= 1, gdzie {x

1

, . . . , x

k+1

} — wierzchołki ustalonego

sympleksu z π

µ

, to ψ

µ

(x) =

P

k+1
j=1

λ

j

ψ

µ

(x

j

). Tak zdefiniowane ψ

µ

jest ciągłe, a zatem na mocy

twierdzenia Brouwera ma punkt stały, który możemy oznaczyć przez x

µ

. Ponadto

x

µ

=

k+1

X

j=1

λ

µ
j

x

µ
j

,

k+1

X

j=1

λ

µ
j

= 1, λ

µ
j

­ 0.

Ze zwartości S można założyć bez straty ogólności, że x

µ
i

, λ

µ
i

, ψ

µ

(x

µ
i

) są zbieżne przy µ → ∞; x

µ
i

oraz x

µ

mają tę samą granicę x

∗

∈ S. Niech lim

µ

λ

µ
j

= λ

∗

j

, a lim

µ

ψ

µ

(x

µ
j

) = η

∗

j

.

Mamy x

µ

= ψ

µ

(x

µ

) =

P

λ

µ
j

ψ

µ

(x

µ
j

). Wtedy x

∗

=

P

λ

∗

j

η

∗

j

, a z własności, które spełnia ψ

wynika, że η

∗

j

∈ ψ(x

∗

) dla każdego j. Stąd x

∗

∈ ψ(x

∗

), bo ψ(x

∗

) jest wypukły, a więc x

∗

jest

szukanym punktem zbioru S.

Dowód tw. Nasha: Idea tego dowodu polega na tym, żeby skonstruować odwzorowanie,
które będzie miało punkt stały wtedy i tylko wtedy, gdy gra posiada równowagę Nasha.
Wtedy sprawdzimy, że to odwzorowanie spełnia założenia twierdzenia Kakutaniego, zatem
ma punkt stały, a gra ma równowagę. Dowód twierdzenia przeprowadzimy dla przypadku,
gdy jest dwóch graczy. Ta zmiana upraszcza jedynie notację, natomiast dowód w ogólnym
przypadku nie jest ani trochę bardziej skomplikowany.

Niech:

B

1

(y) = {a ∈ X

1

: u

1

(a, y) = max

x∈X

1

u

2

(x, y)},

B

2

(x) = {b ∈ X

2

: u

2

(x, b) = max

y∈X

2

u

2

(x, y)}.

Zbiór B

1

(y) interpretujemy jako zbiór najlepszych odpowiedzi 1. gracza na strategię y

drugiego. Podobną interpretację ma zbiór B

2

(x). Jeśli teraz zdefiniujemy sobie multifunkcję

F (x, y) = B

1

(y) × B

2

(x),

to to będzie to odwzorowanie, którego szukamy, bo ewentualny punkt stały takiego odwzo-
rowania (x

∗

, y

∗

) ∈ F (x

∗

, y

∗

) będzie miał taką własność, że x

∗

będzie najlepszą odpowiedzią

na strategię y

∗

i na odwrót, czyli to będzie równowaga Nasha.

Sprawdźmy zatem, czy spełnione są założenia twierdzenia Kakutaniego.

1. Multifunkcja F jest zdefiniowana na zbiorze U = X

1

× X

2

, który jest zwarty. To

można uzasadnić na wiele sposobów (wyciągając podciąg zbieżny z jednej współrzęd-
nej, a potem z niego podciąg zbieżny po drugiej, lub mówiąc, że produkt zbiorów
domkniętych i ograniczonych też ma tę własność). Jest też wypukły jako produkt
zbiorów wypukłych.

2. Zbiory B

1

(y) (B

2

(x)) są zawsze niepuste, bo każda funkcja ciągła na zbiorze zwartym

osiąga swoje supremum na tym zbiorze.

3. Funkcja u

1

(·, y) jest wklęsła dla każdego y ∈ X

2

, stąd jeśli dla ustalonego y osiąga ona

maksimum dla x

1

oraz x

2

, to musi osiągać je także dla kombinacji wypukłych tych

punktów, a to oznacza, że dla każdego y, zbiór B

1

(y) jest wypukły. Podobnie można

uzasadnić wypukłość B

2

(x). Ponieważ iloczyn kartezjański dwóch zbiorów wypukłych

też jest wypukły, to F (x, Y ) jest zbiorem wypukłym dla dowolnych x i y.

4. Weźmy teraz dowolny ciąg {x

i

} elementów zbioru B

1

(y) dla dowolnego ustalonego

y, zbieżny do pewnego x. Ponieważ funkcja u

1

jest ciągła, to x też należy do B

1

(y).

Zatem zbiór ten jest domknięty. Jako podzbiór X

1

jest także ograniczony, a zatem

zwarty. Podobnie pokazujemy, że B

2

(x) są zbiorami zwartymi. Oczywiście F (x, y),

jako iloczyn kartezjański zbiorów zwartych, jest dla dowolnych x i y także zbiorem
zwartym (patrz punkt 1.).

8

5. Domkniętość wykresu. Znowu (bez utraty ogólności) ograniczymy się do jednej współ-

rzędnej. Załóżmy nie wprost, że wykres B

1

nie jest domknięty, czyli istnieje ciąg

{(x

n

, y

n

)} zbieżny do (x, y) taki, że x

n

∈ B

1

(y

n

), ale x 6∈ B

1

(y). Pierwsza z tych

równości oznacza, że

u

1

(a, y

n

) ¬ u

1

(x

n

, y

n

)

∀a ∈ X

1

,

ale ponieważ u

1

jest ciągła, więc prawdziwe musi być także

u

1

(a, y) ¬ u

1

(x, y)

∀a ∈ X

1

,

co jest równoważne x ∈ B

1

(y) – sprzeczność. Czyli wykres naszego odwzorowania jest

domknięty.

A zatem wszystkie założenia twierdzenia Kakutaniego są spełnione, więc gra Γ posiada
równowagę Nasha.

Wniosek 1.2 Twierdzenie Nasha dla gier dwumacierzowych wynika z powyższego twier-
dzenia w następujący sposób:
Niech X

1

= P (W ), gdzie W = {1, . . . , m} – zbiór wierszy macierzy, a X

2

= P (K), gdzie

K = {1, . . . , n} – zbiór kolumn. Dowolny rozkład prawdopodobieństwa µ = (µ

1

, . . . , µ

m

) ∈

P (W ) jest układem m liczb spełniających warunki

P

i

µ

i

= 1, µ

i

­ 0 ∀i. Zbiór takich µ jest

wypukłym i zwartym podzbiorem R

m

. Podobnie w przypadku zbioru strategii mieszanych

2. gracza. Z kolei wypłata gracza 1. (podobnie z wypłatą 2.), gdy używane są strategie µ
i σ, u

1

(µ, σ) =

P

i

P

j

A

ij

µ

i

σ

j

jest funkcją liniową (właściwie afiniczną) względem µ i σ z

osobna; taka funkcja jest też w szczególności ciągła i wklęsła. A zatem spełnione są zało-
żenia udowodnionego przez nas uogólnionego twierdzenia Nasha, i gra posiada równowagę
w strategiach z X

1

i X

2

, czyli strategiach mieszanych w wyjściowej grze dwumacierzowej.

Wniosek 1.3 Oczywiście, jeśli rozważymy grę dwuosobową, w której wypłaty będą speł-
niać u

1

= −u

2

, to wynika z tego twierdzenia również twierdzenie von Neumanna.

Oczywiście, udowodnione przez nas twierdzenie nie jest najbardziej ogólnym twierdze-

niem o istnieniu równowagi Nasha w grach niekooperacyjnych. Istnieje na przykład twier-
dzenie Glicksberga [1], mówiące, że w grze dwuosobowej ze zwartymi metrycznymi prze-
strzeniami akcji graczy (niekoniecznie będącymi podzbiorami R

k

), i ciągłymi funkcjami

wypłaty, zawsze istnieje równowaga w strategiach mieszanych. Wiadomo natomiast tak-
że, że osłabienie założeń tego twierdzenia może prowadzić do sytuacji, gdy równowagi nie
ma, nawet w strategiach mieszanych. W szczególności osłabienie założenia o ciągłości w
taki sposób, że funkcja wypłaty tylko jednego z graczy nie jest ciągła w jednym punkcie
X

1

× X

2

może prowadzić do braku równowagi (nawet w strategiach mieszanych). Przykład

takiej gry znalazł Vieille [5]. Innym przykładem gry z nieciągłymi funkcjami wypłat graczy
(już w więcej niż jednym punkcie), jest przykład gry o sumie zerowej, posiadającej wartość,
ale nie posiadającej strategii optymalnych (w przypadku takiej gry strategie optymalne są
również strategiami w równowadze Nasha), który mieli Państwo znaleźć w 4. zadaniu na 1.
liście zadań.

9

1.3

Algorytmy szukania równowag w grach niekoope-
racyjnych

1.3.1

Gry macierzowe

Na ćwiczeniach pojawiły się jakieś sposoby szukania równowag w grach macierzowych (dwu-
macierzowych), tyle że w praktyce nadają się one do zastosowania tylko do niektórych gier
(w większości z nich ilość obliczeń, które musielibyśmy wykonać byłaby ogromna), nie
mówiąc o tym, żeby zastosować je do obliczania równowag w grach maszynowo. Dlatego
najbliższe dwa wykłady będą poświęcone temu, jak szukać rozwiązań gier (algorytmicz-
nie). Dzisiaj opowiem o tym, jak to się robi w przypadku gier macierzowych. W przyszłym
tygodniu opowiem, jak rozwiązywać gry bardziej skomplikowane. To, od czego zaczniemy
dzisiaj, nie będzie miało bezpośredniego związku z grami, ten związek wyłoni się dopiero
później.

Programowanie liniowe
Problem programowania liniowego, to bodaj najlepiej znany problem optymalizacyjny, i w
związku z tym, jeśli ktoś z państwa w przyszłości zapisze się na zajęcia z optymalizacji, to
tam będzie to bardzo dokładnie omówione (bodaj przez pół semestru) – tu ograniczę się do
zdefiniowania problemu, opowiedzenia o tym, jak taki problem się rozwiązuje, no i (przede
wszystkim) do opowiedzenia o jego związku z problemem szukania strategii optymalnych
w grach macierzowych.

Problem programowania liniowego możemy zapisać następująco:

Znaleźć maksimum

m

X

i=1

c

i

x

i

przy ograniczeniach

m

X

i=1

a

ij

x

i

¬ b

j

dla

j = 1, . . . , n,

x

i

­ 0

Macierzowo możemy zapisać to następująco:

Dla zadanych C

1×m

, A

m×n

, b

n×1

zmaksymalizować C

T

x przy ograniczeniach A

T

x ¬ B, x ­ 0.

Przykład: A =

"

1
4

5 −1

−1 1

1

#

, B =






0

10

3






, C =

h

2 −3

i

, X =

"

x
y

#

. To oznacza, że

maksymalizujemy funkcję F (x, y) = 2x − 3y przy ograniczeniach































1
4

x − y ¬ 0

5x + y ¬ 10
−x + y ¬ 3
x ­ 0
y ­ 0

Jeśli narysujemy sobie ten zbiór (patrz rysunek poniżej), okazuje się, że jest to wypukły
wielokąt (czworokąt ograniczony prostymi i osia Oy). Dodatkowo, jeśli zaznaczymy sobie,
w którym kierunku zwiększa się funkcja celu (funkcja, którą maksymalizujemy – tu ten
kierunek wskazuje wektor, na prostych prostopadłych do tego wektora funkcja celu się nie
zmienia, zwiększając swoją wartość w kierunku przezeń wskazywanym), okazuje się, że mak-
simum musi być osiągnięte w jednym wierzchołku tego wielokąta (to jest ten wierzchołek,
który zaznaczyłem kropką).

10

6

x

-

y

D

D

D

D

D

D

D

D

D

D

D

D

D

D

D

D

D

D

t

J

J

J

J

^

Jeśli funkcja celu byłaby inna, maksimum mogłoby być osiągnięte we wszystkich punk-

tach któregoś z boków naszego wielokąta, i w przypadku maksymalizowania funkcji liniowej
na płaszczyźnie innych możliwości nie będzie.

Teraz – co się dzieje w ogólności? Otóż w tym przykładzie (dwuwymiarowym), każdy

z warunków ograniczających X mówił, że rozwiązanie musi się znajdować po jednej, okre-
ślonej stronie prostej. W przypadku m-wymiarowym te ograniczenia oznaczają, że X musi
się znajdować po jednej stronie hiperpłaszczyzny, a część wspólna takich zbiorów leżących
po jednej stronie hiperpłaszczyzny jest wypukłym wielościanem. W przypadku wielościanu,
maksimum funkcji liniowej musi być przyjmowane w którymś z wierzchołków tego wielo-
ścianu (ewentualnie we wszystkich punktach którejś ze ścian tego wielościanu, cokolwiek
słowo ściana miałoby tutaj oznaczać). To oznacza, że chcąc szukać naszego maksimum,
wystarczy przeszukać kolejne wierzchołki tego wielościanu. Dodatkowo, żeby algorytm szu-
kania maksimum był zbieżny, algorytm powinien po sprawdzeniu, czy w jakimś jednym
wierzchołku nie ma maksimum, przechodzić do któregoś z wierzchołków, w których funkcja
celu będzie miała większą wartość, dzięki czemu po skończonej liczbie kroków dojdzie do
tego jednego (albo jednego z tych) wierzchołka, w którym jest osiągnięte maksimum.

Algebraicznie ten pomysł będzie realizował algorytm sympleks, który teraz po krótce

omówię.
Algorytm sympleks
W algorytmie będziemy kolejne kroki, o których mówiłem, opisywali algebraicznie, wycho-
dząc od układu nierówności, które musi spełniać nasze rozwiązanie:















a

11

x

1

+ a

21

x

2

+ . . . + a

m1

x

m

¬ b

1

..

.
a

1n

x

1

+ a

2n

x

2

+ . . . + a

mn

x

m

¬ b

n

.

Ten układ nierówności możemy równoważnie zapisać jako układ równań:















a

11

x

1

+ a

21

x

2

+ . . . + a

m1

x

m

− b

1

= −u

1

..

.
a

1n

x

1

+ a

2n

x

2

+ . . . + a

mn

x

m

− b

n

= −u

n

,

gdzie u

1

,. . . , u

n

są dodatkowymi zmiennymi nieujemnymi, zwanymi zmiennymi wolnymi.

Tak jak w przypadku algorytmów rozwiązywania równań macierzowych wygodniej jest

działać na odpowiednich macierzach zamiast całych równań, tu też zapisujemy te równania

11

przy pomocy pewnego schematu, który nazywamy „tablicą sympleks”:

−x

1

−x

2

. . . −x

m

1

a

11

a

21

. . .

a

m1

b

1

u

1

..

.

..

.

..

.

..

.

..

.

a

1n

a

2n

. . .

a

mn

b

n

u

n

−c

1

−c

2

. . .

−c

m

0

z

.

Ostatni wiersz tablicy odpowiada funkcji celu.

Interpretacja takiej tablicy jest taka: środkowa część tablicy przedstawia współczynniki

przy zmiennych u góry, dolny wiersz to samo dla funkcji celu, zmienne znajdujące się u
góry tablicy (tzw. zmienne niebazowe) są równe zero, a zmienne z prawej strony tablicy są
równe wartościom w przedostatniej kolumnie. To, że m zmiennych ma wartość zero alge-
braicznie ma oznaczać, że jesteśmy w wierzchołku wielościanu (bo w m ograniczeń zachodzi
równość). W trakcie algorytmu będziemy wymieniać zmienne wyzerowane ze zmiennymi ba-
zowymi (tymi z prawej), uzyskując w ten sposób inny wierzchołek. Jedyny problem może
być taki, że któreś z ograniczeń obetnie nam punkt, w którym w m z pozostałych ograni-
czeń są równości. Reguły przechodzenia od jednego wierzchołka do następnego będą nam
gwarantowały, że tak nie będzie – jeśli byliśmy w wierzchołku, to przejdziemy do wierz-
chołka. Problem może być tylko z punktem startowym, bo oczywiście nie zawsze zmienne
x

1

,. . . ,x

n

ustawione na zera muszą być wierzchołkiem zbioru rozwiązań dopuszczalnych.

Dlatego pierwsza faza algorytmu ma właśnie na celu znalezienie jednego z wierzchołków
wielościanu.

Pierwsza faza:
Sprawdzamy, czy w ostatniej kolumnie nie ma elementów ujemnych. Jeśli nie ma, to x

1

=

. . . = x

m

= 0 jest wierzchołkiem tego wielościanu. Jeśli takie są, to

1. wybieramy ostatni z nich (w najdalszym wierszu), w wierszu k. Dla uproszczenia no-

tacji wszystkie elementy tablicy będę oznaczał przez α

ij

(włącznie z ostatnią kolumną

i ostatnim wierszem).

2. W wierszu k (tym z elementem ujemnym w ostaniej kolumnie) wybieramy element,

dla którego α

kj

0

< 0 (to j

0

jest tu istotne). Jeśli takiego nie ma – zbiór rozwiązań

dopuszczalnych jest pusty.

3. Następnie wśród wierszy i ­ k poza wierszem funkcji celu wybieramy ten, dla którego

iloraz

α

i,m+1

α

ij0

jest najmniejszy dodatni. Oznaczamy go przez i

0

.

4. Wymieniamy zmienne, które są w wierszu i

0

i kolumnie j

0

.

Tablica po wymianie zmiennych wygląda następująco (

g

α

ij

oznacza elementy tablicy po

wymianie, α

ij

– przed wymianą):

g

α

i

0

j

0

=

1

α

i

0

j

0

g

α

i

0

j

=

α

i

0

j

α

i

0

j

0

j 6= j

0

g

α

ij

0

= −

α

ij

0

α

i

0

j

0

i 6= i

0

g

α

ij

= α

ij

−

α

i

0

j

α

ij

0

α

i

0

j

0

.

Jeśli w ostatniej kolumnie po wymianie zmiennych bazowych dalej jest element ujemny, to
powtarzamy tę fazę metody sympleksowej. Jeśli nie – przechodzimy do drugiej fazy.

12

Druga faza algorytmu polega na przechodzeniu od jednego wierzchołka do innego

w taki sposób, żeby za każdym razem zwiększać funkcję celu. Robimy to w następujący
sposób:

1. Wybieramy kolumnę j

0

, w której w wierszu funkcji celu mamy wartość ujemną.

2. Następnie z elementów tej kolumny wybieramy taki, że α

ij

0

jest dodatni i

α

i,m+1

α

ij0

jest

jak najmniejsze.

3. W ten sposób dostajemy wiersz i

0

i kolumę j

0

, w których wymieniamy zmienną ba-

zową ze zmienną niebazową. Reguły zmieniania tablicy sympleksowej przy wymianie
zmiennych są takie same jak w pierwszej fazie.

Tę fazę powtarzamy tak długo, aż w wierszu celu nie ma elementów ujemnych. Współ-

rzędne optymalnego rozwiązania odczytujemy z tablicy – te zmienne, które zostały u góry
są równe zero, pozostałe są równe wartościom, które stoją obok nich w ostatniej kolumnie.
Z kolei optymalną wartość funkcji celu odczytujemy z prawej kolumny ostatniego wiersza.

Zanim przejdziemy do tego, w jaki sposób sprowadzić problem szukania rozwiązania

optymalnego do programowania liniowego, napiszę jeszcze jedno twierdzenie, które ma fun-
damentalne znaczenie w programowaniu liniowym, a które będzie miało też związek z tym,
co nas najbardziej interesuje, czyli z grami.
Problem dualny do problemu zdefiniowanego na początku wykładu definiujemy nastę-
pująco: Znaleźć Y = [y

1

, . . . , , y

m

]

T

minimalizujący

P

m
i=1

b

i

y

i

przy ograniczeniach: Y ­ 0,

AY ­ C

T

.

Prawdziwe będzie takie twierdzenie:

Twierdzenie 1.5 (o dualności) Jeśli program liniowy i program do niego dualny mają
rozwiązania, to max

X

P

n
j=1

c

j

x

j

= min

Y

P

m
i=1

b

i

y

i

.

I teraz, po godzinie wykładu, wracamy do gier (przypominam) o sumie zerowej. Okazuje

się, że problem szukania strategii optymalnych w takiej grze można zapisać przy pomocy
programu liniowego, a, co więcej, okaże się, że twierdznie von Neumanna będzie w takim
wypadku wynikać z twierdzenia o dualności.

Niech W = [w

ij

]

k×l

będzie macierzą wypłat w grze macierzowej. Wtedy rozważać bę-

dziemy problem programowania liniowego następującej postaci:

A

T

=












1 −1

−W

T

..

.

..

.

1 −1

1

. . .

1 0

0

−1

. . .

−1 0

0












,

X = [µ

1

, . . . , µ

k

, v

1

, v

2

]

T

, B = [0, . . . , 0, 1, −1]

T

, C = [0, . . . , 0, 1, −1]. Maksymalizujemy

v

1

− v

2

=: v. Jeśli zapisać ten problem w postaci układu równań, dostaniemy:











P

k
i=1

w

ij

µ

i

­ v

dla j = 1, . . . , l

P

k
i=1

µ

i

= 1

µ

i

­ 0 dla i = 1, . . . , k

.

Te równania oznaczają, że µ = (µ

1

, . . . , µ

k

) jest rozkładem prawdopodobieństwa na wier-

szach macierzy W . Dodatkowo, jeśli µ

∗

będzie rozwiązniem tego problemu, a v

∗

wartością

funkcji celu dla tego rozwiązania, to:

k

X

i=1

w

ij

µ

∗
i

­ v

∗

dla każdej kolumny j,

13

czyli dla dowolnego rozkładu prawdopodobieństwa σ = (σ

1

, . . . , σ

l

) na kolumnach:

k

X

i=1

l

X

j=1

w

ij

µ

∗
i

σ

j

­ v

∗

,

Ponieważ σ było dowolne, a prawa strona nie zależy od σ, więc możemy napisać

min

σ

k

X

i=1

l

X

j=1

w

ij

µ

∗
i

σ

j

­ v

∗

,

a stąd

v = max

µ

min

σ

k

X

i=1

l

X

j=1

w

ij

µ

i

σ

j

­ v

∗

.

A teraz popatrzmy się na problem dualny. Jeśli przyjmiemy Y = [σ

1

, . . . , σ

l

, v

1

, v

2

]

T

,

a wszystkie pozostałe macierze – jak poprzednio, to dostajemy, że mamy zminimalizować
v = v

1

− v

2

przy ograniczeniach

P

l
j=1

w

ij

σ

j

¬ v,

P

l
j=1

σ

j

= 1 dla i = 1, . . . , k, σ

j

­ 0,

j = 1, . . . , l, skąd w podobny sposób co poprzednio dostajemy:

v = min

σ

max

µ

k

X

i=1

l

X

j=1

w

ij

µ

i

σ

j

¬ v

∗

,

a ponieważ v

∗

na mocy twierdzenia o dualności jest takie samo, to dostaliśmy, że gra

ma wartość równą v

∗

(czyli tezę twierdzenia von Neumanna), a strategiami optymalnymi,

realizującymi tę wartość, są µ

∗

i σ

∗

, będące rozwiązaniami naszych dualnych problemów

programowania liniowego.

Przykład: Rozważmy grę macierzową z macierzą wypłat






3 0

1

−1 2

2

1 0 −1






. Zgodnie z tym,

co było powiedziane przed chwilą, żeby znaleźć wartość tej gry oraz strategie optymalne
graczy, musimy rozwiązać problem programowania liniowego z macierzą

A

T

=











−3

1 −1 1 −1

0 −2

0 1 −1

−1 −2

1 1 −1

1

1

1 0

0

−1 −1 −1 0

0











,

X = [µ

1

, µ

2

, µ

3

, v

1

, v

2

]

T

, B = [0, . . . , 0, 1, −1]

T

, C = [0, . . . , 0, 1, −1], oraz problem do niego

dualny. Na początek zapisujemy tablicę sympleksową:

−µ

1

−µ

2

−µ

3

−v

1

−v

2

1

−3

1

−1

1

−1

0 u

1

0

−2

0

1

−1

0 u

2

−1

−2

1

1

−1

0 u

3

1

1

1

0

0

1 u

4

−1

−1

−1

0

0 −1 u

5

0

0

0

−1

1

0

v

.

W ostatniej kolumnie jest jedna liczba ujemna, w 5. wierszu. Ponieważ jest to ostatni
wiersz poza wierszem celu, więc wybieramy do zamiany zmiennej ten wiersz. Wybieramy

14

też kolumnę taką, żeby w 5. wierszu stał w niej element ujemny, na przykład 1. kolumnę.
Po zamianie zmiennych dostajemy:

−u

5

−µ

2

−µ

3

−v

1

−v

2

1

−3

4

2

1

−1 3 u

1

0

−2

0

1

−1 0 u

2

−1

−1

2

1

−1 1 u

3

1

0

0

0

0 0

u

4

−1

1

1

0

0 1 µ

1

0

0

0

−1

1 0

v

.

Na tym kończy się pierwsza faza metody sympleksowej, bo w ostatniej kolumnie nie ma już
elementów ujemnych. Zaczynamy drugą fazę. Wybieramy 4. kolumnę, bo tam w wierszu
funkcji celu znajduje się wartość ujemna, oraz drugi wiersz, bo tam iloraz elementu w
ostatniej kolumnie i elementu w kolumnie wybranej (czwartej) jest najmniejszy z wierszy,
w których w 4. kolumnie stoi liczba dodatnia. Po zamianie zmiennych dostajemy:

−u

5

−µ

2

−µ

3

−u

2

−v

2

1

−3

6

2

−1

0 3 u

1

0

−2

0

1

−1 0

v

1

−1

1

2

−1

0 1

u

3

1

0

0

0

0 0 u

4

−1

1

1

0

0 1 µ

1

0

−2

0

1

0 0

v

.

W ostatnim wierszu w drugiej kolumnie stoi element ujemny, więc wybieramy tę kolumnę,
a z elementów dodatnich tej kolumny wybieramy szóstkę w pierwszym wierszu, bo dla niej
iloraz elementu w ostatniej kolumnie i elementu w wybranej przez nas jest najmniejszy. Po
zamianie zmiennych dostajemy:

−u

5

−u

1

−µ

3

−u

2

−v

2

1

−

1
2

1
6

1
3

−

1
6

0

1
2

µ

2

−1

1
3

2
3

2
3

−1 1

v

1

−

1
2

−

1
6

5
3

−

5
6

0

1
2

u

3

1

0

0

0

0

0 u

4

−

1
2

−

1
6

2
3

1
6

0

1
2

µ

1

−1

1
3

0

1

0

1

v

.

Dalej wybieramy pierwszą kolumnę i czwarty wiersz, otrzymując:

−u

4

−u

1

−µ

3

−u

2

−v

2

1

1
2

1
6

1
3

−

1
6

0

1
2

µ

2

1

1
3

2
3

2
3

−1 1

v

1

1
2

−

1
6

5
3

−

5
6

0

1
2

u

3

1

0

0

0

0

0 u

5

1
2

−

1
6

2
3

1
6

0

1
2

µ

1

1

1
3

0

1

0

1

v

.

I na tym się kończy algorytm, bo w wierszu funkcji celu nie ma już wartości ujemnych.
Odczytujemy wynik – µ

3

= 0, bo pozostało u góry, pozostałe wartości odczytujemy z 6.

kolumny: µ

1

= µ

2

=

1
2

, a wartość gry (funkcja celu) v = 1. Mamy w takim razie strategię

pierwszego gracza. Aby otrzymać strategię drugiego, rozwiązujemy problem dualny. Nie

15

będę rozpisywał, jak on wygląda – od razu zapiszę go w postaci tablicy sympleksowej.

−σ

1

−σ

2

−σ

3

−v

1

−v

2

1

3

0

1

−1

1

0

u

1

−1

2

2

−1

1

0

u

2

1

0

−1

−1

1

0

u

3

−1

−1

−1

0

0 −1

u

4

1

1

1

0

0

1

u

5

0

0

0

1

−1

0 −v

.

Zaczynamy od pierwszej fazy metody sympleksowej, czyli szukamy wiersza, który ma w
ostatniej kolumnie wartość ujemną – takim wierszem jest wiersz czwarty. Wybieramy inną
kolumnę, w której stoi wartość ujemna, np. pierwszą, i sprawdzamy w czwartym i piątym
wierszu, gdzie odpowiedni iloraz jest najmniejszy. W obu jest taki sam (równy 1), więc
możemy np. wybrać czwarty wiersz. Wymieniamy zmienne:

−u

4

−σ

2

−σ

3

−v

1

−v

2

1

3

−3

−2

−1

1 −3

u

1

−1

3

3

−1

1

1

u

2

1

−1

−2

−1

1 −1

u

3

−1

1

1

0

0

1

σ

1

1

0

0

0

0

0

u

5

0

0

0

1

−1

0 −v

.

Teraz bierzemy ostatni wiersz z ujemną wartością w ostatniej kolumnie, i kolumnę, w
której w tym (trzecim) wierszu stoi element ujemny (np. 2. kolumnę), i po porównaniu
odpowiednich ilorazów stwierdzamy, że zamieniamy zmienną w trzecim wierszu i drugiej
kolumnie:

−u

4

−u

3

−σ

3

−v

1

−v

2

1

0

−3

4

2

−2

0

u

1

2

3

−3

−4

4 −2

u

2

−1

−1

2

1

−1

1

σ

2

0

1

−1

−1

1

0

σ

1

1

0

0

0

0

0

u

5

0

0

0

1

−1

0 −v

.

Jedyny element ujemny w ostatniej kolumnie jest w drugim wierszu. W tym wierszu są
poza tym dwie wartości ujemne, wybieramy kolumnę 3., w której znajduje się jedna z nich.
Porównujemy ilorazy wartości w ostatniej kolumnie i kolumnie przez nas wybranej, i docho-
dzimy do wniosku, że najmniejszy dodatni iloraz (

1
2

) jest w 3. wierszu, więc wymieniamy

zmienną w trzecim wierszu σ

2

ze zmienną w trzeciej kolumnie σ

3

:

−u

4

−u

3

−σ

2

−v

1

−v

2

1

2

−1

−2

0

0

−2

u

1

1
2

3
2

3
2

−

5
2

5
2

−

1
2

u

2

−

1
2

−

1
2

1
2

1
2

−

1
2

1
2

σ

3

−

1
2

1
2

1
2

−

1
2

1
2

1
2

σ

1

1

0

0

0

0

0

u

5

0

0

0

1

−1

0 −v

.

16

Następnie wymieniamy zmienne w 4. kolumnie (v

1

) i w 2. wierszu (u

2

):

−u

4

−u

3

−σ

2

−u

2

−v

2

1

2

−1

−2

0

0

−2

u

1

−

1
5

−

3
5

−

3
5

−

2
5

−1

1
5

v

1

−

2
5

−

1
5

4
5

1
5

0

2
5

σ

3

−

3
5

1
5

1
5

−

1
5

0

3
5

σ

1

1

0

0

0

0

0

u

5

1
5

3
5

3
5

2
5

0 −

1
5

−v

.

Dalej wymieniamy zmienną u

3

ze zmienną u

1

:

−u

4

−u

1

−σ

2

−u

2

−v

2

1

−2

−1

2

0

0

−2

u

3

−

7
5

−

3
5

3
5

−

2
5

−1

7
5

v

1

−

4
5

−

1
5

6
5

1
5

0

4
5

σ

3

−

1
5

1
5

−

1
5

−

1
5

0

1
5

σ

1

1

0

0

0

0

0

u

5

7
5

3
5

−

3
5

2
5

0 −

7
5

−v

.

Na tym kończy się pierwsza faza, bo w ostatniej kolumnie nie ma już elementów ujem-
nych. Zaczynamy drugą fazę. W ostatnim wierszu (poza ostatnią kolumną) jest tylko jedna
wartość ujemna, w trzeciej kolumnie, więc wybieramy tę kolumnę. Porównujemy następnie
ilorazy elementów ostatniej kolumny z dodatnimi elementami wybranej (3.) kolumny. Wy-
bieramy trzeci wiersz, bo tam ten iloraz jest najmniejszy (równy

2
3

). Po wymianie zmiennych

dostajemy:

−u

4

−u

1

−σ

3

−u

2

−v

2

1

−

2
3

−

2
3

−

5
3

−

1
3

0

2
3

u

3

−1

−

1
2

−

1
2

−

1
2

−1

1

v

1

−

2
3

−

1
6

5
6

1
6

0

2
3

σ

2

−

1
3

1
6

1
6

−

1
6

0

1
3

σ

1

1

0

0

0

0

0

u

5

1

1
2

1
2

1
2

0 −1 −v

.

I na tym kończymy, bo jedyną wartością ujemną w ostatnim wierszu jest wartość funkcji
celu, a ona ma prawo być ujemna. Otrzymanym rozwiązaniem jest rozkład σ = (

1
3

,

2
3

, 0).

Uwaga 1.5 Jakkolwiek algorytm sympleks w najgorszym przypadku ma złożonośc wy-
kładniczą, to istniejące algorytmy rozwiązywania problemów programowania liniowego,
które mają złożoność wielomianową (np. algorytm Karmarkara) zwykle działają znacznie
wolniej. Dlatego omawiałem tę metodę.

1.3.2

Gry dwumacierzowe

W zeszłym tygodniu mówiłem o tym, jak sprowadzić problem szukania strategii optymal-
nych w grze macierzowej do rozwiązania odpowiedniego zagadnienia optymalizacyjnego,
konkretnie do zadania programowania liniowego. Dzisiaj poopowiadam trochę o tym, jak
to jest w przypadku bardziej skomplikowanych gier. Większość wykładu będzie poświę-
cona grom dwumacierzowym, bo o zagadnieniu szukania równowag w takich grach dosyć
dużo wiemy, natomiast o przypadkach bardziej skomplikowanych powiem trochę na końcu
wykładu, nie wchodząc już w szczegóły konkretnych algorytmów.

Zacznijmy więc wykład od próby przedstawienia problemu szukania równowagi w grze

dwumacierzowej w postaci analogicznej do tego, co było na końcu ostatniego wykładu,

17

czyli przy pomocy pewnego układu nierówności. Niech tradycyjnie A

m×n

oznacza macierz

wypłat pierwszego gracza, a B

m×n

– macierz wypłat drugiego. Niech µ = [µ

1

, . . . , µ

m

] będzie

strategią mieszaną w równowadze 1., a σ = [σ

1

, . . . , σ

n

] – 2. gracza. Dodatkowo, przez v

1

oznaczymy wypłatę w tej równowadze pierwszego z graczy, a przez v

2

– drugiego. Zgodnie

z tym, co pokazaliśmy na ćwiczeniach, dla strategii w równowadze muszą być spełnione
następujące warunki:

(

P

j

a

ij

σ

j

= v

1

dla i z nośnika µ

P

j

a

ij

σ

j

¬ v

1

dla i spoza nośnika,

(To było zadanie 8. z pierwszej listy). Podobnie dla drugiego gracza:

(

P

i

b

ij

µ

i

= v

2

dla j z nośnika σ

P

i

b

ij

µ

i

¬ v

2

dla j spoza nośnika,

Ponadto, ponieważ v

1

i v

2

są wypłatami w równowadze (µ, σ), więc dodatkowo musi być

spełnione

P

i

P

j

a

ij

µ

i

σ

j

= v

1

oraz

P

i

P

j

b

ij

µ

i

σ

j

= v

2

.

Przyjmijmy teraz sobie x =

µ

v

2

oraz y =

σ

v

1

. Dla takich x i y, warunki podane wcześniej

będą implikować:

(

P

j

a

ij

y

j

= 1

dla i z nośnika x

P

j

a

ij

y

j

¬ 1

dla i spoza nośnika x

(

P

i

b

ij

x

i

= 1

dla j z nośnika y

P

i

b

ij

x

i

¬ 1

dla j spoza nośnika y,

a także:

X

i

x

i

+

X

j

y

j

=

1

v

2

+

1

v

1

=

X

i

X

j

a

ij

x

i

y

j

+

X

i

X

j

b

ij

x

i

y

j

.

Okazuje się, że ten układ warunków (plus założenie o nieujemności x i y), już wystarczy
do policzenia strategii w równowadze. Dokładniej, prawdziwe będzie takie twierdzenie:

Twierdzenie 1.6 Niech z = [x, y]

T

, q = [1, . . . , 1]

T
1×m+n

oraz C =

"

0

A

B

T

0

#

i dodatkowo

załóżmy, że C > 0. Dowolne niezerowe rozwiązanie z

∗

następującego problemu: znajdź z

takie, że:

z ­ 0,

(1.1)

q − Cz ­ 0,

(1.2)

z

T

(q − Cz) = 0,

(1.3)

ma taką własność, że µ =

x

P

i

x

i

oraz σ =

y

P

j

y

j

jest równowagą w grze dwumacierzowej o

macierzach wypłat A i B.

Uwaga 1.6 Założenie, że C > 0 nie ogranicza nas zbytnio, bo strategie w równowadze
w grze dwumacierzowej z macierzami wypłat A, B pozostają w równowadze w grze z
macierzami A + c, B + c, gdzie c jest pewną stałą. Żeby więc znaleźć równowagę w grze
z macierzami, w których są elementy ujemne, wystarczy do tych macierzy dodać pewną
stałą dodatnią, otrzymując w ten sposób grę spełniającą założenia naszego twierdzenia, a
jednocześnie posiadającą równowagi takie same jak w grze wyjściowej.

Dowód: Jeśli zapiszemy warunek (1.3), dostaniemy ostatnią z równości zapisanych przed
twierdzeniem. Warunek (1.2) zapisany w postaci układu nierówności będzie wyglądał tak:

(

1 −

P

j

a

ij

y

j

­ 0

1 −

P

i

b

ij

x

i

­ 0,

18

czyli są to (lekko osłabione warunki, które zapisałem wcześniej). Dla odmiany, warunek
(1.1) musi być spełniony, żeby µ i σ były rozkładami prawdopodobieństwa. Wniosek z
tego taki, że równowaga Nasha na pewno będzie rozwiązaniem problemu sformułowanego
w twierdzeniu.

Druga część dowodu musi więc być taka, że mamy pokazać, że nie ma rozwiązań tego

problemu, które nie dawałyby równowagi Nasha. No to załóżmy nie wprost, że µ =

x

P

i

x

i

,

σ =

y

P

j

y

j

, [x, y]

T

jest niezerowym rozwiązaniem naszego problemu, ale µ i σ nie tworzą

równowagi Nasha. (1.2) będzie oznaczało, że

P

j

a

ij

y

j

¬ 1 oraz

P

i

b

ij

x

i

¬ 1. Niech teraz I

będzie zbiorem takich i, że w pierwszej nierówności jest równość, a J zbiorem j dla których
jest równość w drugiej nierówności. Wtedy:

X

i

X

j

a

ij

x

i

y

j

+

X

i

X

j

b

ij

x

i

y

j

=

=

X

i∈I

x

i

X

j

a

ij

y

j

+

X

i6∈I

x

i

X

j

a

ij

y

j

+

X

j∈J

y

j

X

i

x

i

b

ij

+

X

j6∈J

y

j

X

i

x

i

b

ij

¬

¬

X

i

x

i

+

X

j

y

j

,

gdzie równość w ostatniej nierówności zachodzi wtedy i tylko wtedy (i po to zostało to
rozpisane na sumę po I i jego dopełnieniu, oraz po J i jego dopełnieniu), gdy x

i

= 0 na

zbiorze I

C

, a y

j

= 0 na zbiorze J

C

. Tyle że warunek (1.3) implikuje, że tu jest równość. A

zatem dostajemy warunki:

(

P

j

a

ij

y

j

= 1

jeśli x

i

> 0

P

j

a

ij

y

j

< 1

jeśli x

i

= 0,

oraz

(

P

i

b

ij

x

i

= v

2

jeśli y

j

> 0

P

i

b

ij

x

i

< v

2

jeśli y

j

= 0,

co jest równoważne warunkom:







P

j

a

ij

σ

j

=

1

P

j

y

j

=: v

1

dla i z nośnika µ

P

j

a

ij

σ

j

< v

1

dla i spoza nośnika,

(

P

i

b

ij

µ

i

=

1

P

i

x

i

=: v

2

dla j z nośnika σ

P

i

b

ij

µ

i

< v

2

dla j spoza nośnika,

ale w zadaniu 8. z 1. listy udowodniliśmy, że strategie µ i σ są w równowadze wtedy i
tylko wtedy gdy spełniają powyższe warunki, a więc mamy sprzeczność, bo zakładaliśmy,
że µ i σ nie tworzą równowagi Nasha.

Teraz, co wynika z udowodnionego twierdzenia? Otóż problem, który pojawił się w

powyższym twierdzeniu należy do znanej klasy problemów, i istnieją algorytmy, służące do
jego rozwiązywania, i teraz sformułujemy ogólnie taki problem, i opowiem, na czym polega
algorytm ich rozwiązywania.

Problem komplementarności liniowej (LCP)
Niech C będzie macierzą l × l (kwadratową), a q – wektorem l × 1 złożonym z samych
jedynek. Znajdź z

l×1

, spełniający:

z ­ 0,

q − Cz ­ 0,

z

T

(q − Cz) = 0.

19

Pierwsze dwa warunki, to ograniczenia liniowe takie, jakie znamy z problemu programo-
wania liniowego. Trzeci warunek nazywamy warunkiem komplementarności, bo oznacza on
tyle, że na każdej współrzędnej i, albo z

i

= 0 albo i-ta współrzędna q − Cz jest równa zero

(innych możliwości nie ma, bo dwa pierwsze warunki gwarantują, że każda współrzędna z
i każda współrzędna q − Cz jest nieujemna).

Algorytm rozwiązywania LCP wymyślili Lemke i Howson, i wygląda następująco:

Algorytm Lemke-Howsona
Zbiór wektorów w odpowiedniej przestrzeni l-wymiarowej spełniających zestaw liniowych
ograniczeń (dwa pierwsze warunki zadające LCP), podobnie jak w przypadku programowa-
nia liniowego jest wypukłym wielościanem (bo to są takie same warunki jak te, które tam
się pojawiły). Stąd kolejne kroki algorytmu będą wyglądały podobnie jak w przypadku al-
gorytmu sympleks. Tu też będziemy przechodzili od wierzchołka do wierzchołka wielościanu
zadanego przez te warunki (stąd kolejne kroki algorytmu będą polegały na wymienianiu
między sobą zmiennych, których wyzerowanie odpowiada równości w poszczególnych wa-
runkach). Cel algorytmu będzie tylko inny. W programowaniu liniowym mieliśmy funkcję
celu, która zwiększała się przy każdym kolejnym kroku algorytmu, tu takiej funkcji celu
nie ma, w związku z tym nie ma takiego jasnego kryterium wyboru kolejnego wierzchołka
wielościanu, do którego ma przejść algorytm. Warunek, który będziemy sprawdzali przy
zamianie zmiennych, będzie miał na celu jedynie to, żeby algorytm nie cofał się – nie
przechodził do wierzchołka, który już sprawdzaliśmy.

Jak poprzednio, zapisujemy wszystko w postaci tablicy:

z

1

z

2

. . .

z

l

−c

11

−c

12

. . . −c

1l

1

r

1

−c

21

−c

22

. . . −c

2l

1

r

2

..

.

..

.

..

.

..

.

r

3

−c

l1

−c

l2

. . .

−c

ll

1

r

4

Elementy tej tablicy będziemy oznaczać przez d

ij

. Tablica ta reprezentuje układ równań

q − Cz = r, gdzie r

i

jest zmienną równą i-tej współrzędnej q − Cz. Zmienne u góry tablicy,

jak w algorytmie sympleks, są ustawione na zero, wartości pozostałych są równe temu, co
stoi w l + 1. kolumnie tablicy. Startujemy z punktu z = 0, który jest rozwiązaniem LCP, ale
nie generuje równowagi Nasha, i w kolejnych krokach algorytmu wykonujemy następujące
operacje:

1. Wybieramy (dowolną, np. pierwszą) kolumnę macierzy j

0

. Zapamiętujemy, która to

była kolumna (czyli zmienna z jakim indeksem w niej stała).

2. Wybieramy taki wiersz i

0

, że d

i

0

j

0

< 0 oraz

d

i0,l+1

−d

i0j0

jest najmniejsze (tę regułę nazy-

wamy testem najmniejszego ilorazu).

3. Wymieniamy zmienną bazową (z prawej w wierszu i

0

) ze zmienną niebazową (u góry

w wierszu j

0

), stosując te same reguły zmiany tablicy przy wymianie zmiennych co w

algorytmie sympleks w zeszłym tygodniu (jak wtedy, d

i

0

j

0

z tyldą oznaczają wartości

d

i

0

j

0

po wymianie zmiennych):

g

d

i

0

j

0

=

1

d

i

0

j

0

g

d

i

0

j

=

d

i

0

j

d

i

0

j

0

j 6= j

0

g

d

ij

0

= −

d

ij

0

d

i

0

j

0

i 6= i

0

20

f

d

ij

= d

ij

−

d

i

0

j

d

ij

0

d

i

0

j

0

.

Jeśli numer zmiennej opuszczającej bazę r

·

był inny niż zmiennej z pierwszego punktu,

zmienną z tym numerem wybieramy w następnym kroku jako tę, która wejdzie do
bazy. Wybieramy kolumnę, w której stoi zmienna o tym numerze i wracamy do punktu
2.

Jeśli numer zmiennej opuszczającej bazę był taki sam jak numer pierwszej wybranej przez
nas, to algorytm się kończy, a my możemy odczytać z tablicy rozwiązanie LCP. Robimy to
w następujący sposób: te ze zmiennych z

i

, które pozostały u góry tablicy mają wartość 0,

pozostałe mają wartości równe tym w l + 1. kolumnie tablicy.

Sens takiego „łańcuszka”, oraz warunku kończącego algorytm, jest taki: naszym celem

jest znalezienie takiego punktu, w którym dla każdego indeksu i albo zmienna z

i

, albo

i-ta współrzędna q − Cz, r

i

będzie równa zero. W związku z tym, jeśli na którymś kroku

wyzerowaliśmy zmienną o indeksie j, z

j

lub r

j

, to sprawdzamy, czy druga z tych zmiennych

też jest wyzerowana – jeśli tak, staramy się wymienić tę drugą na zmienną o takim indeksie
i, że w danej chwili ani z

i

ani r

i

nie jest wyzerowana. W ten sposób otrzymalibyśmy sytuację,

w której zarówno jedna ze zmiennych z

j

, r

j

, jak i jedna ze zmiennych z

i

, r

i

jest wyzerowana.

Jeśli na danym kroku to nam się nie udaje, to wymieniamy jedną ze zmiennych o indeksie i
(które w takim wypadku są obie u góry tablicy, czyli ich wartość jest ustawiona na zero) na
jakąś inną zmienną (dzięki czemu jednocześnie na żadnym kroku algorytmu nie ma więcej
niż jednego indeksu takiego, że zarówno zmienna r o takim indeksie, jak i zmienna z o
takim indeksie, jest wyzerowana). Powtarzamy to tak długo, aż u góry (wśród zmiennych
wyzerowanych) będzie się znajdowało po jednej zmiennej o każdym indeksie, czyli będzie
spełniony warunek komplementarności.

Przykład
Mamy znależć równowagę w grze dwumacierzowej z macierzami wypłat:

A =

"

5 5 10
1 8

3

#

,

B =

"

2 8 2
3 2 7

#

.

W takim przypadku macierz C =











0 0 5 5 10
0 0 1 8

3

2 3 0 0

0

8 2 0 0

0

2 7 0 0

0











. Zapiszmy teraz wszystko w postaci

tabelki.

z

1

z

2

z

3

z

4

z

5

0

0 −5 −5 −10 1

r

1

0

0 −1 −8

−3 1

r

2

−2 −3

0

0

0 1

r

3

−8 −2

0

0

0 1

r

4

−2 −7

0

0

0 1

r

5

Niech k = 1, co oznacza, że jako zmienną wchodzącą do bazy wybieramy z

1

. Używając testu

najmniejszego ilorazu wybieramy r

4

jako zmienną, którą usuniemy z bazy. Po pierwszej

21

wymianie zmiennych dostajemy:

r

4

z

2

z

3

z

4

z

5

0

0 −5 −5 −10

1

r

1

0

0 −1 −8

−3 1

r

2

1
4

−5

2

0

0

0

3
4

r

3

−1

8

−1

4

0

0

0

1
8

z

1

1
4

−13

2

0

0

0

3
4

r

5

Kolejną zmienną wchodzącą do bazy będzie z

4

, a usuwaną r

2

. Po drugiej zamianie zmien-

nych dostajemy:

r

4

z

2

z

3

r

2

z

5

0

0

−35

8

5
8

−65

8

3
8

r

1

0

0

−1

8

−1

8

−3

8

1
8

z

4

1
4

−5

2

0

0

0

3
4

r

3

−1

8

−1

4

0

0

0

1
8

z

1

1
4

−13

2

0

0

0

3
4

r

5

Następnie wymieniamy z

2

z r

5

, co daje nam nową tablicę:

r

4

r

5

z

3

r

2

z

5

0

0

−35

8

5
8

−65

8

3
8

r

1

0

0

−1

8

−1

8

−3

8

1
8

z

4

2

13

5

13

0

0

0

6

13

r

3

−7

52

1

26

0

0

0

5

52

z

1

1

26

−2

13

0

0

0

3

26

z

2

Dalej wymieniamy z

5

z r

1

, co daje:

r

4

r

5

z

3

r

2

r

1

0

0

−7

13

1

13

−8

65

3

65

z

5

0

0

1

13

−2

13

3

65

7

65

z

4

2

13

5

13

0

0

0

6

13

r

3

−7

52

1

26

0

0

0

5

52

z

1

1

26

−2

13

0

0

0

3

26

z

2

I to już koniec, bo zmienna k-ta (czyli o numerze równym numerowi pierwszej zmiennej,
która weszła do bazy – r

1

) została usunięta z bazy. Stąd rozwiązaniem LCP jest z =

(

5

52

,

3

26

, 0,

7

65

,

3

65

). Po normalizacji otrzymujemy równowagę Nasha w wyjściowej grze µ =

(

5

11

,

6

11

), ν = (0,

7

10

,

3

10

).

Uwaga 1.7 Algorytm Lemke-Howsona, podobnie jak algorytm sympleks, ma wykładni-
czą złożoność obliczeniową. W przypadku zastosowania tego algorytmu do rozwiązywania
dowolnych problemów komplementarności liniowej było to udowodnione już w latach sie-
demdziesiątych. To, że złożoność szukania równowag Nasha przy użyciu tego algorytmu też
jest w najgorszym przypadku wykładnicza udowodnili Savani i von Stengel [4] trzy lata
temu, co sugeruje, że w większości przypadków algorytm jest jednak w miarę szybki. To
o tyle dobrze, że niestety w przypadku problemu komplementarności liniowej nie ma zna-
nych algorytmów, które byłyby szybsze (nawet w teorii). Jakkolwiek nie jest oczywiste, że
ktoś w przyszłości takich nie znajdzie, bo złożoność problemu szukania równowag w grach
dwumacierzowych nie jest znana. Nie jest nawet pokazane, że problem policzenia jednej z
równowag w grze dwumacierzowej jest NP-zupełny. Istnieją tylko rezultaty tego rodzaju
dotyczące szukania równowag o pewnych zadanych własnościach (np. równowag, które są
najlepsze dla któregoś z graczy).

22

Uwaga 1.8 Inną wadą algorytmu Lemke-Howsona jest to, że nie znajduje on wszystkich
równowag Nasha. Jeśli rozpocznie się go w już znalezionej równowadze, można znaleźć
inną, ale nie ma gwarancji, że tą drogą znajdzie się wszystkie równowagi (któreś mogą zo-
stać pominięte). Problem w tym, że nie są znane algorytmy, które efektywnie (nawet jeśli
za kryterium efektywności przyjąć średni czas znalezienia równowagi dla gry o zadanym
rozmiarze) znajdywałyby wszystkie równowagi w zadanej grze. Te, które są znane, są w
mniejszym lub większym stopniu zbliżone do algorytmu używanego przez nas na ćwicze-
niach, polegającego na przeszukiwaniu po kolei wszystkich możliwych nośników strategii
graczy, po odrzuceniu strategii silnie zdominowanych.

1.3.3

Gry n-osobowe

To już końcówka wykładu, i powiem tylko kilka słów na temat algorytmów szukania rów-
nowag w grach z większą liczbą graczy. Podobnie jak w przypadku gier dwumacierzowych,
można pokazać, ze ten problem da się sprowadzić do nieliniowego analogonu LCP, tzn.
problemu znalezienia z takiego, że:

z ­ 0,

f (z) ­ 0,

z

j

f

j

(z) = 0

j = 1, . . . , n,

gdzie f jest pewną funkcją o wartościach z R

n

(niekoniecznie liniową). To nie jest banalny

problem, i jakkolwiek istnieją algorytmy dla gier n-osobowych oparte na tym spostrzeżeniu
(niektóre z nich są uogólnieniami algorytmu Lemke-Howsona – te powstały na początku lat
siedemdziesiątych), tyle że akurat te algorytmy są bardzo trudne do zaimplementowania
(w swoim opracowaniu na temat algorytmów szukania równowag McLennan i McKelvey [3]
piszą nawet, że nie słyszeli o tym, żeby ktoś te algorytmy zaimplementował). W związku z
tym stosuje się inne podejście – mianowicie, jak pokazaliśmy na jednym z wcześniejszych
wykładów, problem szukania równowagi w grze jest równoważny (właściwie pokazaliśmy
tylko wynikanie w jedną stronę, ale przwdziwe jest w obie) pewnemu problemowi szukania
punktu stałego. W związku z tym do szukania równowag w grach n-osobowych stosuje się
algorytmy szukania punktu stałego funkcji ciągłej na zbiorze zwartym. Najbardziej znanym
algorytmem tego rodzaju jest algorytm Scarfa. Większość innych jest jego modyfikacjami.
Osoby zainteresowane tym, jak wygląda algorytm Scarfa zastosowany do szukania równo-
wag w grach n-osobowych, odsyłam do wspomnianej pracy McLennana i McKelveya [3]

23

Bibliografia

[1] I.L. Glicksberg, A further generalization of the Kakutani fixed point theorem with

application to Nash equilibrium points, Proceedings of the American Mathematical
Society 3 (1952) 170–174.

[2] K. Kuratowski, Wstęp do teorii mnogości i topologii, PWN, Warszawa, 2004 (któreś

wydanie).

[3] R.D. McKelvey, A. McLennan, Computation of equilibria in finite games. Handbook of

Computational Economics, Elsevier, 1996, vol. 1, pp 87-142.

[4] B.

von

Stengel,

R.

Savani,

Exponentially

many

steps

for

finding

a

Nash

equilibrium

in

a

bimatrix

game.

Proc.

of

FOCS

2004

(też

http://www.maths.lse.ac.uk/Personal/stengel/TEXTE/focs04.pdf).

[5] N. Vieille, On equilibria on the square, International Journal of Game Theory 25 (1996)

199–205.

24