Vyjednávací protokol

Vyjednáváním (negociacemi) v multiagentních systémech chápeme snahu agentů dosáhnout vzájemné shody během řešení určité úlohy či plnění společných cílů. Konkrétním tématem vyjednávání může být rozdělení úkolů, rozdělení podílů ze zisku, řešení konfliktu sdílených zdrojů či koordinace týmu. Nedílnou součástí vyjednávání je vyjednávací (negociační) protokol, který specifikuje možný počátek a ukončení vyjednávání, i množinu možných odpovědí na přijaté zprávy v průběhu vyjednávání. Vyjednávací protokol dále poskytuje restrikce na možný průběh negociací, avšak neurčuje přesnou posloupnost kroků ve vyjednávacím procesu (tedy přesně nedeterminuje, jak konkrétně se vyjednávání bude vyvíjet). Přesný průběh i výsledek vyjednávání je dále závislý na prostoru možných řešení (negociační množina) a vyjednávací strategii účastníků. Předpokládáme, že vyjednávání agentů splňuje tři důležité předpoklady: komunikace funguje oboustranně, každá strana vyhodnocuje přijaté informace z vlastního úhlu pohledu a konečná dohoda je dosahována společným výběrem.

Vlastnosti vyjednávacího protokolu

Vyjednávací protokol může být posuzován na základě několika různých kritérií. Je poté na designerovi systému, aby zvolil takový protokol, který bude nejlépe vyhovovat v dané situaci důležitým kritériím:

• Social Welafare: toto kritérium sleduje celkový součet užitků všech agentů vyplývající z výsledku vyjednávání.
• Pareto efektivnost: výsledek vyjednáváni je Pareto efektivní (či Pareto optimální), pokud neexistuje jiný možný výsledek vyjednávání, který by zvýšil užitek některého z agentů, aniž by snížil užitek jiného.
• Individuální racionalita: vyjednávací protokol je pro agenta individuálně racionální, pokud výsledný užitek agenta není nižší než kdyby se agent jednání neúčastnil. Vyjednávací mechanismus by měl být individuálně racionální pro všechny agenty. V opačném případě by se totiž kompetitivní (nekooperativní) agenti jednání vůbec neúčastnili.
• Stabilita: systém je stabilní například v případě, kdy pro všechny agenty existuje dominantní strategie – kdy se agent chová podle dané strategie nezávisle na ostatních. V některý případech jde však kritérium Pareto efektivnosti a Stability proti sobě, příkladem může být Vězňovo dilema, kdy dominantní strategií je nekooperovat zatímco Pareto efektivní by bylo kooperovat.
• Výpočetní náročnost: toto kritérium sleduje, jak dlouho trvá proces vyjednávání, než agenti dosáhnou nějakého rozhodnutí. Z praktického hlediska je samozřejmě výhodné, aby byl proces vyjednávání výpočetně co nejméně náročný.
• Distribuovanost a efektivnost komunikace: distribuovanost zamezuje ztroskotání jednání na jednom bodě a tedy zvyšuje pravděpodobnost dosažení výsledku vyjednávání. Na druhé straně je výhodné, pokud k dosažení cíle vyjednávání postačuje co nejméně komunikace. Tyto dvě kritéria jdou tedy částečně proti sobě.

Skupiny vyjednávacích protokolů dle typu vyjednávání

• 1-to-1 vyjednávání: druh vyjednávání, kdy se shodu snaží nalézt skupina dvou agentů. Většina technik pro tento typ vyjednávání je založena na variacích MCP protokolu (Monotonic concession protocol)
• 1-to-many vyjednávání: zde se jeden agent snaží dosáhnout shody se skupinou agentů. Idea je taková, že samostatného agenta chápeme jako „žadatele“, který poptává určitou službu a ze skupiny agentů vybírá nejlevnějšího „poskytovatele“ této služby. Vyjednávací protokoly pro tento druh vyjednávání jsou často založeny na variacích CNP protokolu (contract net protocol), který vychází z typu aukce zvané obálková metoda. Existují také rozšíření CNP protokolu – ECNP (extended contract net protocol) a PAP (provisional-agreement-protocol). Dále se pro tento typ vyjednávání používají protokoly založené na dalších typech aukcí, jako jsou: Vickreyova aukce, Holandská aukce, Anglická aukce
• Many-to-many vyjednávání: v tomto případě mají vyjednávací protokoly za cíl nalézt shodu mezi skupinou agentů. Možné přístupy jsou založené na agregaci 1-to-1 vyjednávacích metod nebo na opakovaném použití 1-to-many vyjednávacích metod. Posledně jmenovaný přístup byl použit např. v telekomunikacích pro vyrovnávání zatížení sítě operátory (v tomto případě je každý agent ve smyslu CNP protokolu zároveň „žadatelem“ i „poskytovatelem“). Vedle těchto dvou přístupů se používá celá řada postupů založených na systému voleb, tj. volební protokol.

Bližší popis některých protokolů

Monotonic concession protocol

V rámci tohoto protokolu se agenti střídají ve vzájemném předkládání svých nabídek. Současně dodržují pravidlo, že každá nabídka je pro druhého agenta o něco výhodnější než ta předešlá. Každý agent začíná s nabídkou, která je pro něj nejlepší (má z ní nejvyšší užitek). Pokud agent obdrží nabídku, z které má vyšší užitek než by měl ze své vlastní nabídky, nabídku druhého agenta přijme a vyjednávání končí. Pokud agent nabídku nepřijme, musí dát protinávrh, který navyšuje užitek druhého agenta minimálně o předem zvolené ε. Ve chvíli, kdy ani jeden z agentů nepošle novou nabídku, vyjednávání končí neúspěchem. Výhodou tohoto protokolu je, že agent lehce vidí, zda ten druhý dodržuje daný protokol – pokud by agent obdržel nabídku, která pro něj znamená nižší užitek než v minulém kole, znamená to jednoznačně, že druhý agent protokol porušil. Dalším kladem tohoto protokolu je, že garantuje konec vyjednávání.

Mezi nevýhody tohoto protokolu patří jeho časová neefektivita, jelikož vyjednávání může být relativně pomalé. Závisí to na počtu možných výsledků vyjednávání a na zvolené hodnotě ε. Nutnou podmínkou implementace tohoto algoritmu je navíc to, že oba agenti musí znát své užitkové funkce. To je však v praxi poměrně vzácné, tedy se tato podmínka obchází tím, že předpokládáme hru s nulovým součtem a agent poté používá pouze vlastní užitkovou funkci.

Pro tento druh vyjednávání existuje speciální strategie zvaná Zeuthenova strategie, která specifikuje, za jakých podmínek je pro agenta výhodnější nabídku přijmout a kdy ji odmítnout resp. dát protinávrh. Je dokázáno, že pokud se oba agenti řídí Zeuthen strategií, jejich vyjednávání je konečné a výsledkem je Nashova rovnováha.

Protokol kontrakční sítě (contract net protocol)

Schéma fungování protokolu kontrakční sítě

V kontrakční síti má každý agent buď roli zadavatele nebo dodavatele (jsou možná i jiná označení zachovávající tuto logiku vztahu agentů). Zadavatel má úlohu (úkol), kterou si chce nechat vyřešit někým z dodavatelů. Za to je ochoten zaplatit. Dle protokolu, zadavatel nejprve obeznámí dodavatele, že poptává danou službu (řešení úlohy) a očekává nabídky. Dodavatel, pokud má zájem, zašle nabídku ceny, za kterou je ochoten službu poskytnout. Zadavatel si jednu z nabídek vybere a zaplatí požadovanou cenu za poskytnutou službu.

Volební protokol (voting protocol)

Volební protokol je mechanismus, který určitým způsobem vyhodnocuje preference jednotlivých agentů vzhledem k množině alternativ volby. Výsledkem je funkce, která se nazývá social choice a měla by splňovat tyto požadavky:

1. Měla by existovat pro všechny možné vstupy (individuální preference)
2. Měla by být definována pro všechny volené alternativy.
3. Být antisymetrická a transitivní
4. Být Pareto-efektivní vzhledem ke všem preferencím
5. Nezávislost na nerelevantních alternativách (en:independent of irrelevant alternatives)
6. Žádný agent se nesmí dostat do role diktátora (to znamená, funkce nesmí ve svých výsledcích kopírovat preference jednoho z agentů)

Existuje však Arrow's Impossibility Theorem, který ukazuje, že žádná funkce social choice nemůže splňovat všech šest požadavků.

Nejvíce používaný volební protokol je pluralitní volební protokol, kdy každý agent má jednu možnost volby a je vybrána alternativa s největším počtem hlasů (tento protokol porušuje 5. výše uvedenou podmínku). Podobně funguje protokol, kdy agent může volit více alternativ a zvolena je opět ta s největším počtem hlasů. Dalším příkladem je binární protokol, kde je volena vždy jedna ze dvou alternativ, která poté postoupí do dalšího kola volby. Nevýhodou tohoto protokolu je, že výsledek volby závisí na výchozím rozdělení alternativ do párů. Tedy jiné výchozí párování může produkovat jiný výsledek volby. Populárním volebním protokolem je protokol Borda. Označme |O| počet všech alternativ. Potom pokaždé, kdy je alternativa nejvýše v něčím listu preferencí, obdrží |O| bodů. Za každé druhé místo obdrží |O| -1 bodů atd. Stejně tak jako v případě pluralitního protokolu, Borda protokol porušuje 5. podmínku.

Literatura

• KUBÍK, Aleš. Inteligentní agenty, tvorba aplikačního software na bázi multiagentových systémů. Brno: Computer Press, 2004. 

• PĚCHOUREK, Michal. Planning autonomous actions in multi-agent environment. Praha: České Vysoké učení technické v Praze, Fakulta elektrotechnická, 2009. (Anglicky) 

• WEISS, Gerhard. Multiagent systems, A modern approach to Distributed Artificial Intelligence. Massachusetts Institute of Technology: The MIT Press, 2000. 619 s. ISBN 0-262-23203-0. (Anglicky) 

Související články

• Multiagentní systém
• Paretovo optimum
• Contract net protocol
• Social choice theory
• Social choice and Individual Values
• Borda protocol
• IIA
• Zeuthen strategy
• Arrow's Impossibility Theorem