Hyresharmoni

Hyresharmoni är ett slags rättvis uppdelningsproblem där odelbara föremål och en fast penningkostnad måste delas upp samtidigt. Huskamratproblemet och rumsuppgift-hyresdelning är alternativa namn till samma problem .

I den typiska miljön finns det $n$ partners som hyr tillsammans ett $n$ -rumshus för kostnad som fastställs av husägaren. Varje kamrat kan ha olika preferenser — en kanske föredrar ett stort rum, en annan kanske föredrar ett rum med utsikt över huvudvägen, etc. Följande två problem bör lösas samtidigt:

• (a) Tilldela ett rum till varje partner,
• (b) Bestäm det belopp som varje partner ska betala, så att summan av betalningar motsvarar den fasta kostnaden.

Det finns flera egenskaper som vi vill att uppdraget ska tillgodose.

• Icke-negativitet (NN) : alla priser måste vara 0 eller högre: ingen partner ska betalas för att få ett rum.
• Envy-freeness (EF) : Givet ett prissättningssystem (en tilldelning av hyra till rum), säger vi att en partner föredrar ett givet rum om han anser att paketet med rum+hyra är svagt bättre än alla andra paket. EF betyder att varje partner föredrar sitt tilldelade rum. Dvs ingen partner skulle vilja ta ett annat rum till den hyra som tilldelas det rummet.
• Pareto-effektivitet (PE) : Ingen annan tilldelning av partners till rum är svagt bättre för alla partners och strikt bättre för minst en partner (med tanke på prisvektorn).

Avundsfrihet innebär Pareto-effektivitet. Bevis: Antag motsägelsefullt att det finns ett alternativt uppdrag, med samma prisvektor, som är strikt bättre för minst en partner. Sedan, i den nuvarande tilldelningen, är den partnern avundsjuk.

Hyresharmoniproblemet har studerats under två olika antaganden om partnernas preferenser:

• I den ordinarie verktygsversionen har varje partner en preferensrelation på buntar [rum, pris]. Givet en prisvektor bör partnern bara kunna säga vilket rum (eller rum) han föredrar att hyra till det priset.
• I kardinalverktygsversionen har varje partner en vektor för monetära värderingar. Partnern ska för varje rum säga exakt hur mycket pengar han är villig att betala för det rummet. Partnern antas ha kvasilinjär nytta , dvs om han värderar rummet som $v$ och betalar $p$ , är hans nettonytta $vp$ .

Det kardinala antagandet innebär det ordinala antagandet, eftersom givet en värderingsvektor är det alltid möjligt att konstruera en preferensrelation. Ordinala antagandet är mer generellt och lägger mindre psykisk belastning på partnerna.

Ordinal version

Sö: en person per rum

Protokollet av Francis Su gör följande antaganden om partnernas preferenser:

1. Bra hus : I varje del av hyran finner varje person minst ett rum + hyrespaket acceptabelt.
2. Inga externa effekter : Varje partners preferensrelation beror på rummen och hyrorna, men inte på andras val.
3. Snåla partners : varje partner föredrar svagt ett ledigt rum (ett rum med en hyra på 0) framför vilket annat rum som helst.
4. Topologiskt slutna preferensuppsättningar : En partner som föredrar ett rum för en konvergerande prissekvens, föredrar det rummet till det begränsande priset.

Normalisera den totala hyran till 1. Sedan är varje prissättningsschema en punkt i en $(n-1)$ -dimensionell simplex med $n$ hörn i $\mathbb { R} ^{n}$ . Sus protokoll fungerar på en dualiserad version av denna simplex på ett liknande sätt som Simmons–Su-protokollen för kakskärning: för varje vertex av en triangulering av den dubbla simplexen, som motsvarar ett visst prisschema, frågar det den ägande partnern " vilket rum föredrar du i det prisschemat?". Detta resulterar i en Sperner-färgning av den dubbla simplexen, och därmed finns det ett litet sub-simplex som motsvarar en ungefärlig avundsfri tilldelning av rum och hyror.

Sus protokoll returnerar en sekvens av tilldelningar som konvergerar till en avundsfri tilldelning. Priserna är alltid icke-negativa. Följaktligen uppfyller resultatet NN- och EF-kraven.

Su's Rental Harmony-protokoll har blivit populärt i flera nyhetsartiklar och har flera onlineimplementeringar.

Azriely och Shmaya: rumskamrater

Azriely och Shmaya generaliserar Sus lösning till en situation där kapaciteten i varje rum kan vara större än ett (dvs flera partners kan bo i samma rum).

De bevisar förekomsten av avundsfria tilldelningar under följande förhållanden:

1. Bra hus : Varje partner gillar minst ett av rummen givet varje prisvektor.
2. Inga externa effekter : Alla partners gillar gratis rum.
3. Snåla partners : Preferenserna är kontinuerliga i priser.

De viktigaste verktygen som används i beviset är:

• KKMS-satsen - en generalisering av Kkm-satsen .
• Halls äktenskapssats .

Deras lösning är konstruktiv i samma mening som Sus lösning - det finns en procedur som approximerar lösningen till vilken precision som helst.

Allmänna egenskaper hos ordinarie protokoll

S. I både Sus lösning och Azrieli&Shmayas lösning är preferensrelationen för varje partner tillåten (men inte skyldig) att bero på hela prisvektorn. Dvs en partner kan säga "om rum A kostar 1000 så föredrar jag rum B framför rum C, men om rum A bara kostar 700 så föredrar jag rum C framför rum B".

Det finns flera anledningar till att sådan generalitet kan vara användbar.

1. Framtidsplanering. Antag att partnern tycker att rum A är bäst, då B, sedan C. Om A är dyrt, bosätter sig partnern på B. Men om A är billigare, kanske partnern köper C (vilket är billigast) och sedan sparar lite pengar och byt till A.
2. Ofullständig information. Prisvektorn kan ge partnern en indikation på kvaliteten på rummen.
3. Grannar. Prisvektorn kan tillåta partnern att i viss mån förutsäga vilken typ av människor som kommer att bo i grannrummen.
4. Irrationalitetseffekter, t.ex. inramningseffekter . Om rum B och rum C är av samma kvalitet och har samma pris, kan partnern köpa A. Men, om rum B blir dyrare, kan partnern byta till C och tänka att "det är samma som B" men till fyndpris...".

B. Både Sus lösning och Azrieli&Shmayas lösning gör ett antagande om "Miserly hyresgäster" - de utgår från att en hyresgäst alltid föredrar ett ledigt rum framför ett icke-fritt rum. Detta antagande är starkt och inte alltid realistiskt. Om ett av rummen är väldigt dåligt är det möjligt att vissa hyresgäster inte vill bo i det rummet ens gratis. Detta är lätt att se i kardinalversionen: om du tror att rum A är värt 0 och rum B är värt 100, och rum A är gratis och rum B kostar 50, så föredrar du verkligen rum B.

Su föreslår att försvaga detta antagande på följande sätt: varje partner väljer aldrig det dyraste rummet om det finns ett ledigt rum. Detta kräver inte att personen väljer det lediga rummet. Detta gäller särskilt om en person alltid föredrar ett ledigt rum framför ett rum som kostar minst $1/(n-1)$ av den totala hyran. Men även detta försvagade antagande kan vara orealistiskt, som i exemplet ovan.

Kardinal version

Som förklarats ovan är input till kardinalversionen en matris av bud: varje partner måste lämna ett bud till varje rum och säga hur mycket (i dollar) detta rum är värt för honom.

En nyckelbegrepp i kardinallösningarna är en maxsum (alias utilitaristisk ) allokering. Detta är en tilldelning av partners till rum, som maximerar summan av bud. Problemet med att hitta en maxsumallokering är känt som tilldelningsproblemet , och det kan lösas med den ungerska algoritmen i tiden $O(n^{3})$ (där $n$ är antalet partners). Varje EF-allokering är maxsumma och varje maxsumallokering är PE.

Inkompatibilitet mellan EF och NN

De två kraven på avundsfrihet och icke-negativa betalningar är inte alltid kompatibla. Anta till exempel att den totala kostnaden är 100 och att värderingarna är:

	Rum 1	Rum 2
Partner 1	150	0
Partner 2	140	10

Här är den enda maxsummanallokeringen att ge rum 1 till partner 1 och rum 2 till partner 2. För att säkerställa att partner 2 inte avundas måste partner 1 betala 115 och partner 2 måste betala -15.

I det här exemplet är summan av värderingar mer än den totala kostnaden. Om summan av värderingar är lika med den totala kostnaden och det finns två eller tre partners, så finns det alltid en EF- och NN-allokering. Men om det finns fyra eller fler partners kan EF och NN återigen vara inkompatibla, som i följande exempel (se för bevis):

	Rum 1	Rum 2	Rum 3	Rum 4
Partner 1	36	34	30	0
Partner 2	31	36	33	0
Partner 3	34	30	36	0
Partner 4	32	33	35	0

Observera att detta exempel inte förekommer i den ordinarie versionen, eftersom ordinarie protokoll gör antagandet "Miserly Partners" - partners föredrar alltid lediga rum. När detta antagande gäller finns det alltid en EF+NN-allokering. Men i exemplet ovan stämmer inte antagandet och en EF+NN-allokering existerar inte. Därför måste protokollen i kardinalversionen kompromissa mellan EF och NN. Varje protokoll gör olika kompromisser.

Brams och Kilgour: NN men inte EF

Brams och Kilgour föreslår Gap-proceduren :

1. Beräkna en maxsumma allokering.
2. Om maxsumman är mindre än den totala kostnaden är problemet olösligt, eftersom partnerna inte vill betala det totala beloppet som husägaren kräver.
3. Om maxsumman exakt motsvarar den totala kostnaden, tilldelas rummen och partnerna betalar sina värderingar.
4. Om maxsumman är mer än den totala kostnaden, sänks priserna baserat på gapet mellan dessa priser och de näst lägsta värderingarna (se boken för mer information).

Tanken bakom det sista steget är att de näst lägsta värderingarna representerar "konkurrensen" på rummen. Om det är ett rum som är mer eftertraktat av näst högstbjudande, borde det kosta mer. Detta liknar Vickrey-auktionen till sin anda . Men medan betalningen i Vickrey-auktionen är helt oberoende av partnerns bud, är betalningen i Gap-förfarandet endast delvis oberoende. Därför är Gap-förfarandet inte strategisäkert .

Gap-proceduren tilldelar alltid icke-negativa priser. Eftersom uppdraget är maxsum är det självklart också Pareto-effektivt. Vissa partners kan dock vara avundsjuka. Dvs. Gap-proceduren uppfyller NN och PE men inte EF.

Dessutom kan Gap-proceduren returnera icke-avundsfria tilldelningar, även när EF-tilldelningar finns. Brams relaterar till detta problem och säger att: "Gappriser tar hänsyn till konkurrenskraften för att bjuda på varor, vilket gör prismekanismen marknadsorienterad. Även om avundsfrihet är en önskvärd egenskap, föredrar jag en marknadsliknande mekanism när det finns en konflikt mellan dessa två fastigheter; partners bör betala mer när buden är konkurrenskraftiga, även om de offrar avundsjuka”.

Haake och Raith och Su: EF men inte NN

Haake, Raith och Su presenterar kompensationsförfarandet. Problemet det löser är mer generellt än hyresharmoniproblemet i vissa aspekter:

• Antalet odelbara objekt att dela ( m ) kan skilja sig från antalet partners ( n ).
• Det kan finnas godtyckliga begränsningar för paket med föremål, så länge de är anonyma (särskilj inte mellan partner baserat på deras identitet). Till exempel kan det inte finnas någon begränsning alls, eller en begränsning som "varje partner måste ta emot minst ett visst antal föremål", eller "vissa föremål måste buntas ihop" (t.ex. för att de är tomter som måste finnas kvar ansluten), etc.
• Den totala "kostnaden" kan också vara positiv, vilket gör att det också finns en del pengar att dela på. Detta är karakteristiskt för scenarier för arvsdelning. På liknande sätt kan "föremålen" ha negativ användbarhet (t.ex. de kan representera odelbara sysslor).

Det finns ett "kvalifikationskrav" för en partner: summan av hans bud måste vara minst den totala kostnaden.

Proceduren fungerar i följande steg.

1. Hitta en maxsum (utilitaristisk) allokering - en allokering med en högsta summa av verktyg som uppfyller begränsningarna för buntar av objekt. Om det inte finns några begränsningar är en allokering som ger varje objekt till partnern med högst värdering maxsum. Om det finns begränsningar (som "minst ett objekt per partner"), kan en maxsumallokering vara svårare att hitta.
2. Debitera varje partner värdet av paketet som tilldelats honom. Detta skapar den initiala poolen av pengar.
3. Betala kostnaden från den första poolen. Om alla partners uppfyller kvalifikationskravet räcker pengarna i poolen och det kan finnas ett visst överskott .
4. Eliminera avund genom att kompensera avundsjuka partners. Det finns högst $n-1$ omgångar av kompensation. Förfarandet är helt beskrivande och säger uttryckligen vilka ersättningar som ska göras och i vilken ordning. Dessutom är det enkelt nog att utföras utan datorstöd.
5. Summan av ersättningar som görs i alla omgångar är den minsta summa som krävs för att eliminera avund, och den överstiger aldrig överskottet. Om något överskott finns kvar kan det delas upp på något sätt som inte skapar avund, t.ex. genom att ge lika mycket till varje partner (papperet diskuterar andra alternativ som kan anses vara "rättvisare").

När det finns många objekt och komplexa begränsningar kan det första steget - att hitta en maxsumallokering - vara svårt att beräkna utan en dator. I detta fall kan kompensationsförfarandet börja med en godtycklig tilldelning. I det här fallet kan proceduren avslutas med en tilldelning som innehåller avundscykler . Dessa cykler kan tas bort genom att flytta buntar längs cykeln. Detta ökar strikt den totala summan av verktyg. Följaktligen, efter ett begränsat antal iterationer, kommer en maxsumallokering att hittas, och proceduren kan fortsätta enligt ovan för att skapa en avundsfri allokering.

Ersättningsförfarandet kan debitera vissa partners en negativ betalning (dvs. ge partnerna en positiv summa pengar). Detta innebär att ersättningsförfarandet är EF (därav också PE) men inte NN. Författarna säger:

"Vi utesluter inte möjligheten att en individ i slutändan får betalt av de andra för att ta ett paket med varor. I samband med rättvis uppdelning finner vi inte detta problematiskt alls. Ja, om en grupp inte vill utesluta någon av sina medlemmar, så finns det ingen anledning till varför gruppen inte skulle subventionera en medlem för att ta emot ett oönskat paket. Dessutom garanterar kvalifikationskravet att subventionering aldrig är en konsekvens av en spelares otillräckliga värdering av den kompletta uppsättningen objekt som ska distribuerad".

Men andra författare hävdar att i det vanliga scenariot med huskamrater:

"en sambo som tilldelas ett rum med negativ rumshyra subventioneras av en del av andra huskamrater. I en sådan situation kan en del kamrater föredra att lämna rummet med negativ hyra outnyttjat och att utesluta den sambo som tilldelas det rummet, eftersom de kan få större rabatt. För att undvika en sådan situation måste negativa lokalhyror undvikas".

Abdulkadiroglu och Sonmez och Unver: EF och NN om möjligt

Abdulkadiroğlu et al. föreslå ett marknadsbaserat tillvägagångssätt. Det är en kombination av en stigande auktion och en fallande auktion . Det är enklast att beskriva som en kontinuerlig prisauktion:

1. Initiera priset för varje rum till $1/n$ av den totala huskostnaden.
2. Beräkna efterfrågeuppsättningen för varje partner: rummet eller uppsättningen rum han gillar mest till aktuella priser.
3. Beräkna uppsättningen av efterfrågade rum (rum som efterfrågas av fler partners än antalet rum; se uppsatsen för exakt definition).
4. Höj priset på alla efterfrågade rum i samma takt;
5. Sänk samtidigt priset på alla andra rum i samma pris, så att summan av priserna för alla rum alltid är lika med den totala kostnaden.
6. Uppdatera efterfrågan från varje partner och uppsättningen av överefterfrågade rum vid varje ögonblick.
7. När uppsättningen av efterfrågade rum är tomma, stoppa och tillämpa Halls äktenskapsteorem för att tilldela varje partner ett rum i deras efterfrågan.

I praktiken är det inte nödvändigt att ändra priset kontinuerligt, eftersom de enda intressanta priserna är priser där efterfrågan från en eller flera partners förändras. Det är möjligt att beräkna uppsättningen av intressanta priser i förväg och konvertera den kontinuerliga prisauktionen till en diskret-prisauktion. Denna auktion med diskreta priser stoppas efter ett begränsat antal steg.

Den returnerade tilldelningen är alltid avundsfri. Priserna kan vara negativa, som i förfarandet av Haake et al. Men till skillnad från det förfarandet är priserna icke-negativa om det finns en EF-allokering med icke-negativa priser.

Sung och Vlach: EF och NN om möjligt

Sung och Vlach bevisar följande allmänna egenskaper för tilldelningar:

1. Avundsfrihet innebär maxsumma: givet en allokering x , om det finns en prisvektor p med vilken x är avundsfri, så är x maxsumma.
2. Maxsumma innebär avundsfrihet: givet en prisvektor p , om det finns en allokering x med vilken p är avundsfri, så är p avundsfri för varje maxsummaallokering.

Baserat på dessa egenskaper föreslår de följande algoritm:

1. Hitta en maximal tilldelning.
2. Hitta en lägsta prisvektor (en vektor där summan av priser är minimerad), med förbehåll för avundsfrihetsbegränsningen. En sådan prisvektor är en lösning på ett linjärt programmeringsproblem , och den kan hittas av Bellman–Ford-algoritmen .
3. Om min-summan är lika med den totala kostnaden, implementera maxsum-allokeringen med minsumma priser och finish.
4. $(kostnadsminimum)/n$ dvs lägg till varje pris: ). Att ändra alla priser med samma belopp säkerställer att uppdraget förblir avundslöst.
5. Om min-summan är mer än den totala kostnaden, så finns det ingen lösning som uppfyller både NN och EF. Det finns flera möjliga sätt att gå tillväga:
   • Sänk alla priser i en konstant takt tills summan är lika med den totala kostnaden (dvs subtrahera från varje pris: $)$ . Vissa priser kommer nödvändigtvis att vara negativa, som i lösningen av Haake Raith och Su.
   • Sänk endast de positiva priserna i konstant takt tills summan är lika med den totala kostnaden. Här ändras inte priserna lika mycket, så vissa partners kommer nödvändigtvis avundsjuka, som i Brams och Kilgours lösning. Men i denna lösning får de avundsjuka partnerna sitt rum gratis .

Körtidskomplexiteten för att både hitta maxsumallokering och hitta minsummapriser är $O(n^{3})$ .

Lösningen av Sung och Vlach verkar ha alla önskvärda egenskaper från de tidigare protokollen, dvs: PE och EF och NN (om möjligt) och polynom körtid, och dessutom garanterar den att varje avundsjuk partner får ett ledigt rum. tillhandahåller en implementering av en liknande lösning, också baserad på att lösa ett linjärt programmeringsproblem men med hänvisning till ett annat dokument.

Mash, Gal, Procaccia och Zick: EF och maximin

Gal, Mash, Procaccia och Zick, baserat på sina erfarenheter av hyresuppdelningsapplikationen på Spliddit-webbplatsen, noterar att enbart avundsfrihet inte är tillräckligt för att garantera deltagarnas tillfredsställelse. Därför bygger de ett algoritmiskt ramverk, baserat på linjär programmering, för att beräkna allokeringar som både är avundsfria och optimerar något kriterium. Baserat på teoretiska och experimentella tester drar de slutsatsen att maximinkriteriet - att maximera den minimala användbarheten av ett medel som utsätts för avundsfrihet - ger optimala resultat.

Observera att eftersom deras lösning alltid är EF, kan det ge negativa priser.

Budgetöverväganden

De flesta tidningar i kardinalmodellen utgår från att agenter har kvasilinjära nyttofunktioner - deras nytta är rumsvärdet minus priset. Men i verkligheten har agenter budgetrestriktioner - om rumspriset är över deras budget, sjunker verktyget mycket snabbare än linjärt. Procaccia, Velez och Yu studerar denna modell och presenterar en algoritm för att ta reda på om det finns en EF-allokering som uppfyller budgetrestriktionerna, och om så är fallet, hitta en sådan allokering som uppfyller ett ytterligare skälighetskriterium.

Strategiska överväganden

Alla protokoll som hittills undersökts utgår från att partnerna avslöjar sina verkliga värderingar. De är inte strategisäkra – en partner kan vinna på att rapportera falska värderingar. Strategisäkerhet är faktiskt oförenligt med avundsfrihet : det finns inget deterministiskt strategisäkert protokoll som alltid returnerar en avundsfri tilldelning. Detta gäller även när det bara finns två partners och när priserna tillåts vara negativa. Bevis : Antag att den totala kostnaden är 100 och partnernas värderingar är enligt nedan (där $x,y$ är parametrar och $0<x<y<100$ ) :

	Rum 1	Rum 2
Partner 1	100	x
Partner 2	100	y

Den enda maxsummanallokeringen är att ge rum 1 till partner 1 och rum 2 till partner 2. Låt $p_{2}$ vara priset för rum 2 (så att priset för rum 1 är ${\ displaystyle 100-p_{2}}$ ). För att säkerställa att partner 1 inte avundas måste vi ha $p_{2}\geq x/2$ . För att säkerställa att partner 2 inte avundas måste vi ha $p_{2}\leq y/2$ .

Antag att ett deterministiskt protokoll sätter priset $p_{2}$ till något värde i $[x/2,y/2]$ . Om priset är mer än $x/2$ har partner 2 ett incitament att rapportera ett lägre värde på ${\displaystyle y} ,$ som fortfarande är över $x$ , för att tryck ner sin betalning mot $x/2$ . På liknande sätt, om priset är mindre än $y/2$ , har partner 1 ett incitament att rapportera ett högre värde på ${\displaystyle x} ,$ som fortfarande är under $y$ , i för att pressa betalningen av partner 2 upp mot ${\displaystyle y/2} ($ och därmed trycka ner sin egen betalning). Därför kan mekanismen inte vara strategisäker.

Forskare har klarat denna omöjlighet på två sätt.

Sun och Yang: Ändrar problemet

Det finns en variant av problemet där vi istället för att anta att den totala huskostnaden är fast, utgår från att det finns en maxkostnad för varje rum. I denna variant existerar en strategisäker mekanism: den deterministiska allokeringsregeln som väljer lägsta summakostnad är strategisäker.

Detta resultat kan generaliseras för större flexibilitet på de odelbara objekten, och ett bevis på koalitionell strategisäkerhet.

Dufton och Larson: Använda randomisering

Om vi ​​går tillbaka till det ursprungliga problemet med hyresharmoni är det möjligt att överväga randomiserade mekanismer . En randomiserad mekanism returnerar en sannolikhetsfördelning över rumsfördelningar och hyresuppdelningar. En randomiserad mekanism är sanningsenlig i förväntan om ingen partner kan öka det förväntade värdet av sin nytta genom att felaktigt rapportera sina värderingar till rummen. Rättvisan hos en randomiserad mekanism kan mätas på flera sätt:

1. Ex-ante Envy-Freeness betyder att ingen partner avundas någon annan partners lotteri. Detta villkor är trivialt att uppnå i en sanningsenlig mekanism: randomisera alla möjliga tilldelningar med lika sannolikhet och debitera varje partner $1/n$ av den totala kostnaden. Men detta villkor är inte tilltalande, eftersom det finns en stor chans att många partners kommer att bli avundsjuka i det slutliga resultatet. De kanske inte tröstas av att lotteriet har varit rättvist.

2. Guaranteed Probability of Envy-Freeness (GPEF) innebär att det finns en viss sannolikhet $p$ så att, oavsett partnernas värderingar, med sannolikhet minst $p$ , det slutliga resultatet blir utan avundsjuka. Det är möjligt att uppnå en GPEF på $1/n$ på följande sätt: hitta en avundsfri uppgift; välj ett heltal $i\in \{0,\dots ,n-1\}$ slumpmässigt; och flytta varje partner cykliskt $i$ rum till höger. Denna randomiserade mekanism är sanningsenlig i förväntan, eftersom varje partner har lika stor sannolikhet att landa i varje rum och den förväntade betalningen är $1/n$ av den totala kostnaden, oavsett partnerns bud. Sannolikheten att ha en EF-allokering är sannolikheten att ${\displaystyle i=0} ,$ vilket är exakt $1/n$ . Detta är inte uppmuntrande, eftersom sannolikheten för avundsjuka konvergerar till 0 när antalet partners växer. Men det är omöjligt att göra bättre: i varje sanningsenlig-i-förväntningar-mekanism är GPEF som mest $1/n$ .

3. Expected Number of Envy-Free partners (ENEF) betyder att det finns ett visst heltal $N$ så att, om vi genomsnittet av antalet partners som inte avundas i alla möjliga utfall av mekanismen, så oavsett partnernas värderingar är förväntningen minst $N$ . ENEF-kriteriet verkar mer lämpligt än GPEF-kriteriet, eftersom det mäter inte bara sannolikheten för fullständig avundsfrihet, utan också kvaliteten på de fall där tilldelningen inte är helt avundsfri. Den maximala ENEF för en sanningsenlig-i-förväntningar-mekanism är som mest $n-1+1/n$ . Det är möjligt att uppnå denna gräns för $n=2$ . För $n>2$ finns det en sanningsenlig-i-förväntningsmekanism som nästan uppnår denna gräns: ENEF är $n-1$ . Den allmänna idén är följande. Använd VCG-mekanismen för att beräkna en maximal tilldelning och betalningar. Välj en partner slumpmässigt. Ignorera den partnern och använd VCG igen. Kombinera resultaten på ett sätt som garanterar att den totala betalningen motsvarar den totala kostnaden (se uppsatsen för detaljer). Det är möjligt att visa att: (a) mekanismen är sanningsenlig-i-förväntning; (b) alla partners utom den ignorerade partnern avundas inte. Därför är ENEF $n-1$ . Simuleringar visar att i cirka 80 % av fallen är GPEF för denna mekanism också på sitt maximum på $1/n$ .

Andersson och Ehlers och Svensson: Att uppnå partiell strategisäkerhet

En möjlig uppmjukning av kravet på strategisäkerhet är att försöka minimera "graden av manipulerbarhet". Detta definieras genom att för varje profil räkna antalet agenter som kan manipulera regeln. Maximalt föredragna rättvisa allokeringsregler är de minimalt (individuellt och koalitionellt) manipulerbara rättvisa och budgetbalanserade tilldelningsreglerna enligt detta nya koncept. Sådana regler väljer tilldelningar med det maximala antalet agenter för vilka nyttan är maximerad bland alla rättvisa och budgetbalanserade tilldelningar.

Se även

Det finns flera problem där det bara finns odelbara föremål att dela, utan penningöverföringar:

• Rättvis slumpmässig tilldelning - varje agent bör få ett enda objekt; rättvisa uppnås genom randomisering.
• Hustilldelningsproblem - varje agent bör få ett enda objekt (hus); randomisering är inte tillåten. Målen är effektivitet och/eller rättvisa.
• Avundsfri matchning - varje agent bör få högst ett objekt; Målet är att maximera antalet uppdrag som är föremål för avundsjuka.
• Rättvis tilldelning av föremål - varje agent kan få ett godtyckligt antal objekt.
• Tilldelningsproblem - varje agent bör få ett enda objekt; målet är att maximera det totala värdet, eller minimera den totala kostnaden.