En el diseño de mecanismos , se dice que un agente tiene utilidad de un solo parámetro si su valoración de los posibles resultados puede representarse con un solo número. Por ejemplo, en una subasta de un solo artículo, las utilidades de todos los agentes son uniparamétricas, ya que pueden ser representadas por su evaluación monetaria del artículo. Por el contrario, en una subasta combinatoria de dos o más artículos relacionados, las utilidades no suelen ser uniparamétricas, ya que suelen estar representadas por sus evaluaciones de todos los posibles paquetes de artículos.
Notación
Hay un conjunto de posibles resultados.
Existen agentes que tienen diferentes valoraciones para cada resultado.
En general, cada agente puede asignar un valor diferente y no relacionado a cada resultado en .
En el caso especial de la utilidad de parámetro único , cada agentetiene un subconjunto propio de resultado conocido públicamente cuáles son los "resultados ganadores" para el agente (p. ej., en una subasta de un solo artículo, contiene el resultado en el que el agente gana el artículo).
Para cada agente, hay un número que representa el "valor ganador" de . La valoración del agente de los resultados enpuede tomar uno de dos valores: [1] : 228
- para cada resultado en ;
- 0 para cada resultado en .
El vector de los valores ganadores de todos los agentes se denota por .
Para cada agente , el vector de todos los valores ganadores de los otros agentes se denota por. Entonces.
Una función de elección social es una función que toma como entrada el vector de valor y devuelve un resultado . Se denota por o .
Monotonicidad
La propiedad de monotonicidad débil tiene una forma especial en los dominios de un solo parámetro. Una función de elección social es débilmente monótona si para cada agente y cada , Si:
- y
- luego:
Es decir, si el agente gana declarando un cierto valor, entonces también puede ganar declarando un valor más alto (cuando las declaraciones de los otros agentes son las mismas).
La propiedad de monotonicidad se puede generalizar a mecanismos aleatorios, que devuelven una distribución de probabilidad en el espacio. . [1] : 334 La propiedad WMON implica que para cada agente y cada , la función:
es una función débilmente creciente de .
Valor crítico
Para cada función de elección social débilmente monótona, para cada agente y para cada vector , hay un valor crítico , tal que el agente gana si-y-solo-si su oferta es al menos .
Por ejemplo, en una subasta de segundo precio , el valor crítico para el agente es la oferta más alta entre los demás agentes.
En entornos de un solo parámetro, los mecanismos verídicos deterministas tienen un formato muy específico. [1] : 334 Cualquier mecanismo verdadero determinista está completamente especificado por el conjunto de funciones c. Agente gana si y solo si su oferta es al menos , y en ese caso, paga exactamente .
Implementación determinista
Se sabe que, en cualquier dominio, la monotonicidad débil es una condición necesaria para la implementabilidad. Es decir, una función de elección social puede implementarse mediante un mecanismo veraz , solo si es débilmente monótono.
En un dominio de un solo parámetro, la monotonicidad débil también es una condición suficiente para la implementación. Es decir, para cada función de elección social débilmente monótona, existe un mecanismo veraz determinista que la implementa. Esto significa que es posible implementar varias funciones de elección social no lineales, por ejemplo, maximizando la suma de cuadrados de los valores o el valor mínimo-máximo.
El mecanismo debería funcionar de la siguiente manera: [1] : 229
- Pida a los agentes que revelen sus valoraciones. .
- Seleccione el resultado según la función de elección social: .
- Cada agente ganador (cada agente tal que ) paga un precio igual al valor crítico: .
- Cada agente perdedor (cada agente tal que ) no paga nada: .
Este mecanismo es veraz, porque la utilidad neta de cada agente es:
- si gana;
- 0 si pierde.
Por tanto, el agente prefiere ganar si y perder si , que es exactamente lo que sucede cuando dice la verdad.
Implementación aleatoria
Un mecanismo aleatorio es una distribución de probabilidad sobre mecanismos deterministas. Un mecanismo aleatorio se llama veraz en expectativa si decir la verdad le da al agente un valor esperado más grande .
En un mecanismo aleatorio, cada agente tiene una probabilidad de ganar, definida como:
y un pago esperado, definido como:
En un dominio de un solo parámetro, un mecanismo aleatorio es veraz en expectativa si y solo si: [1] : 232
- La probabilidad de ganar , es una función débilmente creciente de ;
- El pago esperado de un agente es:
Tenga en cuenta que en un mecanismo determinista, es 0 o 1, la primera condición se reduce a la monotonicidad débil de la función Resultado y la segunda condición se reduce a cargar a cada agente su valor crítico.
Dominios de un solo parámetro frente a dominios de varios parámetros
Cuando las utilidades no son uniparamétricas (por ejemplo, en subastas combinatorias ), el problema del diseño del mecanismo es mucho más complicado. El mecanismo VCG es uno de los únicos mecanismos que funciona para valoraciones tan generales.
Ver también
Referencias
- ↑ a b c d e Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.