AL postup - AL procedure - Wikipedia

The AL postup je postup pro spravedlivé přiřazení položky mezi dvěma lidmi. Najde to přiřazení položky bez závisti podmnožiny položek. Výsledná alokace navíc je Pareto efektivní v následujícím smyslu: neexistuje žádná další alokace bez závisti, která by byla lepší pro jednu osobu a ne horší pro druhou osobu.

Postup AL poprvé publikovali Brams a Kilgour a Klamler.[1]Později to zobecnil Haris Aziz, aby se zabýval případem, kdy agenti mohou vyjádřit lhostejnost.[2]

Předpoklady

Postup AL vyžaduje u lidí následující předpoklady:

  • Každá osoba může hodnotit položky od nejlepšího po nejhorší (tj. Každá osoba může ohlásit přísné preferenční vztah na položkách).
  • Každá osoba má preferenční vztah na svazcích položek, který je kompatibilní s responzivní sada objednávky na zboží.

Požadavky

to je ne předpokládali, že lidé mohou na svazcích hlásit svůj preferenční vztah. Existuje mnoho balíčků a může být obtížné uvést pořadí u všech z nich.

Postup by proto měl vrátit alokaci, která je bez závisti každý relace preferencí, která je v souladu s hodnocením položky a se slabou aditivitou. Jinými slovy, postup by měl vrátit přidělení, které je nutně bez závisti (NEF).[3]:303

Předpokládejme, že dva lidé jsou Alice a George. Přidělení je NEF pro Alici pokud dojde k injekci F od Georgových předmětů k Aliciným předmětům, například pro každý předmět X přijatý Georgem, dává Alice přednost F(X) až X. Přidělení je NEF pro George pokud je symetrická vlastnost splněna. Přiřazení položky je NEF pokud je to NEF pro oba partnery. Všimněte si, že v úkolu NEF dostanou Alice a George stejný počet položek.

Prázdná alokace je samozřejmě NEF, ale je velmi neefektivní. Proto hledáme alokaci, která je „nejlepší“ ze všech alokací NEF. Volá se alokace NEF Pareto-efektivní pokud neexistuje žádná jiná alokace NEF, která by byla lepší pro jednu osobu a ne horší pro druhou osobu.

Postup BT

Na úvod zvažte následující jednoduchý postup dělení:

  • Položte všechny položky na stůl.
  • I když jsou na stole položky, postupujte takto:
    • Požádejte partnery, aby si vybrali svou oblíbenou položku ze všech položek na stole.
    • Pokud jsou možnosti odlišné, dejte každému partnerovi jeho oblíbený předmět a pokračujte.
    • Pokud jsou možnosti identické, odešlete vybranou položku na napadenou hromádku. Nebude přiděleno.

Tento postup vrací NEF alokaci. Je to velmi jednoduché, ale ne příliš efektivní, protože mnoho položek je vyřazeno na napadenou hromádku. Postup AL je o něco složitější, ale zaručuje, že napadená hromada není nikdy větší a může být menší než v případě BT.

Postup AL

Procedura AL funguje podobně jako procedura BT, ale před přesunem položky na napadenou hromádku se ji pokusí přidělit jednomu partnerovi a zároveň kompenzovat druhého partnera jinou položkou. Pouze pokud se to nepodaří, položka se odešle na napadenou hromádku.

Předpokládejme například, že existují čtyři položky (1, 2, 3, 4) a preference partnerů jsou:

  • Alice: 1> 2> 3> 4
  • George: 2> 3> 4> 1

Procedura BT dává 1 Alici a 2 Georgovi, protože jsou to jejich oblíbené a liší se. Poté si Alice i George vyberou 3, aby byly zahozeny. Poté si oba vyberou 4, takže se také zahodí. Konečná alokace je: Alice ← {1}, George ← {2}. Je to NEF, ale ne PE.

Procedura AL také začíná tak, že 1 dáte Alici a 2 Georgovi. Poté, místo toho, aby odhodil položku 3, je dána Alici a George je kompenzován položkou 4. Konečné přidělení je: Alice ← {1,3}, George ← {2,4}. Jsou to NEF a PE.

Oba postupy jsou manipulovatelné: partner může získat nahlášením nesprávných preferencí. Taková manipulace však vyžaduje znalost preferencí druhého partnera, takže je to v praxi obtížné.

AL postup s lhostejností

Původní postup AL zásadně závisí na předpokladu, že pořadí položek je přísné.

[2] zobecňuje tento postup na obecné pořadí s možnou lhostejností.

Reference

  1. ^ Brams SJ, Kilgour DM, Klamler C (1. února 2014). „Spravedlivá divize nedělitelných předmětů pro dva: Efektivní algoritmus bez závisti“ (PDF). Oznámení Americké matematické společnosti. 61 (2): 130. doi:10.1090 / noti1075.
  2. ^ A b Aziz, Haris (2015). "Zobecnění AL metody pro spravedlivé přidělení nedělitelných předmětů". Bulletin ekonomické teorie. 4 (2): 307–324. arXiv:1409.6765. doi:10.1007 / s40505-015-0089-1.
  3. ^ 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 )