Il gioco delle coppie (omosessuali)
In questo articolo https://mizar.unive.it/licalzi/GiocoCoppie.pdf viene esposto un gioco di accoppiamenti matrimoniali tra uomini e donne dove ognuno esprime una preferenza ordinando l'altro insieme dal più preferibile al meno preferibile.
Viene mostrato che esiste sempre almeno un sistema di accoppiappiamenti stabile (in equilibrio) dove non esiste alcuna nuova coppia dove entrambi i membri della nuova coppia stanno meglio rispetto a come stanno nel sistema di accoppiamenti in esame.
Mi sono chiesto che succede se si trasporta questo gioco in ambito omosessuale dove in pratica tutti si possono accoppiare con tutti e dove ognuno elenca gli altri (escluso se stesso) in ordine di preferenza e mi sono accorto che già a partire da gruppi di pochi individui ($4$) si possono creare modelli dove non esistono sistemi di accoppiamento stabili.
Ho modificato leggermente il gioco perché in questo caso non sapevo come far comportare le persone che rimanevano senza compagno e quindi ho imposto che il numero di individui sia pari e ho eliminato la regola dell'* imponendo che ognuno esprima una qualche preferenza su tutti gli altri.
Ad esempio se abbiamo un insieme $D = {A, B, C, D}$ di $4$ individui e le loro preferenze sono...
$A: D>C>B$
$B: D>A>C$
$C: A>D>B$
$D: C>A>B$
Non esiste alcun abbinamento stabile.
Infatti considerando...
${{A, B}, {C, D}}$ - se si forma la coppia ${A, C}$ esiste una coppia dove entrambi (sia $A$ che $C$) stanno meglio rispetto a come stavano in questo sistema di accoppiamenti perché $A$ preferisce $C$ rispetto a $B$ e $C$ preferisce $A$ rispetto a $D$.
${{A, C}, {B, D}}$ - se si forma la coppia ${A, D}$ esiste una coppia dove entrambi stanno meglio.
${{A, D}, {B, C}}$ - se si forma la coppia ${C, D}$ esiste una coppia dove entrambi stanno meglio.
Abbiamo esaurito i casi possibili (intuitivamente tutte le partizioni di $D$ a due a due) e nessuno di questi sistemi di accoppiamenti è stabile.
D'altra parte si riescono a fare anche esempi con ordini di preferenze diversi dove gli abbinamenti stabili esistono. Ad esempio sempre su $D$ se
$A: B>D>C$
$B: A>C>D$
$C: B>D>A$
$D: C>A>B$
il sistema di accoppiamenti ${{A, B},{C, D}}$ è stabile.
La cosa che chiedo è questa: vale sempre quando il numero di individui è $>= 4$?
Insomma dati $N$ individui in numero pari per ($N>= 4$) esiste sempre un'assegnazione di preferenze che rende instabile ogni sistema di accoppiamenti?
Dato un dominio di individui pari, esiste un modo relativamente semplice per determinare nel caso "omosessuale" che ho impostato se un dato sistema di preferenze ammette almeno un sistema di accoppiamenti stabile?
Spero di essere riuscito a spiegarmi.
Viene mostrato che esiste sempre almeno un sistema di accoppiappiamenti stabile (in equilibrio) dove non esiste alcuna nuova coppia dove entrambi i membri della nuova coppia stanno meglio rispetto a come stanno nel sistema di accoppiamenti in esame.
Mi sono chiesto che succede se si trasporta questo gioco in ambito omosessuale dove in pratica tutti si possono accoppiare con tutti e dove ognuno elenca gli altri (escluso se stesso) in ordine di preferenza e mi sono accorto che già a partire da gruppi di pochi individui ($4$) si possono creare modelli dove non esistono sistemi di accoppiamento stabili.
Ho modificato leggermente il gioco perché in questo caso non sapevo come far comportare le persone che rimanevano senza compagno e quindi ho imposto che il numero di individui sia pari e ho eliminato la regola dell'* imponendo che ognuno esprima una qualche preferenza su tutti gli altri.
Ad esempio se abbiamo un insieme $D = {A, B, C, D}$ di $4$ individui e le loro preferenze sono...
$A: D>C>B$
$B: D>A>C$
$C: A>D>B$
$D: C>A>B$
Non esiste alcun abbinamento stabile.
Infatti considerando...
${{A, B}, {C, D}}$ - se si forma la coppia ${A, C}$ esiste una coppia dove entrambi (sia $A$ che $C$) stanno meglio rispetto a come stavano in questo sistema di accoppiamenti perché $A$ preferisce $C$ rispetto a $B$ e $C$ preferisce $A$ rispetto a $D$.
${{A, C}, {B, D}}$ - se si forma la coppia ${A, D}$ esiste una coppia dove entrambi stanno meglio.
${{A, D}, {B, C}}$ - se si forma la coppia ${C, D}$ esiste una coppia dove entrambi stanno meglio.
Abbiamo esaurito i casi possibili (intuitivamente tutte le partizioni di $D$ a due a due) e nessuno di questi sistemi di accoppiamenti è stabile.
D'altra parte si riescono a fare anche esempi con ordini di preferenze diversi dove gli abbinamenti stabili esistono. Ad esempio sempre su $D$ se
$A: B>D>C$
$B: A>C>D$
$C: B>D>A$
$D: C>A>B$
il sistema di accoppiamenti ${{A, B},{C, D}}$ è stabile.
La cosa che chiedo è questa: vale sempre quando il numero di individui è $>= 4$?
Insomma dati $N$ individui in numero pari per ($N>= 4$) esiste sempre un'assegnazione di preferenze che rende instabile ogni sistema di accoppiamenti?
Dato un dominio di individui pari, esiste un modo relativamente semplice per determinare nel caso "omosessuale" che ho impostato se un dato sistema di preferenze ammette almeno un sistema di accoppiamenti stabile?
Spero di essere riuscito a spiegarmi.
Risposte
Ho risposto alla prima domanda in modo affermativo, era facile, sono un idiota.
Dati ${A_1, ..., A_n}$ individui in numero pari, scegliamo un individuo, $A_n$ ad esempio, e piazziamolo in fondo alle preferenze di tutti gli altri. Inoltre facciamo in modo che esiste sempre un individuo preferito diverso tra gli ${A_1, ..., A_(n-1)}$... Così per esempio...
$A_1: A_(2)>... > A_n$
$A_2: A_(3)> ... > A_n$
...
$A_(n-1):A_1> ... > A_n$
$A_n$: ...
Le preferenze di $A_n$ sono ininfluenti, si possono scegliere a caso.
In ogni partizione qualcuno che sta con $A_n$ dovrà pur esserci, ma sicuramente preferirà qualsiasi altro dei restanti rispetto ad $A_n$ dato che questo è il meno preferibile, d'altra parte chi sta con $A_n$ dovrà risultare più preferibile da qualcuno dei restanti rispetto all'individuo con cui è accoppiato questo qualcuno.
Così nella partizione dove $A_i$ sta con $A_n$ ( ${A_i, A_n}$), una coppia che rende instabile questa partizione è ${A_(i-1), A_i}$ se $i != 1$, ${A_1, A_(n-1)}$ altrimenti.
Queste condizioni sulle preferenze sono sufficienti a rendere instabile ogni sistema di accoppiamenti con $n >= 4$ ma non so se sono anche necessarie affinché questo avvenga.
Dati ${A_1, ..., A_n}$ individui in numero pari, scegliamo un individuo, $A_n$ ad esempio, e piazziamolo in fondo alle preferenze di tutti gli altri. Inoltre facciamo in modo che esiste sempre un individuo preferito diverso tra gli ${A_1, ..., A_(n-1)}$... Così per esempio...
$A_1: A_(2)>... > A_n$
$A_2: A_(3)> ... > A_n$
...
$A_(n-1):A_1> ... > A_n$
$A_n$: ...
Le preferenze di $A_n$ sono ininfluenti, si possono scegliere a caso.
In ogni partizione qualcuno che sta con $A_n$ dovrà pur esserci, ma sicuramente preferirà qualsiasi altro dei restanti rispetto ad $A_n$ dato che questo è il meno preferibile, d'altra parte chi sta con $A_n$ dovrà risultare più preferibile da qualcuno dei restanti rispetto all'individuo con cui è accoppiato questo qualcuno.
Così nella partizione dove $A_i$ sta con $A_n$ ( ${A_i, A_n}$), una coppia che rende instabile questa partizione è ${A_(i-1), A_i}$ se $i != 1$, ${A_1, A_(n-1)}$ altrimenti.
Queste condizioni sulle preferenze sono sufficienti a rendere instabile ogni sistema di accoppiamenti con $n >= 4$ ma non so se sono anche necessarie affinché questo avvenga.
Non conosco la teoria a riguardo, ma ho trovato la pagina wiki del problema: https://en.wikipedia.org/wiki/Stable_roommates_problem (in inglese).
"vict85":
Non conosco la teoria a riguardo, ma ho trovato la pagina wiki del problema: https://en.wikipedia.org/wiki/Stable_roommates_problem (in inglese).
Grazie!
Per la verità neanche io conosco bene queste teorie, mi ero "inventato" (dico così perché non avevo letto nulla a riguardo) questo problema immaginando che delle persone stipulavano affari simmetrici prima ancora di leggere quello relativo alle coppie, che ho cercato poi.
Ma ero partito dall'idea di vedere che poteva succedere quando le persone cercano un partner ed hanno delle preferenze e pensavo che era più semplice trattare il caso dove tutti si accoppiano con tutti, io al posto della relazione di ordine avevo messo un numero progressivo di preferenza che scattava solo di una unità e partiva da $0$, formalmente porta agli stessi risultati.
All'inizio ero convinto erroneamente che esistesse sempre l'abbinamento stabile (che io chiamavo di equilibrio), poi ho trovato il controesempio e poi cercando in rete ho visto che già altri erano arrivati alle stesse definizioni, però non ero riuscito a cercare bene, infatti non ero riuscito ad imbattermi nella pagina che hai postato.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo