When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player.
[1]: 244 An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC),[1]: 415 to distinguish it from other kinds of incentive compatibility.
A SP mechanism is immune to manipulations by individual players (but not by coalitions).
In contrast, in a group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes every member better off.
In a strong group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off.
[citation needed] Consider a network as a graph where each edge (i.e. link) has an associated cost of transmission, privately known to the owner of the link.
The owner of a link wishes to be compensated for relaying messages.
As the sender of a message on the network, one wants to find the least cost path.
However, it can be shown that this payment scheme is not SP, that is, the owners of some links can benefit by lying about the cost.
It can be shown that given certain assumptions about the network and the players (owners of links), a variant of the VCG mechanism is SP.
is represented as a function: which expresses the value it has for each alternative, in monetary terms.
It is assumed that the agents have Quasilinear utility functions; this means that, if the outcome is
(positive or negative), then the total utility of agent
: 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 with monetary transfers is SP, then it must satisfy the following two conditions, for every agent
is a function of the chosen outcome and of the valuations of the other agents
Denote: 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.
[citation needed] The monotonicity property is necessary for strategyproofness.
[citation needed] A single-parameter domain is a game in which each player
For this setting, it is easy to characterize truthful mechanisms.
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.
A normalized mechanism on a single-parameter domain is truthful if the following two conditions hold:[1]: 229–230 There are various ways to extend the notion of truthfulness to randomized mechanisms.
, a randomized mechanism is called truthful with probability
goes to 0 when the number of bidders grows, then the mechanism is called truthful with high probability.
This notion is weaker than full truthfulness, but it is still useful in some cases; see e.g. consensus estimate.
A new type of fraud that has become common with the abundance of internet-based auctions is false-name bids – bids submitted by a single bidder using multiple identifiers such as multiple e-mail addresses.
False-name-proofness means that there is no incentive for any of the players to issue false-name-bids.
[4] False-name-proofness is importantly different from group strategyproofness because it assumes that an individual alone can simulate certain behaviors that normally require the collusive coordination of multiple individuals.