Caracterización de mecanismos verídicos de bandido multi-brazo

Consideramos un escenario de subasta multironda motivado por subastas de pago por clic para publicidad en Internet. En cada ronda, el subastador selecciona un anunciante y muestra su anuncio, que luego puede ser clickeado o no. Un anunciante obtiene valor de los clics; el valor de un clic es su información privada. Inicialmente, ni el subastador ni los anunciantes tienen información sobre la probabilidad de clics en los anuncios. El objetivo del subastador es diseñar un mecanismo verídico (de estrategias dominantes) que maximice (aproximadamente) el bienestar social. Si los anunciantes pujan sus verdaderos valores privados, nuestro problema es equivalente al problema del bandido multi-brazo, y por lo tanto puede verse como una versión estratégica de este último. En particular, para ambos problemas, la calidad de un algoritmo puede caracterizarse por el arrepentimiento, que es la diferencia en bienestar social entre el algoritmo y el punto de referencia que siempre selecciona el mismo anuncio “mejor”. Investigamos cómo el diseño de algoritmos de bandido multi-brazo se ve afectado por la restricción de que el mecanismo resultante debe ser verídico. Encontramos que los mecanismos verídicos determinísticos tienen ciertas propiedades estructurales fuertes; esencialmente, deben separar la exploración de la explotación; y sufren un arrepentimiento mucho mayor que los algoritmos óptimos de bandido multi-brazo. Además, proporcionamos un mecanismo verídico que (esencialmente) iguala nuestro límite inferior sobre el arrepentimiento.