Monotonía (diseño de mecanismos)

En el diseño de mecanismos , la monotonía es una propiedad de una función de elección social . Es una condición necesaria para poder implementar dicha función utilizando 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 los 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 tan grande 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 elección anterior.

Notación

Hay un conjunto de resultados posibles. ${\displaystyle X}$

Existen agentes que tienen valoraciones diferentes para cada resultado. La valoración del agente se representa como una función: que expresa el valor que le asigna a cada alternativa. ${\displaystyle n}$ ${\displaystyle i}$ $${\displaystyle v_{i}:X\longrightarrow R_{+}}$$

El vector de todas las funciones de valor se denota por . ${\displaystyle v}$

Para cada agente , el vector de todas las funciones de valor de los otros agentes se denota por . Por lo tanto . ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle v\equiv (v_{i},v_{-i})}$

Una función de elección social es una función que toma como entrada el vector de valores y devuelve un resultado . Se denota por o . ${\displaystyle v}$ ${\displaystyle x\in X}$ ${\displaystyle {\text{Outcome}}(v)}$ ${\displaystyle {\text{Outcome}}(v_{i},v_{-i})}$

En mecanismos sin dinero

Una función de elección social satisface la propiedad de monotonía fuerte (SMON) si para cada agente y cada , si: entonces: (según las preferencias iniciales, el agente prefiere el resultado inicial). (según las preferencias finales, el agente prefiere el resultado final). O equivalentemente: ${\displaystyle i}$ ${\displaystyle v_{i},v_{i}',v_{-i}}$ $${\displaystyle x={\text{Outcome}}(v_{i},v_{-i})}$$ $${\displaystyle x'={\text{Outcome}}(v'_{i},v_{-i})}$$ $${\displaystyle x\succeq _{i}x'}$$ $${\displaystyle x\preceq _{i'}x'}$$ $${\displaystyle v_{i}(x)-v_{i}(x')\geq 0}$$ $${\displaystyle v_{i}'(x)-v_{i}'(x')\leq 0}$$

Necesidad

Si existe un mecanismo a prueba de estrategias sin dinero, con una función de resultado , entonces esta función debe ser SMON. ${\displaystyle Outcome}$

PRUEBA: Fijar un agente y un vector de valoración . La estrategia a prueba significa que un agente con valoración real prefiere débilmente declarar que mentir y declarar ; por lo tanto: De manera similar, un agente con valoración real prefiere débilmente declarar que mentir y declarar ; por lo tanto: ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}'}$ $${\displaystyle v_{i}(x)\geq v_{i}(x')}$$ ${\displaystyle v_{i}'}$ ${\displaystyle v_{i}'}$ ${\displaystyle v_{i}}$ $${\displaystyle v_{i}'(x')\geq v_{i}'(x)}$$

En mecanismos con dinero

Cuando se permite que el mecanismo utilice 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 monotonía débil (WMON) si para cada agente y cada , si: entonces: ${\displaystyle i}$ ${\displaystyle v_{i},v_{i}',v_{-i}}$ $${\displaystyle x={\text{Outcome}}(v_{i},v_{-i})}$$ $${\displaystyle x'={\text{Outcome}}(v'_{i},v_{-i})}$$ $${\displaystyle v_{i}(x)-v_{i}(x')\geq v_{i}'(x)-v_{i}'(x')}$$

Necesidad

Si existe un mecanismo a prueba de estrategias con una función de resultado , entonces esta función debe ser WMON. ${\displaystyle {\text{Outcome}}}$

PRUEBA: ^{[2] : 227} Fije 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 pago recibe el agente cuando el resultado del mecanismo es ; este precio depende del resultado pero no debe depender directamente de . La a prueba de estrategias significa que un jugador con valoración débil prefiere declarar en lugar de declarar ; por lo tanto: De manera similar, un jugador con valoración débil prefiere declarar en lugar de declarar ; por lo tanto: Restando la segunda desigualdad de la primera se obtiene la propiedad WMON. ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle Price_{i}(x,v_{-i})}$ ${\displaystyle i}$ ${\displaystyle x}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}'}$ $${\displaystyle v_{i}(x)+{\text{Price}}_{i}(x,v_{-i})\geq v_{i}(x')+{\text{Price}}_{i}(x',v_{-i})}$$ ${\displaystyle v_{i}'}$ ${\displaystyle v_{i}'}$ ${\displaystyle v_{i}}$ $${\displaystyle v_{i}'(x)+{\text{Price}}_{i}(x,v_{-i})\leq v_{i}'(x')+{\text{Price}}_{i}(x',v_{-i})}$$

Suficiencia

La monotonía no siempre es una condición suficiente para la implementabilidad, pero hay algunos casos importantes en los que es suficiente (es decir, cada función de elección social de WMON puede implementarse):

• Cuando los agentes tienen funciones de utilidad de un solo parámetro .
• En muchos dominios convexos, más notablemente cuando el rango de cada función de valor es . ^[1] ${\displaystyle \mathbb {R} ^{+}}$
• Cuando el rango de cada función-valor es , o un cubo (Gui, Müller y Vohra (2004)). ${\displaystyle \mathbb {R} }$
• En cualquier dominio convexo (Saks y Yu (2005)).
• En cualquier dominio con un cierre convexo. ^[3]
• En cualquier "dominio de monotonía". ^[3]

Ejemplos

1. Cuando los agentes tienen preferencias de un solo pico , la función de elección social mediana (que selecciona la mediana entre los resultados que son mejores para los agentes) es fuertemente monótona . De hecho, el mecanismo que selecciona el voto mediano es un mecanismo veraz sin dinero. Véase la regla del voto mediano .
2. Cuando los agentes tienen preferencias generales representadas por funciones de utilidad cardinales , la función de elección social utilitaria (selección del resultado que maximiza la suma de las valoraciones de los agentes) no es fuertemente monótona, pero sí débilmente monótona . De hecho, puede implementarse mediante el mecanismo VCG , que es un mecanismo veraz con dinero.
3. En la programación de tareas, la función de elección social de minimización de makespan no es fuertemente monótona ni débilmente monótona. De hecho, no puede implementarse mediante un mecanismo veraz; consulte programación de tareas veraz .

Véase también

• El criterio de monotonía en los sistemas de votación.
• Monotonía de Maskin
• Otros significados de monotonía en diferentes ámbitos.

Referencias

1. Bikhchandani, Sushil; Chatterji, Shurojit; Lavi, Ron; Mu'Alem, Ahuva; Nisán, Noam; Sen, Arunava (2006). "La monotonicidad débil caracteriza la implementación de la estrategia dominante determinista" (PDF) . Econométrica . 74 (4): 1109. doi :10.1111/j.1468-0262.2006.00695.x. S2CID  6210226.
2. Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
3. "Monotonicidad e Implementabilidad". Econometrica . 78 (5): 1749–1772. 2010. doi :10.3982/ECTA8882. S2CID  1024035.