Zeuthenova strategie

Zeuthenova strategie je vyjednávací strategií užívanou v multiagentních systémech. Smyslem je hodnocení ochoty riskovat konflikt. Agent bude více ochoten riskovat konflikt, pokud rozdíl užitku mezi jeho současným účelem a konfliktním řešením bude nízký. Když se Zeuthenova strategie použije oběma agenty v Monotonic concession protokolu, tak vede agenty k dohodě na řešení ve vyjednávací množině. Ta obsahuje všechna nekonfliktních řešení, která jsou individuálně racionální a pareto efektivní. Výsledkem je potom Nashova rovnováha. Pokud jeden agent používá Zeuthenovu strategii ostatní nemohou udělat lépe, než ji použít sami. Zeuthenova strategie je vhodná kdykoli, kdy je v multiagentních systémech cílem maximalizovat společenský užitek.

Princip

Zeuhenova strategie se používá ve vyjednávání v rámci Monotonic concession protokolu, který spočívá ve vzájemném předkládání nabídek mezi agenty, přičemž musí být dodrženo pravidlo, že každá další předkládaná nabídka musí být výhodnější než ta předešlá. Pokud agent obdrží nabídku ze které by měl větší užitek než z jeho vlastní, vyjednávání končí úspěchem. +more Pokud žádný z agentů novou nabídku nepošle, vyjednávání končí neúspěchem.

Zeuthenova strategie dále předpokládá, že agenti znají své vlastní užitkové funkce.

V rámci úvahy o strategií je možné položit si 3 otázky # Jaký by měl být první návrh agenta. # Kdo by měl v daném kole ustoupit. +more # Do jaké míry by měl agent ustoupit, v případě, že ustupuje.

Na první otázku je jednoduchá odpověď. Prvním návrhem by mělo být to nejvíce preferovanější řešení z hlediska užitku. +more Agent i hledá takový návrh \delta, který by maximalizoval jeho užitkovou funkci U.

: \delta(i,0)=\arg\max_{\delta\in{NS}}U_{i}(\delta)

Druhá otázka je rozpracována Zeuthenovou strategií pomocí ohodnocení ochoty agenta riskovat konflikt. Intuitivně bude agent ochoten více riskovat konflikt, pokud rozdíl v užitku mezi jeho současným návrhem a konfliktním řešením je nízký. +more Naproti tomu, když rozdíl mezi agentovým současným návrhem a konfliktním řešením je vysoký, agent očekává více ztrát z konfliktu a je proto méně ochoten ho riskovat. Proto bude agent více ochoten ustoupit.

Ochota agenta i riskovat konflikt v kole t je dána následujícím vztahem:

: \text{Riziko}(i,t)= \frac{\mbox{užitek agenta (i) ztracený ústupkem a přijetím nabídky agenta (j)}} {\mbox{užitek agenta (i) ztracený neustupováním a vzniklým konfliktem}}

Čitatel je ve skutečnosti definován jako rozdíl mezi užitkem agenta i v jeho současném návrhu a užitkem agenta i v návrhu agenta j. Jmenovatel je definován jako užitek návrhu agenta i. +more Dokud není dosaženo dohody, hodnota rizika se bude pohybovat mezi 0 a 1. Vyšší hodnota rizika (přibližuje se 1) ukazuje, že agent i má menší ztrátu z konfliktu a také je méně ochoten riskovat konflikt. Naopak, nižší hodnota rizika (přibližuje se 0) ukazuje, že agent i má více ztráty z konfliktu a také menší ochotu konflikt riskovat. Pak dostáváme vzorec:.

: \text{Riziko}(i,t)= \begin{cases} 1 & U_{i}(\delta(i,t))=0 \\ \frac{U_{i}(\delta(i,t))-U_{i}(\delta(j,t))}{U_{i}(\delta(i,t))} & \text{jinak} \end{cases}

Myšlenka přiřazování riziku hodnotu 1, pokud je užitek agenta i z jeho vlastní nabídky v kole t je roven nule, vyplývá z toho, že užitek současného návrhu agenta i je stejný jako konfliktní řešení. V tomto případě je agent i kompletně ochoten riskovat konflikt neustupováním.

Čím delší je vyjednávání, tím menší je ochota riskovat. Kdo v daném kole méně riskuje, měl by ustoupit, ale pouze tak, aby se riziko převážilo na druhého agenta.

Zeuthenova strategie přichází s tím, že by v kole t vyjednávání měl ustoupit ten agent, který hodnotí riziko jako nižší. Otázkou zůstává, o kolik by měl agent ustoupit.

Pokud budou oba agenti používat Zeuthenovu strategii, bude dosaženo Nashovy rovnováhy, a sice v bodě:

: \delta=\arg\max_{\delta'\in{NS}}\{\pi(\delta')\},

Dostatečný ústupek

Pokud by agent neustoupil dostatečně, v příštím kole by poměr rizika ukazoval, že může konfliktem stále dost ztratit. Proto by měl udělat nejmenší ústupek nezbytný ke změně poměru rizika. +more Tím bude další agent v příštím kole ustupovat.

Pokud agent A udělá dostatečný ústupek, tak, za předpokladu, že agent B používá racionální vyjednávací strategii, ustoupí agent B v příštím kroku, pokud tak neučiní již v kroku tomto. Množina všech dostatečných ústupků agenta A v kroku t je určena jako \text{SC}(A,t) . +more Minimální ústupek je pak takový ústupek, který leží na této množině a přináší maximální možný užitek.

: \delta'=\arg\max_{\delta\in{SC(A,t)}}\{U_{A}(\delta)\}

Důkaz

Nechť δA = δ(A,t). Nechť δB = δ(B,t). Podle Zeuthenovi strategie by měl agent A ustoupit v kole t za předpokladu, že nastane tato podmínka.

: Riziko(A,t)\leq Riziko(B,t).

To se stane právě pokud

: \frac{U_{A}(\delta_{A})-U_{A}(\delta_{B})}{U_{A}(\delta_{A})}\leq \frac{U_{B}(\delta_{B})-U_{B}(\delta_{A})}{U_{B}(\delta_{B})}

: U_{B}(\delta_{B})(U_{A}(\delta_{A})-U_{A}(\delta_{B}))\leq U_{A}(\delta_{A})(U_{B}(\delta_{B})-U_{B}(\delta_{A}))

: U_{A}(\delta_{A})U_{B}(\delta_{B})-U_{A}(\delta_{B})U_{B}(\delta_{B})\leq U_{A}(\delta_{A})U_{B}(\delta_{B})-U_{A}(\delta_{A})U_{B}(\delta_{A})

: -U_{A}(\delta_{B})U_{B}(\delta_{B})\leq -U_{A}(\delta_{A})U_{B}(\delta_{A})

: U_{A}(\delta_{A}) U_{B}(\delta_{A})\leq U_{A}(\delta_{B}) U_{B}(\delta_{B})

: \pi(\delta_{A})\leq \pi(\delta_{B})

Agent A tedy ustoupí (bud souhlasit s dohodou) právě tehdy, když jeho vlastní nabídka (\delta_{A}) nepřinese vyšší užitek, než nabídka agenta B.

To je důvod, proč strategie garantuje konečnou dohodu a maximalizaci Nashova produktu.

Průběh protokolu

Zeuthenova strategie použitá v Monotonic concession protokolu by odpovídala tomuto pseudokódu Průběh vyjednávání je zaznamenán z pohledu agenta A. V prvním kroku vypočítává agent A jeho preferovaný návrh, ve kterém by maximalizoval svůj užitek. +more V druhém kroku posílá svůj návrh a následně přijímá návrh agenta B. Pokud užitek agenta A z návrhu agenta B vyšší nebo roven užitku z jeho vlastního návrhu, tak přijímá návrh agenta B. V opačném případě se vykalkulují rizika pro oba agenty. Pokud je riziko agenta A nižší, tak bude ustupovat a musí propočítat takový návrh, který by změnil poměr rizik a navrhnout ho. V opačném případě ustupovat nemusí a čeká na zaslání nové nabídky agentem B. Proces se opakuje, dokud agenti nepřestanou posílat nové návrhy (i když se tato možnost ve strategii nepředpokládá je třeba brát ji v úvahu z důvodu technických nebo jiných neočekávaných okolností) nebo se nedohodnou. V situaci, kdy mají agenti shodná rizika, oba ustupují a zasílají novou nabídku. V tomto případě může ovšem nastat problém. (viz odstavec Problémy).

# \delta_{A} \gets \arg \max_{\delta} U_{A}(\delta)

# \mbox{Návrh}~\delta_{A}

# \mbox{Přijetí návrhu}~\delta_{B}

# \mbox{pokud}~U_{A}(\delta_{B}) \ge U_{A}(\delta_{A})

#: \mbox{tak}~\mbox{Přijmi}~\delta_{B}

# \mbox{Riziko}_{A} \gets \frac{U_{A}(\delta_{A})-U_{A}(\delta_{B})}{U_{A}(\delta_{A})}

# \mbox{Riziko}_{B} \gets \frac{U_{B}(\delta_{B})-U_{B}(\delta_{A})}{U_{B}(\delta_{B})}

# \mbox{pokud}~\mbox{Riziko}_{A}

#: \mbox{tak}~\delta_{A} \gets \delta_{A}' \mbox{takové, že}~\mbox{Riziko}_{A}(\delta_{A}') > \mbox{Riziko}_{B}(\delta_{B}')

#:: \mbox{jdi na}~2

# \mbox{jdi na}~3

Příklad

Grafické znázornění vyjednávání pomocí Zeuthenovy strategie Na obrázku je vidět grafický průběh vyjednávání Mezi agenty i a j. +more Na ose x je znázorněn užitek (U) a na ose y množina návrhů (\delta). Počátečními návrhy (krok 0) je \delta(i,0) = 0 pro agenta i a \delta(j,0) = 6 pro agenta j. Po úvodním návrhu agenti propočítávají svá rizika (hodnoty dle obrázku).

: Riziko(i,0) = \frac{5-(-1)}{5} = \frac{6}{5}

: Riziko(j,0) = \frac{4-0}{4} = 1

Agent j má menší hodnotu rizika a musí udělat ústupek. Nový návrh musí být takový, aby agent j nebyl nucen ustupovat i v příštím kole.

: Riziko_{i} = \frac{5-(5-\delta_{j}}{5}

: tedy \delta_{j}~

Ze vztahu plyne, že nabídka agenta musí být méně než 5. V tomto případě si agent pro další krok volí \delta(j,1) = 4,9.

Problémy

Předpokládejme, že v konečném kole vyjednávání oba agenti mají srovnatelné riziko.

: Riziko(A,t)~=~Riziko(B,t), kde t je poslední kolo vyjednávání

Zde by se podle strategie měli oba agenti ustoupit. Ve skutečnosti skrývá tento bod potenciální problém. +more Pokud jeden z agentů strategii poruší neustupováním, získá větší užitek na úkor druhého. Pokud by se takto zachovali oba agenti, nastane konfliktní situace. V tomto případě s jedná o typický případ hry na kuře popisovaný teorií her. Agenti, dle protokolu, volí své nabídky současně a tudíž se nemohou domlouvat. Rozhodují se buď to ustoupit nebo neustupovat. Jejich zájmem je zvolit zvolit protichůdnou možnost (neustoupení přináší větší užitek). Pokud jí ovšem zvolí oba, dojde ke konfliktu, což je nepřípustné pro oba agenty. Jedná se o nekooperativní a antikoordinační hru.

Konkrétní podoba rozhodování se agenta záleží na užitkových funkcích. Příkladem mohou být tyto hodnoty.

Situaci je v praxi možné řešit rozšířením strategie o „házení mincí“. Tedy libovolnou techniku, která náhodně určí, který z agentů by měl ustoupit. +more Teprve s tímto opatřením lze považovat strategii za stabilní a tedy vyhovuje pravidlu o Nashově rovnováze.

Dalším problémem je praktická použitelnost při velkém počtu zpracovávaných úloh. Množina možných řešení narůstá exponenciálně a výrazně znevýhodňuje použití Zeuthenovy strategie v reálných úlohách.

: Výpočetní složitost = O(2^

Reference

Kategorie:Umělá inteligence Kategorie:Robotika Kategorie:Informatika Kategorie:Multiagentní systémy