Maximální rozdělení podle hodnosti

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. ledna 2021; ověření vyžaduje 1 úpravu .

Přidělení maximálního pořadí ( RM) je pravidlem pro spravedlivé rozdělení nedělitelných položek .  Předpokládejme, že potřebujeme rozdělit několik položek mezi určitý počet lidí. Každý může seřadit položky od nejlepší po nejhorší. Pravidlo MP říká, že bychom měli dát co největšímu počtu lidí nejlepší položku (č. 1 na seznamu). Pak bychom měli dát co největšímu počtu lidí druhou nejdůležitější položku (č. 2 na seznamu) a tak dále.

Ve speciálním případě, kdy každá osoba musí obdržet jednu položku (například pokud jsou „předměty“ nějaké akce a každá akce musí být provedena jednou osobou), se problém nazývá maximální shoda v pořadí nebo chamtivá shoda .

Myšlenka je podobná jako u krájení dortu podle užitku , kde je cílem maximalizovat součet užitků všech účastníků. Pravidlo užitku však pracuje s kardinálními (množstevními) užitkovými funkcemi , zatímco pravidlo MP pracuje s ordinálními užitkovými funkcemi (hodnocení).

Definice

Existuje několik položek a několik agentů. Každý agent má lineární řazení položek. Agenti nemusí některé položky oceňovat. Pro každého agenta můžeme rozdělit položky do tříd ekvivalence , které obsahují položky stejné úrovně. Je-li například Alicin preferenční vztah x > y, z > w , znamená to, že Alicina nejlepší volba je x , což je lepší než všechny ostatní položky. Alice pak preferuje y a z , které v jejích očích mají stejnou hodnotu, ale nejsou tak cenné jako x . Na posledním místě má Alice w , kterou považuje za nejhorší ze všech položek.

Pro jakoukoli distribuci položek agentům zkonstruujeme její vektor hodnosti následovně. Prvek #1 ve vektoru se rovná celkovému počtu položek, které jsou pro vlastníky na prvním místě, prvek #2 se rovná celkovému počtu položek, které jsou pro vlastníky na druhém místě a tak dále.

Maximální hodnostní distribuce je distribuce, ve které je hodnostní vektor maximální (v lexikografickém pořadí ).

Příklad

Tři položky, x, y, a z, mají být rozděleny mezi tři agenty, jejichž pořadí je následující:

V distribuci ( x , y , z ) získá Alice první prvek ( x ), Bob dostane druhý prvek ( y ) a Carl třetí prvek ( z ). Vektor pořadí je pak (1,1,1).

V distribuci ( x , z , y ) dostanou Alice a Carl předměty na první místo, zatímco Bob dostane předmět, který umístí na 3. místo. Vektor pořadí je pak (2,0,1), který je lexikograficky větší než vektor (1,1,1) - dává více lidem možnost volby 1. místa.

Je snadné zkontrolovat, že žádná distribuce neposkytuje lexikograficky větší vektor hodnosti. Proto je rozdělení ( x , z , y ) v pořadí maximální. Podobně je rozdělení ( z , x , y ) rank-maximum - dává stejný rank vektor (2,0,1).

Algoritmy

MP párování poprvé studoval Robert Irving, který je nazval chamtivé párování . Navrhl algoritmus , který najde MP odpovídající v čase , kde n je počet agentů ac je maximální délka seznamu preferencí agenta [1] .

Později byl nalezen algoritmus, který běží v čase , kde m je celková délka všech seznamů preferencí (celkový počet hran v grafu) a C je maximální hodnost položky použité v MP párování (tj. maximální počet nenulových prvků v optimálním vektoru hodnosti) [2] .

Jiné řešení využívající přizpůsobení maximální hmotnosti dosahuje podobné doby běhu - [3] .

Možnosti

Úkol má několik možností.

1. Při shodě MP s maximální mohutností je cílem najít mezi všemi různými shodami MP shodu s maximálním počtem kombinací.

2. Při spravedlivém párování je cílem najít maximální párování mohutnosti, které používá minimální počet hran hodnosti r , pak minimální počet hran hodnosti r −1 atd.

Jak maximální velikost MP přizpůsobení, tak spravedlivé přizpůsobení lze nalézt snížením na maximální přizpůsobení hmotnosti [3] .

3. V problému kapacitního MR-matchingu má každý agent horní kapacitu, která určuje horní hranici celkového počtu položek, které mohou být převedeny na agenta. Každá položka má horní kvótu, která určuje horní limit počtu různých agentů, kterým může být položka přidělena. Problémem se zabývali Melhorn a Michail, kteří navrhli algoritmus s dobou běhu [4] . Existuje vylepšený algoritmus s dobou běhu , kde B je minimální součet kvót agentů a součtů kvót položek. Je založen na rozšíření Galai-Edmondsova rozkladu vícehranných párování [5] .

Viz také

Poznámky

  1. ↑ Irving, 2003 , str. Tr–2003–136.
  2. ↑ Irving, Kavitha a kol., 2006 , s. 602–610.
  3. ↑ 12 Michail , 2007 , str. 125–132.
  4. ↑ Mehlhorn, Michail, 2005 .
  5. ↑ Paluch, 2013 , str. 324–335.

Literatura