Aktiemaksimering

Aktiemaksimering (MMD, eng. Maximin share , MMS) er et kriterium for en retfærdig fordeling af objekter . Givet et sæt af objekter med forskellige værdier, betyder 1-ud-n maximin-share den største værdi, der kan opnås ved at opdele objekterne i n dele og vælge delen med minimumsværdien.

Fordelingen af objekter blandt n agenter med forskellige score kaldes MMD-fair, hvis hver agent får et sæt, der er mindst lige så godt som dens 1 -ud- n maximin-share. MDM-retfærdighed blev foreslået af Eric Budisch [1] som en svækkelse af proportionalitetskriteriet - hver agent modtager et sæt med en værdi, der ikke er mindre end den lige store fordeling (1/ n af hver ressource). Proportionalitet kan garanteres, hvis objekterne er delelige, men ikke hvis de er udelelige, selvom alle agenter har identiske estimater. Derimod kan MMD-fairness altid garanteres for identiske agenter, så dette er et naturligt alternativ til proportionalitet, selvom agenterne er forskellige.

Motiver og eksempler

De samme objekter. Antag først, at m identiske objekter skal fordeles retfærdigt blandt n personer. Ideelt set bør hver person modtage m / n objekter, men det kan vise sig, at hvis m ikke er deleligt med n , er dette umuligt, da objekterne er udelelige. Et naturligt kriterium på andet niveau er at runde m / n ned til nærmeste heltal og give hver person mindst etage( m / n ) objekter. At få mindre end gulv( m / n ) genstande ville være "for uretfærdigt" - denne uretfærdighed kan ikke længere dækkes af genstandes udelelighed.

Fornemme genstande. Antag nu, at objekterne er forskellige og hver har en forskellig værdi. Afrunding ned til nærmeste heltal giver muligvis ikke den ønskede løsning. Antag for eksempel, at n = 3 og m = 5, og værdien af objekterne er 1, 3, 5, 6, 9. Summen af værdierne er 24, og dette tal er deleligt med 3, så ideelt set ville du give hver deltager en genstand til en værdi af mindst 8, men det er ikke muligt. Den højeste værdi, vi kan garantere for alle agenter, er 7, hvilket er resultatet af fordelingen {1,6},{3,5},{9}.

Sættet {1,6}, hvorpå værdien af maximin nås, kaldes "1-out-3 maximin-parts" - dette er den bedste undergruppe af objekter, der kan oprettes ved at opdele det originale sæt i 3 dele og vælge mindst betydningsfulde sæt. Derfor er fordelingen i dette eksempel MMD-fair, hvis og kun hvis værdien hver agent modtager er mindst 7.

Forskellige vurderinger. Antag nu, at hver agent evaluerer hvert objekt forskelligt , f.eks

Alice vurderer objekter til 1,3,5,6,9;
George vurderer dem til 1,7,2,6,8;
Dayna vurderer dem til 1,1,1,4,17.

Nu har hver agent et andet sæt MMD'er:

Alices MMD er stadig {1,6} som ovenfor;
Georges MMD vil være {1,7}, {2,6} eller {8} ved opdeling af {1,7},{2,6},{8} (alle disse sæt er ækvivalente for ham);
Dinas MMD vil være {1,1,1} ved opdeling af {1,1,1},{4},{17}.

Her er fordelingen MMD-fair, hvis den giver Alice en værdi på mindst 7, George mindst 8 og Dina en værdi på mindst 3. For eksempel en fordeling, hvor George får de to første objekter {1,7 }, Alice får de følgende to {5,6} og Daina får objektet {17} er MMD-fair.

Fortolkning . En agents 1-ud- n MMD kan tolkes som den maksimale nytte, en agent kan håbe på at få ud af en distribution, hvis andre agenter har de samme præferencer, hvis han altid får den dårligste andel. Dette er den minimale nytte, som agenten er berettiget til (efter hans mening), baseret på følgende argumenter: hvis andre agenter vil have de samme præferencer som mig, er der mindst én distribution, der vil give mig en sådan nytte, og som giver andre agenter ikke mindre, derfor har de ingen grund til at give mig mindre.

Alternativ fortolkning: det mest foretrukne sæt for agenten, garanteret af divideren i del-og-vælg-protokollen blandt rivaliserende modstandere - agenten foreslår den bedste tildeling og overlader sætudvælgelsesreglen til andre, mens han tager det resterende sæt [2 ] .

MMD-retfærdighed kan også beskrives som resultatet af den følgende forhandlingsproces. En vis fordeling er blevet foreslået. Hver agent kan klage over en sådan distribution og tilbyde sin egen. Men efter at have gjort det, skal han lade de andre tage deres andele, mens han selv tager det resterende sæt. Derfor vil en agent kun klage over en distribution, hvis den kan tilbyde en distribution, hvor alle sæt er bedre end det nuværende. En tildeling er MMD-fair, hvis og kun hvis ingen af agenterne klager over det, det vil sige, at der for en agent i enhver tildeling er et sæt, der ikke er bedre end den andel, han får i den aktuelle tildeling.

Eksistensen af MMD-fair distributioner

Hvis alle n agenter har identiske værdiansættelser, eksisterer der pr. definition altid en MMD-fair fordeling.

Hvis kun n -1 agenter har identiske score, eksisterer MMD-fair-fordelingen stadig og kan findes ved hjælp af opdel-og-vælg-protokollen - n -1 identiske agenter opdeler objekter i n sæt, som hver især ikke er værre end MMD, derefter vælger den n'te agent det sæt med den højeste score, og de identiske agenter sorterer de resterende n -1 sæt.

Især for to agenter eksisterer der altid en MMD-fair fordeling.

Bouvre og Lemaitre [2] udførte intensive simuleringer på tilfældige data for mere end 2 agenter og fandt, at MMD-fair-fordelinger fandtes i hvert forsøg. De beviste, at der findes MMD-fair-fordelinger i følgende tilfælde:

Binære vurderinger - agenten kan enten lide objektet (værdien er 1) eller kan ikke lide det (værdien er 0).
Identiske multisæt — agenter kan evaluere objekter på forskellige måder, men multisæt af agenters evalueringer er de samme.
Få genstande - . $m\leqslant n+3$

Procaccia og Won [3] samt Kurokawa [4] konstruerede et eksempel med n= 3 agenter og m =12 objekter, hvor fordelingen garanterer hver agent en 1-ud-3 MMD. Desuden viste de, at der for enhver er et eksempel med objekter. $n\geqslant 3$ $3n+4$

Multiplikativ approksimation

I tilfælde af, at MMD-fordelingerne ikke eksisterer, foreslog Procaccia og Vaughn en multiplikativ tilnærmelse for MMD - fordelingen kaldes en r-andel MMD for en brøkdel r fra [0,1], hvis værdien af en agent ikke er mindre end brøkdelen r af værdien af hans/hendes MMD.

De præsenterede en algoritme, der altid finder den -delte MMD, hvor , og oddfloor( n ) er det største ulige heltal, der ikke overstiger n . Især falder den, når n stiger og er altid større end . Deres algoritme kører i polynomiel tid i m , hvis n er konstant. $r_{n}$ $r_{n}:={\tfrac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}$ $r_{3}=r_{4}={\tfrac {3}{4))$ ${\tfrac {2}{3))$

Amanatidis, Markakis, Nikzad og Saberi [5] beviste, at der i tilfældigt genererede problemer eksisterer MMD-fair-fordelinger med høj sandsynlighed . De foreslog flere forbedrede algoritmer

Enkel og hurtig 1/2-delt MMD-algoritme;
2/3-partiel MMD-algoritme, der kører i polynomiel tid i både m og n ;
7/8-delt MMD-algoritme til 3 agenter;
MMD-fair-algoritme til tilfælde af ternære evalueringer - når værdien er lig med et af tre tal - 0, 1 eller 2.

Barman og Krishnamurti [6] præsenterede

En enkel og effektiv algoritme til 2/3-delt MDM med additive estimater baseret på proceduren for misundelsescyklusser .
En simpel algoritme for 1/10-delt MDM til det mere komplekse tilfælde af submodulære sætfunktioner baseret på fordelingen af objekter i en cirkel (Round-robin).

Godsi, Hadzhigoyi, Sedigin og Yami [7] foreslog

For additive estimater: polynomiel tidsalgoritme for 3/4-delt MMD.
For n =4 tilsætningsstoffer: Algoritme for 4/5-delt MDM.
For submodulære estimater: en polynomisk tidsalgoritme for 1/3-delt MMD og en øvre grænse for 3/4-delt MMD.
For estimater med fraktioneret subadditivitet : polynomiel tidsalgoritme for 1/8-del MMD, bevis for eksistensen af 1/5-del MMD og en øvre grænse for 1/2-del MMD.
For semi-additive estimatorer: bevis for eksistensen af log( m )/10-partiel MMD og en øvre grænse for 1/2-partiel MMD.

Garg, McGlaflin og Taki [8] foreslog en simpel algoritme for 2/3-delt MMD, hvis analyse er enkel.

Det er i øjeblikket uvist, hvad der er den største værdi af r , for hvilken der altid eksisterer en r -partiel MMD-fordeling. Det kan være et tal mellem 3/4 og 1 (ikke inkluderet 1).

Amanatidis, Burmpas og Markakis [9] foreslog usårbare strategier for omtrentlige MMD-fair-fordelinger (se også Strategisk retfærdig opdeling ):

For n midler: 1/O( m )-partiel MMD.
For 2 agenter: 1/2 deler MMD og bevis på, at ingen usårbar mekanisme vil give mere end 1/2.

Xin og Pingyang [10] undersøgte den MMD-retfærdige fordeling af pligter (objekter med negative vurderinger) og viste, at en 9/11-partiel MMD-fordeling altid eksisterer.

Ordinal tilnærmelse

Budish [1] foreslog en anden tilnærmelse af 1 -ud- n MMD-fordelingen - 1-ud-( $n+1$ ) MMD (hver agent får mindst lige så meget, som han kunne få ved at opdele i n + 1 sæt og vælge det værste af dem) . Han viste, at en tilnærmet konkurrencemæssig ligevægt med lige indkomst altid garanterer 1-af-( $n+1$ ) MMD. Denne fordeling kan dog overstige antallet af tilgængelige objekter og, endnu vigtigere, overstige behovene - summen af sæt distribueret til alle agenter kan være lidt større end summen af alle objekter. En sådan fejl er acceptabel ved tildeling af pladser til kursets studerende, da en lille mangel kan rettes ved at tilføje et lille antal stole. Men det klassiske fair divisionsproblem forudsætter, at der ikke kan tilføjes varer.

For et hvilket som helst antal agenter med additive estimatorer giver enhver misundelsesfri retfærdig fordeling med undtagelse af én ( EF1) hver agent mindst 1-ud-( 2n - 1) MMD [11] . BZ1-fordelingen kan f.eks. findes ved hjælp af den cykliske fordeling af objekter eller misundelsescyklusser .

Desuden kan 1-ud-( 2n -2) MMD-fordelingen findes ved hjælp af misundelsesfri matchning [12] .

På nuværende tidspunkt vides det ikke, hvad der er minimum N , for hvilket der altid eksisterer en 1-ud- N MMD-fordeling. Det kan være et hvilket som helst tal mellem n +1 og 2 n -2. Den mindste værdi af n , som sådan N ikke længere er kendt for, er 4.

Den indledende MDM-betingelse kan bruges til asymmetriske midler (midler med forskellige andele på grund af dem) [13] .

Andre algoritmiske problemer

Nogle grundlæggende algoritmer relateret til MMD:

Beregning af MMD for den givne agent. Dette problem er NP-svært selv for agenter med additive værdiansættelser - det kan reduceres fra problemet med at opdele et sæt tal . Voginger [14] udviklede en algoritme med PTAS- kompleksitet til dette problem.
Problemet med at bestemme, om en given fordeling er 1-af- MMD $n$ , co-NP er komplet for midler med additive estimater.
At finde ud af, om et givet problem tillader nogen MMD-fordeling, hører til klassen , det vil sige, at problemet kan løses i ikke-deterministisk polynomisk tid ved hjælp af et orakel til et NP-problem (en forudsigelse er nødvendig for at beregne MMD-agenten). Imidlertid er den nøjagtige beregningsmæssige kompleksitet af dette problem ukendt - det kan have niveau 2, 1 eller endda 0 i polynomiehierarkiet [2] [15] . $NP^{NP}$

MMD-retfærdighed for grupper

En tildeling kaldes parvis -maximin-share-fair ( PMMS -fair), hvis agent i for et hvilket som helst par af agenter i og j modtager mindst sin 1-ud-2 maximin- andelen begrænset af objekter fra det samlede sæt af objekter i og j [16] .

Fordelingen kaldes gruppe - wise-maximin-share-fair ( GMMS -fair), hvis, for en undergruppe af agenter af størrelse k , hvert medlem af undergruppen modtager sin 1- ud af- k maximin-share, begrænset til genstande opnået af denne undergruppe [17] .

Forskellige begreber om retfærdighed er relateret til additive værdiansættelser på følgende måde.

Fra retfærdighed med fravær af misundelse følger HMMD-retfærdighed, [17] ;
Fra HMMD-fairness følger MMD-fairness (hvis vi tager en gruppe af størrelse n ) og PMMD-fairness (hvis vi tager gruppestørrelse 2);
Fra PMMD-fairness følger 1/2-HMMD-fairness [16] ;
Fra PMMD-justice følger BZX [18] , hvorfra følger BZ1.
Fra MMD-retfærdighed følger ikke PMMD-retfærdighed, det samme for PMMD=>MMD.

HMMD-distributioner er garanteret at eksistere, når agenternes estimater er enten binære eller identiske. Med generelle additive estimater eksisterer 1/2-HMMD-fordelinger og kan findes i polynomiel tid [17] .

Se også

Misundelig distribution af genstande

Noter

↑ 1 2 Budish, 2011 , s. 1061-1103.
↑ 1 2 3 Bouveret, Lemaître, 2015 , s. 259.
↑ Procaccia, Wang, 2014 , s. 675-692.
↑ Arkiveret kopi . Hentet 26. februar 2020. Arkiveret fra originalen 28. juli 2019. (ubestemt)
↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , s. 1-28.
↑ Barman, Krishnamurthy, 2017 , s. 647-664.
↑ Ghodsi, Hajiaghayi et al., 2018 , s. 539-556.
↑ Garg, McGlaughlin, Taki, 2018 , s. 20:1–20:11.
↑ Amanatidis, Birmpas, Markakis, 2016 , s. 31-37.
↑ Huang, Lu, 2019 .
↑ Segal-Halevi, Suksompong, 2019 , s. 103167.
↑ Aigner-Horev, Segal-Halevi, 2019 .
↑ Segal-Halevi, 2019 .
↑ Woeinger, 1997 , s. 149-154.
↑ Lang, Rothe, 2016 , s. 493-550.
↑ 1 2 Caragiannis, Kurokawa et al., 2019 , s. 12:1–12:32.
↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
↑ Misundelse af frihed op til det mindst værdsatte gode . Se Caragiannis, Kurokawa et al.

Litteratur

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 .
Sylvain Bouveret, Michel Lemaître. Karakterisering af konflikter i retfærdig opdeling af udelelige varer ved hjælp af en skala af kriterier // Autonome agenter og multiagentsystemer. - 2015. - T. 30 , no. 2 . - doi : 10.1007/s10458-015-9287-3 .
Jérome Lang, Jörg Rothe. Fair Division of Indivisible Goods // Økonomi og beregning: En introduktion til algoritmisk spilteori, Computational Social Choice og Fair Division / Rothe . - Springer Berlin Heidelberg, 2016. - (Springer Texts in Business and Economics). — ISBN 9783662479049 . - doi : 10.1007/978-3-662-47904-9_8 .
Ioannis Caragiannis, David Kurokawa, Herve Moulin, Ariel D. Procaccia, Nisarg Shah, Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare // ACM Trans. Øko. Comput.. - 2019. - V. 7 , no. 3 . — ISSN 2167-8375 . - doi : 10.1145/3355902 .
Procaccia AD, Wang J. Fair nok: garanterer omtrentlige maksimalandele // EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation. - 2014. - S. 675-692. — ISBN 9781450325653 . - doi : 10.1145/2600057.2602835 .
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi. Approksimationsalgoritmer til beregning af Maximin Share Allocations // ACM Transaktioner på Algoritmer. - 2017. - T. 13 , no. 4 . - doi : 10.1145/3147173 . - arXiv : 1503.00941 .
Siddharth Barman, Sanath Kumar Krishnamurthy. Proceedings of the 2017 ACM Conference on Economics and Computation. – 2017.
Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Hadi Yami. Fair Allocation of Indivisible Goods: Improvement and Generalization // Proceedings of the 2018 ACM Conference on Economics and Computation. – 2018.
Jugal Garg, Peter McGlaughlin, Setareh Taki. Approximating Maximin Share Allocations // 2nd Symposium on Simplicity in Algorithms (SOSA 2019) / Jeremy T. Fineman, Michael Mitzenmacher. — Dagstuhl, Tyskland: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. — T. 69 . - ISBN 978-3-95977-099-6 . - doi : 10.4230/OASIcs.SOSA.2019.20 .
Georgios Amanatidis, Georgios Birmpas, Evangelos Markakis. Femogtyvende internationale fælleskonference om kunstig intelligens, IJCAI 2016. - 2016.
Xin Huang, Pinyan Lu. En algoritmisk ramme til at tilnærme maksimal andel tildeling af opgaver. – 2019.
Erel Segal-Halevi, Warut Suksompong. Demokratisk retfærdig fordeling af udelelige varer // Kunstig intelligens. - 2019. - T. 277 . — ISSN 0004-3702 . - doi : 10.1016/j.artint.2019.103167 . - arXiv : 1709.02564 .
Elad Aigner-Horev, Erel Segal-Halevi. Misundelsesfrie matchninger i bipartite grafer og deres applikationer til fair division. – 2019.
Erel Segal-Halevi. Maximin Share-dominansforholdet. – 2019.
Gerhard J. Woeinger. Et polynomisk-tidstilnærmelsesskema til at maksimere den minimale maskingennemførelsestid // Operations Research Letters. - 1997. - T. 20 , no. 4 . — ISSN 0167-6377 . - doi : 10.1016/S0167-6377(96)00055-7 .
Siddharth Barman, Arpita Biswas, Sanath Kumar Krishnamurthy, Y. Narahari. Groupwise Maximin Fair Allocation of Indivisible Goods // 32. AAAI-konference om kunstig intelligens. – 2018.