Effektiv kageskæring

Effektiv kageskæring er et problem inden for økonomi og datalogi : der er en heterogen ressource, såsom en kage med forskellige typer dekorationer eller et stykke jord med forskellig vegetation. Det antages, at ressourcen er delelig - den kan skæres i vilkårligt små dele uden tab af værdi. Ressourcen skal deles mellem flere deltagere under hensyntagen til deres ønsker: nogle mennesker foretrækker chokoladedekorationer, andre foretrækker kirsebær, og nogen ønsker at få det størst mulige stykke, og så videre. Den endelige partition skal være Pareto-effektiv .

Den mest almindelige undersøgelse af effektivitet har været i forhold til retfærdighed , hvor målet er at finde en skillevæg, der både opfylder effektivitets- og retfærdighedskriterier.

Formalisering af problemet

Der er en kage . Modellen antages normalt at være et endeligt endimensionelt segment eller en todimensionel polygon eller en endelig delmængde af et flerdimensionelt euklidisk rum . $C$ $\mathbb{R}^d$

Lad der være deltagere. Hver deltager har en subjektiv vurderingsfunktion for den pågældende ressource, som kortlægger delmængder til tal. $n$ $jeg$ $V_i$ $C$

Det er påkrævet at opdele i ikke-overlappende undersæt, således at hver deltager modtager et separat stykke. Det stykke, der sendes til deltageren, vil blive betegnet som ; på denne måde . $C$ $n$ $jeg$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n))$

Et eksempel på en kage

Nedenfor vil vi se på en todelt kage, chokolade og vanilje, delt af to personer: Alice og George. Lad værdierne for evalueringsfunktionerne have følgende værdier:

	chokolade del	vanilje del
Alice	9	en
George	6	fire

Effektivitet

Partitionen er Pareto-dominant (betragtes som mere optimal), hvis mindst én person har det bedre end , og ingen har det dårligere end . Symbolsk: $Y$ $x$ $Y$ $x$ $Y$ $x$

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

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

Pareto-effektiv (EP, engelsk Pareto-efficient , PE) distribution er en distribution, der ikke er Pareto-domineret af nogen anden distribution, det vil sige, den kan ikke forbedres. I eksemplet med en kage er flere EP distributioner mulige, mens . For eksempel er enhver opdeling, der giver hele kagen til én person, en EP, da enhver ændring i fordelingen vil resultere i, at den ene person protesterer. Naturligvis er EP-fordelingen ikke nødvendigvis retfærdig.

En kombination af effektivitet og retfærdighed

En partition, der er både Pareto-effektiv og proportional , kaldes EPPR ( eng. Pareto-efficient and proportional , PEPR), og en partition, der er både EP- og misundelsesfri , kaldes EPSP ( eng. Pareto-efficient and envy-free , PEEF ) for kort.

Opdeling af EPPR

EP-inddeling kan fås trivielt ved at give hele kagen videre til én deltager. Men EP-fordelingen, som også er proportional med , kan ikke findes af en endelig algoritme. Beviset svarer til det, der bruges til problemet med at skære kagen efter brug .

Opdelingen af EPSP

For n deltagere med additive værdiansættelsesfunktioner, når brikkerne kan afbrydes, eksisterer der altid en FTE-split. Dette er Wellers sætning .

Hvis kagen er et endimensionelt segment, og hver person skal modtage et forbundet segment, gælder følgende generelle resultater: hvis evalueringsfunktionerne er strengt monotone (det vil sige, at hver person stærkt foretrækker et stykke frem for alle sine egne delmængder), vil evt. SZ-distribution er også en EP (bemærk, at dette ikke er sandt, hvis agenter kan modtage afskårne stykker). Derfor skaber Simmons-Su-protokollerne i dette tilfælde en EPSP-deling.

Hvis kagen er en endimensionel cirkel (det vil sige et segment, hvis to ender er topologisk identificeret), og hver deltager skal modtage forbundne buer, så holder ovenstående resultater ikke - SZ-fordelingen er ikke nødvendigvis EP. Derudover er der par af (ikke-additive) estimatorfunktioner, for hvilke der ikke eksisterer en FTE-fordeling. Men hvis der er 2 agenter, og mindst én af dem har en additiv vurderingsfunktion, så eksisterer EPSP [1] .

Se også

Noter

↑ Thomson, 2006 , s. 501.

Litteratur

Thomson W. Børn, der græder ved fødselsdagsfester. Hvorfor? // Økonomisk teori. - 2006. - T. 31 , no. 3 . - S. 501-521 . - doi : 10.1007/s00199-006-0109-3 . . Overskrift: "Børn græder ved fødselsdagsfester. Hvorfor?"