Aktiemaximering

Aktiemaximering (MMD, eng.  Maximin share , MMS) är ett kriterium för en rättvis fördelning av objekt . Givet en uppsättning objekt med olika värden, betyder 1-ut-n maximin-andelen det största värdet som kan erhållas genom att dela upp objekten i n delar och välja delen med det lägsta värdet.

Fördelningen av objekt mellan n agenter med olika poäng kallas MMD-fair om varje agent får en uppsättning som är minst lika bra som dess 1 -out- n maximin-andel. MDM-rättvisa föreslogs av Eric Budisch [1] som en försvagning av proportionalitetskriteriet — varje agent får en uppsättning med ett värde som inte är mindre än den lika fördelningen (1/ n av varje resurs). Proportionalitet kan garanteras om objekten är delbara, men inte om de är odelbara, även om alla agenter har identiska uppskattningar. Däremot kan MMD-rättvisa alltid garanteras för identiska ombud, så detta är ett naturligt alternativ till proportionalitet även om ombuden är olika.

Motiv och exempel

Samma föremål. Antag först att m identiska objekt ska fördelas rättvist mellan n personer. Helst ska varje person ta emot m / n objekt, men det kan visa sig att om m inte är delbart med n är detta omöjligt, eftersom objekten är odelbara. Ett naturligt kriterium på andra nivån är att avrunda m / n ner till närmaste heltal och ge varje person minst golv( m / n ) objekt. Att få föremål med mindre än golv( m / n ) skulle vara "för orättvist" - denna orättvisa kan inte längre täckas av föremålens odelbarhet.

Utmärkta föremål. Anta nu att objekten är distinkta och att alla har olika värde. Avrundning nedåt till närmaste heltal kanske inte ger den önskade lösningen. Anta till exempel att n = 3 och m = 5 och värdet på objekten är 1, 3, 5, 6, 9. Summan av värdena är 24 och detta tal är delbart med 3, så helst skulle du ge varje deltagare ett föremål, värt minst 8, men det är inte möjligt. Det högsta värdet vi kan garantera alla agenter är 7, vilket är resultatet av fördelningen {1,6},{3,5},{9}.

Uppsättningen {1,6} på vilken värdet för maximin uppnås kallas "1-out-3 maximin-parts" - detta är den bästa delmängden av objekt som kan skapas genom att dela upp originaluppsättningen i 3 delar och välja minst betydande uppsättning. Därför, i det här exemplet, är fördelningen MMD-rättvis om och endast om värdet varje agent får är minst 7.

Varierande betyg. Anta nu att varje agent utvärderar varje objekt på olika sätt , till exempel

Nu har varje agent en annan uppsättning MMD:er:

Här är fördelningen MMD-rättvis om den ger Alice ett värde på minst 7, George minst 8 och Dina ett värde på minst 3. Till exempel en fördelning där George får de två första objekten {1,7 }, Alice får följande två {5,6} och Daina får objektet {17} är MMD-rättvist.

Tolkning . En agents 1-ut- n MMD kan tolkas som den maximala nytta en agent kan hoppas få på en distribution om andra agenter har samma preferenser, om han alltid får den sämsta andelen. Detta är den minimala nyttan som agenten har rätt till (enligt hans åsikt), baserat på följande argument: om andra agenter kommer att ha samma preferenser som jag, finns det åtminstone en distribution som ger mig en sådan nytta och som ger andra agenter inte mindre, därför har de ingen anledning att ge mig mindre.

Alternativ tolkning: den mest föredragna uppsättningen för agenten, garanterad av avdelaren i dela-och-välj-protokollet bland rivaliserande motståndare - agenten föreslår den bästa tilldelningen och överlåter setvalsregeln till andra, medan han tar den återstående uppsättningen [2 ] .

MMD-rättvisa kan också beskrivas som ett resultat av följande förhandlingsprocess. Viss fördelning har föreslagits. Varje agent kan klaga på en sådan distribution och erbjuda sin egen. Men efter att ha gjort det måste han tillåta de andra att ta deras andelar, medan han själv tar resterande set. Därför kommer en agent att klaga på en distribution endast om den kan erbjuda en distribution där alla uppsättningar är bättre än den nuvarande. En tilldelning är MMD-rättvis om och endast om ingen av ombuden klagar på det, det vill säga för någon agent i någon tilldelning finns en uppsättning som inte är bättre än den andel han kommer att få i den aktuella tilldelningen.

Förekomsten av MMD-rättvisa distributioner

Om alla n agenter har identiska värderingar, existerar alltid en MMD-rättvis fördelning per definition.

Om endast n -1 agenter har identiska poäng, finns MMD-rättvis fördelning fortfarande och kan hittas med hjälp av dividera-och-välj-protokollet - n -1 identiska agenter delar upp objekt i n uppsättningar, som var och en inte är sämre än MMD, sedan väljer den n :e agenten uppsättningen med högst poäng, och de identiska agenterna sorterar de återstående n -1 uppsättningarna.

I synnerhet för två agenter finns alltid en MMD-rättvis fördelning.

Bouvre och Lemaitre [2] utförde intensiva simuleringar på slumpmässiga data för mer än 2 agenter och fann att MMD-rättvisa distributioner fanns i varje försök. De bevisade att MMD-rättvisa utdelningar finns i följande fall:

Procaccia och Won [3] , samt Kurokawa [4] , konstruerade ett exempel med n= 3 agenter och m =12 objekt, där fördelningen garanterar varje agent en 1-ut-3 MMD. Dessutom visade de att det för alla finns ett exempel med föremål.

Multiplikativ approximation

För fallet att MMD-distributionerna inte existerar, föreslog Procaccia och Vaughn en multiplikativ approximation för MMD - fördelningen kallas en r-andel MMD för någon bråkdel r från [0,1] om värdet av någon agent inte är mindre än bråkdelen r av värdet av hans/hennes MMD.

De presenterade en algoritm som alltid hittar den delade MMD, där , och oddfloor( n ) är det största udda heltal som inte överstiger n . I synnerhet minskar den när n ökar och är alltid större än . Deras algoritm körs i polynomtid i m om n är konstant.

Amanatidis, Markakis, Nikzad och Saberi [5] bevisade att i slumpmässigt genererade problem existerar MMD-rättvisa distributioner med hög sannolikhet . De föreslog flera förbättrade algoritmer

Barman och Krishnamurti [6] presenterade

Godsi, Hadzhigoyi, Sedigin och Yami [7] föreslog

Garg, McGlaflin och Taki [8] föreslog en enkel algoritm för 2/3-dels MMD, vars analys är enkel.

Det är för närvarande okänt vad som är det största värdet av r för vilket det alltid finns en r -partiell MMD-fördelning. Det kan vara ett tal mellan 3/4 och 1 (exklusive 1).

Amanatidis, Burmpas och Markakis [9] föreslog osårbara strategier för ungefärliga MMD-rättvisa distributioner (se även Strategiskt rättvis uppdelning ):

Xin och Pingyang [10] studerade MMD-rättvis fördelning av tullar (objekt med negativa betyg) och visade att en 9/11-partiell MMD-fördelning alltid existerar.

Ordinal approximation

Budish [1] föreslog en annan approximation av 1 -ut- n MMD-fördelningen - 1-ut-( ) MMD (varje agent får minst lika mycket som han kunde få genom att dela upp i n + 1 set och välja den sämsta av dem) . Han visade att en ungefärlig konkurrensjämvikt med lika inkomst alltid garanterar 1-av-( ) MMD. Denna fördelning kan dock överstiga antalet tillgängliga objekt, och, ännu viktigare, överstiga behoven - summan av set som distribueras till alla agenter kan vara något större än summan av alla objekt. Ett sådant fel är acceptabelt vid tilldelning av platser till kursens studenter, eftersom en liten brist kan korrigeras genom att lägga till ett litet antal stolar. Men det klassiska rättvisa uppdelningsproblemet förutsätter att föremål inte kan läggas till.

För valfritt antal agenter med additiv estimator, ger varje avundsfri rättvis fördelning med undantag av  en ( EF1) varje agent minst 1-ut-(2n -1 ) MMD [11] . BZ1-fördelningen kan till exempel hittas med hjälp av den cykliska fördelningen av objekt eller förfarandet för avundsjuka .

Dessutom kan 1-ut-(2n -2) MMD-distributionen hittas med hjälp av avundsfri matchning [12] .

För närvarande är det inte känt vad som är det minsta N för vilket det alltid finns en 1-ut- N MMD-fördelning. Det kan vara vilket tal som helst mellan n +1 och 2 n -2. Det minsta värdet på n för vilket sådant N inte längre är känt är 4.

Det initiala MDM-villkoret kan användas för asymmetriska medel (agenter med olika andelar på grund av dem) [13] .

Andra algoritmiska problem

Några grundläggande algoritmer relaterade till MMD:

MMD-rättvisa för grupper

En tilldelning kallas parvis -maximin-share-fair ( PMMS -fair) om agent i för något par av agenter i  och j får åtminstone sin 1-out-2 maximin- andelen begränsad av objekt från den totala uppsättningen av objekt i och j [16] .

Fördelningen kallas group - wise-maximin-share-fair ( GMMS  -fair) om, för någon undergrupp av agenter av storlek k , varje medlem i undergruppen får sin 1- av- k maximin-andel, begränsad till objekt som erhållits av denna undergrupp [17] .

Olika föreställningar om rättvisa relateras till additiva värderingar på följande sätt.

HMMD-distributioner finns garanterat när agenternas uppskattningar är antingen binära eller identiska. Med allmänna additiva uppskattningar existerar 1/2-HMMD-distributioner och kan hittas i polynomtid [17] .

Se även

Anteckningar

  1. ↑ 1 2 Budish, 2011 , sid. 1061–1103.
  2. ↑ 1 2 3 Bouveret, Lemaître, 2015 , sid. 259.
  3. ↑ Procaccia, Wang, 2014 , sid. 675–692.
  4. ↑ Arkiverad kopia . Hämtad 26 februari 2020. Arkiverad från originalet 28 juli 2019.
  5. ↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , sid. 1–28.
  6. ↑ Barman, Krishnamurthy, 2017 , sid. 647-664.
  7. ↑ Ghodsi, Hajiaghayi et al., 2018 , sid. 539-556.
  8. ↑ Garg, McGlaughlin, Taki, 2018 , sid. 20:1–20:11.
  9. ↑ Amanatidis, Birmpas, Markakis, 2016 , sid. 31-37.
  10. ↑ Huang, Lu, 2019 .
  11. ↑ Segal-Halevi, Suksompong, 2019 , sid. 103167.
  12. ↑ Aigner-Horev, Segal-Halevi, 2019 .
  13. ↑ Segal-Halevi, 2019 .
  14. ↑ Woeinger, 1997 , sid. 149–154.
  15. ↑ Lang, Rothe, 2016 , sid. 493–550.
  16. ↑ 1 2 Caragiannis, Kurokawa et al., 2019 , sid. 12:1–12:32.
  17. ↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
  18. ↑ Avundslöshet upp till det minst värderade godset .  Se Caragiannis, Kurokawa et al.

Litteratur