Qual è l'algoritmo di voto "rendere tutti felici"?

Question

Sto cercando un algoritmo di voto che raccolga i vincitori sulla base della combinazione di maggioranza dei voti e numero di voti.

esempio di vita reale:

La nostra azienda ha una barretta di cereali. Abbiamo spazio per 3 diversi cereali. Noi vogliamo consentire ai nostri dipendenti di votare su quali cereali vogliono.

Noi non vogliamo prendere rigorosamente i primi 3 vincitori in base alla popolarità perché ci può essere una minoranza di dipendenti che può mangiare solo 1 particolare di cereali (per qualsiasi motivo) e vorremmo dare loro assegno speciale possibile.

Dato il seguente esito del voto, ecco i risultati che ci piacerebbe che l'algoritmo ci fornisse.

Sto cercando un algoritmo che fa questo tipo di classifica. Se puoi almeno fornire il nome di quello che sto cercando, sarebbe un grande aiuto perché potrei cercarlo meglio. :)

Grazie!

Answer 1

Si consiglia di prendere in considerazione le generalizzazioni di Hall's marriage theorem e/o assignment problem.

L'idea di questo paradigmi è quello di creare un grafo bipartito in cui i nodi sono persone e cereali, con un bordo tra la persona p e cereali c se p votato per c.L'obiettivo è quello di selezionare 3 cereali tale che il grafico risultante dalla rimozione di tutti gli altri cereali è

1. collegato (ognuno mangiare almeno uno dei cereali selezionati), e

2. massimizza il minimo/medio grado di ogni persona (massimizza min/felicità avg)

Si potrebbe invece pensare a questo come un Maximum Coverage Problem. In questo caso, hai impostato C1,C2,...,Cm dove Ci è l'insieme di persone a cui piacciono i cereali i. Per voi esempio, prendendo i cereali e le persone nell'ordine indicato in tabella, si ha

C1 = {1,5} 
C2 = {2} 
C3 = {1,4,5} 
C4 = {3,5} 

Let n essere il numero di persone, in modo che Ci è un sottoinsieme di {1,2,...,n}. L'obiettivo è di trovare k set in modo tale che la cardinalità dell'unione sia massimizzata. Se esistono più soluzioni, scegli quella che minimizza la cardinalità delle intersezioni (riduce al minimo la quantità di dominio di una persona) o massimizza il numero di volte in cui l'elemento meno frequente viene ripetuto (massimizza la felicità della persona meno felice).

Per questo esempio, il più piccolo k per il quale sono coperti tutti gli elementi è k=3 e fornisce la soluzione univoca C2,C3,C4.

Tuttavia, se lo si guarda, si ha un problema con NP, ma esistono degli algoritmi noti per risolverli (controllare gli articoli di wikipedia per i riferimenti).

Answer 2

Non esiste un sistema di votazione perfetto - vedere http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem. Ci sono stati vari tentativi per superare questo problema piegando le regole, tra cui http://en.wikipedia.org/wiki/Range_voting.

Un'idea vicina al voto a distanza è di dare a tutti 12 voti e consentire loro di distribuirli come desiderano. Osservando il tuo esempio, se ritieni che le persone che hanno più scelte distribuiscano i loro 12 voti uguali - 12x1 o 6x2 o 4x3 o 3x4 - allora penso che otterrai il risultato desiderato, con Lucky Charms che ottiene un totale di 10 voti e tutto il resto ottenere più di questo

Answer 3

Se il numero di cereali è di piccole dimensioni, è possibile visualizzare il problema come un problema sottoinsieme-copertina e la forza bruta buona strada per trovare quale configurazione da maggior "felicità"

var max_happyness = -INF 
for every subset {c1, c2, c3} of C: 
    max_hapyness = max(max_happyness, happyness(i1,i2,i3)) 

Hai ancora il problema di definire comunque una funzione di felicità adatta. Ad esempio, puoi scegliere una funzione happyness che come prima priorità calcola il numero di persone che riescono a mangiare qualsiasi cibo. Poi come seconda priorità il numero di persone a cui piacciono due dei cereali, poi quelli a cui piacciono i tre cereali e così via.

Pro: Se è possibile definire una funzione happyness, questo garantisce il miglior risultato garantito.

Contro: Devi essere in grado di definire una funzione happyness.