Fix an agent and valuations . Denote: - the outcome when the agent acts truthfully. - the outcome when the agent acts untruthfully. By property 1, the utility of the agent when playing truthfully is: and the utility of the agent when playing untruthfully is: By property 2: so it is a dominant strategy for the agent to act truthfully. Outcome-function characterization The actual goal of a mechanism is its function; the payment function is just a tool to induce the players to be truthful. Hence, it is useful to know, given a certain outcome function, whether it can be implemented using a SP mechanism or not (this property is also called implementability). The Monotonicity (mechanism design) property is necessary, and often also sufficient. Truthful mechanisms in single-parameter domains A single-parameter domain is a game in which each player gets a certain positive value for "winning" and a value 0 for "losing". A simple example is a single-item auction, in which is the value that player assigns to the item. For this setting, it is easy to characterize truthful mechanisms. Begin with some definitions. A mechanism is called normalized if every losing bid pays 0. A mechanism is called monotone if, when a player raises his bid, his chances of winning (weakly) increase. For a monotone mechanism, for every player i and every combination of bids of the other players, there is a critical value in which the player switches from losing to winning. A normalized mechanism on a single-parameter domain is truthful iff the following two conditions hold: The assignment function is monotone in each of the bids, and: Every winning bid pays the critical value. Truthfulness of randomized mechanisms There are various ways to extend the notion of truthfulness to randomized mechanisms. They are, from strongest to weakest: Universal truthfulness: for each randomization of the algorithm, the resulting mechanism is truthful. In other words: a universally-truthful mechanism is a randomization over deterministic truthful mechanisms, where the weights may be input-dependent. Strong stochastic-dominance truthfulness (strong-SD-truthfulness): The vector of probabilities that an agent receives by being truthful has first-order stochastic dominance over the vector of probabilities he gets by misreporting. That is: the probability of getting the top priority is at least as high AND the probability of getting one of the two top priorities is at least as high AND ... the probability of getting one of the m