Monotonicity (mechanism design)

game-theory 1043 tokens 3 outbound links

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 such a function using a strategyproof mechanism. Its verbal description is:

In other words:

Notation There is a set <math>X</math> of possible outcomes.

There are <math>n</math> agents which have different valuations for each outcome. The valuation of agent <math>i</math> is represented as a function:<math display="block">v_i : X \longrightarrow R_+</math>which expresses the value it assigns to each alternative.

The vector of all value-functions is denoted by <math>v</math>.

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

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

In mechanisms without money <div id="smon" ></div> A social choice function satisfies the strong monotonicity property (SMON) if for every agent <math>i</math> and every <math>v_i,v_i',v_{-i}</math>, if:<math display="block">x = \text{Outcome}(v_i, v_{-i})</math><math display="block">x' = \text{Outcome}(v'_i, v_{-i})</math>then:<math display="block">x \succeq_i x'</math> (by the initial preferences, the agent prefers the initial outcome).<math display="block">x \preceq_{i'} x'</math> (by the final preferences, the agent prefers the final outcome). Or equivalently:<math display="block">v_i(x) - v_i(x') \geq 0</math><math display="block">v_i'(x) - v_i'(x') \leq 0</math>

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

PROOF: Fix some agent <math>i</math> and some valuation vector <math>v_{-i}</math>. Strategyproofness means that an agent with real valuation <math>v_i</math> weakly prefers to declare <math>v_i</math> than to lie and declare <math>v_i'</math>; hence: <math display="block">v_i(x) \geq v_i(x')</math>Similarly, an agent with real valuation <math>v_i'</math> weakly prefers to declare <math>v_i'</math> than to lie and declare <math>v_i</math>; hence:<math display="block">v_i'(x') \geq v_i'(x)</math>

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 <math>i</math> and every <math>v_i,v_i',v_{-i}</math>, if:<math display="block">x = \text{Outcome}(v_i, v_{-i})</math><math display="block">x' = \text{Outcome}(v'_i, v_{-i})</math>then:<math display="block">v_i(x) - v_i(x') \geq v_i'(x) - v_i'(x')</math>

Necessity If there exists a strategyproof mechanism with an outcome function <math>\text{Outcome}</math>, then this function must be WMON.

PROOF:

Examples # 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 voting rule. # 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. # In 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.

Monotonicity (mechanism design)