En el diseño de mecanismos , la monotonicidad es una propiedad de una función de elección social . Es una condición necesaria para poder implementar la función mediante un mecanismo a prueba de estrategias . Su descripción verbal es: [1]
Si cambiar el tipo de un agente (mientras se mantienen fijos los tipos de otros agentes) cambia el resultado bajo la función de elección social, entonces la diferencia resultante en las utilidades de los resultados nuevos y originales evaluados en el nuevo tipo de este agente debe ser al menos igual como esta diferencia en las utilidades evaluadas en el tipo original de este agente.
En otras palabras: [2] : 227
Si la elección social cambia cuando un solo jugador cambia su valoración, entonces debe ser porque el jugador aumentó su valor de la nueva elección en relación con su valor de la antigua elección.
Notación
Hay un conjunto de posibles resultados.
Existen agentes que tienen diferentes valoraciones para cada resultado. La valoración del agente se representa como una función:
que expresa el valor que asigna a cada alternativa.
El vector de todas las funciones de valor se denota por .
Para cada agente , el vector de todas las funciones de valor 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 .
En mecanismos sin dinero
Una función de elección social satisface la propiedad de monotonicidad fuerte (SMON) si para cada agente y cada , Si:
Necesidad
Si existe un mecanismo a prueba de estrategias sin dinero, con una función de resultado, entonces esta función debe ser SMON.
PRUEBA: Arregle algún agente y algún vector de valoración . Strategyproofness significa que un agente con valoración real débilmente prefiere declarar que mentir y declarar ; por eso:
En mecanismos con dinero
Cuando se permite que el mecanismo use dinero, la propiedad SMON ya no es necesaria para la implementación, ya que el mecanismo puede cambiar a una alternativa que sea menos preferible para un agente y compensar a ese agente con dinero.
Una función de elección social satisface la propiedad de monotonicidad débil (WMON) si para cada agente y cada , Si:
Necesidad
Si existe un mecanismo a prueba de estrategias con una función de resultado, entonces esta función debe ser WMON.
PRUEBA: [2] : 227 Arregle algún agente y algún vector de valoración . Un mecanismo a prueba de estrategias tiene una función de precio., que determina cuánto agente de pagos recibe cuando el resultado del mecanismo es ; este precio depende del resultado pero no debe depender directamente de. La resistencia a la estrategia significa que un jugador con valoración débilmente prefiere declarar sobre declarar ; por eso:
Suficiencia
La monotonicidad no siempre es una condición suficiente para la implementabilidad, pero hay algunos casos importantes en los que es suficiente (es decir, se pueden implementar todas las funciones de elección social de WMON):
- Cuando los agentes tienen funciones de utilidad de un solo parámetro .
- En muchos dominios convexos, sobre todo cuando el rango de cada función de valor es . [1]
- Cuando el rango de cada función de valor es , o un cubo (Gui, Müller y Vohra (2004)).
- En cualquier dominio convexo (Saks y Yu (2005)).
- En cualquier dominio con cierre convexo. [3]
- En cualquier "dominio de la monotonicidad". [3]
Ejemplos de
1. Cuando los agentes tienen preferencias puntuales únicas , la función de elección social mediana (seleccionar la mediana entre los resultados que son mejores para los agentes) es fuertemente monótona . De hecho, el mecanismo de selección del voto medio es un mecanismo veraz sin dinero. Consulte el teorema del votante mediano .
2. Cuando los agentes tienen preferencias generales representadas por funciones de utilidad cardinales . la función utilitaria de elección social (seleccionar el resultado que maximiza la suma de las valoraciones de los agentes) no es fuertemente monótona, pero es débilmente monótona . De hecho, puede implementarse mediante el mecanismo VCG , que es un mecanismo veraz con dinero.
3. La propiedad de monotonicidad débil tiene una forma especial cuando los agentes tienen funciones de utilidad uniparamétricas .
4. En el trabajo de programación, el makespan la función de elección social -Minimización no es muy monótona ni débilmente monótona. De hecho, no puede implementarse mediante un mecanismo veraz; vea la programación de trabajos veraz .
Ver también
- El criterio de la monotonicidad en los sistemas de votación.
- Monotonicidad de la máscara
- Otros significados de la monotonicidad en diferentes campos.
Referencias
- ^ a b Bikhchandani, Sushil; Chatterji, Shurojit; Lavi, Ron; Mu'Alem, Ahuva; Nisan, Noam; Sen, Arunava (2006). "Débil monotonicidad caracteriza la implementación de la estrategia dominante determinista" (PDF) . Econometrica . 74 (4): 1109. doi : 10.1111 / j.1468-0262.2006.00695.x .
- ^ a b 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.
- ^ a b "Monotonicidad y aplicabilidad". Econometrica . 78 (5): 1749-1772. 2010. doi : 10.3982 / ECTA8882 .