Misundelig distribution af genstande

Misundelsesfri fordeling af objekter (uden misundelse, KB, engelsk Misundelsesfri , EF-fordeling [1] ) er et problem med retfærdig fordeling af objekter , hvor retfærdighedskriteriet er fraværet af misundelse i den resulterende fordeling - hver agent skal modtage et sæt genstande, hvis værdi (som han mener) ikke er mindre end de aktier, som andre agenter har modtaget [2] .

Da objekterne er udelelige, eksisterer KB-distributionen muligvis ikke. Det enkleste tilfælde af en sådan opdeling er et objekt, som bør fordeles mellem mindst to agenter: hvis en agent får objektet, vil den anden misunde ham. Delingsprocedurer involverer således forskellige former for lempelse af kravet om ikke -misundelse .

At finde en misundelsesfri distribution, hvis den findes

Bestillingspræferencer for sæt: Ingen jalousi

Beskæringsproceduren finder en komplet KB-fordeling for to agenter, hvis og kun hvis en sådan fordeling findes. Proceduren kræver, at agenter rangordner sæt af objekter, men kræver ikke kvantitative hjælpeoplysninger . Algoritmen virker, hvis agenternes præferencer er strengt monotone , og der ikke er behov for at antage, at de er adaptive præferencer . I værste fald kan agenter have en række mulige sæt, så køretiden kanafhænge eksponentielt af antallet af objekter.

Præferencerækkefølge for objekter: Notorious/Possible Envy-Free

Det er normalt lettere for folk at bestille individuelle objekter, end det er at bestille sæt af objekter. Antag at alle agenter har adaptive præferencer , så er det muligt at hæve rækkefølgen af objekter til en delvis rækkefølge af sæt. Hvis objekterne f.eks. er ordnet w>x>y>z, indebærer dette, at {w, x}>{y, z} og {w, y}>{x, z}, men indebærer ikke nogen præference mellem { w, z} og {x, y}, mellem {x} og {y, z} og så videre.

Givet en rækkefølge af objekter:

En distribution er kendt for at være misundelsesfri ( nødvendigvis misundelsesfri , NEF), hvis den ikke er misundelsesfri for alle adaptive sætbestillinger, der er i overensstemmelse med objektrækkefølgen;
En distribution er muligvis misundelsesfri (muligvis misundelsesfri , PEF), hvis den ikke er misundelsesfri for mindst én adaptiv sætbestilling , der er i overensstemmelse med objektrækkefølgen;
En fordeling er bestemt Pareto - optimal ( NPE), hvis den er Pareto-optimal for alle adaptive sæt-bestillinger i overensstemmelse med objektrækkefølgen;
En fordeling er muligvis Pareto-optimal (PPE), hvis den er Pareto-optimal for mindst én adaptiv sæt-rækkefølge, der er i overensstemmelse med objektrækkefølgen.

Bouvre, Endriss og Leng [3] undersøgte de algoritmiske problemer med at finde en ZBZ/WBZ-fordeling med en yderligere betingelse om effektivitet, partialitet, fuldstændighed, COP eller COP. Generelt er WBZ-sagen beregningsmæssigt enklere, mens ZBZ-sagen er sværere.

Er der en KB-distribution

Den tomme fordeling er altid KB, men hvis vi vil kræve effektivitet ud over KB, bliver løsningen på problemet beregningsmæssigt vanskelig [4] :

At beslutte, om der eksisterer en komplet KB-distribution, er et NP-komplet problem. Dette gælder, selv når der kun er to agenter, og selv når hjælpefunktionerne er additive og identiske , da søgningen efter en KB-distribution i dette tilfælde svarer til at løse problemet med at opdele et sæt tal [5] .
At beslutte, om der er en Pareto-effektiv KB-fordeling, er vanskeligere end NP - den er -komplet selv med dikotome præferencefunktioner [6] og endda med additive hjælpefunktioner [7] . $\Sigma _{2}^{\textrm {P))$

Søgedistribution med begrænset misundelsesniveau

Nogle procedurer finder en fordeling, der ikke har misundelse undtagen for ét objekt (BZ1) - for to vilkårlige agenter A og B er der ét objekt, ved fjernelse af hvilket fra sættet af agent B, agent A ikke længere vil misunde agent B [8] .

Cirkulær procedure

Hvis alle agenter har svagt additive hjælpeprogrammer , giver følgende protokol (som ligner round robin-planlægning ) den fulde KB1-distribution:

Arranger agenterne på en vilkårlig måde.
Så længe der er ikke-allokerede objekter
- Vi tillader agenter med tal fra 1 at vælge et objekt. $n$

Bevis [9] : For enhver agent opdeler vi de valg, som agenterne har foretaget, i undersekvenser - den første undersekvens starter med agent 1 og slutter med agent . Den sidste undersekvens starter med og slutter med . I den anden sekvens vælger agenten først, så han vælger det bedste objekt og misunder derfor ikke den anden agent. En agent kan kun misunde en af agenterne , og enhver misundelse kommer kun fra det objekt, der blev valgt i den første efterfølgende række. Hvis denne genstand fjernes, vil agenten ikke være jaloux.

jeg

i-1

jeg

i-1

jeg

jeg

1,...,i-1

jeg

Round robin-protokollen kræver svag additivitet , da den kræver, at hver agent vælger det "bedste objekt" uden at vide, hvilke objekter der efterfølgende vil blive valgt af ham. Dette forudsætter med andre ord, at genstandene er selvstændige varer .

Envy Cycle Procedure

Proceduren med cyklusser af misundelse returnerer den komplette BZ1-distribution for vilkårlige præferencerelationer. Det eneste krav er agenternes evne til at bestille deres sæt af objekter.

Hvis præferencerne for agenter er repræsenteret af en kardinal nyttefunktion , har BZ1-garantien en yderligere fortolkning: det numeriske niveau af misundelse for hver agent overstiger ikke den maksimale marginale nytte , det vil sige den maksimale marginale nytte af et individuelt objekt for denne agent.

Tilnærmet P-CRRD-procedure

Approximate Competitive Equilibrium from Equal Income ( A -CEEI ) returnerer en delvis B31-fordeling for vilkårlige præferencer. Det eneste krav er, at agenten kan bestille samlinger af objekter.

Et lille antal objekter kan forblive uallokerede. Distribution er Pareto-effektiv for distribuerede objekter. Desuden er P-CRRD-mekanismen omtrent strategisk usårbar, hvis antallet af midler er stort.

Maksimal Nash Wellbeing

Maximum-Nash-Welfare ( MNW) -algoritmen vælger den fulde fordeling, der maksimerer produktet af hjælpeprogrammer. Det kræver, at hver agent angiver en numerisk værdi for hvert objekt og antager, at hjælpeprogrammerne til agenterne er additive. Den resulterende fordeling vil også være BZ1 og Pareto effektiv [9] .

Hvis præferencerne for agenterne ikke er additive, er MNB-løsningen ikke nødvendigvis BZ1, men hvis præferencerne for agenterne er mindst submodulære , opfylder MNB-løsningen en svagere egenskab kaldet marginalfordelingen uden misundelse bortset fra 1 objekt ( Marginal-Misundelse-Freeness) . , MEF1).

BZ1 / BZd

Der er et alternativt kriterium kaldet Ingen misundelse bortset fra den billigste (BZd) for alle to agenter A og B. Hvis vi fjerner et objekt fra agent B's sæt af objekter, vil A ikke misunde B. BZd er strengt taget stærkere end BZ1. Men det er stadig uvist, om der altid er BZd-fordelinger [9] .

Minimering af misundelsesforholdet

Givet en fordeling af X , definer misundelsesforholdet mellem i og j (Misundelsesforhold) som:

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

så forholdet er 1, hvis i ikke er jaloux på j , og større end 1, hvis i er jaloux på j . Vi definerer distributionsmisundelsesforholdet som:

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

Problemet med minimering af misundelsesforhold er problemet med at finde fordelingen X med det mindste misundelsesforhold.

Generelle skøn

Under generelle præferencer kræver enhver deterministisk algoritme , der beregner en fordeling med et minimum misundelsesforhold, et antal forespørgsler, der i værste fald eksponentielt afhænger af antallet af objekter [5] .

Additiv lige score

Med additive og identiske præferencescores [5] :

Den følgende grådige algoritme finder en fordeling, hvis misundelsesforhold højst er 1,4 gange minimum [10] ;
1. Vi arrangerer objekter i faldende værdi;
2. Mens der er ikke-allokerede objekter, giver vi det næste objekt til agenten med den mindste samlede værdi;
Der er en PTAS- ordning for at minimere misundelsesforholdet. Desuden, hvis antallet af spillere er konstant, er der en FPTAS- ordning.

Additiv forskellige skøn

Med additive og forskellige præferenceestimater [11]

Hvis antallet af agenter er inkluderet i inputdataene, er det i polynomiel tid umuligt at opnå en tilnærmelseskoefficient bedre end 1,5. Medmindre P=NP.
Hvis antallet af agenter er konstant, er der en FPTAS-ordning .
Hvis antallet af agenter er lig med antallet af objekter, er der en polynomiel tidsfordelingsalgoritme.

Søg efter delvis distribution uden misundelse

AL-proceduren finder KB-fordelingen for to agenter. Det kan kassere nogle af objekterne, men den endelige fordeling er Pareto-effektiv i den forstand, at ingen anden KB-distribution er bedre for den ene og svagt bedre for den anden. AL-proceduren kræver kun at bestille efter værdi adskilte objekter fra agenter. Proceduren forudsætter, at agenter har adaptive præferencer , og giver en fordeling, der vides at være uden misundelse ( sikkert uden misundelse, ZBZ).

" Justerende vinder "-proceduren returnerer den fulde og effektive distributions-KB for de to agenter, men kan kræve afskæring af et af objekterne (eller et af objekterne forbliver i almindelig brug). Proceduren kræver, at hver agent rapporterer en numerisk nytteværdi for hvert objekt og antager, at agenter har additive hjælpefunktioner .

Eksistensen af placering uden misundelse med tilfældige evalueringer

Hvis agenter har additive nyttefunktioner , som er taget fra sandsynlighedsfordelinger, der opfylder nogle kriterier, og antallet af objekter er tilstrækkeligt stort i forhold til antallet af agenter, så eksisterer KB-fordelingen med høj sandsynlighed . Især [12]

Hvis antallet af objekter er stort nok , så eksisterer KB-fordelingen med stor sandsynlighed (det vil sige, at sandsynligheden har en tendens til 1, da m har en tendens til uendelig). $m=\Omega (n\log n)$
Hvis antallet af objekter ikke er stort nok, det vil sige , så eksisterer KB-fordelingen med stor sandsynlighed ikke. $m=n+o(n)$

Mangel på misundelse og andre retfærdighedskriterier

Enhver KB-distribution er min-max fair . Dette følger direkte af de sædvanlige definitioner og afhænger ikke af additivitet.
Hvis agenter har additive hjælpefunktioner , så er KB-fordelingen også proportional og max-min-fair . Ellers er KB-fordelingen muligvis ikke proportional og måske ikke engang max-min-fair.
Enhver fordeling, der har en konkurrencemæssig ligevægt med lige indkomster, har ingen misundelse. Dette gælder uanset additivitet [8] .
Enhver Nash optimal fordeling (distribution, der maksimerer produktet af hjælpeprogrammer) er en KB1 [9] .

Se artiklen Problemet med en retfærdig fordeling af genstande med en detaljeret beskrivelse og referencer til litteraturen.

Sluttabel

Følgende notationer bruges nedenfor:

$n$ = antal agenter, der deltager i deling;
$m$ = antal genstande (objekter), der skal fordeles;
BE = ingen misundelse, BE1 = ingen misundelse med udelukkelse af ét fag (svagere krav end BE), BE1 = maksimalt ingen misundelse med udelukkelse af ét fag (svagere krav end BE1).
EP = Pareto efficient (PE = engelsk Pareto-efficient ).

Navn	Antal deltagere	Indgang	Præferencer	Antal anmodninger	Retfærdighed	Effektivitet	Kommentarer
Beskæring	2	Bestilte sæt	Strengt monotont	$2^{m}$	BZ	Komplet	Hvis og kun hvis der findes en komplet KB-distribution
AL procedure	2	Ordnede objekter	Svagt tilsætningsstof	$Poly(m)$	Selvfølgelig - BZ	Delvis, men distribution er ikke Pareto-domineret af en anden ZBZ
Justerbar vinder	2	Objektvurdering	Tilsætningsstof	$Poly(m)$	vidende og upartisk	EP	Ét objekt kan deles
cirkulær planlægning	$n$	Ordnede objekter	Svagt tilsætningsstof	$m$	Selvfølgelig - BZ1	Komplet
Cirkler af misundelse	$n$	Bestilte sæt	monotont	$O(mn^{3})$	BZ1	Komplet
P-CRRD mekanisme	$n$	Bestilte sæt	Nogen	?	BZ1, og - maksimering af aktier $(n+1)$	Delvis, men ES i forhold til distribuerede objekter	Omtrent strategisk usårlig, hvis der er mange agenter.
Maksimal Nash-velvære [9]	$n$	Objektvurdering	Tilsætningsstof	NP-hård (men findes i særlige tilfælde af tilnærmelse)	BZ1 og tilnærmelsesvis -maksimering af aktier $n$	EP	Med submodulære hjælpefunktioner er fordelingen EF og PBZ1.

Se også

Maksimering af aktier er et andet retfærdighedskriterium.

Noter

↑ Bogstaveligt talt - fordelingen af objekter uden misundelse, hvilket generelt er forvirrende - netop misundelse er hovedfaktoren i en sådan fordeling.
↑ Brandt, Conitzer, Endriss et al., 2016 , s. 296-297.
↑ Bouveret, Endriss, Lang, 2010 , s. 387-392.
↑ Brandt, Conitzer, Endriss et al., 2016 , s. 300-310.
↑ 1 2 3 Lipton, Markakis, Mossel, Saberi, 2004 , s. 125.
↑ Bouveret, Lang, 2008 , s. 525-564.
↑ De Keijzer, Bouveret, Klos, Zhang, 2009 , s. 98.
↑ 1 2 Budish, 2011 , s. 1061-1103.
↑ 1 2 3 4 5 Caragiannis, Kurokawa et al., 2016 , s. 305.
↑ Graham, 1969 , s. 416-429.
↑ Nguyen, Rothe, 2014 , s. 54-68.
↑ Dickerson, Goldman et al., 2014 , s. 1405-1411.

Litteratur

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Håndbog 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 og misundelsesfrihed i retfærdig opdeling af udelelige varer: logisk repræsentation og kompleksitet // JAIR. - 2008. - T. 32 . - doi : 10.1613/jair.2467 .
Bart De Keijzer, Sylvain Bouveret, Tomas Klos, Yingqian Zhang. Om kompleksiteten af effektivitet og misundelsesfrihed i retfærdig opdeling af udelelige varer med additive præferencer // Algoritmisk beslutningsteori. - 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. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes // Journal of Political Economy. - 2011. - T. 119 , no. 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 nogenlunde retfærdige tildelinger af udelelige varer // 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 , no. 2 . - doi : 10.1137/0117039 .
Trung Thanh Nguyen, Jörg Rothe. Minimering af misundelse og maksimering af gennemsnitlig Nash social velfærd i tildelingen af udelelige varer // Diskret anvendt matematik. - 2014. - T. 179 . - doi : 10.1016/j.dam.2014.09.010 .
John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, Tuomas Sandholm. Retfærdighedens beregningsmæssige stigning og fald // I forløbet af den 28. AAAI-konference om kunstig intelligens (2014). — 2014. ACM-link