A szobatárs -probléma a kooperatív játékok ( játékelmélet és kombinatorika ) matematikai problémája a stabil (stabil) párosítás megtalálásában , amely mellett egyetlen pár sem preferálná egymást jobban, mint a jelenlegi eloszlásban. A probléma abban különbözik a házaspárok problémájától, hogy nincs két nemre oszlás: bárki mással együtt élhet (feltételezzük, hogy a diákok egy hostelben laknak ketten egy szobában).
A feladatot általában a következőképpen fogalmazzák meg:
2n résztvevő van , és mindegyik szigorúan preferálja a többi résztvevőt (a többi résztvevőt csökkenő preferencia szerint rendezi); vegye figyelembe, hogy két résztvevőnek nem lehet ugyanaz a preferenciája: legalábbis különböznek egymástól. Meg kell találnunk egy n párból álló halmazt a legjobb egyezéssel: az M egyezés akkor stabil, ha két különböző párból származó résztvevő sem preferálja egymást a valódi szomszédaival szemben.A házaspárok problémájával ellentétben a szobatársak problémájára általában nincs megoldás. Tegyük fel például, hogy négy személy – A, B, C és D – rendelkezik preferenciákkal:
A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C)Minden megoldásban az A, B vagy C egyikét a D párhoz kell rendelni, a maradék kettő pedig egy második párt alkot (például AD és BC). De D partner és valaki a második párból egymást preferálják. Példánkban ez a pár AC lesz.
Egy hatékony megoldási algoritmust Irving javasolt 1985-ben [1] . Az algoritmus meghatározza, hogy létezik-e megoldás a problémára, és ha igen, akkor megtalálja azt.
Az Irving-algoritmus O( n 2 ) bonyolultságú. Megfelelő adatstruktúrákat határoz meg a preferencialisták és permutációk manipulálásához (lásd alább).
Az algoritmus 2 szakaszból áll. Az első szakaszban a résztvevők javaslatot tesznek egymásnak, nagyjából ugyanúgy, mint a házassági probléma Gale-Shapley algoritmusában . A résztvevők azt javasolják, hogy a preferencialistájukon szereplő személyeket sorrendben párosítsák, és a listán a következő személyre lépnek, ha megtagadják a párosítást. A résztvevő megtagadja a párosítást, ha már van ajánlata az általa jobban kedvelt személytől. Ebben a szakaszban egy résztvevőt az összes többi résztvevő elutasíthat, jelezve, hogy nincs stabil megoldás. Ellenkező esetben az 1. szakasz azzal ér véget, hogy minden résztvevő ajánlatot kap valamelyik résztvevőtől. Ez a helyzet a ( p , q ) alakú rendezett párok S halmazaként ábrázolható , ahol q -nak p ajánlata van , és azt mondjuk, hogy q p aktuális kedvence . Ha ez a halmaz megoldás, azaz S-beli tetszőleges ( q , p ) esetén ( p , q ) benne van S -ben is , akkor az algoritmus véget ér, és ez a megoldás stabil.
Ellenkező esetben a 2. szakaszba lépünk, ahol az S halmazt szekvenciálisan megváltoztatjuk az úgynevezett permutációk segítségével. Legyen ( p , q ) S -hez tartozik , de ( q , p ) nem. Minden egyes ilyen p -hez határozza meg az aktuális második kedvencét , amely a p preferencialistáján q után a következő résztvevő, aki elfogadhatja p ajánlatát . A permutáció S - ben egy sorozat ( p 0 , q 0 ), ( p 1 , q 1 ),. . ., ( p k -1 , q k -1 ) úgy, hogy ( p i , q i ) S -ben legyen bármely i esetén, és q i +1 a p i résztvevő második kedvence (itt i + 1 modulo k ). Ha egy ilyen permutáció ( p 0 , q 0 ), . . . , ( p 2 k , q 2 k ) páratlan hosszúságú, megtaláltuk az úgynevezett páratlan halmazt , ami azt mutatja, hogy nincs stabil megfeleltetés. Ellenkező esetben a ( p i , q i ) párokat ( p i , q i +1 ) -re cseréljük ( ahol i + 1 modulo k ) .
Az algoritmus 2. szakasza a következőképpen ábrázolható:
S = az 1. fázis kimenete ; while ( igaz ) { azonosítani egy r forgást S -ben ; if ( r egy páratlan fél ) return null ; _ ( nincs stabil egyezés ) egyébként alkalmazza az r -t S - re ; if ( S egy egyező ) return S ; _ ( garantáltan stabil ) _ _ _Adott egy preferencialista hat résztvevő számára , p 1 , p 2 , p 3 , p 4 , p 5 , p 6 .
p 1 : p 3 p 4 p 2 p 6 p 5 p 2 : p 6 p 5 p 4 p 1 p 3 p 3 : p 2 p 4 p 5 p 1 p 6 p 4 : p 5 p 2 p 3 p 6 p 1 p 5 : p 3 p 1 p 2 p 4 p 6 p 6 : p 5 p 1 p 3 p 4 p 2
Egy szakasz lehetséges végrehajtása a következő ajánlatokból és elutasításokból áll, ahol a → egy ajánlatot , × pedig egy elutasítást jelöl .
p 1 → p 3
p 2 → p 6
p 3 → p 2
p 4 → p 5
p 5 → p 3 ; p 3 × p 1 p 1 → p 4 p 6 → p 5 ; p 5 × p 6 p 6 → p 1
Így az 1. szakasz az S = {( p 1 , p 4 ), ( p 2 , p 6 ), ( p 3 , p 2 ), ( p 4 , p 5 ), ( p 5 , p 3 ) halmazzal végződik, ( 6. o . , 1. o . )}.
A 2. lépésben megtaláljuk az r 1 = ( p 1 , p 4 ), ( p 3 , p 2 ) permutációt. Ez abból következik, hogy p 2 a p 1 második kedvence , p 4 pedig p 3 második kedvence . Az r 1 segítségével új halmazt kaphat S = {( p 1 , p 2 ), ( p 2 , p 6 ), ( p 3 , p 4 ), ( p 4 , p 5 ), ( p 5 , p 3 ) , ( 6. o . , 1. o . )}. Most megtaláltuk az r 2 = ( p 1 , p 2 ), ( p 2 , p 6 ), ( p 4 , p 5 ) permutációt, és az S = {( p 1 , p 6 ), ( p 2 , p 5 ), ( p 3 , p 4 ), ( p 4 , p 2 ), ( p 5 , p 3 ), ( p 6 , p 1 )}. Végül az r 3 = ( p 2 , p 5 ), ( p 3 , p 4 ) permutálásával S = {( p 1 , p 6 ), ( p 2 , p 4 ), ( p 3 , p 5 ), ( p 4 , p 2 ), ( p 5 , p 3 ), ( p 6 , p 1 )}. Az utolsó meccs a stabil megoldás.