Avundsjuk distribution av föremål

Avundsfri distribution av objekt (utan avund, KB, engelska Envy-free , EF-distribution [1] ) är ett problem med rättvis fördelning av objekt , där kriteriet för rättvisa är frånvaron av avund i den resulterande distributionen - varje agent måste erhålla en uppsättning objekt, vars värde (som han anser) inte är mindre än de andelar som andra ombud erhållit [2] .

Eftersom objekten är odelbara, kanske inte KB-distributionen existerar. Det enklaste fallet med en sådan uppdelning är ett objekt, som bör fördelas mellan minst två agenter: om en agent får objektet kommer den andra att avundas honom. Delningsförfaranden innebär alltså olika typer av lättnader på kravet på icke- avundsjuka .

Att hitta en avundsfri distribution om den finns

Beställningsinställningar för set: Ingen svartsjuka

Beskärningsproceduren hittar en fullständig KB-distribution för två agenter om och endast om en sådan fördelning finns. Förfarandet kräver att agenter rangordnar uppsättningar av objekt, men kräver ingen kvantitativ hjälpinformation . Algoritmen fungerar om agenternas preferenser är strikt monotona och det inte finns något behov av att anta att de är adaptiva preferenser . I värsta fall kan agenter ha ett antal möjliga uppsättningar, så att körtiden kanbero exponentiellt på antalet objekt.

Inställningsordning för objekt: Notorious/Possible Envy-Free

Det är vanligtvis lättare för människor att beställa enskilda objekt än att beställa uppsättningar av objekt. Antag att alla agenter har adaptiva preferenser , då är det möjligt att höja ordningen av objekt till en partiell ordning av set. Till exempel, om objekten är ordnade w>x>y>z, innebär detta att {w, x}>{y, z} och {w, y}>{x, z}, men det innebär inte någon preferens mellan { w, z} och {x, y}, mellan {x} och {y, z} och så vidare.

Med tanke på en ordning av objekt:

En distribution är känd för att vara avundsfri ( nödvändigtvis avundsfri , NEF) om den inte är avundsfri för alla adaptiva uppsättningsordningar som överensstämmer med objektsordningen;
En distribution är möjligen avundsfri (möjligen avundsfri , PEF) om den inte är avundsfri för minst en adaptiv uppsättningsordning som överensstämmer med objektordningen;
En fördelning är säkerligen Pareto -optimal ( NPE) om den är Pareto-optimal för alla adaptiva uppsättningsordningar som överensstämmer med objektordningen;
En fördelning är möjligen Pareto-optimal (PPE) om den är Pareto-optimal för minst en adaptiv uppsättningsordning som överensstämmer med objektordningen.

Bouvre, Endriss och Leng [3] studerade de algoritmiska frågorna för att hitta en ZBZ/WBZ-distribution med ett ytterligare villkor av effektivitet, partialitet, fullständighet, COP eller COP. I allmänhet är WBZ-fallet beräkningsmässigt enklare, medan ZBZ-fallet är svårare.

Finns det en KB-distribution

Den tomma distributionen är alltid KB, men om vi vill kräva effektivitet utöver KB, blir lösningen på problemet beräkningsmässigt svår [4] :

Att avgöra om en fullständig KB-distribution existerar är ett NP-komplett problem. Detta gäller även när det bara finns två agenter och även när verktygsfunktionerna är additiva och identiska , eftersom sökningen efter en KB-distribution i det här fallet motsvarar att lösa problemet med att partitionera en uppsättning nummer [5] .
Att bestämma om det finns en Pareto-effektiv KB-distribution är svårare än NP - den är -komplett även med dikotoma preferensfunktioner [6] och även med additiva nyttofunktioner [7] . $\Sigma _{2}^{\textrm {P))$

Sökdistribution med begränsad nivå av avund

Vissa procedurer hittar en distribution som inte har avund utom för ett objekt (BZ1) - för två agenter A och B finns det ett objekt, efter borttagning från uppsättningen av agent B kommer agent A inte längre att avundas agent B [8] .

Cirkulär procedur

Om alla agenter har svagt additiva verktyg ger följande protokoll (som liknar round robin-planering ) hela KB1-distributionen:

Ordna agenterna på ett godtyckligt sätt.
Så länge det finns ofördelade objekt
- Vi tillåter agenter med nummer från 1 att välja ett objekt. $n$

Bevis [9] : För alla agenter delar vi in de val som görs av agenterna i undersekvenser - den första undersekvensen börjar med agent 1 och slutar med agent . Den sista undersekvensen börjar med och slutar med . I den andra sekvensen väljer agenten först, så han väljer det bästa objektet och avundas därför inte den andra agenten. En agent kan bara avundas en av agenterna , och eventuell avund kommer bara från objektet som valdes i den första efterföljden. Om detta föremål tas bort kommer agenten inte att vara svartsjuk.

i

i-1

i

i-1

i

i

1,...,i-1

i

Round robin-protokollet kräver svag additivitet , eftersom det kräver att varje agent väljer det "bästa objektet" utan att veta vilka objekt som kommer att väljas av honom senare. Detta förutsätter med andra ord att föremålen är oberoende varor .

Envy Cycle Procedur

Proceduren för cykler av avund returnerar den fullständiga BZ1-distributionen för godtyckliga preferensrelationer. Det enda kravet är förmågan för agenter att beställa sina uppsättningar av objekt.

Om agenternas preferenser representeras av en kardinal nyttofunktion , så har BZ1-garantin en ytterligare tolkning: den numeriska nivån av avundsjuka för varje agent överstiger inte den maximala marginella nyttan , det vill säga den maximala marginella nyttan för ett enskilt objekt för denna agent.

Ungefärlig P-CRRD-procedur

Approximate Competitive Equilibrium from Equal Income ( A -CEEI ) returnerar en partiell B31-fördelning för godtyckliga preferenser. Det enda kravet är att agenten ska kunna beställa samlingar av objekt.

Ett litet antal objekt kan förbli oallokerade. Distributionen är Pareto-effektiv för distribuerade objekt. Dessutom är P-CRRD-mekanismen ungefär strategiskt osårbar om antalet agenter är stort.

Maximalt Nash-välbefinnande

Algoritmen Maximum-Nash-Welfare (MNW) väljer den fullständiga distributionen som maximerar produkten av verktyg. Det kräver att varje agent tillhandahåller ett numeriskt värde för varje objekt och förutsätter att verktygen för agenterna är additiv. Den resulterande fördelningen kommer också att vara BZ1- och Pareto-effektiv [9] .

Om agenternas preferenser inte är additiva, är MNB-lösningen inte nödvändigtvis BZ1, men om agenternas preferenser är åtminstone submodulära , uppfyller MNB-lösningen en svagare egenskap som kallas marginalfördelningen utan avund förutom 1 objekt ( Marginal-Envy-Freeness) . , MEF1).

BZ1 / BZd

Det finns ett alternativt kriterium som heter Ingen avund förutom det billigaste (BZd) för två av agenterna A och B. Om vi tar bort något objekt från agent B:s uppsättning objekt kommer A inte att avundas B. BZd är strikt starkare än BZ1. Men det är fortfarande okänt om det alltid finns BZd-distributioner [9] .

Minimera avundsförhållandet

Givet en fördelning av X , definiera avundsförhållandet för i till j (EnvyRatio) som:

EnvyRatio(X,i,j):=\max(1,{u_{i}(X_{j}) \over u_{i}(X_{i})})

så förhållandet är 1 om i inte är avundsjuk på j och större än 1 om jag är svartsjuk på j . Vi definierar distributionsavundsrelationen som:

EnvyRatio(X):=\max _{i,j}(EnvyRatio(X,i,j)

Problemet med att minimera avundskvoten är problemet med att hitta fördelningen X med det minsta avundsförhållandet.

Allmänna uppskattningar

Enligt allmänna preferenser kräver varje deterministisk algoritm som beräknar en fördelning med ett minimalt avundsförhållande ett antal frågor som i värsta fall exponentiellt beror på antalet objekt [5] .

Additiv lika poäng

Med additiva och identiska preferenspoäng [5] :

Följande giriga algoritm hittar en fördelning vars avundsförhållande är högst 1,4 gånger minimum [10] ;
1. Vi arrangerar objekt i fallande värdeordning;
2. Medan det finns oallokerade objekt ger vi nästa objekt till agenten med det minsta totala värdet;
Det finns ett PTAS- schema för att minimera avundsrelationen. Dessutom, om antalet spelare är konstant, finns det ett FPTAS- schema.

Additiv olika uppskattningar

Med additiva och olika preferensuppskattningar [11]

Om antalet agenter ingår i indata, är det i polynomtid omöjligt att erhålla en approximationskoefficient bättre än 1,5. Om inte P=NP.
Om antalet agenter är konstant finns det ett FPTAS-schema .
Om antalet agenter är lika med antalet objekt, finns det en polynomisk tidsfördelningsalgoritm.

Sök efter partiell distribution utan avund

AL-proceduren hittar KB-fördelningen för två agenter. Det kan kassera några av objekten, men den slutliga distributionen är Pareto-effektiv i den meningen att ingen annan KB-distribution är bättre för den ena och svagt bättre för den andra. AL-proceduren kräver att man beställer efter värde endast separata objekt från agenter. Proceduren förutsätter att agenter har adaptiva preferenser , och ger en fördelning som är känd för att vara utan avund ( förvisso utan avund, ZBZ).

Proceduren " justera vinnare " returnerar den fullständiga och effektiva distributions-KB för de två agenterna, men kan kräva att ett av objekten klipps ut (eller så är ett av objekten i vanlig användning). Proceduren kräver att varje agent rapporterar ett numeriskt nyttovärde för varje objekt och förutsätter att agenter har additiva nyttofunktioner .

Förekomsten av placering utan avund med slumpmässiga utvärderingar

Om agenter har additiva nyttofunktioner , som är hämtade från sannolikhetsfördelningar som uppfyller vissa kriterier, och antalet objekt är tillräckligt stort i förhållande till antalet agenter, så existerar KB-fördelningen med hög sannolikhet . I synnerhet [12]

Om antalet objekt är tillräckligt stort , så existerar med stor sannolikhet KB-fördelningen (det vill säga sannolikheten tenderar till 1 eftersom m tenderar till oändlighet). $m=\Omega (n\log n)$
Om antalet objekt inte är tillräckligt stort, det vill säga, så existerar inte KB-fördelningen med stor sannolikhet. $m=n+o(n)$

Brist på avund och andra kriterier för rättvisa

Varje KB-distribution är min-max rättvis . Detta följer direkt av de vanliga definitionerna och är inte beroende av additivitet.
Om agenter har additiva verktygsfunktioner är KB-fördelningen också proportionell och max-min-rättvis . Annars kanske KB-fördelningen inte är proportionell och kanske inte ens max-min-fair.
Varje distribution som har en konkurrenskraftig jämvikt med lika inkomster har ingen avund. Detta gäller oavsett additivitet [8] .
Varje Nash-optimal distribution (distribution som maximerar produkten av verktyg) är en KB1 [9] .

Se artikeln Problemet med en rättvis fördelning av föremål med en detaljerad beskrivning och referenser till litteraturen.

Sluttabell

Följande beteckningar används nedan:

$n$ = antal agenter som deltar i delning;
$m$ = antal föremål (objekt) som ska distribueras;
BE = ingen avund, BE1 = ingen avund med undantag för ett ämne (svagare krav än BE), BE1 = maximalt ingen avund med undantag för ett ämne (svagare krav än BE1).
EP = Pareto efficient (PE = engelska Pareto-efficient ).

namn	Antal deltagare	Ingång	Inställningar	Antal förfrågningar	Rättvisa	Effektivitet	Kommentarer
Beskärning	2	Beställda set	Strikt monotont	$2^{m}$	BZ	Komplett	Om och bara om en komplett KB-distribution finns
AL-förfarande	2	Beställda objekt	Svagt tillsats	$Poly(m)$	Uppenbarligen-BZ	Partiell, men distributionen är inte Pareto-dominerad av en annan ZBZ
Justerbar vinnare	2	Objektsvärdering	Tillsats	$Poly(m)$	kunnig och opartisk	EP	Ett objekt kan delas
cirkulär planering	$n$	Beställda objekt	Svagt tillsats	$m$	Uppenbarligen-BZ1	Komplett
Cykler av avund	$n$	Beställda set	monoton	$O(mn^{3})$	BZ1	Komplett
P-CRRD-mekanism	$n$	Beställda set	Några	?	BZ1, och - maximering av aktier $(n+1)$	Partiell, men ES i förhållande till distribuerade objekt	Ungefär strategiskt osårbar om det finns många agenter.
Maximalt Nash-välbefinnande [9]	$n$	Objektsvärdering	Tillsats	NP-hård (men finns i speciella fall av approximation)	BZ1 och ungefär -maximering av aktier $n$	EP	Med submodulära hjälpfunktioner är fördelningen EF och PBZ1.

Se även

Maximering av aktier är ett annat skälighetskriterium.

Anteckningar

↑ Bokstavligen - fördelningen av objekt utan avund, vilket i allmänhet är förvirrande - just avund är huvudfaktorn i en sådan fördelning.
↑ Brandt, Conitzer, Endriss et al., 2016 , sid. 296–297.
↑ Bouveret, Endriss, Lang, 2010 , sid. 387–392.
↑ Brandt, Conitzer, Endriss et al., 2016 , sid. 300–310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , sid. 125.
↑ Bouveret, Lang, 2008 , sid. 525–564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , sid. 98.
↑ 1 2 Budish, 2011 , sid. 1061–1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , sid. 305.
↑ Graham, 1969 , sid. 416–429.
↑ Nguyen, Rothe, 2014 , sid. 54–68.
↑ Dickerson, Goldman et al., 2014 , sid. 1405–1411.

Litteratur

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Handbok i Computational Social Choice . - Cambridge University Press, 2016. - ISBN 9781107060432 .
Sylvain Bouveret, Ulle Endriss, Jérôme Lang. Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods // ECAI 2010. - 2010. - s. 387–392.
Bouveret S., Lang J. Effektivitet och avundsfrihet vid rättvis uppdelning av odelbara varor: logisk representation och komplexitet // JAIR. - 2008. - T. 32 . - doi : 10.1613/jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. Om komplexiteten av effektivitet och avundsfrihet i rättvis uppdelning av odelbara varor med additiv preferenser // Algoritmisk beslutsteori. - 2009. - T. 5783. - (Lecture Notes in Computer Science). - ISBN 978-3-642-04427-4 . - doi : 10.1007/978-3-642-04428-1_9 .
Eric Buddhist. Det kombinatoriska uppdragsproblemet: Ungefärlig konkurrensjämvikt från lika inkomster // Journal of Political Economy. - 2011. - T. 119 , nr. 6 . - doi : 10.1086/664613 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare // Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16 . - 2016. - S. 305. - ISBN 9781450339360 . - doi : 10.1145/2940716.2940726 .
Lipton RJ, Markakis E., Mossel E., Saberi A. Om ungefär rättvisa tilldelningar av odelbara varor // Proceedings of the 5th ACM conference on Electronic commerce - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
Graham RL Bounds on Multiprocessing Timing Anomalies // SIAM Journal on Applied Mathematics. - 1969. - T. 17 , nr. 2 . - doi : 10.1137/0117039 .
Trung Thanh Nguyen, Jörg Rothe. Minimera avund och maximera genomsnittlig Nash social välfärd vid tilldelning av odelbara varor // Diskret tillämpad matematik. - 2014. - T. 179 . - doi : 10.1016/j.dam.2014.09.010 .
John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, Tuomas Sandholm. The Computational Rise and Fall of Fairness // I förfaranden för den tjugoåttonde AAAI-konferensen om artificiell intelligens (2014). — 2014. ACM-länk