Seznam nevyřešených problémů ve spravedlivém rozdělení - List of unsolved problems in fair division

Tato stránka uvádí významné otevřené problémy související s spravedlivé rozdělení - obor v průsečíku matematiky, informatiky, politologie a ekonomiky.

Otevřené problémy v spravedlivé krájení dortu

Složitost dotazu řezání dortů bez závisti

V problému řezání dortů bez závisti, existuje dort modelovaný jako interval, a ${ displaystyle n}$ agenti s různými hodnotami měří přes dort. Hodnotové míry jsou přístupné pouze prostřednictvím dotazů ve tvaru „vyhodnotit daný kousek dortu“ nebo „označit kousek dortu s danou hodnotou“. S ${ displaystyle n = 2}$ agenti, divize bez závisti lze najít pomocí dvou dotazů, přes rozdělit a vybrat. S ${ displaystyle n> 2}$ agenti, existuje několik otevřených problémů týkajících se počtu požadovaných dotazů.

1. Nejprve předpokládejme, že musí být přidělen celý dort (tj. Existuje žádná likvidace) a kusy mohou být odpojeny. Kolik dotazů je požadováno?

• Dolní mez: ${ displaystyle Omega (n ^ {2})}$;^[1]
• Horní hranice: ${ displaystyle O left (n ^ {n ^ {n ^ {n ^ {n ^ {n}}}}} right)}$.^[2]

2. Dále předpokládejme, že nějaký koláč může zůstat nepřidělen (tj. Existuje bezplatná likvidace ), ale alokace musí být úměrný (navíc bez závisti): každý agent musí dostat alespoň ${ displaystyle 1 / n}$ z celkové hodnoty dortu. Kusy mohou být stále odpojeny. Kolik dotazů je požadováno?

• Dolní mez: není známa (teoreticky může být polynomiálně řešitelná).
• Horní hranice: ${ displaystyle (n!) ^ {2} n ^ {2}}$.^[2]

3. Dále předpokládejme, že existuje bezplatná likvidace, alokace musí být stále proporcionální, ale části musí být připojeno. Kolik dotazů je požadováno?

• Pro ${ displaystyle n = 3}$, existuje algoritmus s 54 dotazy.^[3]
• Pro ${ displaystyle n geq 4}$, v současné době není znám žádný konečný algoritmus.

4. Dále předpokládejme, že existuje bezplatná likvidace, jednotlivé části musí být spojeny, ale rozdělení může být pouze přibližně proporcionální (tj. Někteří agenti mohou získat méně než ${ displaystyle 1 / n}$ z celkové hodnoty dortu). Jakou hodnotu lze každému agentovi zaručit pomocí protokolu bez závisti?

• Pro ${ displaystyle n = 3}$, existuje algoritmus, který dosahuje 1/3, což je optimální.
• Pro ${ displaystyle n = 4}$ (nejmenší otevřený případ), existuje algoritmus, který dosahuje 1/7.^[3]
• Pro všechny ${ displaystyle n}$existuje algoritmus, kterého se dosáhne ${ displaystyle 1 / (3n)}$.^[2]

5. Nakonec předpokládejme, že musí být přidělen celý koláč a kusy mohou být odpojeny, ale počet řezů (nebo počet kusů na agenta) by měl být co nejmenší. Kolik škrtů potřebujeme, abychom našli záviděníhodnou alokaci v konečném počtu dotazů?

• Pro ${ displaystyle n geq 3}$, konečný algoritmus pro neexistuje ${ displaystyle n-1}$ řezy (1 kus na agenta).^[4]
• Pro ${ displaystyle n = 3}$, Postup Selfridge – Conway řeší problém v konečném čase 5 kusy (a maximálně 2 kusy na agenta).
• Pro ${ displaystyle n geq 4}$, postup Aziz-Mackenzie řeší problém v konečném čase, ale s mnoha škrty (a mnoha kusy na agenta).
• Nejmenší otevřený kufřík: tři agenti a 3 nebo 4 řezy; čtyři agenti a 2 kusy na agenta.

Počet řezů pro krájení dortů s různými oprávněními

Pokud mají všichni agenti stejná oprávnění, a proporcionální krájení dortu lze implementovat pomocí ${ displaystyle n-1}$ řezy, což je optimální.

Kolik řezů je zapotřebí k zavedení proporcionálního krájení dortu ${ displaystyle n}$ agenti s různými oprávněními?

• Dolní mez: ${ displaystyle 2n-2}$;^[5]
• Horní hranice: ${ displaystyle 3n-4}$.^[6]
• Nejmenší otevřený kufřík: ${ displaystyle n = 3}$ agenti se všemi různými oprávněními: ${ displaystyle 1/7}$, ${ displaystyle 2/7}$ a ${ displaystyle 4/7}$.^[5]

Kolik škrtů je zapotřebí pro implementaci řezání dortů bez závisti mezi ${ displaystyle n}$ agenti s různými oprávněními?

• Dolní mez: ${ displaystyle 2n-2}$, protože bez závisti znamená proporcionální.
• Horní mez: není známa.

Spravedlivé rozdělení částečně spáleného dortu

A částečně spálený dort je metaforou dortu, ve kterém mohou mít agenti pozitivní i negativní ocenění.^[7]

Proporcionální rozdělení takového dortu vždy existuje.

Jaká je runtime složitost výpočtu připojeného -úměrný přidělení částečně spáleného koláče?

Známé případy:

• Pokud jsou všechna ocenění kladná nebo všechna ocenění záporná, Protokol Even-Paz najde spojené proporcionální dělení pomocí ${ displaystyle O (n log n)}$ dotazy, a to je optimální.
• Pokud mohou být hodnoty smíšené, lze pomocí protokolu pohyblivého nože najít připojené proporcionální dělení pomocí ${ displaystyle O (n ^ {2})}$ dotazy.^[8]:Thm.5 Lze to vylepšit na ${ displaystyle O (n log n)}$ ?

Je zaručeno, že rozdělení závratného dortu bez závisti bude existovat pouze a pouze za předpokladu, že počet agentů bude výkonem primárního celého čísla.^[9] Nelze jej však najít pomocí konečného protokolu - lze jej pouze aproximovat. Vzhledem k malému kladnému číslu Dse nazývá alokace D- bez závisti, pokud pro každého agenta bude alokace bez závisti, pokud posuneme škrty maximálně D (délkové jednotky).

Jaká je runtime složitost (jako funkce D) výpočtu připojeného Bez závisti přidělení částečně spáleného koláče?^[7]

Pravdivé krájení dortu

Pravdivé krájení dortu je design pravdivé mechanismy pro poctivé krájení dortu. Jsou zobrazeny aktuálně známé algoritmy a výsledky nemožnosti tady. Hlavní případy, kdy není známo, zda existuje deterministický pravdivý spravedlivý mechanismus, jsou:^[10]

• Existují 3 nebo více agentů s po částech jednotná ocenění, bez bezplatné likvidace.
• Existují 2 nebo více agentů s po částech konstantní ocenění, s bezplatnou likvidací nebo bez ní (a bez dalších požadavků, jako je připojení nebo plýtvání).

Otevřené problémy v spravedlivé rozdělení nedělitelných položek

Přibližný maximální podíl spravedlnost

The 1 z${ displaystyle n}$ maximální podíl (MMS) agenta je největší utilita, kterou může agent zabezpečit rozdělením položek do ${ displaystyle n}$ svazky a příjem nejhoršího svazku. Pro dva agenty rozdělit a vybrat dává každému agentovi alespoň jeho MMS 1 ze 2. Pro ${ displaystyle n> 2}$ agenti, je téměř vždy, ale ne vždy, možné dát každému agentovi jeho 1${ displaystyle n}$ MMS. To vyvolává několik druhů otázek.

1. Výpočetní složitost

Jaká je runtime složitost rozhodování, zda daná instance připouští 1${ displaystyle n}$ Přidělení MMS?^[11][12]

• Horní hranice: ${ displaystyle {NP} ^ {NP}}$ (který je ${ displaystyle Sigma _ {2} ^ {P}}$ - úroveň 2 v polynomiální hierarchie )
• Dolní mez: žádná (může to být úroveň 2 nebo 1 nebo dokonce 0 hierarchie).

POZNÁMKA: Je známo, že následující související problémy jsou výpočetně náročné:

• Výpočet jeden z${ displaystyle n}$ MMS daného agenta je NP-tvrdé i když všichni agenti mají aditivní preference (redukce z problém s oddílem ).
• Rozhodování, zda a daný alokace je 1 z${ displaystyle n}$ MMS je co-NP kompletní pro agenty s preferencemi aditiv.

2. Kardinální aproximace

Jaký je největší zlomek r takový, že vždy existuje alokace, která dává každému agentovi užitečnost alespoň r krát jeho 1${ displaystyle n}$ maximální podíl?

Známé případy:

• Pro dva agenty: ${ displaystyle r = 1}$ rozdělením a výběrem.
• Pro tři agenty, dokonce is aditivními oceněními: ${ displaystyle r <1}$. Pečlivě vytvořeným příkladem.^[13]
• Pro libovolný počet agentů s aditivním oceněním: ${ displaystyle r geq 3/4}$.^[14]
• Pro libovolný počet agentů s přísadou negativní ocenění (tj. pro domácí práce): ${ displaystyle r geq 9/11}$.^[15]

3. Pořadová aproximace

Jaké je nejmenší celé číslo ${ displaystyle N}$ (jako funkce ${ displaystyle n}$) tak, aby vždy existovalo rozdělení mezi ${ displaystyle n}$ agenti dávající každému agentovi alespoň jeho 1${ displaystyle N}$ MMS?

Známé případy:

• Pro dva agenty: ${ displaystyle N = 2}$. Podle rozdělit a vybrat.
• Pro libovolný počet agentů s binárními hodnotami: ${ displaystyle N = n}$. Každý s každým. Poskytuje EF1, což znamená 1${ displaystyle n}$-MMS.
• Pro ${ displaystyle n> 2}$ agenti: ${ displaystyle N> n}$. Pečlivě vytvořeným příkladem.^[13]
• Pro libovolný počet agentů s aditivním oceněním: ${ displaystyle N leq 2n-1}$, každý s každým. Poskytuje EF1, což znamená 1${ displaystyle (2n-1)}$-MMS.
• Pro libovolný počet agentů s aditivním oceněním: ${ displaystyle N leq 2n-2}$, použitím záviděníhodné shody.^[16]

Odpověď tedy může být cokoli mezi tím ${ displaystyle n + 1}$ a ${ displaystyle 2n-2}$, včetně. Nejmenší otevřený kufřík:

Pro ${ displaystyle n = 4}$ agenti s aditivním hodnocením, existuje vždy alokace maximin-share 1 z 5?

Poznámka: vždy existuje Přibližná konkurenční rovnováha ze stejných příjmů který zaručuje 1 z (${ displaystyle n + 1}$) maximální podíl.^[17] Tato alokace však může mít nadbytečnou nabídku a - co je důležitější - nadbytečnou poptávku: součet balíčků přidělených všem agentům může být o něco větší než sada všech položek. Taková chyba je přiměřená při přidělování sedadel kurzu studentům, protože malou přebytečnou nabídku lze napravit přidáním malého počtu sedadel. Klasický problém spravedlivého rozdělení však předpokládá, že položky nemusí být přidány.

Bez závisti až na jednu položku

Volá se alokace EF1 (bez závisti až na jednu položku), pokud pro dva agenty ${ displaystyle i}$ a ${ displaystyle j}$a pro jakoukoli podmnožinu velikosti nejvýše jednu obsaženou ve svazku ${ displaystyle j}$, pokud tuto podmnožinu odstraníme z ${ displaystyle j}$pak svazek ${ displaystyle i}$ nezávidí. Alokace EF1 vždy existuje a lze ji najít pomocí algoritmus cyklů závisti. Kombinace s dalšími vlastnostmi vyvolává některé otevřené otázky.

Paretooptimální alokace EF1 (zboží a zboží)

Když jsou všechny položky v pořádku a všechna ocenění jsou aditivní, existuje vždy PO + EF1: alokace maximalizující produkt nástrojů je PO + EF1.^[18] Najít tuto maximalizaci alokace je NP-těžké,^[19] ale teoreticky je možné najít další přidělení PO + EF1 (ne maximalizaci produktu).

Jaká je běhová složitost hledání alokace PO + EF1 zboží?

Přidělení PO + EF1 ve výši špatné práce není známo, že existuje, i když jsou všechna ocenění aditivní.

Přiděluje PO + EF1 špatné vždy existují?

Jaká je běhová složitost hledání takové rozdělení, pokud existuje?

Souvislá alokace EF1

Zboží se často objednává na lince, například domy na ulici. Každý agent chce získat souvislý blok.^[20]

Existuje pro tři nebo více agentů s aditivními hodnotami přidělení EF1 vždy?

Známé případy:

• U dvou agentů s aditivním oceněním je odpověď ano: můžeme zaokrouhlit připojené řezání dortů bez závisti (např. nalezen rozdělit a vybrat ).
• Pro ${ displaystyle n}$ agenti s aditivními ohodnocením, můžeme najít alokaci „EF minus 2“ zaokrouhlením spojeného řezání dortu bez závisti a existuje také EF2 alokace (důkaz pomocí varianty Spernerovo lemma ).^[21]
• Pro ${ displaystyle n}$ činidla s přísadou binární ocenění (každá hodnota položky je buď 0 nebo 1), přidělení „EF minus 2“ je také EF1, takže odpověď je Ano.

I když existuje souvislá alokace EF1, je runtime složitost jeho nalezení nejasná:

Jaká je složitost hledání souvislé alokace EF1 pro tři nebo více agentů s hodnotami binárních aditiv?

• Propojené řezání dortů bez závisti může trvat nekonečně mnoho dotazů. Přidělení EF1 lze vždy najít v konečném čase kontrolou všech možných přidělení, ale tento algoritmus vyžaduje exponenciální běh.

Cena spravedlnosti

The cena spravedlnosti je poměr mezi maximální sociální dávkou (součtem veřejných služeb) při jakékoli alokaci a maximální sociální dávkou při spravedlivé alokaci. Jaká je cena spravedlnosti EF1?

• Horní hranice je ${ displaystyle O (n)}$ - buď Každý s každým nebo maximální Nash blahobyt.
• Dolní mez je ${ displaystyle O ({ sqrt {n}})}$.^{[22]:bod 1.1}

Existence přidělení EFx

Volá se alokace EFx („bez závisti až k dobrému“), pokud pro dva agenty ${ displaystyle i}$ a ${ displaystyle j}$, a pro jakékoli zboží ve svazku ${ displaystyle j}$, pokud odstraníme to dobré z ${ displaystyle j}$pak svazek ${ displaystyle i}$ nezávidí.^[23]

Existuje vždy pro tři agenty s přidaným oceněním přidělení EFx?

Pro ${ displaystyle n}$ agenti s obecným monotónním hodnocením, můžeme dokázat, že neexistuje alokace EFx?

Známé případy:

• Pokud alespoň ${ displaystyle n-1}$ ocenění jsou identická: ano.
• Proto pro dva agenty: ano. To platí i pro obecná monotónní ocenění.^[24]
• Pro tři agenty: ano, nedávným pracovním dokumentem.^[25]

Existence Pareto-efektivní alokace PROPx chyb

Alokace bads se nazývá PROPx (aka FSx)^{[26]:Bod 7.} pokud pro nějakého agenta ${ displaystyle i}$a za jakékoli špatné vlastnictví ${ displaystyle i}$, pokud odstraníme to špatné z ${ displaystyle i}$Balíček tedy ${ displaystyle i}$Disutility je menší než ${ displaystyle 1 / n}$ totální disutility.

Existuje vždy alokace chyb, která je PROPx i Pareto efektivní?

Související známé případy:

• Přidělení PROPx ve výši zboží (i bez Paretovy účinnosti) nemusí existovat.
• Přidělení PROPx ve výši špatné (bez Paretovy účinnosti) vždy existuje.
• A PROP1 a Pareto-efektivní alokace zboží nebo zboží vždy existuje.

Konkurenční rovnováha pro téměř všechny příjmy

Konkurenční rovnováha (CE) je velmi silný pojem spravedlnosti - znamená Paretovu optimálnost a závistivost. Pokud jsou příjmy stejné, CE nemusí existovat, i když existují dva agenti a jeden dobrý. Ale ve všech ostatních příjmových prostorech existuje CE, když existují dva agenti a jeden dobrý. Jinými slovy, existuje konkurenční rovnováha pro téměř všechny příjmové vektory.

Existuje pro dva agenty s aditivním oceněním u libovolného počtu zboží konkurenční rovnováha pro téměř příjmy?^[27]

Známé případy:

• Se třemi nebo méně zboží: vždy Ano.
• Se čtyřmi výrobky: Ano pro 2 agenty s obecným oceněním, Ne pro 3 agenty s obecným oceněním, Ne pro 4 agenty, dokonce s aditivními oceněními.^[28]
• S pěti a více zbožím: Ne pro dva agenty s obecným oceněním.

Otevřené domněnky:

• Když jsou dva agenti s přísada oceňování, CE pro téměř všechny příjmy existuje pro libovolný počet zboží.
• Pokud existují tři agenti, i při aditivním ocenění nemusí CE téměř pro všechny příjmy existovat.

Spravedlivé rozdělení částečně dělitelných položek

Runtime složitost spravedlivé alokace s omezeným sdílením

Dáno ${ displaystyle n geq 2}$ agenti, ${ displaystyle m}$ položky a celé číslo ${ displaystyle k}$, předpokládejme nanejvýš ${ displaystyle k}$ položky lze sdílet mezi dvěma nebo více agenty. Jaká je runtime složitost rozhodování, zda existuje proporcionální a závistivé alokace?

Známé případy:

• S ${ displaystyle k = 0}$ a identická ocenění pro všechny ${ displaystyle n geq 2}$, problém je ekvivalentní s problém s oddílem, a proto je NP-kompletní.
• S ${ displaystyle k geq n-1}$, odpověď je vždy „ano“ a alokaci lze najít v polynomiálním čase.^[29]
• S ${ displaystyle n = 3}$ a ${ displaystyle k = 1}$ a identická ocenění lze alokaci najít v polynomiálním čase, pokud existuje.^[30]

Nejmenší otevřené případy:

• ${ displaystyle n = 3}$ a ${ displaystyle k = 1}$ a různá ocenění.
• ${ displaystyle n = 4}$ a ${ displaystyle k in {1,2 }}$ a identická ocenění.

Reference