Problem med stallrumskamrater

Inom matematik , ekonomi och datavetenskap , särskilt inom områdena kombinatorik , spelteori och algoritmer , är stallrumskamratproblemet ( SRP ) problemet med att hitta en stabil matchning för en uppsättning av jämn storlek. En matchning är en uppdelning av uppsättningen i osammanhängande par ("rumskamrater"). Matchningen är stabil om det inte finns två element som inte är rumskamrater och som båda föredrar varandra framför sin rumskamrat under matchningen. Detta skiljer sig från problemet med stalläktenskap genom att problemet med stallrumskamrater tillåter matchningar mellan vilka två element som helst, inte bara mellan klasser av "män" och "kvinnor".

Det brukar sägas som:

I ett givet fall av problem med stallrumskamrater (SRP) rangordnar var och en av 2n deltagare de andra i strikt preferensordning. En matchning är en uppsättning av n osammanhängande par av deltagare. En matchande M i en instans av SRP är stabil om det inte finns två deltagare x och y , som var och en föredrar den andra framför sin partner i M . Ett sådant par sägs blockera M , eller vara ett blockerande par med avseende på M .

Lösning

Till skillnad från problemet med stabila äktenskap kan en stabil matchning inte existera för vissa uppsättningar av deltagare och deras preferenser. För ett minimalt exempel på ett stabilt par som inte existerar, överväg 4 personer A , B , C och D , vars rankningar är:

A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)

I den här rankningen är var och en av A, B och C den person som är mest att föredra för någon. I vilken lösning som helst måste en av A, B eller C paras ihop med D och de andra två med varandra (till exempel AD och BC), men för alla som samarbetar med D kommer en annan medlem att ha rankat dem högst, och D:s partner kommer i sin tur att föredra denna andra medlem framför D. I det här exemplet är AC en mer gynnsam parning än AD, men den nödvändiga återstående parningen av BD väcker då samma problem, vilket illustrerar frånvaron av en stabil matchning för dessa deltagare och deras preferenser.

Algoritm

En effektiv algoritm gavs i ( Irving 1985 ). Algoritmen kommer att avgöra, för alla fall av problemet, om en stabil matchning existerar, och i så fall kommer den att hitta en sådan matchning. Irvings algoritm har O( n2 )-komplexitet , förutsatt att lämpliga datastrukturer används för att implementera nödvändig manipulation av preferenslistorna och identifiering av rotationer.

Algoritmen består av två faser. I fas 1 friar deltagarna till varandra, på ett sätt som liknar Gale-Shapley-algoritmen för problemet med stabila äktenskap . Varje deltagare ordnar de andra medlemmarna efter preferens, vilket resulterar i en preferenslista – en ordnad uppsättning av de andra deltagarna. Deltagarna föreslår sedan till varje person på sin lista, för att fortsätta till nästa person om och när deras nuvarande förslag avvisas. En deltagare kommer att avslå ett förslag om de redan har ett förslag från någon de föredrar. En deltagare kommer också att avslå ett tidigare godkänt förslag om de senare får ett förslag som de föredrar. I det här fallet kommer den avvisade deltagaren att föreslå nästa person på sin lista, och fortsätta tills ett förslag accepteras igen. Om någon deltagare så småningom avvisas av alla andra deltagare, indikerar detta att ingen stabil matchning är möjlig. Annars kommer fas 1 att avslutas med att varje person har ett förslag från en av de andra.

Betrakta två deltagare, q och p . Om q innehåller ett förslag från p , så tar vi bort från q :s lista alla deltagare x efter p , och symmetriskt, för varje borttagen deltagare x , tar vi bort q från x : s lista, så att q är först i p : s lista ; och p , sist i q ' s, eftersom q och valfritt x inte kan vara partner i någon stabil matchning. Den resulterande reducerade uppsättningen preferenslistor tillsammans kallas Fas 1-tabellen. I den här tabellen, om någon reducerad lista är tom, så finns det ingen stabil matchning. Annars är Fas 1-bordet ett stabilt bord . En stabil tabell, per definition, är uppsättningen preferenslistor från den ursprungliga tabellen efter att medlemmar har tagits bort från en eller flera av listorna, och följande tre villkor är uppfyllda (där reducerad lista betyder en lista i den stabila tabellen):



(i) p är först på qs reducerade lista om och endast om q är sist på p ' s (ii) p är inte på qs reducerade lista om och endast om q inte finns på p ' s om och endast om q föredrar den sista personen på sin lista framför p ; eller p , den sista personen på sin lista till q (iii) ingen reducerad lista är tom

Stabila tabeller har flera viktiga egenskaper, som används för att motivera resten av proceduren:

  1. Varje stabil tabell måste vara en undertabell av fas 1-tabellen, där undertabell är en tabell där preferenslistorna för undertabellen är de för supertabellen med några individer borttagna från varandras listor.
  2. I alla stabila tabeller, om varje reducerad lista innehåller exakt en individ, då parning av varje individ med den enskilda personen på deras lista ger en stabil matchning.
  3. Om probleminstansen för stabila rumskamrater har en stabil matchning, så finns det en stabil matchning i någon av de stabila tabellerna.
  4. Vilken stabil deltabell som helst i ett stabilt bord, och i synnerhet vilken stabil deltabell som helst som specificerar en stabil matchning enligt 2, kan erhållas genom en sekvens av rotationseliminationer på det stabila bordet.

Dessa rotationselimineringar omfattar Fas 2 av Irvings algoritm.

Med 2, om varje reducerad lista i Fas 1-tabellen innehåller exakt en individ, ger detta en matchning.

000 Annars går algoritmen in i fas 2. En rotation i en stabil tabell T definieras som en sekvens ( x , y ), ( x 1 , y 1 ), ..., ( x k-1 , y k-1 ) t.ex. att x i är distinkta, y i är först på x i :s reducerade lista (eller x i är sist på y i :s reducerade lista) och y i+1 är tvåa på x i :s reducerade lista, för i = 0, ..., k-1 där indexen tas modulo k. Det följer att i varje stabil tabell med en reducerad lista som innehåller minst två individer, finns en sådan rotation alltid. För att hitta det, börja med ett sådant p som innehåller minst två individer i deras reducerade lista, och definiera rekursivt q i+1 som den andra på pi : s lista och p i+1 som den sista på q i+1 s lista, tills denna sekvens upprepar något p j , vid vilken punkt en rotation hittas: det är sekvensen av par som börjar vid den första förekomsten av ( p j , q j ) och slutar vid paret före den sista förekomsten. Sekvensen av p i fram till p j kallas svansen av rotationen. Det faktum att det är en stabil tabell där denna sökning sker garanterar att varje p i har minst två individer på sin lista.

För att eliminera rotationen avvisar y i x i så att x i föreslår y i+1 , för varje i . För att återställa de stabila tabellegenskaperna (i) och (ii), för varje i , tas alla efterföljare till x i-1 bort från y i :s lista och y i tas bort från deras listor. Om en reducerad lista blir tom under dessa borttagningar finns det ingen stabil matchning. Annars är den nya tabellen återigen en stabil tabell, och antingen anger den redan en matchning eftersom varje lista innehåller exakt en individ eller så återstår en annan rotation att hitta och eliminera, så steget upprepas.

Fas 2 av algoritmen kan nu sammanfattas enligt följande:

    
  
         
       
          
              
             
                              
 T  =  Fas  1-  tabell  ;  while  (  sant  )  {  identifiera  en  rotation  r  i  T  ;  eliminera  r  från  T  ;  om  någon  lista  i  T  blir  tom  ,  returnera  null  ;  (  ingen  stabil  matchning  kan  existera  )  annars  om  (  varje  reducerad  lista  i  T  har  storlek  1  )  returnerar  den  matchande  M  =  {{  x  ,  y  }  |  x  och  y  finns  på  varandras  listor  i  T  }  ;  _  _  (  detta  är  en  stabil  matchning  )  }

För att uppnå en O( n 2 ) löptid, en rankningsmatris vars post på rad i och kolumn j är positionen för den j: e individen i den i :e listan; detta tar O( n 2 ) tid. Med rankningsmatrisen kan man kontrollera om en individ föredrar en framför en annan göras i konstant tid genom att jämföra deras rankningar i matrisen. Istället för att uttryckligen ta bort element från preferenslistorna, bibehålls dessutom indexen för första, andra och sista på varje individs reducerade lista. Den första individen som är oöverträffad , dvs har minst två i sina reducerade listor, bibehålls också. Sedan, i fas 2, lagras sekvensen av pi " genomkörd " för att hitta en rotation i en lista, och en array används för att markera individer som besökta, som i en standard genomgång av en djup-först sökgraf . Efter elimineringen av en rotation fortsätter vi att endast lagra dess svans, om någon, i listan och som besökt i arrayen, och startar sökningen efter nästa rotation vid den sista individen på svansen, och annars vid nästa omatchade individuell om det inte finns någon svans. Detta minskar upprepad traversering av svansen, eftersom den i stort sett är opåverkad av elimineringen av rotationen.

Exempel

Följande är preferenslistorna för en Stall Roommate-instans som involverar 6 deltagare: 1, 2, 3, 4, 5, 6.

     
     
     
     
     
      1 : 3 4 2 6 5 2 : 6 5 4 1 3 3 : 2 4 5 1 6 4 : 5 2 3 6 1 5 : 3 1 2 4 6 6 : 5 1 3 4 2

En möjlig utförande av Fas 1 består av följande sekvens av förslag och avslag, där → representerar föreslår till och × representerar avslag .





 

 
1 → 3 2 → 6 3 → 2 4 → 5 5 → 3; 3 x 1 1 → 4 6 → 5; 5 × 6 6 → 1

Så fas 1 avslutas med följande reducerade preferenslistor: (vi stryker till exempel ut 5 för 1: eftersom 1: får minst 6)

      
     
      
     
      
        1 : 3 4 2 6 5 2 : 6 5 4 1 3 3 : 2 4 5 1 6 4 : 5 2 3 6 1 5 : 3 1 2 4 6 6 : 5 1 3 4 2

identifieras först rotationen r 1 = (1,4), (3,2). Detta beror på att 2 är 1:s andra favorit och 4 är den andra favoriten av 3. Att eliminera r 1 ger:

       
     
       
      
      
         1 : 3 4 2 6 5 2 : 6 5 4 1 3 3 : 2 4 5 1 6 4 : 5 2 3 6 1 5 : 3 1 2 4 6 6 : 5 1 3 4 2

identifieras rotationen r 2 = (1,2), (2,6), (4,5), och dess eliminering ger:

        
       
       
       
       
         1 : 3 4 2 6 5 2 : 6 5 4 1 3 3 : 2 4 5 1 6 4 : 5 2 3 6 1 5 : 3 1 2 4 6 6 : 5 1 3 4 2

Därför är 1 och 6 matchade. Slutligen identifieras rotationen r 3 = (2,5), (3,4), och dess eliminering ger:

        
        
        
        
        
         1 : 3 4 2 6 5 2 : 6 5 4 1 3 3 : 2 4 5 1 6 4 : 5 2 3 6 1 5 : 3 1 2 4 6 6 : 5 1 3 4 2

Därför är matchningen {1, 6}, {2,4}, {3, 5} stabil.

Implementering i mjukvarupaket

  • Python : En implementering av Irvings algoritm är tillgänglig som en del av det matchande biblioteket.
  • Java : En begränsningsprogrammeringsmodell för att hitta alla stabila matchningar i rumskamratproblemet med ofullständiga listor är tillgänglig under CRAPL-licensen.
  • R : Samma begränsningsprogrammeringsmodell är också tillgänglig som en del av R matchingMarkets- paketet.
  • API : MatchingTools API tillhandahåller ett gratis applikationsprogrammeringsgränssnitt för algoritmen.
  • Webbapplikation : Webbplatsen "Dyad Finder" tillhandahåller en gratis, webbaserad implementering av algoritmen, inklusive källkod för webbplatsen och lösare skriven i JavaScript .
  • Matlab : Algoritmen är implementerad i funktionen assignStableRoommates som är en del av United States Naval Research Laboratorys kostnadsfria Tracker Component Library.

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Stable_roommates_problem&oldid=1064590028 "