Rank-maximal tilldelning

Rank-maximal (RM) allokering är en regel för rättvis uppdelning av odelbara poster. Anta att vi måste fördela vissa föremål mellan människor. Varje person kan rangordna objekten från bäst till sämst. RM-regeln säger att vi måste ge så många som möjligt sitt bästa (#1) föremål. Med förbehåll för det måste vi ge så många människor som möjligt deras näst bästa (#2) föremål, och så vidare.

I det speciella fallet där varje person ska få ett enda föremål (till exempel när "artiklarna" är uppgifter och varje uppgift måste utföras av en enda person), kallas problemet rang-maximal matchning eller girig matchning .

Idén liknar den med utilitaristisk kakskärning , där målet är att maximera summan av nyttigheter för alla deltagare. Den utilitaristiska regeln fungerar dock med kardinala (numeriska) hjälpfunktioner , medan RM-regeln fungerar med ordinala verktyg (rankningar).

Definition

Det finns flera föremål och flera agenter. Varje agent har en totalorder på föremålen. Agenter kan vara likgiltiga mellan vissa objekt; för varje agent kan vi dela upp objekten till ekvivalensklasser som innehåller objekt av samma rang. Till exempel, om Alices preferens-relation är x > y,z > w , betyder det att Alices första val är x, vilket är bättre för henne än alla andra objekt; Alices 2:a val är y och z, som är lika bra i hennes ögon men inte lika bra som x; och Alices tredje val är w, som hon anser är värre än alla andra föremål.

För varje allokering av poster till agenterna konstruerar vi dess rangvektor enligt följande. Element #1 i vektorn är det totala antalet föremål som är förstahandsval för sina ägare; Element #2 är det totala antalet föremål som är andrahandsval för sina ägare; och så vidare.

En rank-maximal allokering är en där rank-vektorn är maximal, i lexikografisk ordning.

Exempel

Tre objekt, xy och z, måste delas upp på tre agenter vars rankning är:

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

I tilldelningen ( x , y , z ) får Alice sitt 1:a val ( x ), Bob får sitt 2:a val ( y ), och Carl får sitt 3:e val ( z ). Rangvektorn är alltså (1,1,1).

I tilldelningen ( x , z , y ) får både Alice och Carl sitt 1:a val och Bob får sitt 3:e val. Rang-vektorn är alltså (2,0,1), vilket är lexikografiskt högre än (1,1,1) – det ger fler människor sitt 1:a val.

Det är lätt att kontrollera att ingen allokering ger en lexikografiskt högre rangvektor. Följaktligen är allokeringen ( x , z , y ) rangmaximal. På liknande sätt är allokeringen ( z , x , y ) rank-maximal – den ger samma rank-vektor (2,0,1).

Algoritmer

RM-matchningar studerades först av Robert Irving, som kallade dem giriga matchningar . Han presenterade en algoritm som hittar en RM-matchning i tid ${\displaystyle O(n^{2}c^{3})} ,$ där n är antalet agenter och c är den största längden av en preferenslista för en agent.

Senare hittades en förbättrad algoritm, som körs i tiden ${\displaystyle O(m\cdot \min(n,C{\sqrt {n}}))} ,$ där m är den totala längden av alla preferenslistor (totalt antal kanter i grafen), och C är den maximala rangordningen för ett objekt som används i en RM-matchning (dvs. det maximala antalet element som inte är noll i en optimal rangvektor ). Algoritmen reducerar problemet till maximal kardinalitetsmatchning . Intuitivt vill vi först hitta en maximal kardinalitetsmatchning med endast kanter av rang 1; utöka sedan denna matchning till en maximal kardnialitetsmatchning med endast kanter av rang 1 och 2; utöka sedan denna matchning till en maximal kardnialitetsmatchning genom att endast använda kanter av rang 1 2 och 3; och så vidare. Problemet är att om vi väljer "fel" matchning av maximal kardinalitet för rang 1, så kan vi missa den optimala matchningen för rang 2. Algoritmen för löser detta problem med hjälp av Dulmage–Mendelsohn-nedbrytningen , som är en nedbrytning som använder en maximal kardinalitetsmatchning, men beror inte på vilken matchning som väljs (nedbrytningen är densamma för varje vald matchning med maximal kardinalitet). Det fungerar på följande sätt.

Låt G ₁ vara subgrafen av G som endast innehåller kanter av rang 1 (den högsta rangen).
Hitta en maximal kardinalitetsmatchning i G ₁ och använd den för att hitta nedbrytningen av G ₁ till E ₁ , O ₁ och U ₁ .
En egenskap hos nedbrytningen är att varje maximal kardinalitetsmatchning i G ₁ mättar alla hörn i O ₁ och U ₁ . Därför, i en rang-maximal-matchning, ligger alla hörn i O ₁ och U ₁ intill en kant av rank 1. Så vi kan ta bort alla kanter med rank 2 eller högre intill någon av dessa hörn från grafen.
En annan egenskap hos sönderdelningen är att varje maximal kardinalitetsmatchning i G ₁ endast innehåller E ₁ -O ₁ och U ₁ - U ₁ kanter. Därför kan vi ta bort alla andra kanter (O ₁ -O ₁ och O ₁ -U ₁ kanter) från grafen.
Lägg till G ₁ alla kanter med näst högsta rang. Om det inte finns några sådana kanter, sluta. Annars, gå tillbaka till steg 2.

En annan lösning, med maximiviktsmatchningar , uppnår en liknande körtid: $O(m\cdot \min(n+C,C{\sqrt {n}}))$ .

Varianter

Problemet har flera varianter.

1. I RM-matchning med maximal kardinalitet är målet att bland alla olika RM-matchningar hitta den med maximalt antal matchningar.

2. Vid rättvis matchning är målet att hitta en maximal kardinalitetsmatchning så att det minsta antalet kanter av rang r används, givet att - det minsta antalet kanter av rang r −1 används, och så vidare.

Både maximal kardinalitet RM-matchning och rättvis matchning kan hittas genom reduktion till maximal viktmatchning.

3. I det kapaciterade RM-matchningsproblemet har varje agent en övre kapacitet som anger en övre gräns för det totala antalet föremål han ska få. Varje artikel har en övre kvot som anger en övre gräns för antalet olika agenter som den kan tilldelas. Den studerades först av Melhorn och Michail, som gav en algoritm med körtid $O(Cnm\log(n^{2} /m)\log(n))$ . Det finns en förbättrad algoritm med körtid ${\displaystyle O(m\cdot \min(B,C{\sqrt {B}}))} ,$ där B är minimum av summan av kvoterna för agenterna och summan av kvoterna för föremålen. Den är baserad på en utvidgning av Gallai-Edmonds-nedbrytningen till flerkantsmatchningar.

Se även