Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

Convergencia de Nash de algoritmos de aprendizaje basados ​​en la media en subastas de primer precio

Created by
  • Haebom

Autor

Xiaotie Deng, Xinyan Hu, Tao Lin, Weiqiang Zheng

Describir

Este documento analiza las propiedades de convergencia de la dinámica de aprendizaje en subastas repetidas de primer precio donde los postores con valores fijos usan algoritmos basados ​​en promedios (incluyendo algoritmos sin arrepentimiento como Multiplicative Weights Update y Follow the Perturbed Leader). Caracterizamos completamente la dinámica de aprendizaje de los algoritmos basados ​​en promedios bajo dos conceptos de convergencia: convergencia de promedio temporal (la fracción de tiempo en la que los postores juegan un equilibrio de Nash converge a 1) y convergencia de última iteración (los perfiles de estrategia mixta de los postores convergen a un equilibrio de Nash). El resultado de la convergencia depende del número de postores de mayor valor. Si hay tres o más postores de mayor valor, es casi seguro que el equilibrio de Nash converge tanto en el promedio temporal como en la última iteración; si hay dos postores de mayor valor, el equilibrio de Nash converge en el promedio temporal pero no necesariamente en la última iteración; y si hay un postor con el valor más alto, el equilibrio de Nash puede no converger ni en el promedio temporal ni en la última iteración.

Takeaways, Limitations

•
Takeaways: Presentamos una caracterización completa de las características de convergencia de algoritmos de aprendizaje basado en la media en subastas repetitivas, lo que ofrece potencial para diversas aplicaciones, incluyendo los mercados de publicidad en línea. En particular, revelamos las diferencias en los resultados de convergencia según el número de mejores postores, lo que sugiere nuevas posibilidades para el estudio de la dinámica del aprendizaje.
•
Limitations: El análisis se limitó a algoritmos basados ​​en promedios, lo que limita su generalización a otros tipos de algoritmos de aprendizaje. Además, el análisis asumió valores fijos para los postores, por lo que los resultados pueden variar en situaciones donde los valores fluctúan. Finalmente, el hecho de que la convergencia en la iteración final no esté garantizada cuando hay dos postores con la mejor oferta requiere mayor investigación.
👍
Made with Slashpage