In
mechanism design
Mechanism design (sometimes implementation theory or institution design) is a branch of economics and game theory. It studies how to construct rules—called Game form, mechanisms or institutions—that produce good outcomes according to Social ...
, a strategyproof (SP) mechanism is a
game form
In game theory and related fields, a game form, game frame, ruleset, or outcome function is the set of rules that govern a game and determine its outcome based on each player's choices. A game form differs from a game in that it does not stipulate ...
in which each player has a weakly-
dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. 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.
An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC),
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.
Examples
Typical examples of SP mechanisms are:
* a
majority vote
A majority is more than half of a total; however, the term is commonly used with other meanings, as explained in the "#Related terms, Related terms" section below.
It is a subset of a Set (mathematics), set consisting of more than half of the se ...
between two alternatives;
* a
second-price auction when participants have
quasilinear utility;
* a
VCG mechanism when participants have
quasilinear utility
Typical examples of mechanisms that are ''not'' SP are:
*
any deterministic non-dictatorial election between three or more alternatives;
* a
first-price auction
SP in network routing
SP is also applicable in
network routing. Consider a network as a
graph where each edge (i.e. link) has an associated
cost
Cost is the value of money that has been used up to produce something or deliver a service, and hence is not available for use anymore. In business, the cost may be one of acquisition, in which case the amount of money expended to acquire it i ...
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. There are efficient methods for doing so, even in large networks. However, there is one problem: the costs for each link are unknown. A naive approach would be to ask the owner of each link the cost, use these declared costs to find the least cost path, and pay all links on the path their declared costs. 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. We may end up paying far more than the actual 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.
Formal definitions
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 has for each alternative, in monetary terms.
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 with monetary transfers 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:
: ]