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.
Protokol Francise Su uvádí následující předpoklady o preferencích partnerů:
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 [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:
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.
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] .
Ř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] .
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] .
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 [8] [17] navrhli postup přerušení :
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 [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.
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 [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:
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.
Syn a Vlah [4] prokázali následující obecnou vlastnost distribucí:
Na základě těchto vlastností autoři navrhli následující algoritmus:
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.
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.
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.
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.
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] .
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 žárlitProto se OCHBZ rovná . Modelování ukazuje, že asi v 80 % případů HLH tento mechanismus nepřekračuje .
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í.