výuka

10. přednáška (14. prosince 2005)

Mechanismus, ve kterém agenti předají své vstupy a výsledek je závazný pro všechny. Agenti mají preferenční uspořádání na možných výstupech V (asymetrické, tranzitivní). Výstupem by mělo být uspořádání nad V, které splňuje šest podmínek.

1. Existuje pro všechny možné vstupy.

2. Je definováno pro každé dva prvky z V.

3. Je asymetrické a tranzitivní.

4. Je stabilní.

5. Není závislé na nepodstatných změnách preferencí agentů.

6. Není diktátorské.

Takové uspořádání neexistuje. Obvykle se vynechávají podmínky 1, 3 a 5.

Protokol může být jednokrokový či vícekrokový (postupné hlasování) a může počítat s neupřímnými i upřímnými agenty (jejich preference odpovídají skutečnosti). Každý protokol, který umí implementovat funkci v nějaké rovnováze (dominanci, Nash, ...), lze převést na jednokrokový upřímný protokol v této rovnováze. Jestliže je však funkce upřímně implementovatelná v rovnováze dominantních strategií (a neklademe žádná omezení na preference agentů a počet výstupů je alespoň tři), jde o diktátorský protokol.

Obrana: Náhodný výběr, velká výpočetní složitost neupřímnosti, Clarkův daňový mechanismus.

Pluralitní hlasování: Všechny možné výstupy soupeží najednou. Binární hlasování: Vybírá se lepší vždy ze dvou možných výstupů (pavouk) — záleží na uspořádání výstupů.

Bordův protokol: Prvky preferencí agentů ohodnotíme sestupně přirozenými čísly (poslední má 1 bod), a sečteme sumy přes všechny agenty.

Čtení

V. Conitzer, T. SandholmUniversal Voting Protocol Tweaks to Make Manipulation Hard

The Problem With Voting