Game Theory

Game Theory 1

Game Theory and Mechanism Design Game theory to analyze strategic behavior: Given a strategic environment (a game ), and an assumption about like behavior (e.g. Nash Equilibrium), we can predict what will happen. Mechanism design flips the problem around How do we set up a strategic environment so that if players follow a certain type of behavior (e.g. Nash Equilibrium), we get a desired outcome? 2

Game Theory A game consists of.. Players i=1, ,n Possible actions for each player: A1, ,An Payoff function for each player: ui(a1, ,an) Game is commonly known to the players. 3

Example C D C 2 , 2 -1 , 4 D 4 , -1 0 , 0 4

Dominant Strategies Defn: Action ai is a dominant strategy for player i for all ai and a-I, ui(ai,a-i) ui(ai ,a-i) In other words, player i has a dominant strategy if she has an action that is optimal regardless of how other players play. 5

Example A B A 4 , 4 0 , 3 B 3 , 0 2 , 2 6

Nash Equilibrium The actionprofile a1, ,an is a Nash Equilibrium if for each player i, and action ai , ui(ai,a-i) ui(ai ,a-i). A Nash Equilibrium means that each player i s action is optimal given the actions of the other players. 7

Incomplete Information What if the player don t know each others payoff functions, e.g. in an auction don t know the valuations of the other bidders? Dominant strategy is still a dominant strategy: best action regardless of what others do. (Bayesian) Nash equilibrium more subtle: each player uses best reply given correct probability assessment of what others will do. 8

Allocation Problems An allocation problem consists of Players i=1, ,n A set of possible outcomes or allocations X, and (possibly) payments by each player p1, ,pn. Payoff function for each player: vi(x) pi Problem in mechanism design is that the designer may not know the payoff functions! 9

Good Allocations In different settings, we will try to define good allocations or outcomes. In auction problems, a good allocation might be one that is Pareto efficient given everyone s values. In matching problems, a good allocation might be one that is stable (to be defined in the next class!). 10

Mechanisms A mechanism consists of A set of possible messages for each player: M1, ,Mn An allocation rule: x(m1, ,mn) A payment rule: p1(m1, ,mn), , pn(m1, ,mn) We will look at mechanisms with and without payments if no payments, ignore the p s. 11

Examples of Mechanisms In auction problems, a type might be a person s value, the messages are the bids, and the auction mechanism says who wins given the bids and what they pay. In matching problems, a type might be a person s preferences, the messages are statements of preferences (not necessarily truthful), and the matching mechanism says who gets matched to whom or what given the stated preferences. 12

Mechanisms and Games A mechanism defines a game The possible actions are the messages: M1, ,Mn The payoffs are a function of the messages ui(m1, ,mn) = vi(x(m1, ,mn)) - pi(m1, ,mn) Sometimes we will focus on direct revelation mechanisms: Mi is equal to the the set of i s possible payoff functions (or equiv. preferences). 13

Strategy-proof Mechanisms A strategy for player i specifies what message to send as a function of player i stype. A mechanism is strategy-proof if each player i has a strategy that is optimal regardless of the strategies chosen by the other players. Sometimes we ll look at mechanisms that are not strategy-proof, but have a Nash equilibrium that generates good outcomes. 14

Applying GT to Market Design Studying existing markets Identify the rules of the game, the incentives for the participants, and how they behave. Then try to understand why the market functions well, or not so well. Designing new markets Identify the economic problem to be solved, the players and their incentives and information. Then try to understand what sort of market rules would lead to a good outcome. Economic theory provides a conceptual framework, but need to use data and experiments to test hypotheses, and identify things models may have missed. 15