Sekvence vychystávání - Picking sequence

A sekvence vychystávání je protokol pro spravedlivé přiřazení položky. Předpokládat m položky musí být rozděleny mezi n agenti. Jedním ze způsobů přidělení položek je nechat jednoho agenta vybrat jednu položku, poté nechat jiného agenta vybrat jednu položku atd. Vychystávací sekvence je sekvence m jména agentů, kde každé jméno určuje, který agent je další, kdo vybere položku.

Předpokládejme například, že 4 položky musí být rozděleny mezi Alici a Boba. Některé možné vychystávací sekvence jsou:

  • AABB - Alice vybere dvě položky a potom Bob vybere dvě zbývající položky.
  • ABAB - Alice vybere jednu položku, pak Bob vybere jednu položku, pak znovu Alice, pak znovu Bob. To je „spravedlivější“ než AABB, protože Bobovi to dává větší šanci získat lepší předmět.
  • ABBA - Alice vybere jednu položku, poté Bob vybere dvě položky, pak Alice obdrží zbývající položku. To je intuitivně ještě „spravedlivější“ než ABAB, protože v ABAB je Bob vždy za Alicí, zatímco ABBA je vyváženější.[1]

Výhody

Výběrová sekvence má několik výhod jako protokol spravedlivého rozdělení:[2]:307

  • Jednoduchost: pro agenty je velmi snadné pochopit, jak protokol funguje a co by měli dělat v každém kroku - stačí vybrat nejlepší položku.
  • Ochrana osobních údajů: agenti nemusí prozrazovat celou svou oceňovací funkci nebo dokonce celé hodnocení. Musí v každém kroku pouze odhalit, která položka je pro ně nejlepší.
  • Nízký složitost komunikace: vyžaduje pouze m zprávy, z nichž každý obsahuje číslo mezi 1 a m, takže celková složitost je .

Maximalizace blahobytu

Jak by měla být vybrána sekvence vychystávání? Bouveret a Lang[3] prostudujte tuto otázku za následujících předpokladů:

  • Každý agent má aditivní utilita funkce (to znamená, že položky jsou nezávislé zboží ).
  • Agenti mohou mít různé položky u položek, ale je to společné bodovací funkce který mapuje pořadí na peněžní hodnoty (např. pro každého agenta má jeho nejlepší položka x dolarů, jeho druhá nejlepší položka má hodnotu y dolarů atd.).
  • Alokátor nezná hodnocení agentů, ale ví, že všechna hodnocení jsou náhodná losování od daného rozdělení pravděpodobnosti.
  • Cílem alokátoru je maximalizovat očekávaná hodnota některých funkce sociálního zabezpečení.

Ukazují vychystávací sekvence, které maximalizují očekávané utilitaristický welfare (součet utilit) nebo očekávané rovnostářské welfare (minimum utilit) v různých nastaveních.

Kalinowski a kol[4] ukázat, že když existují dva agenti s a Borda skórovací funkce a každé hodnocení je stejně pravděpodobné, sekvence „round robin“ (ABABAB ...) dosahuje maximálního očekávaného součtu utilit.[2]:308

Spravedlnost s různými nároky

Brams a Kaplan[5] prostudovat problém přidělování ministerstev mezi strany. Existuje koalice stran; každá strana má v parlamentu jiný počet křesel; větším stranám by mělo být přiděleno více ministerstev nebo prestižnějších ministerstev. Toto je zvláštní případ spravedlivé přiřazení položky s různými nároky. Možným řešením tohoto problému je určit sekvenci vychystávání na základě různých oprávnění a nechat každou stranu vybrat ministerstvo. Takové řešení se používá v Severním Irsku, Dánsku a Evropském parlamentu.[6]

Brams předpokládá, že každý agent má přísné pořadí položek a má responzivní preference na svazcích položek. To znamená, že v každém bodě vychystávací sekvence existuje jediná zbývající položka, která je pro agenta „nejlepší položkou“. Je volán agent upřímný (pravdivý) pokud v každém bodě vybere svůj nejlepší předmět. Pokud mají agenti úplné informace o svých preferencích (jak je mezi stranami běžné), nemusí být racionální volit pravdivě; může být pro ně lepší sofistikovaný (strategický) volby. Sekvence vybírání tedy indukuje a sekvenční hra a je zajímavé analyzovat jeho dokonalá rovnováha subgame. Je prokázáno několik výsledků:

  • Se dvěma agenty vedou jak pravdivá, tak strategická rozhodnutí Pareto efektivní alokace. Tato hra navíc je monotóní v následujícím smyslu: agent je vždy na tom lépe, pokud je zlepšena jedna nebo více jeho pozic v sekvenci (např. Alice je na tom lépe v sekvenci ABBA než v BABA). Obě vlastnosti jsou u tří nebo více agentů stále pravdivé, pokud se rozhodnou pravdivě.
  • Se třemi nebo více agenty, kteří provádějí strategická rozhodnutí, může vybírací sekvence vést k neefektivní alokaci (tj. Dokonalá rovnováha subgame nemusí být Pareto-efektivní).
  • Se třemi nebo více agenty, kteří dělají strategická rozhodnutí, by hra mohla být nemonotónní, tj. agent by se mohl zhoršit tím, že vybere dříve v pořadí.[5]:210–212
  • Pro dva agenty existuje jednoduchá modifikace vychystávací sekvence, která je a pravdivý mechanismus - pravdivý výběr položek je dominantní strategií. Proto existuje dokonalá rovnováha subgame, která je Paretova optimální, a hra je monotónní.

Určení sekvence vychystávání

Vzhledem k odlišným právům agentů, jaká by byla sekvence spravedlivého výběru? Brams[5]:202–206 navrhuje použít dělitelské metody, podobné těm, které se používají pro rozdělení kongresových křesel mezi státy. Dvě nejčastěji používané metody jsou ty, které navrhuje Daniel Webster a Thomas Jefferson. Obě metody začínají stejným způsobem:

  • Vypočítejte dělitel - součet nároků vydělený počtem položek (např. pokud je součet všech nároků 201 a existuje 15 položek ke sdílení, pak dělitel je 201/15).
  • Vypočítejte kvóta - zlomkový počet položek, na které má každý agent nárok. Toto je nárok dělený dělitelem (např. Pro agenta s nárokem 10 z 201 je kvóta 10 * 15/201 ~ 0,75 položek).

Konkurenční rovnováha

Sekvence PIcking lze použít k vyhledání alokací, které splňují silnou podmínku spravedlnosti a účinnosti konkurenční rovnováha.[7]

Viz také

The přidělení položky každý s každým protokol je speciální případ vychystávací sekvence, ve které je sekvence cyklická: 1, 2, ..., n, 1, 2, ..., n, ...

Reference

  1. ^ Steven Brams a Alan D. Taylor (1999–2000). „Řešení typu win-win: zaručení spravedlivých akcií všem. New York: W. W. Norton.
  2. ^ A b Sylvain Bouveret a Yann Chevaleyre a Nicolas Maudet, „Spravedlivé přidělení nedělitelného zboží“. Kapitola 12 v: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Příručka výpočetní sociální volby. Cambridge University Press. ISBN  9781107060432. (bezplatná online verze )
  3. ^ Obecný protokol bez přidělení nedělitelného zboží. doi:10.5591 / 978-1-57735-516-8 / ijcai11-024.
  4. ^ Postup postupného alokace optimálního sociálního zabezpečení. AAAI-13. 2013.
  5. ^ A b C Kapitola 9 v Steven J. Brams (2008). Matematika a demokracie: Navrhování lepších hlasovacích a spravedlivých postupů. Princeton, NJ: Princeton University Press. ISBN  9780691133218.. Převzato z Brams, Steven J .; Kaplan, Todd R. (2004). „Rozdělení nedělitelného“. Journal of Theoretical Politics. 16 (2): 143. doi:10.1177/0951629804041118.
  6. ^ O'Leary, Brendan; Grofman, Bernard; Elklit, Jorgen (2005). „Metody dělitele pro postupné přidělování portfolia ve výkonných orgánech více stran: důkazy ze Severního Irska a Dánska“. American Journal of Political Science. 49: 198–211. doi:10.1111 / j.0092-5853.2005.00118.x.
  7. ^ Segal-Halevi, Erel (2020-02-20). „Konkurenční rovnováha pro téměř všechny příjmy: existence a spravedlnost“. Autonomní agenti a multiagentní systémy. 34 (1): 26. doi:10.1007 / s10458-020-09444-z. ISSN  1573-7454.