Hodnost-maximální alokace - Rank-maximal allocation

Maximální alokace (RM) je pravidlem pro spravedlivé rozdělení nedělitelných položek. Předpokládejme, že musíme některé položky rozdělit mezi lidi. Každý může řadit položky od nejlepších po nejhorší. Pravidlo RM říká, že musíme dát co nejvíce lidem jejich nejlepší (# 1) položku. S výhradou toho musíme dát co největšímu počtu lidí jejich next-best (# 2) předmět atd.

Ve zvláštním případě, kdy by každá osoba měla obdržet jednu položku (například když jsou „položkami“ úkoly a každý úkol musí být prováděn jednou osobou), se problém nazývá hodnost-maximální shoda nebo chamtivý shoda.

Myšlenka je podobná myšlence užitkové krájení dortu, kde cílem je maximalizovat součet utilit všech účastníků. Utilitaristické pravidlo však funguje základní (číselné) obslužné funkce, zatímco pravidlo RM funguje s pořadové nástroje (hodnocení).

Definice

Existuje několik položek a několik agentů. Každý agent má celková objednávka na položkách. Agenti mohou být mezi některými položkami lhostejní; pro každého agenta můžeme rozdělit položky do tříd ekvivalence, které obsahují položky stejné hodnosti. Například pokud je Alice preferenční vztah x> y, z> w, to znamená, že Alicina první volba je x, což je pro ni lepší než všechny ostatní položky; Alicina druhá volba je yaz, které jsou v jejích očích stejně dobré, ale ne tak dobré jako x; a Alicina třetí volba je w, což považuje za horší než všechny ostatní položky.

Pro každé přidělení položek agentům vytvoříme jeho hodnostní vektor jak následuje. Prvek # 1 ve vektoru je celkový počet položek, které jsou pro jejich majitele první volbou; Prvek # 2 je celkový počet položek, které jsou pro jejich majitele druhou volbou; a tak dále.

A hodnost-maximální alokace je takový, ve kterém je hodnostní vektor maximální (v lexikografickém pořadí).

Příklad

Tři položky, x yaz, musí být rozděleny mezi tři agenty, jejichž pořadí je:

Alice: x> y> z
Bob: x> y> z
Carl: y> x> z

V alokaci (X, y, z), Alice dostane 1. volbu (X), Bob dostane druhou volbu (y) a Carl dostane svou třetí volbu (z). Hodnostní vektor je tedy (1,1,1).

V alokaci (X,z,y), jak Alice, tak Carl dostanou svoji první volbu a Bob svou třetí volbu. Hodnostní vektor je tedy (2,0,1), což je lexikograficky vyšší než (1,1,1) - dává více lidem první možnost volby.

Je snadné zkontrolovat, že žádná alokace nevytvoří lexikograficky vyšší hodnostní vektor. Proto alokace (X,z,y) je hodnost-maximální. Podobně alokace (z,X,y) je hodnostní-maximální - vytváří stejný hodnostní vektor (2,0,1).

Algoritmy

RM shody nejprve studoval Robert Irving, který je zavolal chamtivé zápasy. Představil algoritmus, který najde shodu RM v čase ${ displaystyle O (n ^ {2} c ^ {3})}$ , kde n je počet agentů a C je největší délka seznamu preferencí agenta.^[1]

Později byl nalezen vylepšený algoritmus, který běží v čase ${ displaystyle O (m cdot min (n, C { sqrt {n}}))}$ , kde m je celková délka všech seznamů preferencí (celkový počet hran v grafu) a C je maximální pořadí položky použité v RM shodě (tj. maximální počet nenulových prvků ve vektoru optimálního pořadí).^[2]

Jiné řešení, použití shody s maximální hmotností, dosáhne podobného běhu - ${ displaystyle O (m cdot min (n + C, C { sqrt {n}}))}$ .^[3]

Varianty

Problém má několik variant.

1. v shoda RM s maximální mohutností, cílem je najít, mezi všemi různými RM shody, ten s maximálním počtem shody.

2. v spravedlivé shody, cílem je najít shodu maximální mohutnosti tak, aby byl minimální počet hran hodnosti r jsou použity, vzhledem k tomu - minimální počet okrajů hodnosti r−1 jsou použity atd.

Porovnání RM s maximální mohutností i spravedlivé shody lze najít redukcí na shodu s maximální hmotností.^[3]

3. V kapacitní přizpůsobení RM problém, každý agent má horní kapacitu označující horní hranici celkového počtu položek, které by měl dostat. Každá položka má horní kvótu označující horní hranici počtu různých agentů, kterým může být přidělena. Poprvé to studovali Melhorn a Michail, kteří poskytli algoritmus za běhu ${ displaystyle O (Cnm log (n ^ {2} / m) log (n))}$ .^[4] Existuje vylepšený algoritmus s dobou běhu ${ displaystyle O (m cdot min (B, C { sqrt {B}}))}$ , kde B je minimum součtu kvót agentů a součtu kvót položek. Je založen na rozšíření Gallai – Edmondsův rozklad do shody s více hranami.^[5]

Viz také

Reference

^ Irving, Robert W. (2003). Chamtivé zápasy. University of Glasgow. str. Tr – 2003–136. CiteSeerX 10.1.1.119.1747.
^ Irving, Robert W .; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (1. října 2006). "Hodnost-maximální shody". ACM Trans. Algoritmy. 2 (4): 602–610. doi:10.1145/1198513.1198520. ISSN 1549-6325.
^ ^A ^b Michail, Dimitrios (10. prosince 2007). Msgstr "Snížení shody mezi pořadím a maximální hmotností". Teoretická informatika. 389 (1): 125–132. doi:10.1016 / j.tcs.2007.08.004. ISSN 0304-3975.
^ Kurt Mehlhorn a Dimitrios Michail (2005). „Problémy se sítí s nepolynomiálními váhami a aplikacemi“.
^ Paluch, Katarzyna (22. května 2013). Maximalizované shody s hodnocením. Algoritmy a složitost. Přednášky z informatiky. 7878. Springer, Berlín, Heidelberg. 324–335. doi:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.

[1] Irving, Robert W. (2003). Chamtivé zápasy. University of Glasgow. str. Tr – 2003–136. CiteSeerX 10.1.1.119.1747.

[2] Irving, Robert W .; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (1. října 2006). "Hodnost-maximální shody". ACM Trans. Algoritmy. 2 (4): 602–610. doi:10.1145/1198513.1198520. ISSN 1549-6325.

[:0-3] A ^b Michail, Dimitrios (10. prosince 2007). Msgstr "Snížení shody mezi pořadím a maximální hmotností". Teoretická informatika. 389 (1): 125–132. doi:10.1016 / j.tcs.2007.08.004. ISSN 0304-3975.

[4] Kurt Mehlhorn a Dimitrios Michail (2005). „Problémy se sítí s nepolynomiálními váhami a aplikacemi“.

[5] Paluch, Katarzyna (22. května 2013). Maximalizované shody s hodnocením. Algoritmy a složitost. Přednášky z informatiky. 7878. Springer, Berlín, Heidelberg. 324–335. doi:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.

[1]

[2]

[3]

[4]

[5]