Introduction to Game Theory and Mechanism Design

What is Game Theory and Mechanism Design?

Game theory is broadly about mathematical modeling of strategic behavior between rational decision makers. A game is defined by: a set of players, with corresponding utility functions and actions, and a payoff function that maps player actions to outcomes. Players always have the incentive to maximize utility. By assuming rationality as common knowledge among the players, we can analyze equilibrium states of the game. Formally, an equilibrium is a configuration of player actions where no player has an incentive to change their action.

At a high level game theory assumes incentives and evaluates outcomes. Mechanism design flips the question: we assume a desirable outcome space and consider incentive schemes that lead to such outcomes.

Arguably, the most famous example of a mechanism is the second price auction. Here, players bid for a single item. The desirable outcome is that players bid their true value for the item. The mechanism is that the highest bidder wins, but only pays the price of the second highest bidder. Omitting a formal game theoretic analysis, this implies that rational players will always bid their true valuation.

What are some practical applications today?

Mechanism design is a cornerstone of crypto systems, both in theory and practice. The most primitive example is the Nakamoto consensus algorithm: the desirable outcome is that miners avoid forks in the blockchain and always reject invalid transactions. The mechanism is that miners receive block rewards when they mine blocks on the longest chain. Since miners assume other miners are rational, they will always mine on the branch with valid transactions that has the most work put into it. Abstractly, this is an example of a Schelling game where the focal point is the valid transactions branch.

Another example of this Schelling mechanism is with p2p oracle systems like TruthCoin. Here, the desired outcome is for a group of voters to come to consensus around the truth. The mechanism is that voters are rewarded when they vote in line with the consensus outcome. Since the truth is a focal point of this game, voters will assume that others come to consensus about the truth, so to receive the reward they should also vote the truth.

There are countless other examples in crypto where mechanism design is important. Here is a far from exhaustive list:

  • Tokenomics
  • Quadratic funding and voting
  • Analysis of competing incentives, e.g. between incentives of staking and on chain lending.
  • Tooling for game theoretic analysis and agent based simulation
  • Attacks on existing mechanisms