Plockningssekvens

En plocksekvens är ett protokoll för rättvis tilldelning av föremål . Antag att m objekt måste delas upp på n agenter. Ett sätt att allokera objekten är att låta en agent välja ett enstaka objekt, sedan låta en annan agent välja ett enstaka objekt, och så vidare. En plockningssekvens är en sekvens av m agentnamn, där varje namn bestämmer vilken agent som är nästa att välja ett objekt.

Som ett exempel, anta att 4 föremål måste delas mellan Alice och Bob. Några möjliga plockningssekvenser är:

• AABB - Alice väljer två föremål, sedan väljer Bob de två återstående föremålen.
• ABAB - Alice väljer ett föremål, sedan väljer Bob ett föremål, sedan Alice igen, sedan Bob igen. Detta är mer "rättvist" än AABB eftersom det ger Bob större chans att få ett bättre föremål.
• ABBA - Alice väljer ett föremål, sedan väljer Bob två föremål, sedan får Alice det återstående föremålet. Detta är intuitivt ännu mer "rättvist" än ABAB, eftersom Bob i ABAB alltid ligger bakom Alice, medan ABBA är mer balanserad.

Fördelar

En plockningssekvens har flera fördelar som ett rättvis uppdelningsprotokoll:

• Enkelhet: det är väldigt lätt för agenterna att förstå hur protokollet fungerar och vad de ska göra i varje steg - välj bara det bästa föremålet.
• Sekretess: agenterna behöver inte avslöja hela sin värderingsfunktion eller ens hela sin rangordning. De behöver bara avslöja vilket föremål som är bäst för dem i varje steg.
• Låg kommunikationskomplexitet : det kräver endast m rapporter, som var och en innehåller ett tal mellan 1 och m , så att den totala komplexiteten är $\Theta (m\log {m})$ .

Välfärdsmaximering

Hur ska plocksekvensen väljas? Bouveret och Lang studerar denna fråga under följande antaganden:

• Varje agent har en additiv nyttofunktion (detta innebär att varorna är oberoende varor ).
• Agenterna kan ha olika rankningar på objekten, men det finns en gemensam poängfunktion som mappar rankningarna till monetära värden (t.ex. för varje agent är hans bästa objekt värt för honom x dollar, hans näst bästa objekt är värt för honom y dollar, etc).
• Tilldelaren känner inte till rankningarna av agenterna, men han vet att alla rankningar är slumpmässiga dragningar från en given sannolikhetsfördelning .
• Målet med fördelaren är att maximera det förväntade värdet av någon social välfärdsfunktion .

De visar plockningssekvenser som maximerar den förväntade utilitaristiska välfärden (summan av nyttan) eller den förväntade jämlika välfärden (minimal nytta) i olika miljöer.

Kalinowski et al visar att när det finns två agenter med en Borda- poängfunktion, och varje rankning är lika sannolik, uppnår "round robin"-sekvensen (ABABAB...) den maximala förväntade summan av nyttigheter.

Rättvisa med olika rättigheter

Brams och Kaplan studerar problemet med att fördela regeringsdepartement mellan partier. Det finns en koalition av partier; varje parti har olika antal platser i parlamentet; större partier bör tilldelas fler departement eller mer prestigefyllda departement. Detta är ett specialfall av tilldelning av rättvis föremål med olika rättigheter. En möjlig lösning på detta problem är att bestämma en plocksekvens, baserat på de olika rättigheterna, och låta varje part välja ett departement i tur och ordning. En sådan lösning används i Nordirland, Danmark och EU-parlamentet.

Brams antar att varje agent har en strikt beställning på föremålen och har lyhörda preferenser på paket med föremål. Detta innebär att det vid varje punkt i plocksekvensen finns en enda kvarvarande artikel som är den "bästa artikeln" för agenten. En agent kallas uppriktig ( sanningsenlig ) om han vid varje tillfälle väljer sitt bästa föremål. Om agenter har fullständig information om varandras preferenser (som är vanligt bland parter), kanske det inte är rationellt för dem att välja sanningsenligt; det kan vara bättre för dem att göra sofistikerade ( strategiska ) val. Således inducerar plockningssekvensen ett sekventiellt spel och det är intressant att analysera dess subspel-perfekta jämvikt . Flera resultat är bevisade:

• Med två agenter leder både sanningsenliga och strategiska val till Pareto effektiva tilldelningar. Dessutom är spelet monotont i följande mening: en agent är alltid bättre ställd om en eller flera av hans positioner i sekvensen förbättras (t.ex. Alice är bättre ställd i sekvensen ABBA än i BABA). Båda egenskaperna är fortfarande sanna med tre eller fler agenter, så länge de gör sanningsenliga val.
• Med tre eller fler agenter som gör strategiska val, kan en plockningssekvens leda till ineffektiva allokeringar (dvs. den perfekta jämvikten i underspelet kanske inte är Pareto-effektiv).
• Med tre eller fler agenter som gör strategiska val, kan spelet vara icke-monotoniskt , dvs en agent kan göra sämre genom att välja tidigare i sekvensen.
• För två agenter finns det en enkel modifiering av plockningssekvensen, vilket är en sanningsenlig mekanism - att plocka föremål sanningsenligt är en dominerande strategi. Därför finns det en subspel-perfekt jämvikt som är Pareto optimal, och spelet är monotont.

Bestämma plockningssekvensen

Med tanke på agenternas olika rättigheter, vad skulle vara en rättvis plocksekvens? Brams föreslår att man använder divisormetoder , liknande de som används för att fördela kongressplatser mellan stater . De två vanligaste metoderna är de som föreslagits av Daniel Webster och Thomas Jefferson . Båda metoderna börjar på samma sätt:

• Beräkna divisorn - summan av rättigheterna dividerat med antalet poster (t.ex. om summan av alla rättigheter är 201, och det finns 15 poster att dela, då är divisorn 201/15).
• Beräkna kvoten - det bråktal av artiklar varje agent har rätt till. Detta är rättigheten dividerad med divisorn (t.ex. för en agent med en rättighet på 10 av 201 är kvoten 10*15/201 ~ 0,75 poster).

Konkurrensjämvikt

Plockningssekvenser kan användas för att hitta tilldelningar som uppfyller ett starkt villkor för rättvisa och effektivitet som kallas konkurrensjämvikt .

Se även

Round -robin-objektallokeringsprotokollet är ett specialfall av en plockningssekvens där sekvensen är cyklisk: 1, 2, ..., n , 1, 2, ..., n , ...

Skolgårdsspel behöver ofta välja "lag". När du använder "ABBA"-valet kommer "A"-laget att deklarera "första val" och B-laget kommer att deklarera "Andra-Två": Lista över traditionella barnspel