Strategyproof
Encyclopedia
In game theory
, an asymmetric game
where players have private information
is said to be strategyproof (or truthful) if there is no incentive for any of the players to lie about or hide their private information from the other players.
The strategyproof concept has applications in several areas of game theory and economics
. For example, payment schemes for network routing. 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. 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 strategyproof, 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), there do exist strategyproof payment schemes. An important one is the Vickrey–Clarke–Groves (VCG) scheme.
Strategyproofness is also known as Dominant Strategy Incentive Compatibility.
See also:
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, an asymmetric game
Symmetric game
In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric. ...
where players have private information
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...
is said to be strategyproof (or truthful) if there is no incentive for any of the players to lie about or hide their private information from the other players.
The strategyproof concept has applications in several areas of game theory and economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
. For example, payment schemes for network routing. Consider a network as a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
where each edge (i.e. link) has an associated cost
Cost
In production, research, retail, and accounting, a cost is the value of money that has been used up to produce something, 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 is counted as cost. In this...
of transmission
Transmission (telecommunications)
Transmission, in telecommunications, is the process of sending, propagating and receiving an analogue or digital information signal over a physical point-to-point or point-to-multipoint transmission medium, either wired, optical fiber or wireless...
, 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 strategyproof, 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), there do exist strategyproof payment schemes. An important one is the Vickrey–Clarke–Groves (VCG) scheme.
Strategyproofness is also known as Dominant Strategy Incentive Compatibility.
See also:
- Incentive compatibilityIncentive compatibilityIn mechanism design, a process is said to be incentive-compatible if all of the participants fare best when they truthfully reveal any private information asked for by the mechanism. As an illustration, voting systems which create incentives to vote dishonestly lack the property of incentive...
- Individual rationality: a player can choose whether or not to participate; in other words, the link will not relay a message if the payment is less than the cost.