aadl intro game theory 20070715

Figure it Out!An Introduction to Game Theory: 

Figure it Out! An Introduction to Game Theory Professor Yan Chen School of Information University of Michigan

Outline: 

Outline What is a game? History of game theory Best response and Equilibrium Auction Experiments Online Auction Design School Choice

It’s Your Move: 

It’s Your Move

It’s Your Move: 

It’s Your Move

It’s Your Move: 

It’s Your Move

It’s Your Move: 

It’s Your Move

Problems of strategic choice: 

Problems of strategic choice The consequences of choices often depend on choices by others Even when people like each other or are partners (social or business) they may have different interests Good problem solving requires strategic thought: “If I do X, what will my competitor / spouse / boss do?”

What is a game?: 

What is a game? A game is being played whenever solving a problem requires people to interact with strategic awareness Bidding in an auction Adoption of a new technology standard Cuban missile crisis What is not a game? When strategic awareness of others not important N = 1: What novel should I read next? N = infinity: (large) markets

Strategic choice tool: Game theory: 

Strategic choice tool: Game theory Short history of game theory: Cournot (1838) and Edgeworth (1881) Zermelo (1913): chess-like games can be solved in a (large!) finite number of moves von Neumann and Morgenstern (1944) Expected utility theory, zero-sum games, cooperative games, backwards induction Nash, Harsanyi, Selten: 1994 Nobel Prize for solution concepts in non-cooperative game theory Aumann and Schelling : 2005 Nobel Prize for game theoretic analysis of conflict and cooperation

Strategic choice tool: Game theory: 

Strategic choice tool: Game theory Game theory has been applied to sociology, economics, political science, decision theory, law, evolutionary biology, experimental psychology, military strategy, anthropology … Where is game theory going to? Behavioral; evolutionary; … In the abstract, games can describe most multi-agent decision problems

Problem representation: strategic form: 

Problem representation: strategic form One way to summarize the problem Example: Prisoners’ Dilemma Set of players: N = {Conductor, Tchaikovsky} Information: common knowledge Timing: simultaneous move Set of strategies: Si = {Confess, Not Confess} Set of payoffs: If one confesses, the other does not: 0, 15 years in jail If both confess: each gets 5 years in jail If neither confess: each gets 1 year in jail

Strategic form: Prisoners’ Dilemma: 

Strategic form: Prisoners’ Dilemma Tchaikovsky Conductor

Solving games?: 

Solving games? For strategic problems, rational choice depends on choices made by others The main tool is to find an equilibrium: a set of choices by all agents that are mutually rational There are many different definitions of “rational”, depending on the particulars of the strategic problem We call the process of finding a reasonable equilibrium “solving the game”

Solving a strategic form game: Best response?: 

Solving a strategic form game: Best response? A strategy is a best response to a particular strategy of another player, if it gives the highest payoff against that particular strategy Is knowing best reply sufficient to find strategic equilibrium?

Best reply: Prisoners’ Dilemma: 

Best reply: Prisoners’ Dilemma Tchaikovsky Conductor

Dominant strategy equilibrium: 

Dominant strategy equilibrium A mild rationality concept: Dominant strategy axiom: If a player has a dominant strategy, she will use it Mild: Dominant strategy gets player best payoff possible no matter what others do If every player has a dominant strategy, the game has a dominant strategy equilibrium (solution) Problem with dominant strategy equilibrium: in many games there does not exist one

Dominance: Prisoners’ Dilemma: 

Dominance: Prisoners’ Dilemma Tchaikovsky Conductor

Efficiency and equilibrium: 

Efficiency and equilibrium Game equilibrium is a characterization of the outcome of individually rational behavior Because of strategic interactions, rational behavior does not always lead to outcomes that are mutually the best Dominant strategy equilibrium in Prisoner’s Dilemma: (Confess, Confess) But this is not socially efficient: both players are better off with (Not Confess, Not Confess) Many applications Arms race Tragedy of commons

What to do when equilibrium is inefficient?: 

What to do when equilibrium is inefficient? Can’t always be improved (arms race not an easy problem!) Opportunities: Collude / cooperate (sometimes illegal!) OPEC marriage Might involve side payments if not win-win Design systems to increase trust Repeated interactions Build trust Or create opportunities for punishment!

Game Theory and Auctions: 

Game Theory and Auctions We will run four auction experiments Assistant: Marco Lorenzon 4-th grader in September: King Elementary School

‘Sniping’ and the Rule for Ending Second-Price Internet Auctions: 

‘Sniping’ and the Rule for Ending Second-Price Internet Auctions Source: Axel Ockenfels and Alvin Roth

– Facts and rules : 

– Facts and rules Auctions on the Web for individuals. 14 million auctions at each time in 4.300 categories. 58 million registered users. 40 bids and $2,000 sales per second.

Second price rule: 

Second price rule Bidders may submit ‘maximum bids’ during one week. Auctions end with a ‘hard close’. The highest maximum bid wins. The price is an increment over the second highest bid.

How much and when to bid on eBay?: 

How much and when to bid on eBay? “eBay always recommends bidding the absolute maximum that one is willing to pay for an item early in the auction.” (eBay.com, 2002)

The Puzzle: 

The Puzzle

Slide28: 

last bid came in at the last second

Cumulative distributions of auctions’ last bids on eBay : 

Cumulative distributions of auctions’ last bids on eBay

The timing of bids: A puzzle: 

The timing of bids: A puzzle “Sniping can not be consistent with the presence of private values.” (Bajari and Hortacsu, 2000) “ ... maybe eBay just makes me giddy …” (Landsburg, 1999) “ …a particularly intriguing puzzle …” (Varian, 2000) … maybe bidders are just indifferent? …

The dangers of sniping : 

The dangers of sniping eBay’s view (2002) “… if you had bid your maximum amount up front … the outcome would not be based on time.” A seller’s view (Axis Mundi, 1999) “Almost without fail after an auction has closed we receive emails from bidders who claim they were attempting to place a bid and were unable to get into eBay. … All we can do in this regard is to urge you to place your bids early.”

Why Sniping?: 

Why Sniping?

Theorem 1: Sniping in private value auctions: 

Theorem 1: Sniping in private value auctions In a private value auction model, sniping can occur in perfect Bayesian equilibria as implicit collusion. “… the essential intuition of the Ockenfels-Roth analysis: bidding high at the last minute and letting chance determine the outcome is better for both players than bidding high early and precipitating a bidding war.” Hal Varian,

Varian’s example: 

Varian’s example Two bidders bid on a pez dispenser. Same value v > 0. The seller‘s reservation price is zero. If both bid v at t < 1, payoffs are zero. If both bid at t = 1, payoffs are p(1-p)v > 0 Any early bid starts a bidding war yielding zero payoffs. (Credible, because an early bidding war is an equilibrium.)

Theorem 2:Sniping in common value auctions: 

Theorem 2: Sniping in common value auctions In a common value auction model, sniping can occur in perfect Bayesian equilibria to protect information. ‘Uninformed’ bidders can incorporate into their bids the information they have gathered from the earlier bids of others. ‘Informed’ bidders can avoid giving information to ‘uninformed’ bidders through their own early bids.

Theorem 3: Sniping as a best response to incremental bidding: 

Theorem 3: Sniping as a best response to incremental bidding Out of equilibrium, sniping can occur as a best response to (‘naive’) incremental bidding. Bidding late would not give the incremental bidder sufficient time to respond. A sniper competing with an incremental bidder might win the auction at the incremental bidder’s initial (low) bid.

Market Design: 

Market Design

Is Amazon’s soft close a solution?: 

Is Amazon’s soft close a solution? “We know that bidding may get hot and heavy near the end of many auctions. Our Going, Going, Gone feature ensures that you always have an opportunity to challenge last-second bids. Here's how it works: whenever a bid is cast in the last 10 minutes of an auction, the auction is automatically extended for an additional 10 minutes from the time of the latest bid. This ensures that an auction can't close until 10 ‘bidless’ minutes have passed.“ [Amazon.com, 2002]

Theorem 4: Amazon’s soft close: 

Theorem 4: Amazon’s soft close In our models, the advantages of sniping are eliminated but the risk remains. As a consequence, sniping (bidding at t = 1) does not occur in perfect Bayesian equilibria.

A Natural Experiment: 

A Natural Experiment

Cumulative distribution of auctions’ last bids over time : 

Cumulative distribution of auctions’ last bids over time More experienced bidders on eBay bid later, while experience in Amazon has the opposite effect.

Summary:  Internet Auction Design: 

Summary: Internet Auction Design Strategic behavior (Subtle) Strategic incentives substantially affect behavior and outcomes. Robust incentives Sniping is a rational strategy against sophisticated bidders and against naive inexperienced bidders. Market design Ceteris paribus a hard close appears to reduce revenues and efficiency.

Game Theory and  the School Choice Problem: 

Game Theory and the School Choice Problem In a school choice problem, there are a number of students each of whom should be assigned a seat at one of a number of schools Each student has strict preferences over all schools Each school has a maximum capacity and a strict priority ordering of all students

Boston Mechanism: 

Boston Mechanism Each student submits a ranking of schools Each school generates a priority ordering of students based on state and local laws (e.g., walk zone, sibling, etc.) Student assignment based on submitted preference ranking and priorities in several rounds

Boston Mechanism: Assignment Phase: 

Boston Mechanism: Assignment Phase Round 1: only the 1st choices of the students are considered. For each school, consider the students who have listed it as their 1st choice and assign seats of the school to these students one at a time following their priority order until either there are no seats left or there is no student left who has listed it as her first choice. Round k: kth choices of the students, following priority order

Boston Mechanism: Properties: 

Boston Mechanism: Properties Truth telling is not a dominant strategy: students might benefit from misrepresenting their preferences by improving ranking of schools for which they have high priority: The Minneapolis algorithm places a very high weight on the first choice, with second and third choices being strictly backup options.This is reflected in the advice CPAC gives out to parents, which is to make the first choice a true favorite and the other two “realistic”, that is, strategic choices. - Glazerman and Meyer (1994)

Boston Mechanism: Properties: 

Boston Mechanism: Properties More manipulation advice: St. Petersburg Times (September 14, 2003) Make a realistic, informed selection on the school you list as your first choice. It's the cleanest shot you will get at a school, but if you aim too high you might miss. Here's why: If the random computer selection rejects your first choice, your chances of getting your second choice school are greatly diminished. That's because you then fall in line behind everyone who wanted your second choice school as their first choice. You can fall even farther back in line as you get bumped down to your third, fourth and fifth choices.

Boston Mechanism: Properties: 

Boston Mechanism: Properties Not Pareto efficient Not stable: Justified envy: if there is a student-school pair (i, s) such that Student i prefers school s to her assignment Student i has higher priority at school s than some other student who is assigned a seat at school s Problem: legal actions Boston’s Children First, et al. v. Boston School Committee (January 25, 2002)

Gale-Shapley Mechanism: 

Gale-Shapley Mechanism Each student submits a ranking of schools Each school generates a priority ordering of students based on state and local laws (e.g., walk zone, sibling, etc.) Student assignment based on submitted preference ranking and priorities in several rounds

Gale-Shapley: Assignment: 

Gale-Shapley: Assignment Round 1: Each student proposes to her 1st choice. Each school rejects the lowest priority students in excess of its capacity and keeps the remaining students on hold Round k: Each student who was rejected in the previous rounds proposes to her next choice. Each school considers the students it has been holding together with its new proposers; it rejects the lowest priority students in excess of its capacity and keeps the remaining students on hold Algorithm terminates when no student is rejected and each student is assigned a seat at her final tentative assignment.

Gale-Shapley: Properties: 

Gale-Shapley: Properties Truth telling is a dominant strategy: students have no incentive to misrepresent their preferences Stable: eliminates justified envy Constrained efficient: Pareto efficiency incompatible with stability Gale-Shapley Pareto dominates any other mechanism which eliminates justified envy

Game Theory and Public Policy: 

Game Theory and Public Policy New York City High Schools: switched to the Gale-Shapley mechanism in fall 2004 Boston School Committee voted to replace the Boston mechanism with Gale-Shapley in July 2005

Game Theory Readings: 

Game Theory Readings Dixit and Nalebuff:Thinking Strategically Fun, intuitive, journalistic International best seller No practice problems Dutta: Strategies and Games: Theory and Practice Precise lot of practice problems