Monotonicity (mechanism design)

In mechanism design, monotonicity is a property of a social choice function. It is a necessary condition for being able to implement the function using a strategyproof mechanism. Its verbal description is:[1]

"If changing one agent's type (while keeping the types of other agents fixed) changes the outcome under the social choice function, then the resulting difference in utilities of the new and original outcomes evaluated at the new type of this agent must be at least as much as this difference in utilities evaluated at the original type of this agent."

In other words:[2]:227

"If the social choice changes when a single player changes his valuation, then it must be because the player increased his value of the new choice relative to his value of the old choice."

Notation

There is a set X of possible outcomes.

There are n agents which have different valuations for each outcome. The valuation of agent i is represented as a function:

v_i : X \longrightarrow R_+

which expresses the value it assigns to each alternative.

The vector of all value-functions is denoted by v.

For every agent i, the vector of all value-functions of the other agents is denoted by v_{-i}. So v \equiv (v_i,v_{-i}).

A social choice function is a function that takes as input the value-vector v and returns an outcome x\in X. It is denoted by Outcome(v) or Outcome(v_i,v_{-i}).

In mechanisms without money

A social choice function satisfies the strong monotonicity property (SMON) if for every agent i and every v_i,v_i',v_{-i}, if:

x = Outcome(v_i, v_{-i})
x' = Outcome(v'_i, v_{-i})

then:

v_i(x) - v_i(x') \geq 0
v_i'(x) - v_i'(x') \leq 0

Necessity

If there exists a strategyproof mechanism without money, with an outcome function Outcome, then this function must be SMON.

PROOF: Fix some agent i and some valuation vector v_{-i}. Strategyproofness means that an agent with real valuation v_i weakly prefers to declare v_i than to lie and declare v_i'; hence:

v_i(x) \geq v_i(x')

Similarly, an agent with real valuation v_i' weakly prefers to declare v_i' than to lie and declare v_i; hence:

v_i'(x') \geq v_i'(x)

In mechanisms with money

When the mechanism is allowed to use money, the SMON property is no longer necessary for implementability, since the mechanism can switch to an alternative which is less preferable for an agent and compensate that agent with money.

A social choice function satisfies the weak monotonicity property (WMON) if for every agent i and every v_i,v_i',v_{-i}, if:

x = Outcome(v_i, v_{-i})
x' = Outcome(v'_i, v_{-i})

then:

v_i(x) - v_i(x') \geq v_i'(x) - v_i'(x')

Necessity

If there exists a strategyproof mechanism with an outcome function Outcome, then this function must be WMON.

PROOF:[2]:227 Fix some agent i and some valuation vector v_{-i}. A strategyproof mechanism has a price function Price_i(x, v_{-i}), that determines how much payment agent i receives when the outcome of the mechanism is x; this price depends on the outcome but must not depend directly on v_i. Strategyproofness means that a player with valuation v_i weakly prefers to declare v_i over declaring v_i'; hence:

v_i(x) + Price_i(x, v_{-i}) \geq v_i(x') + Price_i(x', v_{-i})

Similarly, a player with valuation v_i' weakly prefers to declare v_i' over declaring v_i; hence:

v_i'(x) + Price_i(x, v_{-i}) \leq v_i'(x') + Price_i(x', v_{-i})

Subtracting the second inequality from the first gives the WMON property.

Sufficiency

Monotonicity is not always a sufficient condition for implementability, but there are some important cases in it is sufficient (i.e, every WMON social-choice function can be implemented):

Examples

1. When agents have single peaked preferences, the median social-choice function (selecting the median among the outcomes that are best for the agents) is strongly monotonic. Indeed, the mechanism selecting the median vote is a truthful mechanism without money. See median voter theorem.

2. When agents have general preferences represented by cardinal utility functions. the utilitarian social-choice function (selecting the outcome that maximizes the sum of the agents' valuations) is not strongly-monotonic but it is weakly monotonic. Indeed, it can be implemented by the VCG mechanism, which is a truthful mechanism with money.

3. The weak-monotonicity property has a special form when agents have single-parametric utility functions.

4. In the job-scheduling, The makespan-minimization social-choice function is not strongly-monotonic nor weakly-monotonic. Indeed, it cannot be implemented by a truthful mechanism; see truthful job scheduling.

See also

References

  1. 1 2 Bikhchandani, Sushil; Chatterji, Shurojit; Lavi, Ron; Mu'Alem, Ahuva; Nisan, Noam; Sen, Arunava (2006). "Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation". Econometrica 74 (4): 1109. doi:10.1111/j.1468-0262.2006.00695.x.
  2. 1 2 Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
  3. 1 2 "Monotonicity and Implementability". Econometrica 78 (5): 1749. 2010. doi:10.3982/ECTA8882.
This article is issued from Wikipedia - version of the Sunday, January 10, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.