NP-Hard? ¿Complejidad algorítmica de la detección de colusión de póker en línea?

Question

¿Cuál es la mejor manera de describir la complejidad algorítmica de la detección de colusión para un sitio de póquer en línea de diez millones de jugadores?

Supongamos (no creo que estas suposiciones hacen mucha diferencia así que siéntete libre de ignorarlos, pero sólo para aclarar):

• que el sitio tiene 10.000.000 de usuarios registrados.
• Que estos jugadores hayan jugado un total de 5 mil millones de manos.
• Que la única información que se le proporciona es la "base de datos de historial de manos del maestro" para el sitio, que contiene todas las tarjetas de jugadores y las acciones de apuestas para cada mano.
• En otras palabras, NO puede tomar atajos, como examinar direcciones IP, buscar patrones inusuales de rake/profit, etc.
• Supongamos que se le asigna una función que, cuando pasa un grupo de exactamente N (donde N es entre 2 y 10) jugadores, devuelve VERDADERO si TODOS los jugadores en el grupo han coludido JUNTOS. Si algunos, pero no todos los jugadores son coludidores, la función devuelve FALSO. Se realiza un valor de retorno de TRUE con (por ejemplo) 75% de confianza.

Su trabajo es producir una lista exhaustiva de cada jugador que está en colusión, junto con una lista completa de los jugadores con los que está coludido. Hace poco escuché que este problema se describe como NP-hard, pero ¿es esto exacto? A veces llamamos a las cosas "NP" o "NP-hard" que son simplemente "duras".

Gracias!

Answer 1

El enfoque de fuerza bruta veo de inmediato es:

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); 
    } 
    } 
} 

no veo un punto de llamar haveColluded con un recuento de argumentos más grandes que 2 porque eso podría dar falsos negativos. Supongo que depende de qué tan costosa sea la función. Pero lo anterior da como resultado O (n^2) llamadas a haveColluded (n es el número de jugadores). La función en sí sería aparentemente O (m), donde m es el número de juegos que jugaron juntos. Por lo tanto, el algoritmo parece bien en O (n^3). Para ser NP-hard, debe probar "Un problema H es NP-hard si y solo si hay un problema NP-completo L que es un tiempo polinomial Turing-reducible a H [...] En otras palabras, L puede ser resuelto en tiempo polinomial por una máquina de oráculo con un oráculo para H. " (http://en.wikipedia.org/wiki/NP-hard). Estudié problemas NP-completos (por ejemplo, 3-SAT, problema de vendedor ambulante, etc.) y no veo cómo lo probarías. Pero, de nuevo, parece sospechosamente similar al clique problem.

Answer 2

Parece clique detection, que es NP-hard. Por otro lado, el tamaño de la camarilla está limitado aquí (10), por lo que la fuerza bruta es n^10 en el peor.

Editar: La pregunta clave aquí es cuáles son las propiedades de la función de colusión. ¿Se pueden detectar 10 jugadores coludidos juntos llamando a la función en dos sets más pequeños (digamos 5) jugadores?

Answer 3

Debajo de tu modelo, lo que describes debería ser bastante fácil. Se te da un gráfico implícito (los vértices son jugadores, los bordes corresponden a haber jugado un juego juntos). Quieres un subgrafo de ese grafico

Si la función de colusión fue perfectamente confiable, simplemente llámela a cada par de vértices en el gráfico, y obtendrá el subgráfico.

Ese subgrafo probablemente esta bastante desconectado. Esperaría que el gráfico resultante esté desconectado o muy débilmente conectado; grandes subgrafos bien conectados se caerán rápidamente haciendo algunos min-cortes.

Tenga en cuenta que nos podemos limitarnos a mirar sólo pares, ya que la función colusión debe obedecer (en términos de nivel de confianza) se confabulan (A, B, C) < confabulan (A, B).

Construir esta función global de colusión es la parte que parece difícil.

Answer 4

sin dividir esto en dos pasos:

1. iterar sobre 5 mil millones manos de póquer que examinan el juego en cada mano. Emplea algún algoritmo, vamos a llamarlo algoritmo A, en cada mano. A medida que avanzas, construyes un gráfico de colusión en el que los vértices representan a los jugadores y los bordes pesados ​​no dirigidos representan cierta confianza de colusión entre dos jugadores. Cuando el algoritmo A se activa bajo sospecha de que el jugador X se confabula con el jugador Y, se agrega un valor al borde ponderado XY en el gráfico de colusión. A medida que avanzas por las manos que se han jugado, los pesos de los bordes se acumulan con el tiempo. Cuando se ha alcanzado un umbral, entonces el borde representa colusión entre X e Y.

2. Entonces la función de determinar si una lista de N jugador vértices tiene todo coludieron juntos es una cuestión de la verificación de la subgrafo que contiene los vértices N está completamente conectado (lo que significa que cada nodo tiene un peso de borde mayor que el umbral de colusión para cada otro nodo en el subgráfico). IIRC, determinando esto es O (n * lg (n)).