Acceptabel delmängd

En behaglig delmängd är en delmängd av objekt som av alla människor i en viss grupp anses vara minst lika bra som dess komplement. Att hitta en liten angenäm delmängd är ett problem i beräkningsmässigt socialt val .

Ett exempel på situation där detta problem uppstår är när en familj åker på en resa och ska bestämma sig för vilka föremål som ska tas med. Eftersom deras bil är begränsad i storlek kan de inte välja alla artiklar, så de måste komma överens om en undergrupp av artiklar som är viktigast. Om de lyckas hitta en delmängd av föremål så att alla familjemedlemmar är överens om att det är minst lika bra som delmängden av föremål som finns kvar hemma, så kallas denna delmängd behaglig .

Ett annat användningsfall är när medborgarna i någon stad vill välja en kommitté från en given pool av kandidater, så att alla medborgare är överens om att delmängden av valda kandidater är minst lika bra som delmängden av icke-valda. Med förbehåll för det bör kommitténs storlek vara så liten som möjligt.

Definitioner

Acceptabel delmängd

Det finns en uppsättning S som innehåller m objekt. Det finns n agenter som måste välja en delmängd av S . Varje agent kännetecknas av en preferensrelation på delmängder av S . Preferensrelationen antas vara monoton - en agent föredrar alltid svagt en uppsättning framför alla dess delmängder. En delmängd T av S kallas behaglig om alla agenter föredrar T framför S \ T .

Om en agents preferensrelation representeras av en subadditiv hjälpfunktion u , då för vilken som helst acceptabel delmängd T , u( T ) ≥ u( S )/2.

Anta som ett exempel att det finns två föremål - bröd och vin, och två agenter - Alice och George. Preferensrelationen för Alice är {bröd,vin} > {bröd} > {vin} > {}. Om preferensrelationen för George är densamma, så finns det två behagliga delmängder: {bröd,vin} och {bröd}. Men om Georges preferens-relation är {bröd,vin} > {vin} > {bröd} > {}, så är den enda angenäma delmängden {bröd,vin}.

Nödvändigtvis acceptabel delmängd

Om agenternas preferensrelationer på delmängderna anges är det lätt att kontrollera om en delmängd är acceptabel. Men ofta ges bara agenternas preferensrelationer på enskilda objekt . I det här fallet antas det ofta att agenternas preferenser inte bara är monotona utan också lyhörda . En delmängd T av S kallas nödvändigtvis acceptabel om alla agenter föredrar T framför S \ T enligt den responsiva uppsättningsutvidgningen av deras preferenser på enskilda objekt.

En närbesläktad egenskap hos delmängder är:

• (*) För varje k i 1, ..., m innehåller delmängden T minst k /2 av de bästa k objekten för agent i .

För att uppfylla egenskapen (*) bör delmängden T innehålla det bästa objektet i S ; minst två av de tre bästa objekten i S ; minst tre av de fem bästa objekten i S ; etc.

Om en delmängd T uppfyller (*) för alla agenter, är det nödvändigtvis acceptabelt. Den omvända implikationen gäller om agenternas preferensrelationer på odelbara objekt är strikta.

Worst-case gränser för acceptabel delmängdsstorlek

Vilken är den minsta behagliga delmängd vi kan hitta?

Acceptabel delmängder

Överväg först en enskild agent. I vissa fall bör en acceptabel delmängd innehålla minst $\lceil m/2\rceil$ objekt. Ett exempel är när alla m objekt är identiska. Dessutom finns det alltid en behaglig delmängd som innehåller $\lceil m/2\rceil$ objekt. Detta följer av följande lemma:

• För varje agent i , om två undergrupper V ₁ och V ₂ är disjunkta, då är minst en av S\ V ₁ eller S\ V ₂ acceptabel för i .

(detta beror på att S\ V ₁ innehåller V ₂ och S\ V ₂ innehåller V ₁ och preferenserna är monotona).

Detta kan generaliseras: För alla n agenter och m objekt finns det alltid en behaglig delmängd av storlek ${\bigg \lfloor }{\frac {m+n}{2}}{\ bigg \rfloor }$ , och den är tight (för vissa preferenser är detta den minsta storleken av en angenäm delmängd). Beviset för två agenter är konstruktivt. Beviset för n agenter använder en Kneser-graf . Låt ${\displaystyle k:={\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }} ,$ och låt G vara Kneser-grafen $KG(m,mk)$ , det vill säga grafen vars hörn är alla delmängder av m - k objekt, och två delmängder är sammankopplade om de är disjunkta. Om det finns en vertex V så att alla agenter föredrar S\ V framför V , så är S\ V en acceptabel delmängd av storleken k . Annars kan vi definiera en färg för varje agent och färga varje vertex V i G med en agent som föredrar V framför S\V. Enligt satsen om kromatiskt antal Kneser-grafer är det kromatiska antalet G $m-2(mk)+2=n+1$ ; detta betyder att det i den n -färgningen finns två angränsande hörn med samma färg. Med andra ord, det finns två disjunkta delmängder så att en enda agent i föredrar var och en av dem framför dess komplement. Men detta motsäger ovanstående lemma. Därför måste det finnas en behaglig delmängd av storlek k .

När det finns högst tre agenter, och deras preferenser är lyhörda, en behaglig delmängd av storlek ${\bigg \lfloor }{\frac {m+n}{2}}{\bigg \ rfloor }$ kan beräknas i polynomtid med hjälp av polynom-många frågor av formen "vilken av dessa två delmängder är bättre?".

När det finns ett valfritt antal agenter med additiva verktyg, eller ett konstant antal agenter med monotona verktyg, en behaglig delmängd av storlek ${\bigg \lfloor }{\frac {m+n}{ 2}}{\bigg \rfloor }$ kan hittas i polynomtid med hjälp av resultat från konsensushalvering .

Nödvändigtvis-acceptabla delmängder

När det finns två agenter med lyhörda preferenser, en nödvändigtvis -acceptabel delmängd av storlek ${\bigg \lfloor }{\frac {m+n}{2}}{\bigg \rfloor }$ existerar och kan beräknas i polynomtid.

När det finns n ≥ 3 agenter med lyhörda preferenser, kanske en nödvändigtvis acceptabel delmängd av denna storlek inte existerar. Det finns dock alltid en nödvändig delmängd av storleken $m/2+(n+1)\lceil 4n\log {m}\rceil$ , och en sådan mängd kan beräknas i polynomtid. Å andra sidan, för varje m som är en potens av 3, finns det ordinarie preferenser för 3 agenter så att varje nödvändigtvis överensstämmande delmängd har storleken minst $m/ 2+(\log _{3}{m})/4$ . Båda bevisen använder teorem om diskrepans i permutationshypergrafer .

Det finns en randomiserad algoritm som beräknar en nödvändig delmängd av storleken $m/2+O({\sqrt {m}})$ .

Beräknar en minsta behaglig delmängd

I många fall kan det finnas en acceptabel delmängd som är mycket mindre än den övre gränsen i värsta fall.

För agenter med allmänna monotona preferenser finns det ingen algoritm som beräknar en minsta behaglig uppsättning med hjälp av ett polynomantal frågor. Dessutom, för varje konstant c , finns det ingen algoritm som gör högst mc ^{. /8-} förfrågningar och hittar en behaglig delmängd med förväntad storlek som mest m /( clog m ) av minimum, även med endast en agent Detta är snävt: det finns en polynom-tidsalgoritm som hittar en behaglig delmängd med storleken som högst O( m / log m ) av minimum.

Även för medel med tillsatsfunktioner är det NP-svårt att avgöra om det finns en acceptabel delmängd av storleken m /2; beviset är genom reduktion från problemet med balanserad partition . För alla fixerade additivmedel finns det en pseudopolynomisk tid för detta problem; men om antalet agenter inte är fixat är problemet starkt NP-hårt. Det finns en polynom-tid O(log n ) approximationsalgoritm.

Tillägg

• Problemet med behaglig delmängd studerades med ytterligare begränsningar representerade av en matroid .

Se även

• Avundsfri varufördelning
• Deltagande budgeteringsalgoritm
• Flervinnarval
• Konsensushalvering
• Rättvis uppdelning mellan grupper - en variant av rättvis uppdelning där delarna av resursen ges till förutbestämda grupper snarare än till individer.