Diseño de mecanismos aproximadamente óptimos frente al principio de revelación

Question

El resumen del artículo "Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations" (Dobzinski, Vondrak, 2016) dice

Una cuestión pendiente desde hace tiempo en el diseño de mecanismos algorítmicos es si existen mecanismos veraces computacionalmente eficientes para las subastas combinatorias, con garantías de rendimiento cercanas a las posibles sin consideraciones de veracidad. En este artículo, respondemos a esta pregunta de forma negativa: el requisito de veracidad puede tener un impacto dramático en la capacidad de un mecanismo para lograr una buena relación de aproximación para las subastas combinatorias.

Mi pregunta es dado que el principio de revelación dice que podemos WLOG restringir nuestra atención a los mecanismos de CI de revelación directa en el diseño de mecanismos, ¿cómo puede haber una pérdida de ingresos/una menor relación de aproximación al restringir la búsqueda de mecanismos aproximadamente óptimos (es decir, de maximización de ingresos) a los de CI?

Answer 1

Una parte clave del documento es que están interesados en

mecanismos de verdad computacionalmente eficientes

El mecanismo VCG es un mecanismo directo veraz y eficiente, pero no es eficiente desde el punto de vista computacional. En muchas subastas combinatorias, es imposible calcular las transferencias VCG en un tiempo razonable con la tecnología actual.

En el pasado, los economistas han ignorado en gran medida el problema de la eficiencia computacional en el diseño de mecanismos. Este problema ha sido abordado principalmente por los informáticos. Véase, por ejemplo, la introducción de Milgrom y Segal (2020) Subastas de relojes y reasignación del espectro radioeléctrico. JPE

Answer 2

Si le he entendido bien, aquí hay dos cuestiones.

En primer lugar, ¿por qué los mecanismos directos de CI computacionalmente eficientes tienen un rendimiento inferior al del mecanismo directo de CI óptimo? La respuesta ingenua es simplemente que el mecanismo óptimo es realmente complicado; el documento parece abordar este punto cuidadosamente.

En segundo lugar, ¿por qué hay mecanismos directos computacionalmente eficientes que se aproximan al mecanismo directo óptimo de CI pero que no son de CI? Sin estar demasiado familiarizado con el diseño de mecanismos algorítmicos, sospecho que esto se debe a que la clase de mecanismos directos (CI o no) es mucho mayor que la clase de mecanismos directos CI. En particular, se puede inducir cualquier distribución sobre los resultados si no se requiere CI pero se asume que los agentes informan con veracidad.

Tenga en cuenta que el WLOG del Principio de Revelación debe entenderse de la siguiente manera. Tomemos un mecanismo arbitrario y una distribución de resultados en uno de los equilibrios del mecanismo. Existe un mecanismo directo de CI que produce la misma distribución sobre los resultados bajo la información veraz". El principio de revelación no no afirmar que toda distribución sobre los resultados es alcanzable a través de un mecanismo directo de CI convenientemente elegido, sólo es cierto para aquellas distribuciones que ya están inducidas por algún equilibrio de algún mecanismo indirecto. En este sentido, hay una pérdida al restringir la atención a los mecanismos directos de CI porque algunas distribuciones sobre los resultados simplemente nunca forman parte de un equilibrio.