Mecanismos mejorados e inecuaciones de profeta para dependencias gráficas

Durante las últimas dos décadas, se han logrado avances significativos en problemas estocásticos como el diseño de subastas óptimas en términos de ingresos y las inecuaciones de profeta, modeladas tradicionalmente con n variables aleatorias independientes para representar los valores de n artículos. Sin embargo, en muchas aplicaciones, esta suposición de independencia a menudo se desvía de la realidad. Dado los fuertes resultados de imposibilidad asociados con correlaciones arbitrarias, la investigación reciente se ha orientado hacia la exploración de estos problemas bajo modelos de dependencia suave. En este trabajo, estudiamos los problemas de subasta óptima e inecuaciones de profeta dentro del marco del popular modelo gráfico de Campos Aleatorios de Markov (MRFs), una elección motivada por su capacidad para capturar estructuras de dependencia complejas. Específicamente, para el problema de vender n artículos a un solo comprador para maximizar ingresos, mostramos que el máximo de SRev y BRev es una aproximación O() al ingreso óptimo para compradores subaditivos, donde es el grado ponderado máximo del MRF subyacente. Esta es una generalización así como una mejora exponencial de los resultados de aproximación (O()) de Cai y Oikonomou (EC 2021) para compradores aditivos y de demanda unitaria. También obtenemos una mejora exponencial similar para el problema de inecuaciones de profeta, que es asintóticamente óptimo, ya que mostramos un límite superior coincidente.