Underskärningsprocedur

Underbudsförfarandet är ett förfarande för rättvis tilldelning av föremål mellan två personer. Den hittar bevisligen ett fullständigt avundsfritt objektuppdrag närhelst ett sådant uppdrag existerar. Den presenterades av Brams och Kilgour och Klamler och förenklades och utökades av Aziz.

Antaganden

Underbudsförfarandet kräver endast följande svaga antaganden om folket:

Varje person har en svag preferensrelation på delmängder av objekt.
Varje preferensrelation är strikt monoton : för varje uppsättning $X$ och objekt $y\notin X$ , föredrar personen strikt $X\cup y$ till $X$ .

Det antas inte att agenter har lyhörda preferenser .

Huvudtanken

Underskärningsproceduren kan ses som en generalisering av klyftan och välj protokoll från en delbar resurs till en resurs med odelbarhet. Dela-och-välj-protokollet kräver att en person skär resursen till två lika delar. Men om resursen innehåller med odelbarhet kan det vara omöjligt att göra ett exakt lika stort snitt. Följaktligen fungerar underbudsförfarandet med nästan lika snitt . Ett nästan lika snitt av en person är en uppdelning av uppsättningen objekt till två disjunkta delmängder (X,Y) så att:

Personen föredrar svagt X framför Y;
Om något enskilt objekt flyttas från X till Y, så föredrar personen strikt Y till X (dvs. för alla x i X föredrar personen $Y\cup x$ till $X \setminus x$ ).

Procedur

Varje person rapporterar alla sina nästan-lika-snitt. Det finns två fall:

Fall 1 : rapporterna är olika, t.ex. finns det en partition (X,Y) som är nästan lika för Alice men inte för George. Sedan presenteras denna partition för George. George kan antingen acceptera eller förkasta det:
- George accepterar partitionen om han föredrar Y framför X. Sedan tar Alice emot X och George tar emot Y och den resulterande allokeringen är avundsfri.
- George avvisar partitionen om han föredrar X framför Y. Enligt antagandet är (X,Y) inte ett nästan lika snitt för George. Därför finns det ett objekt x i X så att George föredrar $X\setminus x$ framför $Y\cup x$ . George rapporterar $X\setminus x$ ; vi säger att George underskrider X. Eftersom (X,Y) är ett nästan lika snitt för Alice, föredrar Alice $Y\cup x$ framför $X\setminus x$ . Sedan får George $X\setminus x$ och Alice får $Y\cup x$ och den resulterande allokeringen är avundsfri.
Fall 2 : rapporterna är identiska, dvs. Alice och George har exakt samma uppsättning nästan lika snitt. Sedan frågar proceduren dem om ett av deras nästan-lika-snitt är ett exakt-lika-snitt. Enligt det strikta monotoniska antagandet är (X,Y) ett exakt-lika snitt, om-och-bara-om både (X,Y) och (Y,X) är nästan-lika-snitt. Därför, i fall 2, har Alice och George samma uppsättning exakt lika snitt. Det finns två underfall:
- Enkelt fall: det finns ett exakt lika snitt (X,Y). Då får en person (oavsett vem) X och den andra får Y och uppdelningen är avundsjuk.
- Hårt fall: det finns inget exakt lika snitt. Då återkommer proceduren och rapporterar att "en avundsfri tilldelning inte existerar".

För att bevisa förfarandets korrekthet räcker det att bevisa att det i Hard-fallet inte existerar en avundsfri tilldelning. Anta faktiskt att det finns en avundsfri tilldelning (X,Y). Eftersom vi är i det hårda fallet är (X,Y) inte ett exakt lika snitt. Så en person (t.ex. George) föredrar strikt Y framför X, medan den andra personen (Alice) svagt föredrar X framför Y. Om (X,Y) inte är ett nästan lika snitt för Alice, så flyttar vi några objekt från X till Y, tills vi får en partition (X',Y') som är nästan lika för Alice. Alice föredrar fortfarande svagt X' framför Y'. Genom monotonitetsantagandet föredrar George fortfarande strikt Y' framför X'. Detta betyder att (X',Y') inte är ett nästan lika snitt för George. Men i fallet Hard har båda agenterna samma uppsättning nästan-lika snitt - en motsägelse.

Körtidskomplexitet

I värsta fall kan agenterna behöva utvärdera alla möjliga paket, så körtiden kan vara exponentiell i antalet objekt.

Detta är inte förvånande, eftersom underprisförfarandet kan användas för att lösa uppdelningsproblemet : anta att båda agenterna har identiska och additiva värderingar och kör underprisförfarandet; om den hittar en avundsfri tilldelning, så representerar denna tilldelning en lika stor uppdelning. Eftersom partitionsproblemet är NP-komplett kan det förmodligen inte lösas med en polynom-tidsalgoritm.

Ojämlika rättigheter

Underbudsförfarandet kan också fungera när ombuden har olika rättigheter. Anta att varje agent $i$ har rätt till en bråkdel $e_{i}$ av objekten. Sedan bör definitionen av ett nästan lika snitt (för agent ${\displaystyle i} ) ändras enligt följande:$

$u_{i}(X)\geq {c_{i} \over c_{-i}}u_{i}(Y)$ , och
För alla x i X är $u_{i}(X\setminus x)<{c_{i} \över c_{ -i}}u_{i}(Y\kopp x)$

Generationsfas

I den ursprungliga publikationen föregås underbudsförfarandet av följande generationsfas :

Medan det finns saker på bordet:
- Varje person rapporterar sitt bästa föremål.
  - Om rapporterna är olika får varje person sitt bästa föremål.
  - Om rapporterna är identiska, läggs det bästa föremålet i en omtvistad hög .

Underskärningsproceduren som beskrivs ovan utförs sedan endast på den omtvistade högen.

Denna fas kan göra delningsproceduren mer effektiv: den omtvistade högen kan vara mindre än den ursprungliga uppsättningen av föremål, så det kan vara lättare att beräkna och rapportera nästan lika snitt.

	Alice	George
w	9	1
x	8	4
y	7	3
z	6	2

Genereringsfasen har dock flera nackdelar:

Det kan göra att proceduren missar en eventuell avundsfri tilldelning. Anta till exempel att det finns fyra poster och deras värderingar är som i tabellen intill. Tilldelningen som ger {w,z} till Alice och {x,y} till George är avundsfri. Den kan faktiskt hittas genom den blotta underskärningsproceduren, eftersom partitionen ({w,z}, {x,y}) är en nästan lika snitt för Alice men inte för George, och George skulle acceptera denna partition. Men med genereringsfasen, till en början får Alice w och George får x och de andra föremålen {y,z} läggs i den omtvistade högen, och det finns ingen avundsfri tilldelning av den omtvistade högen, så proceduren misslyckas.
Det kräver att folk väljer sitt "bästa föremål" utan att veta vilka andra föremål de kommer att få. Detta bygger på ett antagande att varorna är oberoende varor . Alternativt förlitar den sig på ett om lyhördhet : om, i en bunt, en artikel ersätts med en bättre artikel, så är den resulterande bunten bättre (det är nära relaterat till svagt additiva preferenser).
Det fungerar inte när ombuden har ojämlika krav.
Den förlitar sig på sekventiell allokering, som är känslig för strategisk manipulation.

Se även

Procedur för minskad efterfrågan och procedur för avundsgraf - två ytterligare procedurer baserade på ordinarie rangordning av buntar.

Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbok i Computational Social Choice . Cambridge University Press. s. 306–307. ISBN 9781107060432 . ( gratis onlineversion )