There is a set of possible outcomes. There are agents which have different valuations for each outcome. The valuation of agent is represented as a function: which expresses the value it assigns to each alternative. The vector of all value-functions is denoted by. For every agent, the vector of all value-functions of the other agents is denoted by. So. A social choice function is a function that takes as input the value-vector and returns an outcome. It is denoted by or.
In mechanisms without money
A social choice function satisfies the strong monotonicity property if for every agent and every, if: then: . . equivalently:
Necessity
If there exists a strategyproof mechanism without money, with an outcome function, then this function must be SMON. PROOF: Fix some agent and some valuation vector. Strategyproofness means that an agent with real valuation weakly prefers to declare than to lie and declare ; hence: Similarly, an agent with real valuation weakly prefers to declare than to lie and declare ; hence:
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 if for every agent and every, if: then:
Necessity
If there exists a strategyproof mechanism with an outcome function, then this function must be WMON. PROOF: Fix some agent and some valuation vector. A strategyproof mechanism has a price function, that determines how much payment agent receives when the outcome of the mechanism is ; this price depends on the outcome but must not depend directly on. Strategyproofness means that a player with valuation weakly prefers to declare over declaring ; hence: Similarly, a player with valuation weakly prefers to declare over declaring ; hence: 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 :
1. When agents have single peaked preferences, the median social-choice function 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 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.
