In mechanism design, monotonicity is a property of a social choice function.
It is a necessary condition for being able to implement such a 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.There is a set
agents which have different valuations for each outcome.
which expresses the value it assigns to each alternative.
The vector of all value-functions is denoted by
, the vector of all value-functions of the other agents is denoted by
A social choice function is a function that takes as input the value-vector
A social choice function satisfies the strong monotonicity property (SMON) if for every agent
(by the initial preferences, the agent prefers the initial outcome).
(by the final preferences, the agent prefers the final outcome).
If there exists a strategyproof mechanism without money, with an outcome function
PROOF: Fix some agent
Strategyproofness means that an agent with real valuation
weakly prefers to declare
Similarly, an agent with real valuation
weakly prefers to declare
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
If there exists a strategyproof mechanism with an outcome function
PROOF:[2]: 227 Fix some agent
A strategyproof mechanism has a price function
, that determines how much payment agent
receives when the outcome of the mechanism is
Strategyproofness means that a player with valuation
weakly prefers to declare
Similarly, a player with valuation
weakly prefers to declare
Subtracting the second inequality from the first gives the WMON property.
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):