Desigualdad profética

En la teoría de algoritmos en línea y parada óptima , una desigualdad de profeta es una cota para el valor esperado de un proceso de toma de decisiones que maneja una secuencia de entradas aleatorias de distribuciones de probabilidad conocidas , en relación con el valor esperado que podría alcanzar un "profeta" que conoce todas las entradas (y no solo sus distribuciones) de antemano. ^{[ 1 ] [ 2 ]} Estas desigualdades tienen aplicaciones en la teoría del diseño de mecanismos algorítmicos y finanzas matemáticas . ^{[ 3 ]}

La desigualdad clásica del profeta de un solo elemento fue publicada por Krengel y Sucheston (1978) , quienes atribuyen su forma precisa a DJH (Ben) Garling. Se refiere a un proceso en el que una secuencia de variables aleatorias${\displaystyle X_{i}}$Proceden de distribuciones conocidas${\displaystyle {\mathcal {D}}_{i}}$Cuando cada${\displaystyle X_{i}}$Cuando llega, el proceso de toma de decisiones debe decidir si aceptarla y detener el proceso, o si rechazarla y pasar a la siguiente variable en la secuencia. El valor del proceso es la única variable aceptada, si la hay, o cero en caso contrario. Se puede suponer que todas las variables son no negativas; de lo contrario, reemplazar los valores negativos por cero no cambia el resultado. Esto puede modelar, por ejemplo, situaciones financieras en las que las variables son ofertas para comprar algún bien indivisible a un precio determinado, y el vendedor debe decidir cuál (si alguna) oferta aceptar. Un profeta, conociendo toda la secuencia de variables, puede obviamente seleccionar la mayor de ellas, logrando valor${\textstyle \max _{i}X_{i}}$para cualquier instancia específica de este proceso y valor esperado${\textstyle \mathbb {E} [\max _ {i}X_ {i}]}$La desigualdad del profeta establece la existencia de un algoritmo en línea para este proceso cuyo valor esperado es al menos la mitad del del profeta :${\textstyle {\tfrac {1}{2}}\mathbb {E} [\max _ {i}X_ {i}]}$Ningún algoritmo puede lograr un mayor valor esperado para todas las distribuciones de entradas. ^{[ 3 ] [ 4 ]}

Un método para demostrar la desigualdad del profeta de un solo elemento es utilizar un "algoritmo de umbral" que establece un parámetro${\displaystyle \tau }$y luego acepta la primera variable aleatoria que sea al menos tan grande como${\displaystyle \tau }$. Si la probabilidad de que este proceso acepte un artículo es${\displaystyle p}$, entonces su valor esperado es${\displaystyle p\tau }$más el exceso esperado sobre${\displaystyle \tau }$que tiene la variable seleccionada (si la hay). Cada variable${\displaystyle X_{i}}$será considerado por el algoritmo de umbral con probabilidad al menos${\displaystyle 1-p}$y si se considera contribuirá${\textstyle \max(X_{i}-\tau ,0)}$al exceso, por lo que por linealidad de la esperanza el exceso esperado es al menos$${\displaystyle \mathbb {E} {\Bigl [}\sum _{i}(1-p)\max(X_{i}-\tau ,0){\Bigr ]}\geq (1-p){\bigl (}\mathbb {E} [\max _{i}X_{i}]-\tau ).}$$Configuración${\displaystyle \tau }$a la mediana de la distribución de${\textstyle \max _{i}X_{i}}$, de modo que${\displaystyle p={\tfrac {1}{2}}}$y añadiendo${\displaystyle p\tau }$a este límite en exceso esperado, causa el${\displaystyle p\tau }$y${\displaystyle (1-p)(-\tau )}$términos para cancelarse entre sí, demostrando que para este escenario de${\displaystyle \tau }$El algoritmo de umbral alcanza un valor esperado de al menos${\textstyle {\tfrac {1}{2}}\mathbb {E} [\max _ {i}X_ {i}]}$. ^{[ 3 ] [ 5 ]} Un umbral diferente,${\textstyle \tau ={\tfrac {1}{2}}\mathbb {E} [\max _ {i}X_ {i}]}$, también alcanza al menos este mismo valor esperado. ^{[ 3 ] [ 6 ]}

Se conocen varias generalizaciones de la desigualdad del profeta de un solo elemento a otros escenarios en línea, y también se denominan desigualdades del profeta. ^{[ 3 ]} Estas incluyen configuraciones donde se puede aceptar más de un valor y el objetivo es maximizar la suma de los valores aceptados sujeto a alguna restricción en el conjunto de elementos aceptados. Por ejemplo, una restricción de cardinalidad de${\displaystyle m}$donde queremos aceptar como máximo${\displaystyle m}$elementos, o una restricción de matroide donde los elementos tienen una estructura de matroide conocida y solo queremos aceptar un conjunto independiente del matroide. ^{[ 6 ]}

Las desigualdades de profeta están relacionadas con el análisis competitivo de algoritmos en línea , pero difieren en dos aspectos. Primero, gran parte del análisis competitivo asume entradas del peor caso , elegidas para maximizar la relación entre el valor calculado y el valor óptimo que podría haberse alcanzado conociendo el futuro, mientras que para las desigualdades de profeta se asume cierto conocimiento de la entrada, su distribución. Segundo, para lograr una determinada relación competitiva , un algoritmo en línea debe tener un rendimiento dentro de esa relación con el rendimiento óptimo en todas las entradas. En cambio, una desigualdad de profeta solo limita el rendimiento en esperanza, permitiendo que algunas secuencias de entrada produzcan un rendimiento peor siempre que el promedio sea bueno. ^{[ 3 ]}

• Desigualdades y diseño de mecanismos del profeta Matroid , The Matroid Union
• Una perspectiva económica de las desigualdades proféticas