It is assumed that the agents have Quasilinear utility functions; this means that, if the outcome is and in addition the agent receives a payment (positive or negative), then the total utility of agent is: 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 mechanism is a pair of functions: An function, that takes as input the value-vector and returns an outcome (it is also called a social choice function); A function, that takes as input the value-vector and returns a vector of payments, , determining how much each player should receive (a negative payment means that the player should pay a positive amount). A mechanism is called strategyproof if, for every player and for every value-vector of the other players : Characterization It is helpful to have simple conditions for checking whether a given mechanism is SP or not. This subsection shows two simple conditions that are both necessary and sufficient. If a mechanism is SP, then it must satisfy the following two conditions, for every agent : 1. The payment to agent is a function of the chosen outcome and of the valuations of the other agents - but not a direct function of the agent's own valuation . Formally, there exists a price function , that takes as input an outcome and a valuation vector for the other agents , and returns the payment for agent , such that for every , if: then: PROOF: If then an agent with valuation prefers to report , since it gives him the same outcome and a larger payment; similarly, if then an agent with valuation prefers to report . As a corollary, there exists a "price-tag" function, , that takes as input an outcome and a valuation vector for the other agents , and returns the payment for agent For every , if: then: 2. The selected outcome is optimal for agent , given the other agents' valuations. Formally: where the maximization is over all outcomes in the range of . PROOF: If there is another outcome such that , then an agent with valuation prefers to report , since it gives him a larger total utility. Conditions 1 and 2 are not only necessary but also sufficient: any mechanism that satisfies conditions 1 and 2 is SP. PROOF: