Zagadnienia

14.1 Wprowadzenie
14.2 Aksjomatyczny model przetargu Nasha (schemat arbitrażowy Nasha)
14.3 Aksjomaty Nasha
14.4 Uwagi o strategicznym modelu przetargu

14. Przetargi

14.1. Wprowadzenie

Przetargi (ang. bargaining) formalizują sytuacje w których nie ma zgody co do akcji które powinni podjąć gracze by uzyskać jak najlepszy wynik i możliwe są negocjacje pomiędzy graczami. Wynikiem może być np. podział zysku między właściciela i pracowników, podział różnicy między ofertą sprzedawcy i kupującego.

Istnieją dwa zasadnicze podejścia do problemu przatargu.

1. Model aksjomatyczny (normatywny, statyczny): wynik przetargu (chciałoby się by był określony jednoznacznie) jest rezultatem spełnienia możliwie rozsądnych aksjomatów. Model taki nie opisuje procedury przetargowej, czyli reguł i przebiegu negocjacji, a jedynie analizuje możliwe wyniki, uwzględniające możliwe akcje graczy i ich preferencje, i na podstawie ustalonych aksjomatów daje jednoznacznie określone rozwiązanie.

2. Model strategiczny (dynamiczny): wynik przetargu jest konsekwencją ciągu sekwencyjnie składanych ofert. W standardowej, podstawowej wersji taki model jest opisany pewną grą ekstensywną z doskonałą informacją.

W tym rozdziale bedziemy zajmować się głównie modelem aksjomatycznym. Opiszemy procedurę (zestaw aksjomatów) która każdemu zbiorowi możliwych ”wyników” stosowania różnych akcji przez graczy przyporządkowuje dokładnie jeden wynik, który będziemy nazywać rozwiązaniem przetargu.

Uwaga 14.1

W szczególności wymaga się by nie istniał taki wynik gry który byłby lepszy od zaproponowanego (wynegocjowanego) dla conajmniej jednego gracza i nie gorszy dla wszystkich (innych) graczy (Pareto-optymalność). Nie może też być wynegocjowany wynik gry który conajmniej jednemu graczowi daje wypłatę niższą niż gdyby nie brał udziału w negocjacjach.

Załóżmy że oddają decyzję dotyczącą tego co ma być grane, tzn. jakie strategie i jaki ma być wynik (wypłata) każdego gracza, w ręce arbitra. Jakimi regułami powinni się kierować gracze i arbiter by istniał taki wynik i był jednoznaczny?

14.2. Aksjomatyczny model przetargu Nasha (schemat arbitrażowy Nasha)

N=2 graczy może się porozumieć lub nie. Niech X oznacza pewien zbiór, nazywany zbiorem możliwych wyników, porozumień graczy, D - zbiór jednoelementowy, oznaczający brak porozumienia, ui:X∪D→R,i=1,2 - funkcja wypłat gracza i. X generuje zbiór par wypłat

v1,v2:vi=ui⁢x,x∈X,i=1,2.

(14.1)

Elementy tego zbioru to możliwe do wynegocjowania wypłaty graczy. Dodatkowo zbiór D generuje parę wypłat d=(d1,d2)=(u1(d~),u2(d~)): d~∈D (jest to jedyny element D).

Powyższy zbiór obiektów precyzuje pewną sytuację przetargową <N,X,D,(ui),i∈N>.

Będziemy chcieli każdej takiej sytuacji przetargowej jednoznacznie przyporządkować parę wypłat, którą będziemy nazywać rozwiązaniem zagadnienia przetargu.

Definicja 14.1

Przetarg jest to para U,d taka że

1.⁢U⊂R2 – zbiór możliwych wyników przetargu (wypłat graczy).

2. d=d1,d2∈U. Jeśli d nazwiemy brakiem zgody to brak zgody jest możliwym wynikiem przetargu.

3. ∃v1,v2∈U:v1>d1,v2>d2 – istnieje wynik przetargu lepszy od braku zgody.

4. U jest wypukły i zwarty w R2.

Przetarg możemy identyfikować z wypukłym i zwartym zbiorem U⊂R2 z wyróżnionym punktem d:∃(v1,v2)∈U:vi>di,i=1,2.

Zwartość pociąga w szczególności ograniczoność wypłat.

d∈U oznacza że niezgoda, brak porozumienia, daje graczom także pewne wypłaty.

vi>di,i=1,2 zapewnia że istnieje inny wynik niż niezgoda, lepszy dla obojga graczy niż niezgoda.

Niech B oznacza zbiór wszystkich przetargów.

Definicja 14.2

Schemat arbitrażowy jest to funkcja f:B→U⊂R2.

Schemat arbitrażowy przyporządkowuje każdemu przetargowi U,d pewien element zbioru U. Ten element nazywamy rozwiązaniem przetargu U,d.

Oczywiście takich schematów jest ”bardzo wiele”. J.F. Nash zaproponował cztery akceptowalne aksjomaty które implikują jednoznaczność schematu arbitrażowego.

14.3. Aksjomaty Nasha

I. Aksjomat optymalności Pareto.

Niech U,d – przetarg, v1,v2∈U,v1′,v2′∈U. Jeżeli v1>v1′,v2>v2′, to v1′,v2′∉f⁢U,d, tzn. v1′,v2′ nie może być rozwiązaniem przetargu U,d.

II. Aksjomat symetrii.

Definicja 14.3

Przetarg U,d jest symetryczny jeżeli d1=d2 oraz v1,v2∈U⇔v2,v1∈U.

Jeżeli U,d jest symetryczny to f1⁢U,d=f2⁢U,d, gdzie f=f1,f2 jest schematem arbitrażowum.

Interpretacja: Jeżeli gracze są nierozróżnialni, to rozwiązanie przetargu musi dać każdemu z nich taką samą wypłatę.

III. Aksjomat niezmienniczości względem afinicznych transformacji wypłat.

Niech v1*,v2* będzie rozwiązaniem przetargu U,d, niech ai>0,bi>0,i=1,2. Zdefiniujmy drugi przetarg U′,d′:

U′=a1⁢v1+b1,a2⁢v2+b2:v1,v2∈U,

oraz stałe di′:=ai⁢di+bi,i=1,2.

Wtedy rozwiązaniem przetargu U′,d′:d′=d1′,d2′ jest para wypłat a1⁢v1*+b1,a2⁢v2*+b2.

Inaczej mówiąc, równość

f⁢U,d=v1*,v2*

implikuje równość

fi⁢U′,d′=ai⁢fi⁢U,d+bi,⁢⁢fi⁢U,d=vi*,⁢⁢i=1,2.

Przykład 14.1

d=0,0,a1=2,a2=1,b1=b+2=0

IV. Aksjomat niezależności od nieistotnych alternatyw.

Niech U,d,U′,d′ przetargi t. że U′⊂U. Niech v*=v1*,v2*–rozwiązanie przetargu U,d, oraz niech v*∈U′, tzn. f⁢U,d∈U′. Wtedy v* jest rozwiązaniem przetargu U′,d′, tzn. f⁢U,d=f⁢U′,d′.

Interpretacja: Jeżeli ”zawęzimy” przetarg nie usuwając pierwotnego rozwiązania przetargu, to pozostaje ono rozwiązaniem przetargu z zawężonym przetargu.

Komentarze do aksjomatów.

I: Gracze nie zgadzają się na rozwiązanie gorsze dla obojga.

II. Jeżeli gracze są nierozróżnialni to rozwiązanie przetargu musi dać każdemu z nich taką samą wypłatę.

III. Oba rozwiązania przetargowe ”reprezentują tę samą sytuację”.

IV. Kalai i Smorodinsky zaproponowali w 1975 roku inny schemat arbitrażowy, nie spelniający aksjomatu IV. Omówienie tego schematu i przykłady można znależć np. w monografii Straffina.

Twierdzenie (ważne) 14.1

Istnieje dokłądnie jeden schemat arbitrażowy fN:B⇒R2 spełniający aksjomaty I-IV. Przyporządkowuje on każdemu przetargowi U,d rozwiązanie przetargu będące rozwiązaniem zagadnienia maksymalizacji:

m⁢a⁢xd1,d2≤v1,v2∈U⁢v1-d1⁢v2-d2.

Inaczej:

fN⁢U,d=a⁢r⁢g⁢m⁢a⁢xd1,d2≤v1,v2∈U⁢v1-d1⁢v2-d2.

Uwaga: fN ma dwie współrzedne.

Definicja 14.4

Schemat arbitrażowy z powyższego twierdzenia nazywamy rozwiązaniem przetargowym Nasha.

Krok 1: fN jest dobrze określona: zbiór v∈U:vi≥di,i=1,2 jest zwarty, funkcja H:U⇒R:⁢H⁢v1,v2:=v1-d1⁢v2-d2 jest ciągła, więc istnieje jednoznaczne rozwiązanie problemu maksymalizacji definiującego fN. Jest ono jedyne, gdyż:

1. H jest ściśle quasi–wklęsła na v∈U:vi≥di,⁢⁢i=1,2

2. ∃v∈U:vi>di,i=1,2

3. U jest wypukły.

Krok 2: fN spełnia aksjomaty I-IV:

III: Niech U,d,U′,d′–jjak w aksjomacie I. Wtedy

v′∈U′⇔∃v∈U:vi′=aivi+bi,i=1,2.

Ponieważ

v1′-d1′⁢v2′-d2′=a1⁢a2⁢v1-d1⁢v2-d2,

więc v1*,v2*=fN⁢U,d maksymalizuje prawą stronę ostatniej równości po U wtedy i tylko wtedy gdy a1⁢v1*,a2⁢v2*+b2=fN⁢U′,d′ maksymalizuje lewa stronę po U′.

II: Niech U,d–przetarg symetryczny. Niech v1*,v2* maksymalizuje funkcję H po zbiorze U. Ponieważ H jest funkcją symetryczną, więc również v2*,v1* maksymalizuje H po U. Z jednoznaczności maksymizera v1*,v2*=v2*,v1*.

IV: Niech U′⊂U. Jeżeli v′∈U′ maksymalizuje H po U, to tym bardziej po U′.

I. Niech v∈U,v′∈U:vi>vi′,i=1,2. Ponieważ H jest rosnąca w każdym swoim argumencie, więc v′ nie może maksymalizować H.

Pokażemy jednoznaczność fN. Niech f–rozwiązanie przetargu spełniające aksjomaty I-IV.

Krok I.

Niech fN⁢U,d=z1,z2. Ponieważ istnieje s1,s2∈U:si>di,i=1,2, więc zi>di,i=1,2. Niech U′,d′–przetarg otrzymany z U,d przez taką transformację si⟶ai⁢si+bi,i=1,2 która przeprowadza punkt d do 0,0 a rozwiązanie fN⁢U,d do 1/2,1/2 (można policzyć). Ponieważ f i fN spełniają aksjomat III, więc

fi⁢U′,0=ai⁢fi⁢U,d+⁢bi,⁢⁢fIN⁢U′,0=ai⁢fiN⁢U,d+bi,⁢i=1,2.

Stąd

fN((U,d))=f((U,d)⇔fN((U′,0))=f((U′,0)).

Ponieważ fN⁢U′,0=1/2,1/2, więc wystarczy pokazać że f⁢U′,0=1/2,1/2. Wykażemy to w krokach II-V.

Krok II.

Stwierdzenie 14.1

U′ nie zawiera punktów (v1′,v2′) t. że v1′+v2′>1.

W przeciwnym przypadku niech

t1,t2:=12⁢1-ϵ+ϵ⁢v1′,12⁢1-ϵ+ϵ⁢v2′

(14.2)

U′ jest wypukly, więc t1,t2∈U′ jako wypukla kombinacja liniowa punktów 12,12 i (v1′,v2′). Dla dostatecznie małego ϵ łatwo sprawdzić że t1⁢t2>14.

W ten sposób znależliśmy punkt (t1,t2)∈U′ taki że t1-0⁢t2-0>14, podczas gdy wiadomo że maksimum iloczynu współrzednych punktów w U′ (pamietajmy że di′=0) jest realizowane przez parę 12,12, co kończy dowód Stwierdzenia.

∎

Krok III. Ponieważ U′ jest ograniczone, więc z kroku II wynika istnienie prostokata T, symetrycznego względem prostej v1=v2, zawierającego U′, na którego brzegu jest punkt 12,12. Otaczamy U′ prostokatem mającym z U′ tylko jeden punkt wspólny: fN⁢U′,0.

Krok IV.

f⁢T,0=12,12, gdyż z aksjomatu II obie współrzędne rozwiązania przetargowego muszą być takie same (tzn. leżeć na prostej v1=v2, a z aksjomatu I wynika że nie mogą leżeć wewnątrz T na tej prostej. Z aksjomatu IV mamy

f(U′0)=f(T,0)=(12,12).

∎

Ćwiczenie 14.1

Sprawdzić że para U′,d1′,d2′ z Aksjomatu II Nasha jest przetargiem.

Ćwiczenie 14.2

Niech U∈R2–czworokąt o wierzchołkach A=(0,0),B=((2,0),c=(4,2),D=(1,5), niech d=2,1). Znależć rozwiązanie przetargu U,d.

Rozwiązanie: Niech N–odcinek prostej przechodzącej przez C⁢i⁢D o wspołrzędnej x∈2,4. Szukamy (x,y)∈N: maksymalizującego iloczyn x-2⁢y-1. Otrzymujemy xm⁢a⁢x=7/2,ym⁢a⁢x=5/2.

Interpretacja: 2 graczy wybiera wyniki A,B,C,D, każdy z pewwnym prawdopodobieństwem: dokładniej, każdy wybiera pewną loterię na A,B,C,D. Jeśli nie uzgodnią wyboru loterii dostają d=2,1. Schemat arbitrażowy Nasha daje loterię 5/2⁢C+1/6⁢D, która daje wypłaty

u1=56⁢4+16⁢1=7/2,⁢⁢u2=56⁢2+16⁢5=5/2.

Uwaga 14.2

Punkty wewnatrz wieloboku nie mogą być rozwiązaniem przetargu, a więc loteria na nich daje zero.

Uwaga 14.3

Przykład zastosowania schematu arbitrażowego Nasha do (teoretycznej) sytuacji negocjacyjnej pomiędzy pracodawcą a pracownikami można znaleźć w [36] (rozdział 17). Jednakże, jak stwierdza autor w ostatnim akapicie, ”…Niestety nie jest mi znany żaden rzeczywisty przypadek zastosowania schematu arbitrażowego Nasha do mediacji w sporze pomiędzy pracodawcami a pracownikami…” . Kwestia możliwych zastosowań schematu Nasha i związanych z nim trudności jest omówiona w [24] (rozdział 16).

Przykład 14.2

Niech U-koło o promieniu R i środku w d=0,0. Dla każdej liczby rzeczywistej c {(v1,v2)∈U:(v1-d1)(v2-d2)=c jest hiperbolą. Rozwiązaniem zagadnienia maksymalizacji jest punkt R⁢2/2,R⁢2/2.

Przykład 14.3

f⁢U,d=d⁢⁢∀U,d spełnia aksjomaty II,III, IV, ale nie spełnia I.

14.4. Uwagi o strategicznym modelu przetargu

Strategiczne (dynamiczne) modele przetargu zakładają możliwość składania i odrzucania ofert, propozycji znalezienia ”rozwiązania” przez graczy. Model ze skończoną liczbą możliwych ofert został zaproponowany przez I. Staehla w monografii [35]. A. Rubinstein zaproponował w 1982r istotne rozszerzenie tego modelu na continuum ofert [30, 29].

W modelu przetargu Rubinsteina–Staehla dwóch graczy muszą zgodzić się na podział tortu o wielkości 1. Podstawowa wersja modelu jest następująca. Czas jest dyskretny. W parzystych chwilach czasu (poczynajac od t=0) gracz 1 proponuje podział x,1-x, który gracz 2 może zaakceptować lub nie. W pierwszym przypadku gra się kończy, w drugim gracz 2 proponuje 1 podział y,1-y (y niekoniecznie musi być różne od x), który gracz 2 może zaakceptować lub nie. W pierwszym przypadku gra się kończy, w drugim gracz 1 proponuje 2 kolejny podział itd. Jeżeli podział jest zaakceptowany w chwili t=0,1,…, to wypłaty graczy mają postać δ1t⁢x,δ2t⁢1-x, gdzie gracz 1 otrzymuje część x tortu, a 2 1-x, δi są czynnikami dyskontowymi (tort schnie z czasem). Z punktu widzenia taksonomii gier można ten model opisać jako grę ekstensywną z contimuum ofert, z nieskończonym horyzontem czasowym i doskonałą informacją. Gra ma nieskończenie wiele równowag Nasha, ale przy pewnych dodatkowych założeniach ma tylko jedną równowagę doskonałą. WMożna też pokazać że w określonych sytuacjach granicznych rozwiązania tego modelu pokrywają się z rozwiązaniem schematu arbitrażowego Nasha.

Omówienie przetargu Rubinsteina–Staehla można znależć np. w monografiach [6, 14].

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Wstęp do Teorii Gier