[general_dat] Más info de Optmización en línea con información estocástica y las desigualdades del profesta

[Pablo Groisman]

En el mensaje anterior omití mandar información sobre la materia. Acá va
(diculpas)

*Descripción del curso*
En la versión clásica del problema de la desigualdad del profeta, un
tomador de decisiones ("jugador") se
enfrenta a una secuencia de recompensas aleatorias presentadas de forma
online. El jugador puede aceptar
o rechazar cada recompensa a medida que se presenta. Rechazar una
recompensa hace que se pierda para
siempre, pero aceptar una recompensa termina el juego inmediatamente. El
juego continúa hasta que el
jugador elige aceptar una recompensa. La recompensa esperada lograda por el
jugador se compara con la
recompensa esperada obtenible por un "profeta" que ve toda la secuencia de
antemano y puede simplemente
elegir la mejor recompensa. Una desigualdad del profeta establece que el
jugador puede lograr una cierta
fracción de la recompensa esperada del profeta, en el peor de los casos,
sobre una clase de distribuciones de
recompensas. Este problema y sus generalizaciones han visto un
resurgimiento en popularidad en la última
década debido a su relevancia en una variedad de aplicaciones, como
subastas de anuncios, fijación de precios
y servicios de transporte. Esto ha llevado a nuevas perspectivas, y las
principales preguntas han evolucionado
hacia la comprensión de los aspectos computacionales e informativos de las
desigualdades del profeta.
Este curso ofrece una introducción exhaustiva a la teoría matemática y
algorítmica de las desigualdades del
profeta y sus aplicaciones en diversas áreas como la optimización
combinatoria estocástica, economía, y la
toma de decisiones en línea. El curso explora técnicas avanzadas y sus
aplicaciones prácticas en escenarios de
subastas, fijación de precios y plataformas de ridesharing.

*Objetivos*

   -

   Comprender el problema clásico de la desigualdad del profeta y sus
   variantes.
   -

   Aplicar técnicas analíticas para resolver problemas de desigualdad del
   profeta.
   -

   Explorar aplicaciones prácticas en subastas combinatorias, fijación de
   precios y plataformas de ridesharing.
   -

   Evaluar algoritmos en términos de su rendimiento relativo y otras
   métricas.

*Programa*

*Introducción (semanas 1 y 2)*



   -

   Descripción del problema clásico de la desigualdad del profeta.
   -

   Orígenes y aplicaciones del problema en la optimización combinatoria y
   economía.
   -

   Relación con otros problemas clásicos de selección/parada en línea
   (e.g., problema del secretario, problema de la caja de Pandora).
   -

   Resumen del plan del curso.


*La Desigualdad del Profeta Básica (semanas 3 y 4)*



   -

   Introducción formal al modelo básico de una sola elección con
   distribuciones independientes.
   -

   Análisis de la política en línea óptima mediante inducción.
   -

   Interpretación económica en términos de utilidad y precios.


*Otros Modelos de Una Sola Elección (semanas 5 y 6)*



   -

   Variantes del problema básico de la desigualdad del profeta.
   -

   Modelos i.i.d. y el poder de los algoritmos de umbral único y múltiple.
   -

   Introducción al modelo del secretario profeta y el modelo de orden libre.


*Desigualdad del Profeta de Múltiples Elecciones (semanas 7 y 8)*



   -

   Extensión del modelo clásico para seleccionar hasta k recompensas.
   -

   Argumentos basados en concentración y esquemas de resolución de
   contención en línea.
   -

   Introducción a los *matroids* y su aplicación en desigualdades del
   profeta.


*Desigualdad del Profeta para **Matching** (semanas 9 y 10)*



   -

   Problema de *matching* en grafos con llegada de aristas y vértices.\
   -

   Técnicas de punto fijo y resolución de contención en línea.
   -

   Aproximación equilibrada de precios para grafos bipartitos y generales.


*Subastas Combinatorias (semanas 11 y 12)*



   -

   Introducción a las subastas combinatorias con valoraciones
   complementarias.
   -

   Algoritmos de aproximación y mecanismos de precios publicados.
   -

   Aplicaciones prácticas en mercados electrónicos y comercio en línea.


*Enfoques Basados en Datos (semanas 13 y 14)*



   -

   Desigualdades del profeta con información limitada y muestras de
   distribuciones.
   -

   Modelos i.i.d. con muestras y garantías de rendimiento.
   -

   Aplicaciones en *matching* bipartito y otros escenarios combinatorios.


*Otras Formas de Medir el Rendimiento y Aplicaciones Prácticas (semana 15)*



   -

   Evaluación del rendimiento relativo de algoritmos en línea.
   -

   *Benchmarks* y análisis de *regret*.


   -

   Aplicaciones prácticas en fijación de precios, mecanismos de subastas y
   plataformas de *ridesharing*.

*Bibliografía*

   -

   Lecturas seleccionadas del libro "Prophet Inequalities: Theory and
   Applications" de José Correa, Paul Dütting, Michal Feldman, Thomas
   Kesselheim, y Brendan Lucier.

   -

   Artículos de referencia y estudios de casos.



On Mon, Jul 22, 2024 at 10:25 AM Pablo Groisman <pgroisma at dm.uba.ar> wrote:

> Durante el 2do cuatrimestre de 2024 el profesor José Correa
> <https://www.dii.uchile.cl/~jcorrea/>, de la Universidad de Chile,
> dictará en *forma remota* la materia optativa
>
> Optimización en línea con información estocástica y las desigualdades del
> profeta
>
> La materia da puntaje para el doctorado en matemática y para la
> licenciatura en ciencias de datos (96hs). También puede dar puntaje para la
> licenciatura en matemática pero hay que hacer el trámite para pedir los
> puntos.
>
> La materia se dictará los martes (labo/consultas) y viernes (teóricas) de
> 13 a 16, empezando el viernes 16 de agosto.
>
> Si estás interesado/a en cursar la materia, por favor completá este
> formulario <https://forms.gle/CyvT415pUssQ1fN89>.
>