Tehtävä jakaa asunto

Jaettu vuokra-ongelma [1] [2] on eräänlainen reilun jakamisen ongelma , jossa jakamattomia esineitä ja kiinteää rahallista hintaa on jaettava samanaikaisesti. Englanninkielisessä kirjallisuudessa tällä ongelmalla on eri nimiä, kuten Rental harmony , housemates problem [ 3] [4] ja room- assignment -rent-division [5] [6] [7] [8] .

Tyypillisissä olosuhteissa löytyy yhteistyökumppaneita, jotka ovat valmiita vuokraamaan yhteishuoneiston vuokranantajan pyytämään hintaan. Jokaisella kumppanilla on omat mieltymyksensä - toinen pitää parempana suuresta huoneesta, toinen saattaa mieluummin huoneen, josta on näkymät päätielle ja niin edelleen. Seuraavat kaksi ongelmaa tulisi ratkaista samanaikaisesti: $n$ $n$

(a) Anna jokaiselle kumppanille huone,
(b) Määritä, kuinka paljon kumppani maksaa niin, että kaikkien maksujen summa on kiinteä hinta.

On olemassa useita ominaisuuksia, jotka meidän tulee täyttää.

Ei-negatiivinen (NUT): Kaikkien hintojen on oltava 0 tai suurempia: ketään jäsentä ei saa veloittaa huoneen vuokraamisesta.
Envy -freeness ( EF) : Kun otetaan huomioon hinnoittelu (huonemaksujen määrittäminen), sanomme kumppanin suosivan tätä huonetta, jos hän uskoo, että huone + maksu -paketti on heikko [9] parempi kuin muut paketit. OZ tarkoittaa, että jokainen kumppani pitää parempana hänelle osoitettua huonetta. Toisin sanoen kukaan kumppani ei haluaisi mieluummin miehittää toisen kumppanin huonetta tälle huoneelle määrätyllä hinnalla.
Pareto-tehokkuus (EP, eng. Pareto-efficiency , PE): Mikään muu kumppanien jako ei ole heikosti parempi kaikille kumppaneille ja ehdottomasti parempi ainakin yhdelle kumppanille (hintavektorilla).

Kateuden puuttumisesta seuraa Pareton tehokkuus. Todiste: (ristiriitaisesti) oletetaan, että on olemassa vaihtoehtoinen toimeksianto samalla hintavektorilla, joka on ehdottomasti parempi ainakin yhdelle kumppanille. Sitten nykyisellä jakelulla tämä kumppani on mustasukkainen.

Asunnon jakamisen ongelmaa tutkittiin kahdella eri oletuksella kumppaneiden mieltymyksistä:

Ordinaalisen hyödyllisyysteorian versiossa jokaisella kumppanilla on mieltymyssuhde nippuihin [huone, hinta]. Kun hintavektori on annettu, kumppanin on sanottava, minkä huoneen (tai huoneet) hän haluaa saada kyseisellä hinnalla.
Kardinaalisen hyödyllisyysteorian versiossa jokaisella kumppanilla on rahallisten arvojen vektori. Kumppanin on kerrottava jokaisesta huoneesta tarkalleen, kuinka paljon rahaa hän on valmis maksamaan siitä huoneesta. Oletetaan, että kumppanilla on kvasilineaarinen hyöty , eli hän arvioi huoneen maksaessaan , huoneen kokonaishyötysuhde on yhtä suuri kuin . $v$ $s$ $vp$

Kardinaalisuus tarkoittaa ordinaalisuutta, koska aina on mahdollista rakentaa preferenssisuhde estimaattien vektorin mukaan. Ordinaalisuus on yleisempi olettamus ja asettaa vähemmän henkistä taakkaa kumppaneille.

Tavallinen versio

Su: yksi henkilö per huone

Francis Sun protokolla tekee seuraavat oletukset kumppaneiden mieltymyksistä:

Hyvä talo : Vuokraerittelyssä jokainen hyväksyy vähintään yhden huone+maksupaketin.
Vähimmäisvaikutus ulkoiseen suuntaan : mieltymyssuhde riippuu huoneesta ja maksusta, mutta ei muiden kumppanien valinnasta.
Stingy Affiliates : Kaikki tytäryhtiöt pitävät ilmaisista (nollamaksuttomista) huoneista verrattuna muihin huoneisiin.
Topologisesti suljettu mieltymysjoukko : kumppani, joka pitää parempana tilaa hintasarjalle, pitää parempana sitä tilaa myös marginaalihinnalle.

Normalisoimme tilojen kokonaismaksun 1:ksi. Tällöin mikä tahansa hintakaavio on piste -ulotteisessa simpleksissä, jonka kärjet ovat . Su-protokolla toimii tämän simpleksin kaksoisversiossa samalla tavalla kuin Simmons-Su -kakkuleikkausprotokollat – mistä tahansa kaksoissimplexin kolmiomittauksen kärjestä, joka vastaa tiettyä hintamallia, algoritmi kysyy kumppanilta "mikä huone, jonka pidät parempana tässä hintajärjestelmässä?". Tämä johtaa kaksoissimplexin Sperner-väritykseen, ja sitten on pieni osasimplex, joka vastaa likimääräistä huoneiden ja maksujen jakautumista ilman kateutta. $(n-1)$ $n$ $\mathbb {R} ^{n}$

Su-protokolla palauttaa sekvenssin jakaumia, jotka konvergoivat jakaumaan ilman kateutta. Hinnat eivät ole aina negatiivisia. Siksi tulos täyttää ei-negatiivisuuden ja OP:n vaatimukset.

Sun [10] ja Procaccia [11] ovat antaneet suositun selityksen Sun asunnonjakoprotokollasta.

Francis Su's Fair Division Page [ 12] ja Divide Your Rent Fairly [13] sisältävät online-toteutuksia.

Azrieli ja Shmaya jakoivat huoneen

Azrieli ja Shmaya [2] yleistivat Su:n ratkaisun tilanteeseen, jossa kunkin huoneen kapasiteetti voi olla suurempi kuin yksi (eli jotkut kumppanit voivat jakaa saman huoneen).

He osoittivat jakelun olemassaolon ilman kateutta seuraavissa olosuhteissa:

Hyvä talo : Jokainen kumppani pitää vähintään yhdestä huoneesta kunkin hintavektorin mukaan.
Minimi ulkoinen vaikutus : Kaikki kumppanit suosivat ilmaisia huoneita.
Niukat kumppanit : Hinnat ovat jatkuvat.

Todistuksessa käytetyt pääasialliset keinot:

Knaster-Kuravtosky-Mazurkiewicz-Shapley- lemma on yleistys Knaster-Kuravtosky-Mazurkiewicz-lemmasta .
häälause .

Heidän ratkaisunsa on rakentava samassa mielessä kuin Su:n ratkaisu – on olemassa menettely, joka likimäärin ratkaisuja mihin tahansa tiettyyn tarkkuuteen.

Järjestysprotokollien perusominaisuudet

V. Sekä Su-protokollassa että Azrieli- ja Shmaiya-protokollassa kunkin kumppanin preferenssisuhteiden sallitaan (mutta ei vaadita) riippuvan täydestä hintavektorista. Toisin sanoen kumppani voi sanoa: "Jos huone A maksaa 1000, niin valitsen huoneen B mieluummin huoneeseen C, mutta jos huone A maksaa vain 700, niin valitsen huoneen C mieluummin B."

On useita syitä, miksi tällainen yleisyys voi olla hyödyllistä [2] .

Tulevaisuuden suunnittelu. Oletetaan, että kumppani ajattelee, että paras huone on A, sitten B, sitten C. Jos A on liian kallis, osallistuja ottaa B:n. Mutta jos A on halvempi, kumppani voi ostaa C:n (halvin) ja sitten säästää rahaa ja muuttaa A.
Puutteelliset tiedot. Hintavektori voi antaa kumppanille tietoa huoneiden laadusta.
Naapurit. Hintavektori voi jossain määrin ennustaa kumppanille, millaisia ihmisiä naapurihuoneissa asuu.
Epäloogiset tehosteet, kuten havaintokehystehosteet . Jos huoneissa B ja C on sama laatu ja sama hinta, niin kumppani valitsee A:n. Mutta jos huone B tulee kalliimmaksi, kumppani voi valita C:n ajattelemalla "se on sama kuin B, mutta halvempi...".

B. Su:n ratkaisu sekä Azrielin ja Shmayan ratkaisu tekevät "niukka vuokralaisen" oletuksen – he olettavat, että vuokralainen pitää aina parempana vapaata huonetta kuin positiivisesti hinnoiteltua huonetta. Tämä oletus on vahva eikä aina realistinen. Jos yksi huone on erittäin huono, voi käydä niin, että jotkut vuokralaiset eivät halua asua sellaisessa huoneessa, vaikka maksu olisi nolla. Tämä on helppo nähdä kardinaalisessa versiossa - jos ajattelet, että huone A maksaa 0 ja huone B maksaa 100, kun taas huone A on ilmainen ja huone B maksaa 50, pidät ehdottomasti huoneesta B.

Su [1] ehdotti tämän oletuksen lieventämistä seuraavasti: kumpikaan kumppani ei koskaan valitse kalleinta huonetta, jos siellä on vapaa huone. Tämä ei edellytä henkilön valitsevan vapaata huonetta. Tämä pätee erityisesti, jos henkilö pitää aina parempana vapaata huonetta kuin vähintään täyden hinnan arvoista huonetta. Tämäkin heikentynyt oletus voi kuitenkin osoittautua epärealistiseksi, kuten yllä olevassa esimerkissä [14] . ${\näyttötyyli 1/(n-1)}$

Cardinal version

Kuten yllä selitettiin, kardinaaliversion syöte on tarjoushintamatriisi – jokaisen kumppanin on tarjottava jokaisesta huoneesta, mikä osoittaa, kuinka paljon he arvostavat huonetta (esim. ruplissa tai dollareissa).

Keskeinen käsite kardinaalisissa päätöksissä on maksimisummajakauma . Tämä on huonekumppanien jakautuminen, joka maksimoi tarjoushintojen summan. Ongelma jakauman löytämisessä maksimisummalla tunnetaan osoitusongelmana ja se voidaan ratkaista unkarilaisen algoritmin avulla ajassa (missä on kumppanien määrä). Mikä tahansa OZ-jakauma on maksimisumma ja mikä tahansa maksimisummajakauma on EP [4] . $O(n^{3})$ $n$

EP:n ja ei-negatiivisuuden välinen yhteensopimattomuus

Nämä kaksi vaatimusta, kateuden puuttuminen ja maksujen negatiivisuus, eivät aina ole yhteensopivia. Oletetaan esimerkiksi, että koko hinta on 100 ja arviot ovat:

	Huone 1	Huone 2
Kumppani 1	150	0
Kumppani 2	140	kymmenen

Tässä vain enimmäissummajakauma antaa huoneen 1 kumppanille 1 ja huoneen 2 kumppanille 2. Jotta kumppani 2 ei olisi mustasukkainen, kumppanin 1 on maksettava 115 ja kumppanin 2 -15.

Tässä esimerkissä arvioiden summa on suurempi kuin kokonaiskustannukset. Jos pisteiden summa on yhtä suuri kuin kokonaiskustannukset ja yhteistyökumppaneita on kaksi tai kolme, niin OD- ja HO-jakauma on aina olemassa [15] . Mutta neljän tai useamman kumppanin tapauksessa OD ja DO voivat jälleen osoittautua yhteensopimattomiksi, kuten seuraavassa esimerkissä (katso Brahmsin artikkeli [16] todisteeksi):

	Huone 1	Huone 2	Huone 3
Kumppani 1	36	34	kolmekymmentä
Kumppani 2	31	36	33
Kumppani 3	34	kolmekymmentä	36
Kumppani 4	32	33	35

Huomaa, että tätä esimerkkiä ei esiinny ordinaalisessa versiossa, koska järjestysprotokolla tekee "niukka kumppanit" -oletuksen, jossa kumppanit suosivat aina ilmaisia huoneita. Jos tämä oletus pitää paikkansa, on aina olemassa OD+HO-jakauma. Yllä olevassa esimerkissä oletus kuitenkin epäonnistuu, eikä OD+HO-jakaumaa ole olemassa. Siksi kardinaaliversion protokollien tulisi etsiä kompromissia DO:n ja DO:n välillä. Jokainen protokolla tekee erilaisia kompromisseja.

Brahms ja Kilgour: MUTTA, ei OZ

Brahms ja Kilgour [8] [17] ehdottivat katkaisumenettelyä :

Laskemme maksimijakauman.
Jos maksimisumma on pienempi kuin täysi hinta, niin ongelma on ratkaisematon, koska osakkaat eivät halua maksaa talon omistajan määräämää täyttä hintaa.
Jos enimmäissumma on täsmälleen sama kuin täysi hinta, huoneet jaetaan ja yhteistyökumppanit maksavat ilmoittamansa hinnat.
Jos enimmäissumma on suurempi kuin täysi hinta, hintoja alennetaan näiden hintojen ja seuraavan (minimi)arvon välisen eron perusteella (katso kirjasta tarkempi keskustelu).

Viimeisen vaiheen ideana on, että seuraava (minimi) pistemäärä edustaa "kilpailua" huoneesta. Jos seuraavaksi korkeimman tarjouksen tehnyt kumppani haluaa enemmän tilaa, sen pitäisi maksaa enemmän. Tämä on hengeltään samanlainen kuin Vickreyn huutokauppa . Vickrey-huutokaupassa maksu on kuitenkin täysin riippuvainen ilmoitetuista hinnoista, ja gap-menettelyssä maksut ovat vain osittain riippumattomia. Siksi katkaisumenettely ei ole haavoittumaton .

Aukkomenettely määrittää aina ei-negatiiviset hinnat. Koska tehtävä on maxsum, on selvää, että se on myös Pareto-tehokas. Jotkut kumppanit voivat kuitenkin olla kateellisia. Toisin sanoen katkaisumenettely tyydyttää BUT:n ja EP:n, mutta ei PP:tä.

Lisäksi katkaisumenettely voi palauttaa kateudella täytetyn jakauman, vaikka OD-jakauma olisi olemassa. Brahms sanoi tästä ongelmasta: "Aukkohinnat ottavat huomioon kilpailun tarjoushinnoissa, jotka tekevät hinnoittelumekanismista markkinoitavan. Vaikka kateuden puuttuminen on toivottava ominaisuus, pidän parempana markkinamaista mekanismia, jossa näiden kahden ominaisuuden välillä on ristiriita; kumppanien pitäisi maksaa enemmän, jos heidän tarjouksensa kilpailevat, vaikka tämä johtaisi kateuteen” [18] .

Haake, Wraith ja Su: OZ, mutta ei MUTTA

Haake, Wraith ja Su [7] esittivät korvausmenettelyn . Ongelma, jonka tämä menettely ratkaisee, on joissakin suhteissa yleisempi kuin asunnon vuokraaminen yhdessä:

Jaettavien jakamattomien kohteiden määrä ( m ) voi poiketa kumppaneiden lukumäärästä ( n ).
Objektijoukoille voi olla mielivaltaisia rajoituksia, kunhan vertaisryhmät eivät erota niitä. Esimerkiksi rajoituksia ei ehkä ole ollenkaan tai rajoituksia, kuten "jokaisen kumppanin on saatava vähintään tietty määrä esineitä" tai "joidenkin esineiden on oltava yhdessä" (esimerkiksi nämä voivat olla tontteja, joiden on oltava vieressä toisiaan) ja niin edelleen.
Kokonais "hinta" voi olla positiivinen, eli osa rahoista on yhteisomistukseen. Tämä on tyypillistä perinnön jakamisskenaariolle. Vastaavasti "esineillä" voi olla negatiivista hyötyä (esimerkiksi ne voivat edustaa jakamattomia askareita).

Kumppaneille on "pätevyysvaatimus" - hakemusten määrä ei saa olla pienempi kuin kokonaiskustannukset.

Menettelyssä on seuraavat vaiheet.

Etsi maksimisummajakauma (pragmaattinen) jakauma, jonka hyötysumma on suurin ja joka täyttää objektinippujen rajoitukset. Jos rajoituksia ei ole, kunkin objektin jakauma suurimman pistemäärän saaneelle kumppanille on maxsum. Jos on olemassa rajoituksia (kuten "vähintään yksi kohde kumppania kohti"), maksimisummajakaumaa voi olla vaikea löytää.
Määritämme jokaiselle kumppanille hänelle jaetun paketin arvon. Tämä luo alustavan kassan.
Maksamme hinnan alkuperäisestä kassasta. Jos kaikki yhteistyökumppanit ovat täyttäneet kelpoisuusvaatimukset, niin kassalla on rahaa riittävästi ja jäännössummaa saattaa ilmestyä.
Suljemme pois kateuden maksamalla kateellisille kumppaneille korvauksia. Voittokierroksia ei enää ole . Menettely on täysin selkeä ja siinä sanotaan selkeästi, mikä korvaus tulee maksaa ja missä järjestyksessä. Lisäksi tämä toimenpide on helppo suorittaa ilman tietokonetta. $n-1$
Kaikilla kierroksilla maksettava korvaus on pienin kateuden poistamiseen vaadittava summa, eikä se koskaan ylitä jäännösmäärää . Jos jotain jää jäljelle, tämä jäännös voidaan jakaa millä tahansa tavalla, joka ei aiheuta kateutta, kuten maksamalla sama summa jokaiselle kumppanille (artikkeleissa käsitellään muita vaihtoehtoja, joita voidaan pitää "oikeudenmukaisempana").

Jos objekteja ja monimutkaisia rajoituksia on monia, jakauman maksimisumman löytämisen ensimmäinen vaihe voi olla vaikea laskea ilman tietokonetta. Tässä tapauksessa "kompensointimenettely" voi alkaa mielivaltaisella allokoinnilla. Tässä tapauksessa menettely voi päätyä jakaumaan, joka sisältää kateuden syklejä . Nämä silmukat voidaan poistaa siirtämällä paketteja silmukan ympäri. Tällainen siirto lisää tiukasti hyödyn kokonaismäärää. Siksi rajallisen iteraatiomäärän jälkeen maksimisummajakauma löydetään ja menettelyä voidaan jatkaa kuten edellä kateudettoman jakauman saamiseksi.

Korvausmenettely voi osoittaa negatiivisia maksuja joillekin kumppaneille (eli antaa kumppaneille positiivisia rahasummia). Tämä tarkoittaa, että kompensointimenettely on OC, mutta ei NA. Kirjoittajat sanovat:

”Emme sulje pois tilanteita, joissa yhdelle henkilölle maksetaan muut. Oikeudenmukaisen jaon yhteydessä emme näe tätä ollenkaan ongelmana. Lisäksi, jos ryhmä ei halua päästä eroon yhdestäkään jäsenestä, ryhmällä ei ole mitään syytä olla tukematta ryhmän jäsentä, joka saa ei-toivotun (muille) esinepaketin. Lisäksi pätevyysvaatimuksella varmistetaan, että tuet eivät johdu siitä, että pelaajat aliarvioivat koko kohdejoukon” [19] .

Muut kirjoittajat kuitenkin väittävät, että tyypillisessä vuokraskenaariossa

”Vuokralainen, jolle on osoitettu huone, jonka elinkustannukset ovat negatiiviset, saa tukea useilta muilta vuokralaisilta. Tällaisessa tilanteessa he saattavat mieluummin jättää huoneen tyhjäksi ja päästä eroon huoneessa asuvasta kämppäkaverista, koska he saavat alennusta majoituksesta. Tällaisten tilanteiden välttämiseksi tiloista perittävä negatiivinen maksu tulisi sulkea pois” [4] .

Abdulkadiroglu, Sönmez ja Unver: OZ ja MUTTA jos mahdollista

Abdulkadiroglu, Sönmez ja Unver [5] ehdottivat markkinamekanismiin perustuvaa lähestymistapaa. Se on yhdistelmä englantilaista ja hollantilaista huutokauppaa . Sitä kuvaillaan yksinkertaisimmin huutokaupaksi jatkuvilla hinnoilla:

Määritämme jokaisen huoneen hinnan talon kokonaishintaan. $1/n$
Laskemme kunkin kumppanin vaatimukset - huoneen tai huonesarjan, jonka kumppani eniten haluaa saada nykyiseen hintaan.
Valitsemme huoneet, joilla on suuri kysyntä (huoneet, jotka haluavat enemmän käyttäjiä kuin huoneiden lukumäärä; katso artikkelista tarkka määritelmä).
Nostamme huoneiden hintoja, joilla on lisääntynyt kysyntä, samalla kertoimella;
Samalla alennamme muiden huoneiden hintoja saman verran, jotta kaikkien huoneiden hintojen summa pysyy samansuuruisena kuin täysi hinta.
Päivitämme välittömästi kumppaneiden vaatimukset ja monet huoneet, joiden kysyntä on kasvanut.
Kun suuren kysynnän huonejoukko on tyhjä, pysähdymme ja sovellamme Hallin häälausetta jakaamme jokaiselle osapuolelle huoneen hänen tarpeensa mukaan.

Käytännössä hintaa ei tarvitse muuttaa jatkuvasti, koska kiinnostavat vain hinnat, joissa yhden tai useamman kumppanin vaatimukset muuttuvat. Voimme määrittää etukäteen meitä kiinnostavan hintajoukon ja muuttaa jatkuvahintaisen huutokaupan erillishinnoin. Tällainen erillisten hintojen huutokauppa pysähtyy rajallisen määrän vaiheita jälkeen [20] .

Tuloksena oleva jakelu on aina vailla kateutta. Hinnat voivat olla negatiivisia, kuten Haaken, Wraithin ja Su:n menettelyssä. Toisin kuin tämä menettely, hinnat eivät kuitenkaan ole negatiivisia, jos OD-jakaumassa on ei-negatiiviset hinnat.

Sleep and Vlah: OZ ja MUTTA, jos mahdollista

Son ja Vlah [4] osoittivat seuraavan jakaumien yleisen ominaisuuden:

Kateuden puuttuminen merkitsee maksimisummaa: jos jakauma x , jos on olemassa hintavektori p siten, että x - jakaumassa ei ole kateutta , niin x on maksimisumma.
Kateuden puuttuminen seuraa maksimisummasta: jos tietylle hintavektorille p on jakauma x , jolle hintavektori p ei aiheuta kateutta, tälle hintavektorille p ei ole kateutta missään maksimisummajakaumassa .

Näiden ominaisuuksien perusteella kirjoittajat ehdottivat seuraavaa algoritmia:

Maksimijakauman löytäminen.
Löydämme hintojen minimivektorin (vektorin, jolla hintojen summa on minimaalinen) ottaen huomioon kateuden puuttumisen tilan. Tällainen hintavektori on lineaarinen ohjelmointiratkaisu ja se löytyy Bellman-Ford-algoritmin avulla .
Jos vähimmäishinta on yhtä suuri kuin täysi hinta, ota käyttöön maxsum-jakauma minimihinnoilla ja poistu.
Jos minimisumma on pienempi kuin täysi hinta, nostamme kaikkia hintoja niin, että summa on yhtä suuri kuin täysi hinta (eli lisäämme arvon jokaiseen hintaan ). Hintojen muuttaminen samalla määrällä varmistaa kateuden puuttumisen. $(cost-minsum)/n$
Jos minimisumma on suurempi kuin kokonaishinta, ei ole yhtä aikaa ratkaisua, joka täyttää HO:n ja OR:n vaatimukset. On olemassa useita mahdollisia tapoja jatkaa menettelyä
- Laskemme kaikkia hintoja samalla määrällä, kunnes summa on yhtä suuri kuin täysi hinta (eli vähennämme arvon jokaisesta hinnasta ). Jotkut hinnat ovat väistämättä negatiivisia, kuten Haake-, Wraith- ja Su-ratkaisussa. $(vähimmäishinta)/n$
- Laskemme vain positiivisia hintoja samalla määrällä, kunnes hintojen summa on yhtä suuri kuin täysi hinta. Täällä hinnat eivät muutu samalla tavalla, mikä johtaa väistämättä kateuteen, kuten Brahmsin ja Kilgourin ratkaisussa. Tässä ratkaisussa kateelliset kumppanit saavat kuitenkin huoneet ilmaiseksi .

Maksimisummajakauman ja minimihintojen suorittamisen monimutkaisuus on yhtä suuri kuin . $O(n^{3})$

Son and Vlachin ratkaisulla näyttää olevan kaikki edellisten protokollien halutut ominaisuudet, eli OZ, NO (jos mahdollista), polynomikäyttöaika, ja lisäksi se takaa, että jokainen kateellinen kumppani saa vapaan huoneen. Artikkeli "Assign Rooms and Share Rent" [21] tarjoaa samanlaisen ratkaisun toteutuksen, joka perustuu myös lineaarisen ohjelmointiongelman ratkaisuun, mutta artikkelissa viitataan muihin töihin.

Mash, Gal, Procaccia ja Zeke: OZ ja maximin

Gal, Mash, Procaccia ja Zeke [22] havaitsivat www.spliddit.org:n vuokrajakelusovelluksesta saamansa kokemuksen perusteella, että pelkän kateuden puuttuminen ei riitä tyydyttämään osallistujien toiveita. Siksi he rakensivat lineaariseen ohjelmointiin perustuvan algoritmisen laitteen laskemaan jakauman, jossa ei ole kateutta ja joka optimoi jotkin kriteerit. Teoreettisten ja kokeellisten testien perusteella he päättelivät, että maksimikriteeri - aineen minimihyötysuhteen maksimointi, kateuden puuttuminen huomioon ottaen - antaa optimaaliset tulokset.

Huomaa, että koska heidän ratkaisunsa on aina OZ, se voi palauttaa negatiiviset hinnat.

Budjettisopimukset

Suurin osa kardinaalimallia käyttävistä artikkeleista olettaa, että agenteilla on kvasilineaariset hyödyllisyysfunktiot – niiden hyödyllisyys on yhtä suuri kuin huoneen arvo miinus hinta. Mutta todellisuudessa agenteilla on budjettirajoituksia - jos huoneen hinta on korkeampi kuin heidän budjettinsa, hyötysuhde laskee paljon nopeammin kuin lineaarisuus. Procaccia, Vélez ja Yu [23] tutkivat tätä mallia ja esittivät algoritmin sen määrittämiseksi, onko olemassa OD-jakauma, joka täyttää budjettirajoitukset, ja jos on, algoritmi löytää jakauman, joka täyttää ylimääräisen oikeudenmukaisuuskriteerin.

Strategiset sopimukset

Kaikissa tarkastetuissa protokollissa oletetaan, että kumppanit ovat rehellisiä arvioissaan. Strategiat eivät ole haavoittumattomia - kumppani voi voittaa määrittämällä väärän arvon. Lisäksi strategian haavoittumattomuus on ristiriidassa kateuden puuttumisen kanssa - ei ole olemassa protokollaa deterministiselle haavoittumattomalle strategialle, joka antaa aina kateudettoman jakelun. Tämä pitää paikkansa, vaikka yhteistyökumppaneita olisi vain kaksi ja hinnat voivat olla negatiivisia. Todiste : Oletetaan, että kokonaishinta on 100 ja kumppanien arviot ovat seuraavat (missä ovat parametrit ja ): $x,y$ $0<x<y<100$

	Huone 1	Huone 2
Kumppani 1	100	x
Kumppani 2	100	y

Vain enimmäismäärä antaa huoneen 1 kumppanille 1 ja huoneen 2 kumppanille 2. Olkoon huoneen 2 hinta (siis huoneen 1 hinta on ). Jotta kumppani 1 ei kadehdi, on suoritettava . Jotta kumppania 2 ei katettaisi, se on suoritettava . $p_{2}$ ${\displaystyle 100-p_{2))$ $p_{2}\geqslant x/2$ $p_{2}\leqslant y/2$

Oletetaan, että deterministinen protokolla asettaa hinnan johonkin arvoon väliltä . Jos hinta on suurempi kuin , niin kumppanilla 2 on kannustin syöttää pienempi arvo , joka on edelleen suurempi kuin , jotta hänen maksujaan voidaan vähentää lähemmäksi arvoa . Samoin, jos hinta on pienempi kuin , niin kumppanilla 1 on syytä veloittaa korkeampi hinta , joka pysyy alhaisempana lisätäkseen kumppanin 2 maksuja sivusuunnassa (ja siten vähentääkseen omia maksujaan). Siksi mekanismi ei voi olla haavoittumaton strategia. $p_{2}$ ${\näyttötyyli [x/2,y/2]}$ $x/2$ $y$ $x$ $x/2$ $y/2$ $x$ $y$ $y/2$

Tutkijat käsittelevät tätä mahdottomuutta kahdella tavalla.

Sun ja Yang: Tehtävän korvaaminen

Ongelmasta on muunnelma, jossa sen sijaan, että oletamme, että talon kokonaiskustannukset ovat kiinteät, oletetaan, että jokaiselle huoneelle on maksimikustannukset. Tässä muunnelmassa on haavoittumattoman strategian mekanismi - deterministinen jakautumissääntö, joka valitsee minimihinnan summassa, on haavoittumattomuusstrategia [24] .

Tämä tulos voidaan yleistää suuremman joustavuuden vuoksi jakamattomiin objekteihin ja todisteeksi koalitiostrategian vakaudesta [25] [26] .

Dufton ja Larson: Sattuman käyttäminen

Palataksemme alkuperäiseen asuntojen oikeudenmukaisen jaon ongelmaan, voimme tarkastella sattuman mekanismia . Satunnaisuusmekanismi palauttaa huonejakauman ja maksujakauman todennäköisyysjakauman. Satunnaisuusmekanismi on oikeudenmukainen odotusten kannalta, jos kukaan kumppani ei lisää hyödyllisyytensä odotettua arvoa antamalla vääriä tietoja huoneiden arvosanasta. Satunnaisuusmekanismin oikeudenmukaisuutta voidaan mitata eri tavoin [6] :

1. Ennakolta kateuden puuttuminen tarkoittaa, että kukaan kumppaneita kadehtivat toisen kumppanin huonetta arvalla. Tämä ehto on triviaali täytettävä: valitsemme kaikki jakaumat yhtä suurella todennäköisyydellä ja määritämme kullekin kumppanille kokonaiskustannusmaksun. Mutta tästä ehdosta on vähän hyötyä, koska on suuri mahdollisuus, että monet kumppanit ovat kateellisia lopullisessa jakelussa. He eivät ehkä ole tyytyväisiä siihen, että lotto oli reilu. $1/n$

2. Taattu kateuden todennäköisyys ( GPEF ) tarkoittaa, että on olemassa tietty todennäköisyys , jolla osallistujien arvioista riippumatta lopullisessa päätöksessä ei ainakaan esiinny kateutta. GVOZ on mahdollista hankkia seuraavalla tavalla: löydämme jakelun ilman kateutta; valitsemme satunnaisesti kokonaisluvun ja siirrämme syklin osapuolet oikealle olevaan huoneeseen. Tämä satunnainen mekanismi on kohtuullinen, koska jokaisella kumppanilla on yhtä suuri todennäköisyys olla jokaisessa huoneessa ja odotettu hinta kokonaiskustannuksissa riippumatta kumppanin ilmoittamista hinnoista. Jakauman CV:n saamisen todennäköisyys on yhtä suuri kuin todennäköisyys, että , joka on täsmälleen yhtä suuri kuin . Tämä ei ole erityisen rohkaisevaa, koska todennäköisyys olla mustasukkainen on yleensä nolla kumppanien määrän kasvaessa, mutta sitä ei voi parantaa, koska missään rehellisen odotuksen mekanismissa GVOA ei ylitä . $s$ $s$ $1/n$ $i\in \{0,\dots ,n-1\}$ $i$ $1/n$ $i = 0$ $1/n$ $1/n$

3. Envy-Free Partners ( ENEF ) tarkoittaa, että on olemassa kokonaisluku , joten jos määritämme kumppaneiden lukumäärän, jotka eivät kadehdi kaikkia mekanismin mahdollisia tuloksia, arvioista riippumatta kumppanit eivät ylitä odotuksia . POCH-testi näyttää sopivammalta kuin HLOT-testi, koska se mittaa paitsi kateuden täydellisen puuttumisen todennäköisyyttä, myös niiden tapausten laatua, joissa jakelu ei ole täysin kateudesta vapaata. Rehellisen vireillä olevan mekanismin OCHBZ:n enimmäisarvo ei ylitä . Tämä raja on mahdollista saada hintaan . Sillä on olemassa rehellinen odotusmekanismi, joka melkein saavuttaa tämän rajan - TWBZ on yhtä suuri kuin . Pääidea on seuraava. Käytämme Vickrey-Clark-Groves-mekanismia laskeaksemme toimeksiannon maksimisummalla ja sen maksujen määrällä. Valitse kumppani satunnaisesti. Ohita tämä kumppani ja käytä Vickrey-Clark-Groves-mekanismia uudelleen. Yhdistämme tulokset, jotta voimme taata tasavertaisen maksun koko hinnasta (katso lisätietoja artikkelista). Sen voi osoittaa $N$ $N$ $n-1+1/n$ $n = 2$ $n>2$ $n-1$

a) mekanismi on rehellinen vireillä (b) kaikki kumppanit, paitsi se, joka jätetään huomiotta, eivät ole kateellisia

Siksi OCHBZ on yhtä suuri kuin . Mallintaminen osoittaa, että noin 80 %:ssa tapauksista HLH ei ylitä tätä mekanismia . $n-1$ $1/n$

Andersson ja Svensson: Osittainen haavoittumattomuus

Haavoittumattomuusvaatimuksen mahdollinen lieventäminen on yritys minimoida "manipuloitavuuden asteet" [27] . Se määritetään laskemalla kussakin tapauksessa niiden agenttien määrä, jotka voivat manipuloida sääntöjä. Suosituimmat oikeudenmukaiset jakosäännöt ovat minimaalisesti manipuloituja (sekä yksilöllisesti että koalitiossa) sekä oikeudenmukaisuuden että budjettitasapainon kannalta. Tällaiset säännöt valitsevat jakauman, jossa on suurin määrä agentteja, joille hyödyllisyys on suurin kaikista oikeudenmukaisista ja tasapainoisista jakaumista.

Katso myös

Esineiden oikeudenmukaisen jakautumisen ongelma on oikeudenmukaisen jaon ongelma, jossa on vain jakamattomia esineitä vaihdettavaksi ilman rahansiirtoja.

Muistiinpanot

↑ 1 2 Su, 1999 , s. 930–942.
↑ 1 2 3 Azrieli, Shmaya, 2014 , s. 128.
↑ Potthoff, 2002 , s. 405.
↑ 1 2 3 4 Sung, Vlach, 2004 .
↑ 1 2 Abdulkadiroğlu, Sönmez, Ünver, 2004 , s. 515.
↑ 1 2 Dufton, Larson, 2011 , s. 34–39.
↑ 1 2 Haake, Raith, Su, 2002 , s. 723.
↑ 1 2 Brams, 2008 , s. 305–328.
↑ Tässä sana heikosti tarkoittaa, että kumppani ei välttämättä erota toista huone+maksuetupakettia määritellystä. Jos kumppani ei pidä paketteja samanarvoisina, käytetään termiä ehdottomasti parempi.
↑ Albert Sun. Vuokran jakamiseksi aloita kolmiosta . Arkistoitu 11. marraskuuta 2020. Haettu 26. elokuuta 2014.
↑ Ariel Procaccia. Reilu jako ja valittavien filosofien ongelma . Turingin näkymätön käsi (15. elokuuta 2012). Haettu 26. elokuuta 2014. Arkistoitu alkuperäisestä 3. syyskuuta 2014. (määrätön)
↑ Francis Su's Fair Division -sivu (linkki ei saatavilla) . Math.hmc.edu . Haettu 5. tammikuuta 2017. Arkistoitu alkuperäisestä 27. lokakuuta 2018. (määrätön)
↑ Jaa vuokrasi reilusti . Arkistoitu alkuperäisestä 31. joulukuuta 2019. Haettu 5. tammikuuta 2017.
↑ Brams, 2008 , s. 320–321.
↑ Sung, Vlach, 2004 , s. 110-111.
↑ Brams, 2008 , s. 318–319.
↑ Brams, Kilgour, 2001 , s. 418.
↑ Brams, 2008 , s. 321.
↑ Haake, Raith, Su, 2002 , s. 746.
↑ Abdulkadiroğlu, Sönmez, Ünver, 2004 , s. 525-528.
↑ Määritä huoneet ja jaa vuokra - Spliddit . Haettu 5. maaliskuuta 2016. Arkistoitu alkuperäisestä 5. maaliskuuta 2016. (määrätön)
↑ Gal, Mash, Procaccia, Zick, 2016 , s. 67–84.
↑ Procaccia, Velez, Yu, 2018 .
↑ Sun, Yang, 2003 , s. 73.
↑ Andersson, Svensson, 2008 , s. 350.
↑ Andersson, 2009 , s. 1719-1724
↑ Andersson, Ehlers, Svensson, 2014 , s. 753.

Kirjallisuus

Su FE Rental Harmony: Sperner's Lemma in Fair Division // The American Mathematical Monthly. - 1999. - T. 106 , numero. 10 . - doi : 10.2307/2589747 . — .
Yaron Azrieli, Eran Shmaya. Vuokrausharmonia kämppäkavereiden kanssa // Journal of Economic Theory. - 2014. - T. 153 . - doi : 10.1016/j.jet.2014.06.006 . - arXiv : 1406.6672 .
Richard F. Potthoff. Lineaarisen ohjelmoinnin käyttäminen kateudettoman ratkaisun löytämiseen, joka on lähimpänä Brams-Kilgour Gap -ratkaisua kotitovereiden ongelmaan // Ryhmäpäätökset ja neuvottelut. - 2002. - T. 11 , no. 5 . - doi : 10.1023/A:1020485018300 .
Shao Chin Sung, Milanon vlach. Kilpailukykyinen kateudeton jako // Sosiaalinen valinta ja hyvinvointi. - 2004. - T. 23 . - doi : 10.1007/s00355-003-0240-z .
Atila Abdulkadiroğlu, Tayfun Sönmez, M. Utku Ünver. Huonevuokraus-jako: markkinalähtöisyys // Sosiaalinen valinta ja hyvinvointi. - 2004. - T. 22 , no. 3 . - doi : 10.1007/s00355-003-0231-0 .
Lachlan Dufton, Kate Larson. Satunnaistettujen huoneiden luovutus-vuokraosasto // Sosiaalista valintaa ja tekoälyä käsittelevän IJCAI-2011 -työpajan aineisto . – 2011.
Claus-Jochen Haake, Matthias G. Raith, Francis Edward Su. Tarjous kateudettomuudesta: Menettelytapa n-pelaajan reilun jaon ongelmiin // Social Choice and Welfare. - 2002. - T. 19 , numero. 4 . - doi : 10.1007/s003550100149 .
Steven J Brams. Matematiikka ja demokratia: parempien äänestys- ja oikeudenmukaisten jakomenettelyjen suunnittelu. — Princeton, NJ: Princeton University Press, 2008. — ISBN 9780691133218 .
Steven J. Brams, D. Marc Kilgour. Kilpailukykyinen messuosasto // Journal of Political Economy. - 2001. - T. 109 , numero. 2 . - doi : 10.1086/319550 .
Ya'akov Gal, Moshe Mash, Ariel D. Procaccia, Yair Zick. Mikä on niistä kaikista oikeudenmukaisin (vuokraosasto)?. - ACM, 2016. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940724 .
Ariel D. Procaccia, Rodrigo A. Velez, Dingli Yu. Kohtuullinen vuokra-osasto budjetilla // AAAI. – 2018.
Ning Sun, Zaifu Yang. Yleinen strategian mukainen oikeudenmukainen jakomekanismi // Economics Letters. - 2003. - T. 81 . - doi : 10.1016/s0165-1765(03)00151-4 .
Tommy Andersson, Lars-Gunnar Svensson. Ei-manipuloitava yksilöiden kohdistaminen uudelleen tarkasteltuihin tehtäviin // Mathematical Social Sciences. - 2008. - T. 56 , no. 3 . - doi : 10.1016/j.mathsocsci.2008.05.004 .
Tommy Andersson. Yleinen strategian kestävä oikeudenmukainen allokaatiomekanismi tarkasteltu uudelleen // Economics Bulletin. - 2009. - T. 29 , no. 3 .
Tommy Andersson, Lars Ehlers, Lars-Gunnar Svensson. Budjettitasapaino, oikeudenmukaisuus ja minimaalinen manipuloitavuus // Teoreettinen taloustiede. - 2014. - T. 9 , no. 3 . - doi : 10.3982/te1346 .