Rättvis fördelning av föremål och pengar

Rättvis fördelning av föremål och pengar är en klass av rättvis fördelningsproblem där det under tilldelningsprocessen är möjligt att ge eller ta pengar från några av deltagarna. Utan pengar kan det vara omöjligt att fördela odelbara föremål rättvist. Till exempel, om det finns ett föremål och två personer, och föremålet måste ges helt till en av dem, blir tilldelningen orättvis mot den andra. Monetära betalningar gör det möjligt att uppnå rättvisa, som förklaras nedan.

Två agenter och en vara

Med två agenter och ett föremål är det möjligt att uppnå rättvisa med hjälp av följande enkla algoritm (som är en variant av klipp och välj ):

Alice säger ett pris p som hon är villig att betala för varan.
George väljer om han vill ta varan och betala p , eller lämna varan till Alice så att Alice betalar p .

Denna algoritm förutsätter att agenterna har kvasilinjära verktyg , det vill säga deras nytta är värdet av föremål plus summan pengar som de har. Om George tycker att Alices pris är lågt (han är villig att betala mer än p ), så tar han föremålet och betalar p , och hans nytta är positiv, så han avundas inte Alice. Alice avundas inte heller George eftersom hans nytta - i hennes ögon - är 0. På samma sätt, om George tycker att Alices pris är högt (han är villig att betala p eller mer ), så lämnar han föremålet till Alice och gör det inte avund, eftersom Alices nytta i hans ögon är negativ.

De betalda pengarna p kan senare delas lika mellan spelarna, eftersom en lika monetär överföring inte påverkar de relativa verktygen. Sedan betalar köpagenten i praktiken p /2 till säljaren. Den totala nyttan för varje agent är minst 1/2 av hans/hennes nytta för föremålet. Om ombuden har olika rättigheter , bör de betalda pengarna p fördelas mellan partnerna i proportion till deras rättigheter.

Det finns olika verk som utökar denna enkla idé till fler än två spelare och mer komplexa inställningar. De viktigaste rättvisekriterierna i dessa verk är avundsfrihet . Dessutom överväger vissa verk en miljö där en välvillig tredje part är villig att subventionera tilldelningen, men vill minimera subventionsbeloppet beroende på avundsfrihet. Detta problem kallas minimibidrag avundsfri tilldelning .

Agenter för enhetsefterfrågan

Agenter som efterfrågar enheter är intresserade av högst en enskild artikel.

Hyresharmoni

Ett specialfall av denna inställning är när man delar upp rum i en lägenhet mellan hyresgäster. Det kännetecknas av tre krav: (a) antalet agenter är lika med antalet föremål, (b) varje agent måste få exakt en artikel (rum), (c) den totala summan som betalas av agenterna måste vara lika med en fast konstant, som representerar den totala lägenhetshyran. Detta är känt som Rental Harmony- problemet.

Mer allmänna inställningar

Generellt sett är det i ekonomilitteraturen vanligt att anta att varje agent har en nyttofunktion på buntar (en bunt är ett par av ett objekt och en viss summa pengar). Nyttofunktionen ska vara kontinuerlig och öka i pengar. Det behöver inte vara linjärt i pengar, men måste vara "arkimediskt", dvs det finns ett värde V så att för vartannat objekt j och k bör nyttan av objekt j plus V vara större än nyttan av objekt k (alternativt är nyttan av att få objekt j gratis är större än nyttan av att få objekt k och betala V ). Kvasilinjär nytta är ett specialfall av arkimedisk nytta, där V är den största värdeskillnaden (för samma agent) mellan två objekt.

Svensson bevisade först att, när alla agenter är arkimediska, existerar en avundsfri tilldelning och är Pareto-optimal.

Demange, Gale och Sotomayor visade en naturligt stigande auktion som uppnår en avundsfri tilldelning med hjälp av monetära betalningar för agenter för enhetsefterfrågan.

Maskin bevisade existensen av en Pareto-optimal avundsfri allokering när den totala penningtilldelningen är mer än ( n-1 ) V. Bevisen använder konkurrenskraftig jämvikt .

Observera att en subvention på ( n -1) V kan krävas: om alla agenter värderar ett enstaka objekt till V och de andra objekten till 0, så kräver avundsfrihet en subvention på V för varje agent som inte tar emot objektet.

Tadenuma och Thomson studerar flera konsistensegenskaper hos regler för avundsfri tilldelning.

Aragones kännetecknar minimibeloppet av subventioner som krävs för avundsjuka. Tilldelningen som uppnår denna minimisubvention är nästan unik: det finns bara ett sätt att kombinera objekt med agenter, och alla agenter är likgiltiga bland alla minimisubventionstilldelningar. Det sammanfaller med lösningen som kallas "pengar-Rawlsian-lösningen" av Alkan, Demange och Gale. Den kan hittas i polynomtid, genom att hitta en maxviktsmatchning och sedan hitta kortaste vägarna i en viss inducerad graf.

Klijn presenterar en annan polynom-tidsalgoritm för samma inställning. Hans algoritm använder polytopen av sidobetalningar som gör en given allokering avundsfri: denna polytop är icke tom om den ursprungliga allokeringen är Pareto-effektiv. Anslutningen av den oriktade avundsgrafen kännetecknar extrempunkterna för denna polytop. Detta innebär en metod för att hitta extrema avundsfria tilldelningar.

Tillsatsmedel

Tillsatsmedel kan ta emot flera objekt, så allokeringsproblemet blir mer komplext - det finns många fler möjliga allokeringar.

Knasters auktion

Det första förfarandet för rättvis fördelning av föremål och pengar uppfanns av Bronislaw Knaster och publicerades av Hugo Steinhaus . Denna auktion fungerar enligt följande, för varje föremål separat:

Varje agent lägger ett bud på föremålet.
Objektet ges till högstbjudande (bryter band godtyckligt).
Vinnaren betalar ( n -1)/ n av sitt bud;
Var och en av de andra agenterna får 1/ n av sitt bud;
Eftersom vinnaren är högstbjudande finns det ett icke-negativt överskott; överskottet fördelas lika mellan ombuden.

Användbarheten för varje agent är minst 1/ n av det värde han tillskriver hela uppsättningen objekt, så allokeringen är proportionell . Dessutom maximerar allokeringen summan av verktyg, så den är Pareto-effektiv .

Knasters auktion är inte strategisäker . Vissa forskare analyserade dess prestation när agenter spelar strategiskt:

Essen bevisar att jämviktsallokeringen fortfarande är Pareto-effektiv, men kanske inte är proportionell i efterhand. Men i genomsnitt får agenter samma resultat som om alla vore sanningsenliga. Det vill säga mekanismen är proportionell ex-ante.
Fragnelli och Marina visar att även agenter som är oändligt riskvilliga kan få en säker vinst genom en gemensam felaktig rapportering av sina värderingar, oavsett de andra agenternas deklarationer.

Knasters auktion har anpassats till rättvis tilldelning av trådlösa kanaler.

Raiths auktion

Matthias G. Raith presenterade en variant på Knasters auktion, som han kallade "Adjusted Knaster". Liksom på Knasters auktion ges varje föremål till högstbjudande. Men betalningarna är olika. Betalningarna bestäms enligt följande:

Varje agent som vinner ett föremål betalar sitt bud för detta föremål;
Det totala beloppet som betalas av agenterna fördelas mellan dem i proportion till deras bud.

För att illustrera skillnaden mellan Knasters auktion och Raiths auktion, överväg en inställning med två föremål och två agenter med följande värden:


	Punkt 1	Punkt 2	Belopp
Alice	10	10	20
George	60	120	180

I båda auktionerna vinner George båda föremålen, men betalningarna är olika:

I Knasters auktion betalar George 90, Alice får 10, och skillnaden på 80 delas lika, så nettoförsörjningen är 50, 130.
I Raiths auktion betalar George 180 och det är uppdelat i förhållandet 20:180 = 1:9, det vill säga Alice får 18 och George får 162. Observera att betalningarna beräknas till alla föremål på en gång - inte för varje föremål separat.

I experiment med mänskliga försökspersoner fann man att deltagarna föredrar Raiths auktion (Adjusted Knaster) framför Divide-and-Choose och Proportional Knaster (en variant där varje vinnare betalar 1/n av vinsten till varje förlorare; i ovanstående George betalar till exempel 90 till Alice, och nettoförsörjningen är 90, 90).

Ersättningsförfarande

Haake, Raith och Su presenterar kompensationsförfarandet. Deras procedur tillåter godtyckliga begränsningar för buntar av föremål, så länge de är anonyma (gör inte skillnad på partner baserat på deras identitet). Till exempel kan det inte finnas någon begränsning alls, eller en begränsning som "varje partner måste ta emot minst ett visst antal föremål", eller "vissa föremål måste buntas ihop" (t.ex. för att de är tomter som måste finnas kvar anslutna), etc. "Artiklar" kan ha både positiva eller negativa verktyg. Det finns ett "kvalifikationskrav" för en partner: summan av hans bud måste vara minst den totala kostnaden. Proceduren fungerar i följande steg.

Hitta en maxsumma ( utilitaristisk ) allokering - en allokering med en högsta summa av verktyg som uppfyller begränsningarna för buntar av objekt. Om det inte finns några begränsningar är en allokering som ger varje objekt till partnern med högst värdering maxsum. Om det finns begränsningar (som "minst ett objekt per partner"), kan en maxsumallokering vara svårare att hitta.
Debitera varje partner värdet av paketet som tilldelats honom. Detta skapar den initiala poolen av pengar.
Betala kostnaden från den första poolen. Om alla partners uppfyller kvalifikationskravet räcker pengarna i poolen och det kan finnas ett visst överskott .
Eliminera avund genom att kompensera avundsjuka partners. Det finns högst $n-1$ omgångar av kompensation. Förfarandet är helt beskrivande och säger uttryckligen vilka ersättningar som ska göras och i vilken ordning. Dessutom är det enkelt nog att utföras utan datorstöd.
Summan av ersättningar som görs i alla omgångar är den minsta summa som krävs för att eliminera avund, och den överstiger aldrig överskottet. Om något överskott finns kvar kan det delas upp på något sätt som inte skapar avund, t.ex. genom att ge lika mycket till varje partner (papperet diskuterar andra alternativ som kan anses vara "rättvisare").

När det finns många objekt och komplexa begränsningar kan det första steget - att hitta en maxsumallokering - vara svårt att beräkna utan en dator. I detta fall kan kompensationsförfarandet börja med en godtycklig tilldelning. I det här fallet kan proceduren avslutas med en tilldelning som innehåller avundscykler . Dessa cykler kan tas bort genom att flytta buntar längs cykeln, som i avundsdiagrammet . Detta ökar strikt den totala summan av verktyg. Följaktligen, efter ett begränsat antal iterationer, kommer en maxsumallokering att hittas, och proceduren kan fortsätta enligt ovan för att skapa en avundsfri allokering.

Ersättningsförfarandet kan debitera vissa partners en negativ betalning (dvs. ge partnerna en positiv summa pengar). Författarna säger:

"Vi utesluter inte möjligheten att en individ i slutändan får betalt av de andra för att ta ett paket med varor. I samband med rättvis uppdelning finner vi inte detta problematiskt alls. Ja, om en grupp inte vill utesluta någon av sina medlemmar, så finns det ingen anledning till varför gruppen inte skulle subventionera en medlem för att ta emot ett oönskat paket. Dessutom garanterar kvalifikationskravet att subventionering aldrig är en konsekvens av en spelares otillräckliga värdering av den kompletta uppsättningen objekt som ska distribuerad".

Minsta subventionsförfaranden

Vissa verk antar att en välvillig tredje part är villig att subventionera tilldelningen, men vill minimera subventionsbeloppet beroende på avundsfrihet. Detta problem kallas minimibidrag avundsfri tilldelning .

Halpern och Shah studerar subventionsminimering i den allmänna artikelfördelningen. De överväger två fall:

Tilldelningen ges i förväg. I det här fallet är den "avundsfri" om och bara om den maximerar summan av verktyg över alla omtilldelningar av sina paket till agenter, om och bara om dess avundsgraf inte har några cykler. Ett avundsfritt pris med minsta subvention kan beräknas i starkt polynomisk tid, genom att konstruera den viktade avundsgrafen och ge, till varje agent i , ett pris lika med den maximala vikten av en väg som utgår från i . Vikten av varje väg är högst summan av m termer, som var och en är värdet av någon agent till någon vara. I synnerhet, om värdet av varje vara för varje agent är högst V , då är vikten av varje väg högst mV . Eftersom vi alltid kan sänka priserna så att en agent får noll subvention, följer att det alltid finns en avundsfri tilldelning med en subvention på högst ( n -1) mV . Denna subvention kan vara nödvändig, till exempel när alla varor är identiska och en agent får alla.
Tilldelningen kan väljas. I detta fall räcker en subvention på ( n -1) V i följande fall:
- När agenternas värderingar är binära (0 eller 1). Då kräver all maxproduktallokering eller leximinoptimal allokering högst ( n -1) V- subvention och kan hittas i polynomtid. Att beräkna minimisubventionen som krävs för att uppnå EF är Turing-likvärdig med att kontrollera förekomsten av en avundsfri tilldelning, vilket är NP-svårt när det begränsas till icke-slösaktiga tilldelningar.
- När alla agenter har samma additiv värdering. Då är varje tilldelning avundsfri. En tilldelning som kräver högst ( n -1) V -stöd kan hittas i polynomtid. En tilldelning minimerar subventionen om den minimerar den maximala nyttan för någon agent. Att beräkna en sådan allokering är NP-svårt och kan lösas med algoritmen för maxprodukt.
- När det finns två agenter hittar round-robin-varufördelning med en specifik agentbeställning en tilldelning som är avundsfri med subvention som högst V.

Brustle, Dippel, Narayan, Suzuki och Vetta förbättrar de övre gränserna för den erforderliga subventionen:

räcker det alltid med en subvention på högst V per agent, och högst ( n -1) V i allmänhet. Dessutom finns det en allokering som uppnår denna gräns som också är EF1 och balanserad (kardinaliteterna för de tilldelade buntarna skiljer sig med högst en vara). Den kan beräknas i polynomtid med en enkel algoritm: hitta iterativt en maximiviktsmatchning i agent-objekts tvådelade graf .
räcker det alltid med en subvention på högst 2( n -1) V per agent, och högst O( n ² V ). Framför allt är det bidrag som krävs inte beroende av antalet objekt. En allokering som uppnår denna gräns kan beräknas i polynomtid med hjälp av värdefrågor.

Caragiannis och Ioannidis studerar beräkningsproblemet med att minimera subventionen:

För ett konstant antal agenter presenterar de en algoritm som approximerar minimibeloppet för subventioner med den noggrannhet som krävs. För valfri ε > 0 hittar den en allokering med subvention som mest ${\displaystyle OPT+\varepsilon \cdot S} ,$ där S är maximala värdet som en agent tilldelar objekt. Algoritmen använder dynamisk programmering och körs i tiden $O((m/\varepsilon )^{n^{2}+1})$ .
För ett variabelt antal agenter uppnår en trivial approximationsalgoritm $displaystyle OPT+(n-1)\cdot S}$ \ dock svårt att uppnå en approximationsfaktor oberoende av n : det är NP-svårt att beräkna en allokering med subvention som mest $OPT+3\cdot 10^{-4} \cdot S$ . Beviset är genom reduktion från en begränsad variant av maximal 3-dimensionell matchning , där varje vertex visas exakt två gånger.

Observera att en avundsfri tilldelning med subvention förblir avundsfri om ett fast belopp tas från varje agent. Därför kan liknande metoder användas för att hitta tilldelningar som inte är subventionerade:

Att debitera varje agent för den genomsnittliga betalningen ger en avundsfri tilldelning som också är budgetbalanserad . Att minimera subventionen är detsamma som att minimera det högsta belopp som varje enskild agent måste betala.
Det är också möjligt att använda negativ subvention (skatt), samtidigt som man minimerar det totala beloppet som alla ombud måste betala.

Ytterligare procedurer

Alkan, Demange och Gale visade att en avundsfri tilldelning alltid finns när pengarna är tillräckligt stora. Detta gäller även när objekt kan ha negativ värdering.

Meertens, Potters och Reijnierse bevisar förekomsten av avundsfria och Pareto-optimala tilldelningar under mycket milda antaganden om värderingarna (inte nödvändigtvis kvasilinjära).

Cavallo generaliserar de traditionella binära kriterierna för avundsfrihet, proportionalitet och effektivitet (välfärd) till gradmått som sträcker sig mellan 0 och 1. I de kanoniska rättvisa uppdelningsinställningarna, under alla allokativt effektiva mekanismer är den värsta välfärdsgraden 0 och disproportionalitetsgraden är 1; med andra ord, de värsta resultaten är så dåliga som möjligt. Han letar efter en mekanism som uppnår hög välfärd, låg avundsjuka och låg oproportionalitet i förväntan över ett spektrum av rättvisa uppdelningsinställningar. VCG -mekanismen är inte en tillfredsställande kandidat, men omfördelningsmekanismen för Bailey och Cavallo är det.

Relaterade problem

Avundsfri prissättning

När man säljer föremål till köpare är summan av betalningar inte fastställd i förväg, och målet är att maximera antingen säljarens intäkter eller sociala välfärden, med förbehåll för avundsfrihet. Dessutom kan antalet objekt vara annorlunda än antalet agenter, och vissa objekt kan kasseras. Detta är känt som problemet med avundsfri prissättning .

Flerdimensionella mål

Ofta måste vissa andra mål uppnås förutom rättvisa. Till exempel, när man tilldelar uppgifter till agenter, krävs det både för att undvika avundsjuka och för att minimera omfattningen (- slutförandetiden för den sista agenten). Mu'alem presenterar ett allmänt ramverk för optimeringsproblem med garanti för avundsfrihet som naturligtvis utökar rättvisa objektallokeringar med hjälp av monetära betalningar.

Aziz strävar efter att, med hjälp av monetära överföringar, uppnå en tilldelning som är både avundsfri och rättvis . Han studerar inte bara additiva positiva verktyg, utan också för alla superadditiva verktyg , vare sig de är positiva eller negativa:

För superadditiva verktyg finns det en polynom-tidsalgoritm som uppnår avundsfrihet, rättvisa och budgetbalans (det är lätt att byta ut budgetbalans med subvention).
Om en given allokering är EFEQ-konverterbar, så kan minimisubventionen som krävs för att göra den EFEQ+EQ hittas i linjär tid.
Att hitta en allokering som är EFEQ-konverterbar med minsta subvention är NP-svårt och kan inte uppskattas inom någon positiv faktor. Detta beror helt enkelt på att det är NP-svårt att kontrollera förekomsten av en EF-tilldelning (som kräver 0 subventioner).
En subvention på högst ( n -1) mV är alltid tillräcklig och kan behövas oavsett om tilldelning ges eller inte.

Se även

Avundsfri objektallokering - inställningen utan monetära överföringar.