Úkol sdílet byt

Problém sdíleného nájemného [1] [2]  je druh problému spravedlivého sdílení , ve kterém musí být sdíleny nedělitelné předměty a pevná peněžní cena současně. V anglické literatuře má tento problém různé názvy, například Rental harmony , housemates problem [ 3] [4] a room- assign -rent-division [5] [ 6] [7] [8] .

Za typických podmínek existují partneři ochotní pronajmout si dům se sdílenou místností za cenu požadovanou pronajímatelem. Každý z partnerů má své preference – jeden preferuje velký pokoj, druhý může preferovat pokoj s výhledem na hlavní silnici a podobně. Současně by měly být vyřešeny následující dva problémy:

Existuje několik vlastností, které budeme vyžadovat, aby byly splněny.

Z absence závisti vyplývá Pareto efektivita. Důkaz: (rozporem) předpokládejme, že existuje alternativní přiřazení se stejným cenovým vektorem, které je jednoznačně lepší pro alespoň jednoho partnera. Pak při současné distribuci bude tento partner žárlit.

Problém sdílení bytu byl studován za dvou různých předpokladů o preferencích partnerů:

Kardinalita implikuje ordinalitu, protože vždy je možné sestavit preferenční vztah podle vektoru odhadů. Obyčejnost je obecnější předpoklad a méně psychicky zatěžuje partnery.

Řádová verze

Su: jedna osoba na pokoj

Protokol Francise Su uvádí následující předpoklady o preferencích partnerů:

  1. Dobrý dům : V každém členění nájemného je pro každou osobu přijatelný alespoň jeden balíček pokoj + poplatek.
  2. Minimální vnější vliv : Preferenční vztah závisí na pokoji a platbě, ale ne na výběru ostatních partnerů.
  3. Lakomý affiliate partneři : Všichni affiliate partneři mají rádi pokoje zdarma (nulový poplatek) ve srovnání s jakoukoli jinou místností.
  4. Topologicky uzavřená sada preferencí : Partner, který preferuje místnost pro cenovou posloupnost, preferuje tuto místnost také za mezní cenu.

Celkovou platbu za prostory normalizujeme na 1. Jakékoli cenové schéma je pak bodem v dimenzionálním simplexu s vrcholy na . Protokol Su funguje na duální verzi tohoto simplexu podobným způsobem jako protokoly Simmons-Su na řezání koláčů - pro jakýkoli vrchol triangulace duálního simplexu, který odpovídá určitému cenovému schématu, se algoritmus partnera zeptá, „který preferujete pokoj v tomto cenovém schématu?" To vede ke Spernerovu zbarvení duálního simplexu a pak je zde malý subsimplex, který odpovídá přibližnému rozložení místností a výplat bez závisti.

Protokol Su vrací sekvenci distribucí, které konvergují k distribuci bez závisti. Ceny jsou vždy nezáporné. Výsledek tedy splňuje požadavky na nezápornost a OP.

Sun [10] a Procaccia [11] podali populární vysvětlení Suova protokolu sdílení bytů.

Stránky Fair Division od Francise Su [ 12] a Divide Your Rent Fairly [13] mají online implementace.

Azrieli a Shmaya sdíleli pokoj

Azrieli a Shmaya [2] zobecnili Suovo řešení situace, kdy kapacita každé místnosti může být větší než jedna (to znamená, že někteří partneři mohou sdílet stejnou místnost).

Prokázali existenci distribuce bez závisti za následujících podmínek:

  1. Dobrý dům : Každý partner má rád alespoň jeden pokoj podle každého cenového vektoru.
  2. Minimální vnější vliv : Všichni partneři preferují volné pokoje.
  3. Lakomí partneři : Preference jsou stálé v ceně.

Hlavní prostředky použité v důkazu:

Jejich řešení je konstruktivní ve stejném smyslu jako Suovo řešení – existuje postup, který řešení aproximuje na danou přesnost.

Základní vlastnosti ordinálních protokolů

Odpověď : Jak v protokolu Su, tak v protokolu Azrieli a Shmaiya mohou preferenční vztahy každého partnera záviset (ale není to vyžadováno) na úplném cenovém vektoru. To znamená, že partner může říci: "Pokud pokoj A stojí 1000, pak dám přednost pokoji B před pokojem C, ale pokud pokoj A stojí pouze 700, pak dám přednost pokoji C před pokojem B."

Existuje několik důvodů, proč by taková obecnost mohla být užitečná [2] .

  1. Plánování do budoucna. Předpokládejme, že partner si myslí, že nejlepší pokoj je A, pak B, pak C. Pokud je A příliš drahý, účastník obsadí B. Ale pokud je A levnější, může si partner koupit C (nejlevnější) a pak ušetřit peníze a přestěhovat se do A.
  2. Neúplné informace. Cenový vektor může poskytnout partnerovi informace o kvalitě pokojů.
  3. Sousedé. Cenový vektor může partnerovi do určité míry předpovědět, jací lidé budou bydlet v sousedních místnostech.
  4. Nelogické efekty, jako jsou efekty vjemového rámce . Pokud mají pokoje B a C stejnou kvalitu a stejnou cenu, pak si partner vybere A. Pokud ale pokoj B zdraží, může si partner vybrat C s tím, že „je to stejné jako B, ale levnější...“.

Řešení B. Su a řešení Azrieliho a Shmaya vycházejí z předpokladu „skúpého nájemníka“ – předpokládají, že nájemník vždy upřednostňuje volný pokoj před pokojem s kladnou cenou. Tento předpoklad je silný a ne vždy realistický. Pokud je jeden pokoj velmi špatný, může se stát, že někteří nájemníci v takovém pokoji nebudou chtít bydlet, i když je platba nulová. V kardinální verzi je to dobře vidět - pokud uvážíte, že pokoj A stojí 0 a pokoj B 100, zatímco pokoj A je zdarma a pokoj B stojí 50, určitě dáte přednost pokoji B.

Su [1] navrhl zmírnění tohoto předpokladu následovně: každý z partnerů si nikdy nevybírá nejdražší pokoj, pokud je k dispozici volný pokoj. To nevyžaduje, aby si osoba vybrala volný pokoj. To platí zejména v případě, že člověk vždy preferuje volný pokoj před pokojem v hodnotě alespoň plné ceny. I tento oslabený předpoklad se však může ukázat jako nereálný, jako v příkladu výše [14] .

Kardinální verze

Jak je vysvětleno výše, vstupem do základní verze je matice nabídkové ceny – každý partner musí nabídnout za každý pokoj s uvedením toho, na kolik si daný pokoj cení (řekněme v rublech nebo dolarech).

Klíčovým konceptem v zásadních rozhodnutích je rozdělení maximálního součtu . Jedná se o rozložení partnerů pokojů, které maximalizuje součet nabídkových cen. Problém nalezení distribuce s maximálním součtem je známý jako problém přiřazení a může být vyřešen maďarským algoritmem v čase (kde  je počet partnerů). Jakékoli rozdělení OZ je maximální součet a jakékoli rozdělení maximálního součtu je EP [4] .

Neslučitelnost mezi EP a nezáporností

Tyto dva požadavky, absence závisti a nezápornost plateb, nejsou vždy kompatibilní. Předpokládejme například, že plná cena je 100 a odhady jsou:

Místnost 1 Místnost 2
Partner 1 150 0
Partner 2 140 deset

Zde pouze rozdělení maximálního součtu dává pokoj 1 partnerovi 1 a pokoj 2 partnerovi 2. Aby partner 2 nežárlil, partner 1 musí zaplatit 115 a partner 2 musí zaplatit -15.

V tomto příkladu je součet odhadů větší než celkové náklady. Pokud se součet skóre rovná celkovým nákladům a jsou dva nebo tři partneři, pak vždy existuje rozdělení OD a HO [15] . Ale v případě čtyř nebo více partnerů se opět OD a DO mohou ukázat jako neslučitelné, jako v následujícím příkladu ( pro důkaz viz článek Brahmse [16] ):

Místnost 1 Místnost 2 Místnost 3 Místnost 4
Partner 1 36 34 třicet 0
Partner 2 31 36 33 0
Partner 3 34 třicet 36 0
Partner 4 32 33 35 0

Všimněte si, že tento příklad se nevyskytuje v řadové verzi, protože řadový protokol vychází z předpokladu „skúpých partnerů“, kde partneři vždy preferují volné pokoje. Pokud je tento předpoklad pravdivý, vždy existuje rozdělení OD+HO. Ve výše uvedeném příkladu však předpoklad selže a rozdělení OD+HO neexistuje. Proto by protokoly v kardinální verzi měly hledat kompromis mezi DO a DO. Každý protokol přináší různé kompromisy.

Brahms a Kilgour: ALE, ne OZ

Brahms a Kilgour [8] [17] navrhli postup přerušení :

  1. Vypočítáme rozdělení max. součtu.
  2. Pokud je maximální částka nižší než plná cena, pak je problém neřešitelný, protože partneři nechtějí platit plnou cenu určenou majitelem domu.
  3. Pokud se maximální součet přesně rovná plné ceně, pokoje jsou přiděleny a partneři platí své inzerované ceny.
  4. Pokud je max. součet větší než plná cena, pak jsou ceny sníženy na základě rozdílu mezi těmito cenami a dalším (minimálním) oceněním (podrobnější diskusi najdete v knize).

Myšlenka posledního kroku spočívá v tom, že další (minimální) skóre představuje „soutěž“ o místnost. Pokud chce partner s další nejvyšší nabídkou více místa, pak by to mělo stát více. V duchu se to podobá aukci Vickrey . V aukci Vickrey je však platba zcela závislá na deklarovaných cenách a v proceduře mezery jsou platby nezávislé pouze částečně. Procedura přerušení tedy není nezranitelná .

Gapová procedura vždy přiřadí nezáporné ceny. Vzhledem k tomu, že zadání je maxsum, je zřejmé, že je také Pareto efektivní. Někteří partneři však mohou žárlit. To znamená, že postup přerušení vyhovuje VUT a EP, ale ne EP.

Kromě toho může procedura přerušení vrátit distribuci plnou závisti, i když existuje distribuce OD. Brahms o tomto problému řekl: „Mezerové ceny berou v úvahu konkurenci v nabídkových cenách, díky nimž je cenový mechanismus prodejný. Ačkoli je absence závisti žádoucí vlastností, preferuji mechanismus podobný trhu, kde dochází ke konfliktu mezi těmito dvěma vlastnostmi; partneři by měli platit více, pokud si jejich nabídky konkurují, i když to vede k závisti“ [18] .

Haake, Wraith a Su: OZ, ale ne ALE

Haake, Wraith a Su [7] předložili kompenzační postup . Problém, který tento postup řeší, je v některých ohledech obecnější než problém společného pronájmu bytu:

Pro partnery existuje „kvalifikační požadavek“ – počet žádostí nesmí být nižší než celkové náklady.

Postup zahrnuje následující kroky.

  1. Najděte maximální (pragmatické) rozdělení, rozdělení s nejvyšším součtem užitku, které splňuje omezení na balíčky objektů. Pokud neexistují žádná omezení, pak rozdělení, které každý objekt dává partnerovi s nejvyšším skóre, je maximální součet. Pokud existují omezení (například "alespoň jeden objekt na partnera"), může být obtížné najít rozdělení maximálního součtu.
  2. Každému partnerovi přiřadíme hodnotu jemu distribuovaného balíčku. Tím se vytvoří počáteční pokladna.
  3. Cenu platíme z prvotní pokladny. Pokud všichni partneři splnili kvalifikační předpoklady, pak je v pokladně dostatek peněz a může se objevit nějaká zbytková částka.
  4. Závist vylučujeme kompenzačními platbami závistivým partnerům. Již neprobíhají žádná výplatní kola. Postup je zcela jasný a jasně říká, jaké odškodnění má být vyplaceno a v jakém pořadí. Tento postup lze navíc snadno provést bez počítače.
  5. Výše kompenzace provedená ve všech kolech je nejmenší částka potřebná k odstranění závisti a nikdy nepřesáhne zbývající částku. Pokud něco zbyde, lze tento zbytek rozdělit jakýmkoli způsobem, který nevyvolává závist, například vyplacením stejné částky každému partnerovi (články pojednávají o dalších možnostech, které lze považovat za „spravedlivější“).

Pokud existuje mnoho objektů a složitých omezení, může být počáteční krok nalezení maximálního součtu rozdělení obtížné vypočítat bez počítače. V tomto případě může „kompenzační řízení“ začít libovolným přidělením. V tomto případě může postup skončit distribucí obsahující cykly závisti . Tyto smyčky lze odstranit pohybem balíčků kolem smyčky. Takový převod striktně zvyšuje celkové množství užitku. Proto bude po omezeném počtu iterací nalezeno rozdělení maximálního součtu a postup může pokračovat jako výše, aby se získalo rozdělení bez závisti.

Kompenzační postup může některým partnerům přiřadit záporné výplaty (tj. poskytnout partnerům kladné peněžní částky). To znamená, že kompenzační postup je OC, ale ne NA. Autoři říkají:

„Nevylučujeme situace, kdy jedna osoba bude placena ostatními. V kontextu spravedlivého rozdělení to vůbec nevidíme jako problém. Navíc, pokud se skupina nechce zbavit žádného ze členů, není důvod, aby skupina nedotovala člena skupiny, který obdrží (pro ostatní) nechtěný balík předmětů. Kvalifikační požadavek navíc zajišťuje, že dotace nevyplývají z podcenění celého souboru objektů ze strany hráčů“ [19] .

Jiní autoři však tvrdí, že v typickém scénáři pronájmu

„Nájemník, kterému je přidělen pokoj se zápornými životními náklady, je dotován několika dalšími nájemníky. V takové situaci mohou raději nechat pokoj prázdný a zbavit se spolubydlícího, který pokoj obývá, protože dostanou slevu na ubytování. Aby se takovým situacím předešlo, záporný poplatek za prostory by měl být vyloučen“ [4] .

Abdulkadiroglu, Sönmez a Unver: OZ a VUT pokud možno

Abdulkadiroglu, Sönmez a Unver [5] navrhli přístup založený na tržním mechanismu. Jde o kombinaci anglické aukce a nizozemské aukce . Nejjednodušeji se popisuje jako aukce s průběžnými cenami:

  1. Cenu každého pokoje přiřadíme v plné ceně domu.
  2. Spočítáme soubor požadavků každého partnera - pokoj nebo soubor pokojů, které chce partner nejvíce získat za aktuální cenu.
  3. Vybíráme pokoje, které jsou velmi žádané (místnosti, které chtějí více uživatelů, než je počet pokojů; přesnou definici viz článek).
  4. Stejným koeficientem zdražujeme pokoje se zvýšenou poptávkou;
  5. O stejnou částku zároveň snižujeme cenu ostatních pokojů, aby součet cen všech pokojů zůstal roven plné ceně.
  6. Okamžitě aktualizujeme požadavky partnerů a mnoho pokojů se zvýšenou poptávkou.
  7. Když je množina místností s vysokou poptávkou prázdná, zastavíme se a aplikujeme Hallův svatební teorém , abychom každému partnerovi přidělili pokoj podle jeho požadavků.

V praxi není nutné cenu průběžně měnit, zajímavé jsou pouze ceny, při kterých se mění soubor požadavků jednoho nebo více partnerů. Můžeme předem definovat sadu cen, které nás zajímají, a z aukce s průběžnými cenami udělat aukci s diskrétními cenami. Taková aukce s diskrétními cenami se zastaví po konečném počtu kroků [20] .

Výsledná distribuce je vždy bez závisti. Ceny mohou být záporné jako v postupu Haake, Wraith a Su. Na rozdíl od tohoto postupu jsou však ceny nezáporné, pokud existuje distribuce OD s nezápornými cenami.

Spánek a Vlah: OZ a ALE, pokud možno

Syn a Vlah [4] prokázali následující obecnou vlastnost distribucí:

  1. Absence závisti implikuje maxsum: je-li dané rozdělení x , pokud existuje cenový vektor p takový, že v x rozdělení není žádná závist , pak x je maxsum.
  2. Absence závisti vyplývá z maximálního součtu: pro daný cenový vektor p , pokud existuje rozdělení x , pro které cenový vektor p nevytváří závist, pro tento cenový vektor p nebude závist v žádném rozdělení max. součtu.

Na základě těchto vlastností autoři navrhli následující algoritmus:

  1. Hledání rozdělení maximálního součtu.
  2. Najdeme minsum vektor cen (vektor, na kterém je součet cen minimální) s přihlédnutím k podmínce nepřítomnosti závisti. Takový cenový vektor je řešením lineárního programování a lze jej nalézt pomocí Bellman-Fordova algoritmu .
  3. Pokud se minimální cena rovná plné ceně, implementujte maximální rozdělení s minimálními cenami a ukončete.
  4. Pokud je minsum menší než plná cena, zvýšíme všechny ceny tak, aby se součet rovnal plné ceně (to znamená, že ke každé ceně přidáme hodnotu ). Změna cen o stejnou částku zajišťuje absenci závisti.
  5. Pokud je minsum větší než celková cena, pak neexistuje řešení, které by současně vyhovovalo požadavkům HO a OR. Existuje několik možných způsobů, jak pokračovat v postupu
    • Všechny ceny snižujeme o stejnou částku, dokud se součet nerovná plné ceně (to znamená, že od každé ceny odečteme hodnotu ). Některé ceny budou nutně záporné, jako v případě řešení Haake, Wraith a Su.
    • Pouze kladné ceny snižujeme o stejnou částku, dokud se součet cen nerovná plné ceně. Zde se ceny nemění stejným způsobem, což nevyhnutelně povede k závisti, jako v řešení Brahmse a Kilgoura. V tomto řešení však závistiví partneři dostanou své pokoje zdarma .

Složitost provádění maximální distribuce a minimálních cen je rovna .

Řešení Syna a Vlacha má podle všeho všechny požadované vlastnosti předchozích protokolů, tedy OZ, NO (pokud je to možné), polynomiální dobu běhu a navíc zaručuje, že každý závistivý partner dostane volný pokoj. Článek "Assign Rooms and Share Rent" [21] poskytuje implementaci podobného řešení, rovněž založeného na řešení problému lineárního programování, ale článek cituje jinou práci.

Mash, Gal, Procaccia a Zeke: OZ a maximin

Gal, Mash, Procaccia a Zeke [22] na základě svých zkušeností s aplikací pro distribuci pronájmu na www.spliddit.org poznamenali, že samotná absence závisti nestačí k uspokojení aspirací účastníků. Proto sestrojili algoritmický aparát založený na lineárním programování pro výpočet distribuce, která nemá závist a která optimalizuje některá kritéria. Na základě teoretických a experimentálních testů dospěli k závěru, že kritérium maximin  - maximalizace minimálního užitku prostředku, s přihlédnutím k absenci závisti - poskytuje optimální výsledky.

Všimněte si, že protože jejich řešení je vždy OZ, může vrátit záporné ceny.

Rozpočtové konvence

Většina článků s kardinálním modelem předpokládá, že agenti mají kvazilineární užitkové funkce  – jejich užitek se rovná hodnotě místnosti mínus cena. Ale ve skutečnosti mají agenti rozpočtová omezení – pokud je cena pokoje vyšší než jejich rozpočet, užitečnost klesá mnohem rychleji než linearita. Procaccia, Vélez a Yu [23] studovali tento model a představili algoritmus k určení, zda existuje distribuce OD, která vyhovuje rozpočtovým omezením, a pokud ano, algoritmus najde distribuci, která splňuje další kritérium spravedlnosti.

Strategické dohody

Všechny kontrolované protokoly předpokládají, že partneři jsou ve svých odhadech upřímní. Strategie nejsou nezranitelné  – partner může vyhrát zadáním nesprávné hodnoty. Kromě toho je nezranitelnost strategie neslučitelná s absencí závisti  – neexistuje žádný protokol pro deterministickou nezranitelnou strategii, která vždy poskytuje distribuci bez závisti. To platí i v případě, že jsou pouze dva partneři a ceny mohou být záporné. Důkaz : Předpokládejme, že celková cena je 100 a odhady partnerů jsou následující (kde jsou parametry a ):

Místnost 1 Místnost 2
Partner 1 100 X
Partner 2 100 y

Pouze maximální alokace dává pokoj 1 partnerovi 1 a pokoj 2 partnerovi 2. Nechť je cena pokoje 2 (takže cena pokoje 1 je ). Aby partner 1 nezáviděl, musí být provedeno . Abychom nezáviděli partnerovi 2, je třeba provést .

Předpokládejme, že deterministický protokol nastaví cenu na nějakou hodnotu z intervalu . Pokud je cena vyšší než , pak má partner 2 motivaci zadat nižší hodnotu , která zůstává vyšší než , aby snížil své platby blíže k . Stejně tak, pokud je cena nižší než , pak má partner 1 důvod účtovat vyšší cenu za , která zůstává nižší , aby se tak bokem zvýšily platby partnera 2 (a tím snížily své vlastní platby). Mechanismus proto nemůže být nezranitelnou strategií.

Vědci se s touto nemožností vyrovnávají dvěma způsoby.

Sun and Yang: Náhrada úkolů

Existuje varianta problému, kdy místo toho, abychom předpokládali, že celkové náklady na dům jsou fixní, předpokládáme, že pro každou místnost existují maximální náklady. V této variantě existuje mechanismus nezranitelné strategie - deterministické distribuční pravidlo, které vybírá minimální cenu v součtu, je strategie nezranitelnosti [24] .

Tento výsledek lze zobecnit pro větší flexibilitu k nedělitelným objektům a důkaz stability koaliční strategie [25] [26] .


Dufton a Larson: Použití náhody

Vrátíme-li se k původnímu problému spravedlivého rozdělení bydlení, můžeme uvažovat o mechanismu náhody . Mechanismus náhodnosti vrací rozdělení pravděpodobnosti přes rozdělení místností a rozdělení platby. Mechanismus náhodnosti je spravedlivý v očekávání , pokud žádný partner nezvýší očekávanou hodnotu svého užitku zkreslením svého hodnocení pokojů. Spravedlnost mechanismu náhodnosti lze měřit různými způsoby [6] :

1. Absence závisti předem znamená, že neexistují žádní partneři, kteří by záviděli jakémukoli jinému partnerovi vylosovaný pokoj. Tato podmínka je triviální ke splnění: všechny distribuce vybíráme se stejnou pravděpodobností a každému partnerovi přiřazujeme poplatek za celkové náklady. Tato podmínka je však málo užitečná, protože existuje velká šance, že mnoho partnerů bude při konečné distribuci žárlit. Nemusí být spokojeni s tím, že loterie byla spravedlivá.

2. Garantovaná pravděpodobnost nezávistosti ( GPEF  ) znamená, že existuje určitá pravděpodobnost , při které bez ohledu na hodnocení účastníků nebude v konečném rozhodnutí alespoň závist. GVOZ je možné získat následujícím způsobem: najdeme distribuci bez závisti; vybereme náhodně celé číslo a přesuneme partnery v cyklu do místnosti doprava. Tento náhodný mechanismus je spravedlivý v očekávání, protože každý partner má stejnou pravděpodobnost, že bude v každém pokoji, a očekávanou cenu v celkových nákladech, bez ohledu na ceny deklarované partnerem. Pravděpodobnost získání distribučního CV se rovná pravděpodobnosti, že , což je přesně rovno . To není nijak zvlášť povzbudivé, protože pravděpodobnost, že nebudete žárlit, má s rostoucím počtem partnerů tendenci k 0, ale neexistuje způsob, jak to zlepšit, protože v žádném mechanismu poctivosti v očekávání GVOA nepřekračuje .

3. Expected Number of  Envy-Free Partners ( ENEF ) znamená, že existuje nějaké celé číslo , takové, že pokud určíme počet partnerů, kteří nezávidí všechny možné výsledky mechanismu, bez ohledu na odhady partneři nepřekročí očekávání . Test POCH se zdá být vhodnější než test HLOT, protože měří nejen pravděpodobnost úplné absence závisti, ale také kvalitu případů, kdy distribuce není zcela prostá závisti. Maximální OCHBZ poctivého mechanismu nepřesahuje . Tuto hranici je možné získat za . Existuje poctivý čekací mechanismus, který téměř dosáhne této hranice - TWBZ se rovná . Hlavní myšlenka je následující. K výpočtu zakázky s maximální částkou a její výší plateb používáme mechanismus Vickrey-Clark-Groves Náhodně si vyberte partnera. Ignorujte tohoto partnera a znovu použijte mechanismus Vickrey-Clark-Groves. Výsledky kombinujeme tak, abychom zaručili rovnost plné úhrady celých nákladů (podrobnosti viz článek). Dá se to ukázat

a) mechanismus je čestný a čeká (b) všichni partneři, kromě jednoho ignorovaného, ​​nebudou žárlit

Proto se OCHBZ rovná . Modelování ukazuje, že asi v 80 % případů HLH tento mechanismus nepřekračuje .

Andersson a Svensson: Získání částečné nezranitelnosti

Možným zmírněním požadavku nezranitelnosti je pokus minimalizovat „stupně manipulovatelnosti“ [27] . Určuje se tak, že se pro každý případ spočítá počet agentů, kteří mohou manipulovat s pravidly. Nejpreferovanější pravidla spravedlivého rozdělení jsou minimálně manipulována (jak jednotlivě, tak v koalici), a to jak z hlediska spravedlivosti, tak z hlediska rozpočtové vyrovnanosti. Tato pravidla vybírají distribuci s maximálním počtem agentů, pro které je užitek maximální ze všech spravedlivých a vyvážených distribucí.

Viz také

Poznámky

  1. ↑ 1 2 Ne, 1999 , str. 930–942.
  2. ↑ 1 2 3 Azrieli, Shmaya, 2014 , str. 128.
  3. ↑ Potthoff, 2002 , str. 405.
  4. ↑ 1 2 3 4 Sung, Vlach, 2004 .
  5. ↑ 1 2 Abdulkadiroğlu, Sönmez, Ünver, 2004 , str. 515.
  6. ↑ 1 2 Dufton, Larson, 2011 , str. 34–39.
  7. ↑ 1 2 Haake, Raith, Su, 2002 , str. 723.
  8. ↑ 1 2 Brams, 2008 , s. 305–328.
  9. ↑ Zde slovo slabě znamená, že partner nemusí odlišit jiný pokoj + balíček preference platby od zadaného. Pokud partner nepovažuje pakety za rovnocenné, používá se výraz přísně lepší.
  10. ↑ Albert Sun. Chcete-li rozdělit nájemné, začněte trojúhelníkem . Archivováno 11. listopadu 2020. Staženo 26. srpna 2014.
  11. ↑ Ariel Procaccia. Spravedlivé rozdělení a problém fňukajících filozofů . Turingova neviditelná ruka (15. srpna 2012). Získáno 26. srpna 2014. Archivováno z originálu 3. září 2014.
  12. ↑ Stránka spravedlivé divize Francise Su (odkaz není dostupný) . Math.hmc.edu . Získáno 5. ledna 2017. Archivováno z originálu 27. října 2018. 
  13. ↑ Rozdělte si nájem spravedlivě . Archivováno z originálu 31. prosince 2019. Staženo 5. ledna 2017.
  14. ↑ Brams, 2008 , s. 320–321.
  15. ↑ Sung, Vlach, 2004 , str. 110–111.
  16. ↑ Brams, 2008 , s. 318–319.
  17. ↑ Brams, Kilgour, 2001 , str. 418.
  18. ↑ Brams, 2008 , s. 321.
  19. ↑ Haake, Raith, Su, 2002 , str. 746.
  20. ↑ Abdulkadiroğlu, Sönmez, Ünver, 2004 , s. 525-528.
  21. ↑ Přiřadit pokoje a sdílet nájem - Spliddit . Získáno 5. března 2016. Archivováno z originálu 5. března 2016.
  22. ↑ Gal, Mash, Procaccia, Zick, 2016 , str. 67–84.
  23. ↑ Procaccia, Velez, Yu, 2018 .
  24. ↑ Sun, Yang, 2003 , str. 73.
  25. ↑ Andersson, Svensson, 2008 , str. 350.
  26. ↑ Andersson, 2009 , str. 1719–1724
  27. ↑ Andersson, Ehlers, Svensson, 2014 , str. 753.

Literatura