Effektiv tårtskärning

Effektiv tårtskärning är ett problem inom ekonomi och datavetenskap : det finns en heterogen resurs, som en tårta med olika typer av dekorationer eller en bit mark med olika vegetation. Det antas att resursen är delbar - den kan skäras i godtyckligt små delar utan värdeförlust. Resursen bör delas upp på flera deltagare, med hänsyn till deras önskemål: vissa människor föredrar chokladdekorationer, andra föredrar körsbär och någon vill få den största möjliga biten, och så vidare. Den sista partitionen bör vara Pareto-effektiv .

Den vanligaste studien av effektivitet har varit i relation till rättvisa , där målet är att hitta en skiljevägg som uppfyller både effektivitets- och rättvisekriterier.

Formalisering av problemet

Det finns en tårta . Modellen antas vanligtvis vara ett ändligt endimensionellt segment, eller en tvådimensionell polygon , eller en ändlig delmängd av ett flerdimensionellt euklidiskt utrymme . $C$ $\mathbb{R}^d$

Låt det finnas deltagare. Varje deltagare har en subjektiv bedömningsfunktion för resursen i fråga, som mappar delmängder till siffror. $n$ $i$ $V_i$ $C$

Det krävs att delas upp i icke-överlappande delmängder, så att varje deltagare får en separat del. Stycket som skickas till deltagaren kommer att betecknas som ; på detta sätt . $C$ $n$ $i$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

Ett exempel på en tårta

Nedan kommer vi att titta på en tvådelad tårta, choklad och vanilj, delad av två personer: Alice och George. Låt värdena för utvärderingsfunktionerna ha följande värden:

	choklad del	vanilj del
Alice	9	ett
George	6	fyra

Effektivitet

Partitionen är Pareto-dominant (anses mer optimal) om minst en person mår bättre än , och ingen mår sämre än . Symboliskt: $Y$ $X$ $Y$ $X$ $Y$ $X$

\forall {i}:\ V_{i}(Y_{i})\geqslant V_{i}(X_{i})

och

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

Pareto-effektiv (EP, engelska Pareto-efficient , PE) distribution är en distribution som inte är Pareto-dominerad av någon annan distribution, det vill säga den kan inte förbättras. I exemplet med en tårta är flera EP-distributioner möjliga, medan . Till exempel är varje split som ger hela kakan till en person en EP, eftersom varje förändring i fördelningen kommer att resultera i att den ena personen protesterar. Naturligtvis är EP-fördelningen inte nödvändigtvis rättvis.

En kombination av effektivitet och rättvisa

En partition som är både Pareto-effektiv och proportionell kallas EPPR ( eng. Pareto-efficient and proportional , PEPR), och en partition som är både EP- och avundsfri kallas EPSP ( eng. Pareto-efficient and envy-free , PEEF ) för korta.

Dela EPPR

EP-indelning kan erhållas trivialt genom att skicka hela tårtan till en deltagare. Men EP-fördelningen, som också är proportionell mot , kan inte hittas med en ändlig algoritm. Beviset liknar det som används för problemet med att skära kakan efter användbarhet .

Uppdelningen av EPSP

För n deltagare med additiv värderingsfunktion, när bitarna kan kopplas bort, finns det alltid en FTE-delning. Detta är Wellers sats .

Om kakan är ett endimensionellt segment och varje person måste få ett kopplat segment, gäller följande allmänna resultat: om utvärderingsfunktionerna är strikt monotona (det vill säga varje person föredrar starkt en bit framför alla sina egna delmängder) SZ-distribution är också en EP (observera att detta inte är sant om agenter kan ta emot skurna bitar). Därför skapar Simmons-Su-protokollen i det här fallet en EPSP-delning.

Om kakan är en endimensionell cirkel (det vill säga ett segment vars två ändar är topologiskt identifierade), och varje deltagare måste ta emot anslutna bågar, stämmer inte ovanstående resultat - SZ-fördelningen är inte nödvändigtvis EP. Dessutom finns det par (icke-additiva) estimatorfunktioner för vilka det inte finns någon FTE-fördelning. Men om det finns två agenter och minst en av dem har en additiv klassificeringsfunktion, så finns EPSP:n [1] .

Se även

Anteckningar

↑ Thomson, 2006 , sid. 501.

Litteratur

Thomson W. Barn som gråter på födelsedagsfester. Varför? // Ekonomisk teori. - 2006. - T. 31 , nr. 3 . - S. 501-521 . - doi : 10.1007/s00199-006-0109-3 . . Rubrik: "Barn gråter på födelsedagskalas. Varför?"