Skär kakan efter användbarhet

Att skära kakan med hjälp (eller skära kakan med maxsum ) är regeln att dela heterogena resurser , som en tårta eller fastighet , mellan flera deltagare med olika kvantitativa nyttofunktioner så att summan av nytta för deltagarna blir lika stor som möjlig. Sådan skärning inspirerades av utilitarismens filosofi . Att skära kakan efter användbarhet är ofta "orättvist". Därför är utilitarism i konflikt med att bara skära kakan .

Exempel

Låt oss föreställa oss en tårta som består av två delar - choklad och vanilj. Låt det vara två deltagare - Alice och George med följande uppskattningar

Deltagare	Choklad	Vanilj
Alice	9	ett
George	6	fyra

Verktygsregeln ger varje del till deltagaren med högst nyttopoäng . I det här fallet, enligt bruksregeln, får Alice all choklad och George får all vanilj. Det maximala värdet blir 13.

Skärningen enligt nyttan är orättvis – den är inte proportionell eftersom George får mindre än hälften av fullbetyget. Det är inte heller fri från avundsjuka , eftersom George är avundsjuk på Alice.

Notation

Låt oss beteckna kakan med bokstaven . Det antas vanligtvis att det antingen är ett ändligt endimensionellt segment, en tvådimensionell polygon eller en ändlig delmängd av ett högredimensionellt euklidiskt utrymme . $C$ $\mathbb{R}^d$

Det finns deltagare. Varje deltagare har en personlig poängfunktion som mappar delmängder ("pieces of cake") till siffror. $n$ $i$ $V_i$ $C$

$C$ måste delas upp i icke-överlappande delar, en per deltagare. Den del som skickas till deltagaren betecknas som och . $n$ $i$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

En split kallas en utility split , eller maximum utility (MP), eller maxsum om den maximerar följande uttryck: $X$

{\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i)))))

Konceptet generaliseras ofta genom att tilldela olika vikter till varje deltagare. En partition kallas viktad-utilitarian-maximal ( WUM ) om den maximerar följande uttryck: $X$

{\displaystyle \sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i)))))

där ges positiva konstanter. $w_{i}$

Maxsum och Pareto effektivitet

Alla MVP-partitioner med positiva vikter är uppenbarligen Pareto-effektiva . Om partitionen är Pareto-dominant är den viktade summan av verktygen i strikt större än i , så det kan inte vara en MVP-partition. $Y$ $X$ $Y$ $X$ $X$

Mer överraskande är att varje Pareto-effektiv partition är en MVP för vissa val av vikter [1] [2] .

Funktioner i maxsum- regeln

Christopher P. Chambers föreslog de karakteristiska egenskaperna hos MVP-regeln [3] . Funktionerna är baserade på följande egenskap hos delningsregeln R :

Pareto-effektivitet (PE, engelska Pareto-efficiency , PE): R - regeln returnerar endast partitioner som är Pareto-effektiva.
Division independence ( ND, engelsk division independence , DI) : om kakan är uppdelad i flera delar och var och en av dem skärs enligt R -regeln , blir resultatet detsamma som om den ursprungliga kakan skärs enligt R -regeln .
Independence of infeasible mark ( IIL): när en delkaka delas enligt R-regeln beror resultatet inte på nyttan av deltagare i andra delkakor.
Positiv behandling av lika ( PTE) : om alla deltagare har samma nyttofunktioner rekommenderar R -regeln minst en uppdelning som ger positiv nytta för varje deltagare.
Skala -invarians ( SI) : när deltagarens utvärderingsfunktioner multipliceras med ett konstant värde (olika konstanter är tillåtna för olika deltagare) ändras inte rekommendationerna som ges av R -regeln.
Kontinuitet ( kontinuitet , CO ): För en fast bit av kakan, stängs uppsättningen av verktygsscheman som mappar till en viss distribution av punktvis konvergens .

Följande fakta är bevisade för deltagare som tilldelar en tårtbit med positiv storlek positiv nytta:

Om regeln R har egenskaperna PE, ND och NNS, så finns det en sekvens av vikter så att alla partitioner som rekommenderas av regeln R är MVP:er med dessa vikter (det har visat sig att varje PE-partition är en MVP med vissa vikter Det som är nytt är att alla partitioner som rekommenderas av regel R är MVP:er med samma vikter (detta följer av ND-egenskaperna). ${\displaystyle w_{1},\dots ,w_{n))$
Om regeln R har egenskaperna PE, ND, NNS och POR, så är alla partitioner som rekommenderas av regeln R maximalt användbara (med andra ord, alla divisioner måste vara MVP och alla agenter måste ha lika vikt. Detta följer av POR:en fast egendom).
Om regel R har egenskaperna PE, ND, NNS och NS, så är regel R en diktatorisk regel - den ger hela kakan till en deltagare.
Om en regel R har egenskaperna PE, ND, NNS och LR, så finns det en sekvens av vikter så att regel R är en MVP-regel med dessa vikter (dvs. R rekommenderar endast en MVP-division med dessa vikter). ${\displaystyle w_{1},\dots ,w_{n))$

Hitta maxsumman av partitioner

Frånkopplade stycken

Om poängfunktionerna är additiva finns alltid maxsum-divisionerna. Intuitivt kan vi ge varje del av kakan till den deltagare som betygsätter den högst, som i exemplet ovan . På samma sätt kan MVP-divisionen hittas genom att skicka varje bit av kakan till den partner för vilken förhållandet har störst värde. $V_{i}/w_{i}$

Denna process är lätt att implementera om kakan är bitvis homogen , det vill säga den kan delas upp i ett ändligt antal bitar för vilka densiteten av värdefunktionerna för alla deltagare är konstant.

Om kakan inte är bitvis homogen, misslyckas algoritmen ovan eftersom det finns ett oändligt antal olika "bitar" att ta hänsyn till.

I det här fallet finns maxsum-partitionen fortfarande kvar. Detta är en konsekvens av Dubins-Spaniers kompakthetsteorem och kan bevisas med Radon-Nikodim-uppsättningen .

Men ingen ändlig algoritm kan hitta maxsum-partitionen. Bevis [4] . Den slutliga algoritmen har data om värdet av ett ändligt antal bitar. Det vill säga, det finns bara ett ändligt antal delmängder av kakan för vilka algoritmen känner till deltagarnas poäng. Låt oss anta att algoritmen stannade efter att ha tagit emot data om delmängder. Nu är det möjligt att alla deltagare svarade att de har samma chunk- poäng. I det här fallet är den högsta möjliga nyttan som kan uppnås av algoritmen 1. Det är dock möjligt att djupt inom en av bitarna finns en delmängd som de två deltagarna värderar olika. I det här fallet finns det en superproportionell division där varje deltagare får ett värde som är större än , så att summan av verktyg är strikt större än 1. Därför kommer divisionen som returneras av den slutliga algoritmen inte att vara maxsumma. $k$ $k$ $1/n$

Anslutna delar

Om kakan är endimensionell och bitarna måste kopplas ihop fungerar inte längre den enkla algoritmen för att tilldela varje mest värdefulla bit till en agent, även om bitarna är bitvis konstanta. I detta fall är uppgiften att hitta MT-imputationen NP-hård , och dessutom är inget FPTAS- schema möjligt om inte P=NP.

Det finns en 8-faldig approximationsalgoritm och en lösbar -algoritm med fasta parametrar som är exponentiell i antalet spelare [5] .

För alla positiva vikter finns det en MVP-partition och den kan hittas på liknande sätt.

Maxsum och eget kapital

Maxsum-indelningen är inte alltid rättvis, se exemplet ovan . Likaså är en rättvis uppdelning inte alltid maxsum.

Ett tillvägagångssätt för att lösa konflikten är att begränsa "rättvisans pris" - vi beräknar de övre och nedre gränserna för minskningen av mängden nytta för att få en rättvis uppdelning. För detaljer, se artikeln " Priset på aktier ".

Ett annat sätt att kombinera effektivitet och rättvisa är att söka bland alla möjliga rättvisa divisioner för divisionen med maximal nytta:

Hitta rättvisa maxsum-distributioner

Följande algoritmer kan användas för att hitta ett avundslöst snitt med maximal total nytta för en tårta i form av ett endimensionellt intervall, om varje deltagare kan ta emot olika (bortkopplade) delar av kakan och utvärderingsfunktionerna är additiva [6] :

För deltagare med styckvis konstanta uppskattningar: dela upp kakan i m helt konstanta regioner (). Vi löser ett linjärt programmeringsproblem med nm variabler - varje par (agent, area) har en variabel som bestämmer andelen av arean som överförs till agenten. För varje region finns det en begränsning att summan av alla delar av regionen är 1. För varje par (agent, agent) finns det en begränsning att den första agenten inte är avundsjuk på den andra agenten. Observera att uppdelningen av kakan som erhålls genom ett sådant förfarande kan visa sig vara extremt liten. $n$
För deltagare med bitvis linjära uppskattningar: för varje punkt på kakan beräknar vi förhållandet mellan verktyg: . Vi ger deltagaren 1 poäng från , och deltagaren 2 poäng från , där är tröskeln beräknad så att divisionen blir fri från avundsjuka. I allmänhet kan det inte beräknas eftersom det kan vara irrationellt , men i praktiken, när uppskattningarna är bitvis linjära, kan det approximeras med den "irrationella sök"-approximationsalgoritmen. För varje , hittar algoritmen en fördelning som är -SZ (värdet för varje agent är inte mindre än värdet för någon annan agent minus ) och summan når åtminstone den maximala summan av SZ-fördelningar. Algoritmens körtid beror polynomiellt på indata och på . $2$ ${\displaystyle r=u_{1}/u_{2))$ $r\geqslant r^{*}$ $r<r^{*}$ $r^{*}$ $r^{*}$ $r^{*}$ $\epsilon > 0$ $\epsilon$ $\epsilon$ $\log(1/\epsilon )$
För deltagare med allmänna skattare: en additiv uppskattning för att få en avundsfri och effektiv fördelning baserad på en bitvis linjär poängalgoritm. $n$

Egenskaper för maxsum-fair distributioner

Artikeln av Brahms et al [7] studerar både avundsfri (SE, eng. avundsfri , EF) och opartisk (DB, eng. equitable , EQ) kakdelning, och etablerar deras koppling till maxsum och Pareto optimal ( OP, eng. Pareto-optimality , PO) efter divisioner. Som förklarats ovan är maxsumman för en fördelning alltid OP. Men när maxsum begränsas av skälighetsvillkoret är detta inte nödvändigtvis sant. Brahms och medförfattare bevisade följande

När det finns två agenter kommer SZ max, DB max och SZ-DB max distribution alltid att vara OD.
När det finns tre eller flera agenter med bitvis homogena estimatorer är SZ-maximifördelningarna alltid OP (eftersom SZ är ekvivalent med proportionalitet , som bevaras under Pareto-förbättringar). Det kan dock inte finnas en maximal DB och en maximal distribution DB-SZ som skulle vara OP.
Om det finns tre eller flera agenter med styckvis konstant utvärderingsfunktioner (d.v.s. har styckvis konstanta densiteter), kanske det inte finns en SZ-maximalfördelning som är OP. Tänk till exempel en kaka med tre regioner och tre agenter med värden: Alice : 51/101, 50/101, 0 Bob : 50/101, 51/101, 0 Carl : 51/111, 10/111, 50/111 . Maxsum-regeln ger område i till agent i, men denna uppdelning är inte utan avund, eftersom Carl är avundsjuk på Alice. Med hjälp av linjär programmering kan man hitta en enda SZ-maximalfördelning och visa att den borde ge andelar i region 1 och region 2 till både Alice och Bob. En sådan tilldelning kan dock inte vara OP, eftersom Alice och Bob skulle kunna dra nytta av aktiebyten i dessa regioner.
Om alla agenter har bitvis linjära utvärderingsfunktioner, så är summan av verktygen för den maximala fördelningen SZ inte mindre än verktygen för den maximala fördelningen DB. Detta resultat expanderar till allmänna poäng för additiva approximationer (det vill säga -SZ-distributioner har en summa av verktyg som inte är mindre än verktygen för DB-distributionerna minus ). $\epsilon$ $\epsilon$

Se även

Pleasure Counting är ett försök att bestämma nytta med hjälp av matematiska formler.
Effektiv tårtskärning
Fair Cake Cutting Challenge
Wellers sats
Pareto effektiv distribution utan avund
Maximal fördelning efter rang

Anteckningar

↑ Barbanel och Zwicker 1997 , sid. 203.
↑ Se även Wellers sats . För liknande resultat relaterade till problemet med oenhetlig resursallokering, se Varians satser .
↑ Chambers, 2005 , sid. 236–258.
↑ Brams och Taylor 1996 , sid. 48.
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Brams, Feldman et al., 2012 , sid. 1285–1291.

Litteratur

Julius B. Barbanel, William S. Zwicker. Två tillämpningar av ett teorem av Dvoretsky, Wald och Wolfovitz på kakdelning // Teori och beslut. - 1997. - T. 43 , nr. 2 . - doi : 10.1023/a:1004966624893 .
Christopher P. Chambers. Tilldelningsregler för jorddelning // Journal of Economic Theory. - 2005. - T. 121 , nr. 2 . - doi : 10.1016/j.jet.2004.04.008 .
Steven J. Brams, Alan D. Taylor. rättvis delning; Från tårtskärning till tvistlösning. - 1996. - ISBN 978-0521556446 .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Computing Socialt-Efficient Cake Divisions // AAMAS . — 2013.
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Optimal avundsfri tårtskärning // AAAI . — 2011.
Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, Ariel D. Procaccia. Om Maxsum Fair Cake Divisions // Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12) . — 2012.