Envy Cycle -menettely

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. maaliskuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Kateuden syklien menettely on menettely esineiden oikeudenmukaiseen jakamiseen .

Tämä kokeilu suoritettiin yli 75 maassa ympäri maailmaa. Niiden joukossa: Venäjä, Yhdysvallat, Kanada, Ranska, Kiina, Japani, Kazakstan, Pohjois-Korea ja Italia.

Tähän prosessiin voi osallistua useita ihmisiä, jotka haluavat jakaa joitain esineitä erillisessä tilassa, kuten perintötavarat, herkut tai luokkahuoneen istuimet.

On toivottavaa varmistaa, että esineiden jakelu tapahtuu ilman kateutta , toisin sanoen, että jokainen löytää tarvitsemansa. Esineiden jakamattomuudesta johtuen tällainen jakautuminen on yleensä saavuttamaton (esimerkiksi yhden kohteen jakautuminen kahden agentin välillä), joten kateuden syklien menettely pyrkii saavuttamaan "toisen tason" tavoitteen - kateuden puuttumisen. yhdelle esineelle . Menetelmän tuloksena on jakauma, jossa yhden henkilön kateutta toiselle rajoittaa yksittäisen esineen rajahyöty. Toisin sanoen, kahdelle ihmiselle on sellainen esine, jota kukaan ei kadehdi, jos se poistetaan.

Menetelmän esittelivät Lipton, Markakis, Mossel ja Sabury [1] , ja se kuvataan myös julkaisussa Brandt ym. [2] .

Oletukset

Kateuden syklissä oletetaan, että jokaisella henkilöllä on määrällinen hyödyllisyysfunktio esinesarjoissa. Tämän aputoiminnon ei tarvitse olla additiivinen. Eli kohteiden ei oletetaan olevan riippumattomia .

Agenttien ei tarvitse paljastaa todellista määrällistä käyttökelpoisuuttaan – riittää, että he osaavat tilata nippuja hyödyllisyyskohtaisesti.

Toimenpide

Järjestä tuotteet satunnaiseen järjestykseen.
Vaikka kohdentamattomia kohteita on:
- Varmistetaan, että on kadehditon agentti - agentti, jota kukaan muu agentti ei kadehdi;
- Annamme seuraavan tuotteen kadehdimattomalle agentille.

Jos vaiheessa 2 ei ole kadehdittavia agentteja, tämä tarkoittaa, että kateuskaaviossa on suunnattu sykli - suunnattu graafi , jossa jokainen agentti osoittaa kaikkiin kadehtimiinsa agenteihin . Pyörit voidaan poistaa pyöräilemällä esinesarjoja. Kun kaikki syklit on poistettu, kateuskaaviossa tulisi olla solmu , joka ei saa mitään kaaria ja edustaa kadehdittavaa agenttia.

Tuloksena oleva jakelu ei välttämättä ole kateudeton, mutta se on kateudeton jakelu yhtä kohdetta lukuun ottamatta . Tämä ei päde vain loppujakelulle, vaan myös jokaiselle välijakelulle - koska tuote annetaan aina kadehdittavalle agentille, kaikkien muiden välittäjien kateus kohteen siirron jälkeen voi heijastua vain yhteen tavaraan.

Ajoaikaanalyysi

Oletetaan, että kohdetta on m . Jokainen kohteen siirto lisää enintään n -1 kaaria kateuskaavioon. Siksi kaaria ei lisätä yhteensä. Jokainen silmukan poisto poistaa vähintään kaksi kaarta. Siksi meidän ei tarvitse suorittaa silmukan poistovaihe useammin kuin kerran. Kiertohaku voidaan tehdä ajoissa käyttämällä esimerkiksi syvyyshakua . Kokonaiskäyttöaika tulee olemaan . ${\näyttötyyli (n-1)m}$ $(n-1)m/2$ $O(n^{2})$ $O(n^{3}m)$

Esimerkkejä

Näissä esimerkeissä mieltymykset annetaan arvoilla 1-3, missä suurempi numero tarkoittaa suurempaa etua. Tässä A, B ja C ovat ihmisiä ja X, Y ja Z esineitä.

1) Kolmella ihmisellä ja kolmella esineellä jokainen mahdollinen jakauma tuottaa erilaisia tuloksia. Tämä tapahtuu, kun jokaisella kolmesta osallistujasta on samat mieltymykset.

6 erilaista tulosta

	X	Y	Z
A	3	2	yksi
B	3	2	yksi
C	3	2	yksi

Objektien jakamiseen on kuusi erilaista tapaa:

Aluksi, koska kenelläkään ei ole mitään esineitä, kaikki agentit ovat kadehdittomia, ja tämä on totta kaikissa tapauksissa. Jos linkki on olemassa, jaamme linkin kadehdittavien agenttien välillä leksikografisessa järjestyksessä.

Aloitetaan kohteen X siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme tuotteen Y agentille B. Sen jälkeen on agentti C, jolle kukaan ei ole kateellinen, joten annamme kohteen Z agentille C. Nyt agentti C on mustasukkainen sekä B:lle että A:lle, agentti B on mustasukkainen, ja agentti A ei ole kateellinen kenellekään. Siten ei ole kateuden syklejä eikä jaettavia esineitä, joten menettely päättyy ja tuloksena on, että agentilla A on kohde X, agentilla B on kohde Y ja agentilla C on kohde Z.
Aloitetaan kohteen X siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Z agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Y agentille C. Nyt C on mustasukkainen A:lle, B kateellinen A:lle ja C:lle, ja agentti A ei ole kateellinen kenellekään, ja nyt, koska kateussilmukkaa ei ole eikä jaettavia esineitä ole, prosessi päättyy ja tuloksena A saa X:n, B Z:n ja C Y:n.
Aloitetaan tavaran Y siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen X agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Z agentille C. Nyt C on mustasukkainen A:lle ja B:lle, A kateellinen B:lle, ja B ei ole kateellinen kenellekään ja nyt, koska kateuden kierrettä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja tuloksena A saa Y:n, B X:n ja C Z:n.
Aloitetaan tavaran Y siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Z agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen X agentille C. Nyt A on mustasukkainen C:lle, B kateellinen A:lle ja C:lle, ja C ei ole nyt kateellinen kenellekään, koska kateuden kierrettä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja seurauksena A saa Y:n, B Z:n ja C X:n.
Aloitetaan tavaran Z siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen X agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Y agentille C. Nyt C on mustasukkainen B:lle, A on mustasukkainen B:lle ja C:lle, ja B ei ole kateellinen kenellekään ja nyt, koska kateuden kierrettä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja tuloksena A saa Z:n, B X:n ja C Y:n.
Aloitetaan tavaran Z siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Y agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen X agentille C. Nyt B on mustasukkainen C:lle, A kateellinen B:lle ja C:lle ja C ei ole nyt kateellinen kenellekään, koska kateuskiertoa ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja seurauksena A saa Z:n, B Y:n ja C X:n.

2) Kolmella ihmisellä ja kolmella esineellä jokainen mahdollinen jakauma antaa saman tuloksen. Tämä tapahtuu, kun jokaisella kolmesta ihmisestä on täysin erilaiset mieltymykset kuin muilla agenteilla, jolloin jokaisella henkilöllä on jotain erilaista, riippumatta siitä, mitä he saavat.

Sama tulos

	X	Y	Z
A	3	2	yksi
B	yksi	3	2
C	2	yksi	3

Objektien jakamiseen on kuusi erilaista tapaa:

Alussa, koska kenelläkään ei ole mitään, kaikki agentit ovat kadehdittomia ja tämä on totta kaikissa tapauksissa. Jos linkki on olemassa, jaamme linkin kadehdittavien agenttien välillä leksikografisessa järjestyksessä.

Aloitetaan kohteen X siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Y agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen Z agentille C. Nyt A, B ja C eivät ole kateellisia kenellekään ja nyt, koska kateussykliä A ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja seurauksena A saa X:n, B saa Y:n ja C Z:n.
Aloitetaan kohteen X siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Z agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole mustasukkainen, annamme viimeisen kohteen Y agentille C. Nyt C on mustasukkainen B:lle, B kateellinen C:lle ja A on ei kateellinen kenellekään. Koska B:n ja C:n välillä on kateussykli, ne vaihtavat objekteja, ja nyt B saa Y:n ja C Z:n. Tämän jälkeen, koska kateussykliä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy. tuloksena A saa X, B saa Y ja C saa Z.
Aloitetaan tavaran Y siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen X agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Z agentille C. Nyt B on mustasukkainen A:lle, A kateellinen B:lle ja C ei ole kateellinen kenellekään. Koska agenttien B ja C välillä on kateuden kierre, he vaihtavat esineitä ja nyt agentti A vastaanottaa X:n ja B vastaanottaa Y:n. Tämän jälkeen, koska kateuden kiertokulkua ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja seurauksena A saa X:n, B saa Y:n ja C Z:n.
Aloitetaan tavaran Y siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Z agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen X agentille C. Nyt B on mustasukkainen A:lle, A kateellinen C:lle ja C on mustasukkainen B:lle. Koska A:n, B:n ja C:n välillä on kateuden kierre, he kiertävät esineitä kateuden vastakkaiseen suuntaan, joten nyt A saa X:n, B saa Y:n ja C Z:n. Sen jälkeen, koska ei ole olemassa kateussilmukka eikä enää prosessoitavia kohteita, prosessi päättyy ja tuloksena A saa X:n, B saa Y:n ja C Z:n.
Aloitetaan tavaran Z siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen X agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Y agentille C. Nyt B on mustasukkainen A:lle ja C:lle, A kateellinen B:lle ja C ja C on mustasukkainen B:lle ja A:lle. Koska A:n, B:n ja C:n välillä on syklinen kateus, ohitamme esineitä vasten kateuden suuntaa, joten nyt A saa X:n, B saa Y:n ja C saa Z. , koska kateussykliä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja tuloksena A saa X:n, B saa Y:n ja C Z:n.
Aloitetaan tavaran Z siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Y agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen X agentille C. Nyt C on mustasukkainen A:lle, A kateellinen C:lle ja B kateellinen ei keneltäkään. Koska A:n ja C:n välillä on kateusjakso, ne vaihtavat objekteja ja nyt A saa X:n ja C Z:n. Tämän jälkeen, koska kateussykliä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja sen seurauksena A saa X:n, B saa Y:n ja C Z:n.

3) Kun kyseessä on 3 ihmistä ja 3 esinettä, kaikki muut tilanteet kuin ensimmäinen ja toinen esimerkki antavat useita tuloksia välillä 1-6. Jotta tämä tapahtuisi, vähintään kahdella henkilöllä on oltava sama etusija yhdelle esineelle ja enintään kaksi ihmistä, joilla on erilaiset mieltymykset samaan kohteeseen.

3 erilaista tulosta

	X	Y	Z
A	3	2	yksi
B	3	yksi	2
C	yksi	2	3

Objektien allokointiin on kuusi eri tapaa: Alussa, koska kenelläkään ei ole mitään, kaikki agentit ovat kadehdittavia ja tämä on totta kaikissa tapauksissa. Jos linkki on olemassa, jaamme linkin kadehdittavien agenttien välillä leksikografisessa järjestyksessä.

Aloitetaan kohteen X siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Y agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Z agentille C. Nyt A ei ole kateellinen kenellekään, B on mustasukkainen A:lle ja C:lle. , ja C ei ole kateellinen kenellekään, ja nyt, koska kateussilmukkaa ei ole eikä prosessoitavia esineitä ole, prosessi päättyy ja tuloksena A saa X:n, B saa Y:n ja C Z:n.
Aloitetaan kohteen X siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Z agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen kohteen Y agentille C. Nyt A ei ole kateellinen kenellekään, B on mustasukkainen A:lle ja C on mustasukkainen B:lle, ja nyt, koska kateuden kierrettä ei ole eikä prosessoitavia kohteita ole enää, prosessi päättyy ja tuloksena A saa X:n, B Z:n ja C Y:n.
Aloitetaan tavaran Y siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen X agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen Z agentille C. Nyt B ja C eivät ole kateellisia kenellekään ja A on kateellinen B:lle , ja nyt, koska ei ole kateuden syklejä eikä enää käsiteltäviä kohteita, prosessi päättyy ja tuloksena A saa Y:n, B X:n ja C Z:n.
Aloitetaan tavaran Y siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Z agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen X agentille C. Nyt A on mustasukkainen C:lle, B kateellinen C:lle ja C on mustasukkainen A:lle ja B:lle, joten on olemassa kaksi kateuden sykliä, toinen A:n ja C:n välillä ja toinen B:n ja C:n välillä. On olemassa linkki, jonka katkaisemme leksikografisessa järjestyksessä. Proseduuri ottaa ensin kateuden kierteen A:n ja C:n välillä ja vaihtaa näiden agenttien esineitä, joten nyt A ei ole kateellinen kenellekään, B on kateellinen A:lle ja C on kateellinen B:lle, joten nyt, koska kateuden kierrettä ei ole eikä prosessoitavia objekteja ole enää, proseduuri päättyy ja tuloksena A saa X:n, B saa Z:n ja C saa Y:n.
Aloitetaan tavaran Z siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen X agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen Y agentille C. Nyt A on mustasukkainen B:lle ja C:lle, B ei ole kateellinen kenellekään, ja C on mustasukkainen A:lle. Koska A:n ja C:n välillä on kateuden kierre, he vaihtavat esineitä ja nyt A saa Y:n ja C saa Z:n, ja koska nyt ei ole kateussilmukkaa eikä enää käsiteltäviä kohteita, prosessi päättyy ja tuloksena A saa Y, B saa X ja C saa Z.
Aloitetaan tavaran Z siirrosta agentille A. Sen jälkeen agentteja B ja C ei kadehdi kukaan. Joten nyt annamme kohteen Y agentille B. Sen jälkeen jää agentti C, jolle kukaan ei ole kateellinen, annamme viimeisen esineen X agentille C. Nyt B on mustasukkainen A:lle ja C:lle, A kateellinen B:lle ja C:lle , ja C on mustasukkainen B:lle ja A:lle. Koska A:n, B:n ja C:n välillä on syklinen kateus, ne vaihtavat esineitä kateuden vastakkaiseen suuntaan. Koska A:n, B:n ja C:n välillä on kuitenkin kaksi kateusjaksoa, on kaksi mahdollisuutta. Ratkaisemme epäselvyyden leksikografisessa järjestyksessä siten, että A saa X:stä C, B saa Z:stä A ja C saa Y:stä B, joten tuloksena on, että A omistaa X:n, B omistaa Z:n ja C omistaa Y:n. ei kateussykliä eikä jaettavia esineitä ole, prosessi päättyy ja tuloksena A saa X:n, B Z:n ja C Y:n.

Katso myös

Esineiden kateellinen jakelu

Muistiinpanot

↑ Lipton, Markakis, Mossel, Saberi, 2004 , s. 125.
↑ Brandt, Conitzer et ai., 2016 , s. 300-301.

Kirjallisuus

Lipton RJ, Markakis E., Mossel E., Saberi A. Jakamattomien tavaroiden suunnilleen oikeudenmukaisesta jaosta // Proceedings of the 5th ACM Conference on Electronic Commerce - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Laskennallisen sosiaalisen valinnan käsikirja . - Cambridge University Press, 2016. - ISBN 9781107060432 .