NP-Hard? Complessità algoritmica del rilevamento della collusione nel poker online?

Question

Qual è il modo migliore per descrivere la complessità algoritmica del rilevamento di collusione per un sito di poker online da dieci milioni di giocatori?

assuma (non credo che queste ipotesi fanno molta differenza quindi sentitevi liberi di ignorarli, ma tanto per chiarire):

• che il sito ha 10.000.000 utenti registrati.
• Che questi giocatori abbiano giocato un totale di 5 miliardi di mani.
• Che l'unica informazione che ti viene data è il "database della cronologia delle mani" per il sito, contenente tutte le carte giocatore e le azioni di scommessa per ogni mano.
• In altre parole, NON è possibile utilizzare scorciatoie come l'esame di indirizzi IP, la ricerca di pattern di profitto/profitto insoliti e così via.
• Supponiamo che ti venga assegnata una funzione che, quando passa un gruppo di esattamente N (dove N è tra 2 e 10) giocatori, restituisce VERO se TUTTI i giocatori del gruppo hanno colluso INSIEME. Se alcuni ma non tutti i giocatori sono collusi, la funzione restituisce FALSE. Un valore di ritorno di TRUE è fatto con (per esempio) il 75% di confidenza.

Il vostro compito è quello di produrre un elenco completo di tutti i giocatori che sono stati collusi, insieme a un elenco completo dei giocatori con cui ha collaborato. Recentemente ho sentito questo problema descritto come NP-hard ma è accurato? A volte chiamiamo le cose "NP" o "NP-hard" che sono semplicemente "difficili".

Grazie!

Answer 1

L'approccio a forza bruta vedo subito è:

Set colluders = new Set(); 
for(Player p1 : allPlayers) 
{ 
    for(Player p2 : allPlayers) 
    { 
    if(!p1.equals(p2) && haveColluded(p1, p2)) 
    { 
     colluders.add(p1); 
     colluders.add(p2); 
    } 
    } 
} 

non vedo un punto a chiamare haveColluded con conta di argomenti più grandi di 2 perché questo potrebbe dare falsi negativi. Suppongo che dipenda quanto sia costosa la funzione. Ma quanto sopra risulta in O (n^2) chiama ad avereColluded (n è il numero di giocatori). La funzione stessa sembrerebbe essere O (m), dove m è il numero di giochi che hanno giocato insieme. Pertanto, l'algoritmo sembra well in O (n^3). Per essere NP-hard, devi dimostrare "Un problema H è NP-difficile se e solo se c'è un problema NP-completo L che è tempo polinomiale Turing-riducibile a H [...] In altre parole, L può essere risolto in tempo polinomiale da una macchina di oracolo con un oracolo per H. " (http://en.wikipedia.org/wiki/NP-hard). Ho studiato i problemi NP-completi (ad es. 3-SAT, Problemi di venditore ambulante, ecc.) E non vedo come lo dimostreresti. Ma poi di nuovo, sembra sospettosamente simile allo clique problem.

Answer 2

Sembra clique detection, che è NP-rigido. D'altra parte, la dimensione della clique è limitata qui (10), quindi la forza bruta è n^10 nel peggiore dei casi.

Modifica: la domanda chiave qui è quali sono le proprietà della funzione di collusione. Possono essere rilevati 10 giocatori colludendo insieme chiamando la funzione su due giocatori più piccoli (diciamo 5)?

Answer 3

Sotto il tuo modello, ciò che descrivi dovrebbe essere abbastanza facile. Ti viene dato un grafico implicito (i vertici sono giocatori, i bordi corrispondono ad aver giocato una partita insieme). Vuoi un sottografo di quel grafico.

Se la funzione di collusione era perfettamente affidabile, basta chiamarla su ogni coppia di vertici nel grafico e si ottiene il sottografo.

Questo sottografo è probabilmente abbastanza disconnesso. Mi aspetto che il grafico risultante sia disconnesso o collegato molto debolmente; grandi sottotitoli ben collegati cadranno rapidamente facendo alcuni piccoli tagli.

Nota che siamo in grado di limitarci a guardare solo le coppie, perché la funzione di collusione deve obbedire (in termini di livello di confidenza) colludere (A, B, C) < colludere (A, B).

Costruire questa funzione di collusione globale è la parte che sembra difficile.

Answer 4

Vorrei dividere questo in due fasi:

1. Iterate oltre 5 miliardi di mani di poker che esaminano il gioco in ogni mano. Impiegare qualche algoritmo, chiamiamolo algoritmo A, su ogni mano. Mentre procedete, costruite un grafico di collusione in cui i vertici rappresentano i giocatori e i bordi ponderati non orientati rappresentano una certa sicurezza di collusione tra due giocatori. Quando l'algoritmo A genera un trigger in base al sospetto che il giocatore X colluda con il giocatore Y, alcuni valori vengono aggiunti al bordo pesato XY nel grafico della collusione. Man mano che procedete tra le mani che sono state giocate, i pesi di bordo si accumulano nel tempo. Quando è stata raggiunta una certa soglia, allora il bordo rappresenta collusione tra X e Y.

2. Poi la funzione che determina se un elenco di giocatore vertici N ha tutti collusi insieme è una questione di verificare sottografo contenente i vertici N è completamente connesso (significa che ogni nodo ha un peso di bordo maggiore della soglia di collusione per ogni altro nodo nel sottografo). IIRC, determinando che questo è O (n * lg (n)).