Game Theory and Applications A Friendly Tutorial June 2, 2009 Y.

Game Theory and Applications A Friendly Tutorial June 2, 2009 Y. NARAHARI (IISc), DINESH GARG (Yahoo! Labs) , RAMASURI NARAYANAM (IISc) E-Commerce Laboratory Computer Science and Automation Indian Institute of Science, Bangalore 1 E-Commerce Lab, CSA, IISc

Talk Based on Y. Narahari, Dinesh Garg, Rama Suri, Hastagiri Prakash Game Theoretic Problems in Network Economics and Mechanism Design Solutions Monograph Published by Springer, London, 2009 2 E-Commerce Lab, CSA, IISc

OUTLINE Strategic Form Games, Examples, Dominant Strategy Equilibrium, Nash Equilibrium, Key Results Mechanism Design and Application to Auctions Application to Design of Sponsored Search Auctions on the Web Cooperative Games, Shapley Value, Application to Social Networks To Probe Further 3 E-Commerce Lab, CSA, IISc

Inspiration: John von Neumann Founded Game Theory with Oskar Morgenstern (1928-44) Pioneered the Concept of a Digital Computer and Algorithms 60 years later (2000), there is a convergence; this has been the John von Neumann (1903-1957) inspiration for our created two intellectual currents research in the 1930s and 40s 4 E-Commerce Lab, CSA, IISc

Robert Aumann Nobel 2005 Excitement: The Nobel Prizes in Economic Sciences Leonid Hurwicz Nobel 2007 The Nobel Prize was awarded to two Game Theorists in 2005 – Aumann visited IISc on January 16, 2007 The prize was awarded to three mechanism designers in 2007 Thomas Schelling Nobel 2005 Myerson has been one of our heroes since 2003 Eric Maskin Nobel 2007 Eric Maskin visited IISc on December 16, 2009 and gave a talk in the Centenary Conference Roger Myerson Nobel 2007 5 E-Commerce Lab, CSA, IISc

Applications of Game Theory Microeconomics, Sociology, Evolutionary Biology Auctions and Market Design: Spectrum Auctions, Procurement Markets, Double Auctions Industrial Engineering, Supply Chain Management, E-Commerce, Resource Allocation Computer Science: Algorithmic Game Theory, Internet and Network Economics, Protocol Design An important tool to model, analyze, and solve decentralized design problems involving multiple autonomous agents that interact strategically 6 E-Commerce Lab, CSA, IISc

MOTIVATING PROBLEMS Indirect Materials Procurement at Intel (2000) Direct Materials Procurement at GM (2002) Network Formation Problems at GM (2003) Infosys (2006), and IBM (2006) Sponsored Search Auctions on the Web (2006-09) Optimal solutions translate into significant benefits 7 E-Commerce Lab, CSA, IISc

Problem 1: Direct Materials Procurement at IISc SUPPLIER 1 SUPPLIER 2 Buyer 1,00,000 units of raw material SUPPLIER 3 Supply Curves Incentive Compatible Procurement Auction with Volume Discounts Even 1 percent improvement could translate into millions of rupees

PROBLEM 2: Supply Chain Network Formation Supply Chain Network Planner X2 X1 X3 X4 n Y X i Stage Manager 9 i 1 E-Commerce Lab, CSA, IISc

Abstraction: Shortest Path Problem with Incomplete Information SP1 S SP3 SP3 A B C SP4 SP5 T SP6 The costs of the edges are not known with certainty 10 E-Commerce Lab, CSA, IISc

PROBLEM 3: Sponsored Search Auction 1 2 n CPC Advertisers Paid search auction is the leading revenue generator on the web 11 E-Commerce Lab, CSA, IISc

NATURE OF THESE PROBLEMS All these are optimization problems with incomplete information Problem solving involves two phases: (1) Preference Elicitation (2) Preference Aggregation Preference Elicitation – Game Theory and Mechanism Design Preference Aggregation – Optimization Theory and algorithms Other mathematical paraphernalia are also needed 12 E-Commerce Lab, CSA, IISc

KEY OBSERVATIONS Players are rational, Intelligent, strategic Both conflict and cooperation are “issues” Some information is “common knowledge” Other information is “private”, “incomplete”, “distributed” Our Goal: To implement a system wide solution (social choice function) with desirable properties Game theory is a natural choice for modeling such problems 13 E-Commerce Lab, CSA, IISc

Game Theory Mathematical framework for rigorous study of conflict and cooperation among rational, intelligent agents Market Buying Agents (rational and intelligent) 14 Social Planner (Mechanism Designer) Selling Agents (rational and intelligent) E-Commerce Lab, CSA, IISc

Strategic Form Games (Normal Form Games) S1 Sn N {1, ,n} Players U1 : S R Un : S R S1, , Sn Payoff functions Strategy Sets (Utility functions) S S1 X X S n 15 E-Commerce Lab, CSA, IISc

Example 1: Matching Pennies 1, -1 -1,1 -1,1 1,-1 Two players simultaneously put down a coin, heads up or tails up. Two-Player zero-sum game N {1, 2}; S1 S2 {H,T} 16 E-Commerce Lab, CSA, IISc

Example 2: Prisoner’s Dilemma 17 No Confess NC Confess C No Confess NC - 2, - 2 - 10, - 1 Confess C -1, - 10 - 5, - 5 E-Commerce Lab, CSA, IISc

Example 3: Coordination Game B IISc MG Road IISc 100,100 0,0 MG Road 0,0 10,10 A Models the strategic conflict when two players have to choose their priorities 18 E-Commerce Lab, CSA, IISc

Dominant Strategy Equilibrium A dominant strategy is a best response whatever the strategies of the other players No Confess NC Confess C No Confess NC - 2, - 2 - 10, - 1 Confess C -1, - 10 - 5, - 5 (C,C) is a dominant strategy equilibrium 19 E-Commerce Lab, CSA, IISc

Pure Strategy Nash Equilibrium A profile of strategies s1* , s 2* ,., s n* is said to be a pure strategy Nash Equilibrium if si* is a best response strategy against s *i i 1,2,., n 20 E-Commerce Lab, CSA, IISc

Nash Equilibrium A Nash equilibrium strategy is a best response against the Nash equilibrium strategies of the other players No Confess Confess NC C No Confess NC - 2, - 2 - 10, - 1 Confess C -1, - 10 - 5, - 5 (C,C) is a Nash equilibrium Every DSE is a NE but not vice-versa 21 E-Commerce Lab, CSA, IISc

Equilibria in Matching Pennies (1,-1) (-1,1) (-1,1) (1,-1) No pure strategy NE here, only a mixed strategy NE 22 E-Commerce Lab, CSA, IISc

Equilibria in Coordination Game B IISc MG Road IISc 100,100 0,0 MG Road 0,0 10,10 A Two pure strategy Nash equilibria and one mixed strategy Nash equilibrium 23 E-Commerce Lab, CSA, IISc

Nash’s Theorem Every finite strategic form game has at least one mixed strategy Nash equilibrium Mixed strategy of a player ‘i’ is a probability distribution on Si . * 1 , 2* ,., n* is a mixed strategy Nash equilibrium if i* is a best response against 24 i 1,2,., n *i , E-Commerce Lab, CSA, IISc

GAME THEORY PIONEERS John Nash Jr 1928 Nobel 1994 Robert Aumann 1930 Nobel 2005 25 John Harsanyi 1920 - 2000 Nobel 1994 Thomas Schelling 1921 Nobel 2005 Richard Selten 1930 Nobel 1994 Lloyd Shapley 1923 Nobel ? E-Commerce Lab, CSA, IISc

MECHANISM DESIGN Game Theory involves analysis of games – computing NE, DSE, MSNE, etc and analyzing equilibrium behaviour Mechanism Design is the design of games or reverse engineering of games; could be called Game Engineering Involves inducing a game among the players such that in some equilibrium of the game, a desired social choice function is implemented 26 E-Commerce Lab, CSA, IISc

Example 1: Mechanism Design Fair Division of a Cake Mother Social Planner Mechanism Designer Kid 1 Rational and Intelligent Kid 2 Rational and Intelligent

Example 2: Mechanism Design Truth Elicitation through an Indirect Mechanism Tenali Rama (Birbal) Mechanism Designer Mother 1 Rational and Intelligent Player Baby Mother 2 Rational and Intelligent Player

MECHANISM DESIGN: EXAMPLE 3 : VICKREY AUCTION One Seller, Multiple Buyers, Single Indivisible Item Example: B1: 40, B2: 45, B3: 60, B4: 80 Winner: whoever bids the highest; in this case B4 Payment: Second Highest Bid: in this case, 60. Vickrey showed that this mechanism is Dominant Strategy Incentive Compatible (DSIC) ;Truth Revelation is good for a player irrespective of what other players report 29 E-Commerce Lab, CSA, IISc

William Vickrey (1914 – 1996 ) Inventor of the celebrated Vickrey auction Nobel Prize : 1996 30 E-Commerce Lab, CSA, IISc

Four Basic Types of Auctions Dutch Auction English Auction 1 0, 10, 20, 30, 40, 45, 50, 55, 58, 60, stop. n Seller 1 40 2 50 3 55 4 60 Buyers Vickrey Auction 40 1 Winner 4 Price 60 n Buyers First Price Auction 31 100, 90, 85, 75, 70, 65, 60, stop. Auctioneer or seller Buyers 1 2 45 3 60 4 80 Winner 4 Price 60 Buyers E-Commerce Lab, CSA, IISc

Social Choice Function (SCF) n 2 1 2 1 1 n 2 n f : 1 n X x X 32 x f 1, , n E-Commerce Lab, CSA, IISc

Mechanism 1 C1 C2 2 1 c1 n Cn 2 n c2 cn g : C1 Cn X x X 33 x g c1, , c n u1 : X 1 u 2 : X 2 un : X n u1 x, 1 u 2 x, 2 u n x, n E-Commerce Lab, CSA, IISc

Implementing an SCF Dominant Strategy Implementation We say that mechanism M g (.), (Ci ) i N implements SCF f : X in dominant strategy equilibrium if g s1d ( 1 ), snd ( n ) f ( 1 , , n ) ( 1 , , n ) Bayesian Nash Implementation We say that mechanism M g (.), (Ci ) i N implements SCF f : X in Bayesian Nash equilibrium if g s1* ( 1 ), sn* ( n ) f ( 1 , , n ) ( 1 , , n ) Observation Dominant Strategy-implementation 34 Bayesian Nash- implementation E-Commerce Lab, CSA, IISc

PROPERTIES OF SOCIAL CHOICE FUNCTIONS DSIC (Dominant Strategy Incentive Compatibility) Reporting Truth is always good AE (Allocative Efficiency) Allocate items to those who value them most Non-Dictatorship No single agent is favoured all the time 35 BIC (Bayesian Nash Incentive Compatibility) Reporting truth is good whenever others also report truth BB (Budget Balance) Payments balance receipts and No losses are incurred Individual Rationality Players participate voluntarily since they do not incur losses E-Commerce Lab, CSA, IISc

IMPOSSIBILITY THEOREMS Arrow’s Impossibility Theorem Green Laffont Impossibility Theorem 36 Gibbard Satterthwaite Impossibility Theorem Myerson Satterthwaite Impossibility Theorem E-Commerce Lab, CSA, IISc

PIONEERS IN MECHANISM DESIGN Leonid Hurwicz Nobel 2007 37 Eric Maskin Nobel 2007 Roger Myerson Nobel 2007 E-Commerce Lab, CSA, IISc

WBB SBB EPE dAGVA GROVES AE DSIC BIC MECHANISM DESIGN SPACE 38 MYERSON CBOPT SSAOPT VDOPT IR E-Commerce Lab, CSA, IISc

Application to Sponsored Search Auction 1 2 n CPC Advertisers Paid search auction is the leading revenue generator on the web 39 E-Commerce Lab, CSA, IISc

Cooperative Game with Transferable Utilities (TU Games) T ( N , v ) N {0,1,., n} setof players N v : 2 characteri stic function ; v( ) 0 C N is called a coalition . There are 2 N 1 possible coalitions

Given a TU game, two central questions are: Which coalition(s) should form ? How should a coalition that forms divide the surplus among its members ? Cooperative game theory offers several solution concepts: The Core Shapley Value

Divide the Dollar Game There are three players who have to share 300 dollars. Each one proposes a particular allocation of dollars to players. N {0,1,2} S 0 S1 S 2 {( x0 , x1 , x2 ) 3 : x1 0; x2 0; x3 0; x0 x1 x2 300}

Divide the Dollar : Version 1 The allocation is decided by what is proposed by player 0 ui ( s0 , s1 , s2 ) xi 0 if s0 ( x0 , x1 , x2 ) otherwise Apex Game or Monopoly Game Characteristic Function v({0}) 300 v({1}) v({2}) v({1,2}) 0 v({0,1}) v({0,2}) v({0,1,2}) 300

Divide the Dollar : Version 2 It is enough 0 and 1 propose the same allocation ui ( s0 , s1 , s2 ) xi 0 if s0 s1 ( x0 , x1 , x2 ) otherwise Players 0 and 1 are equally powerful; Characteristic Function is: v({0}) v({1}) v({2}) 0 v({0,1}) 300 v({0,2}) v({1,2}) 0 v({0,1,2}) 300

Divide the Dollar : Version 3 Either 0 and 1 should propose the same allocation or 0 and 2 should propose the same allocation ui ( s0 , s1 , s2 ) xi 0 if s0 s1 ( x0 , x1 , x2 ) or s0 s2 ( x0 , x1 , x2 ) otherwise Characteristic Function v({0}) v({1}) v({2}) v({1,2}) 0 v({0,1}) v({0,2}) v({0,1,2}) 300

Divide the Dollar : Version 4 It is enough any pair of players has the same proposal ui ( s0 , s1 , s2 ) xi if s0 s1 ( x0 , x1 , x2 ) or s0 s2 ( x0 , x1 , x2 ) or s1 s2 ( x0 , x1 , x2 ) 0 otherwise Also called the Majority Voting Game Characteristic Function v({0}) v({1}) v({2}) 0 v({0,1}) v({0,2}) v({1,2}) v({0,1,2}) 300

The Core Let N {0,1,., n} Core of (N, v) is the collection of all allocations (x0 , x1 , , xn) satisfying: Individual Rationality Coalitional Rationality Collective Rationality xi v({i}) i N C N , x i v(C ) i C x0 x1 . xn v( N )

The Core: Examples Version of Divide-the-Dollar Core {(300,0,0)} Version 1 Version 2 {( x0 , x1 ,0) : x0 0; x1 0; x0 x1 300} Version 3 {(300, 0, 0)} Version 4 Empty

Some Observations If a feasible allocation x ( x0 , , xn ) is not in the core, then there is some coalition C such that the players in C could all do strictly better than in x. If an allocation x belongs to the core, then it implies that x is a Nash equilibrium of an appropriate contract signing game, so players are reasonably happy. Empty core is bad news so also a large core!

Shapley Value : A Fair Allocation Scheme Provides a unique payoff allocation that describes a fair way of dividing the gains of cooperation in a game (N, v) (v) ( 0 (v),., n (v)) where C !( N C 1)! {v(C {i}) v(C )} N ! C N i i (v )

Shapley Value: Examples Version of Divide-the-Dollar Shapley Value Version 1 (300,0,0) Version 2 (150,150,0) Version 3 (200,50,50) Version 4 (100,100,100)

Shapley Value: An Application to Finding Influential Nodes in a Social Network

TO PROBE FURTHER Philip D Straffin, Jr. Game Theory and Strategy, American Mathematical Society, 1993 Martin Osborne. Introduction to Game Theory. Oxford University Press, 2003 Roger Myerson. Game Theory and Analysis of Conflict. Harvard University Press, 1997 A, Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory, Oxford University Press, 1995 53 E-Commerce Lab, CSA, IISc

TO PROBE FURTHER (contd.) Y. Narahari, Dinesh Garg, Ramasuri, and Hastagiri Game Theoretic Problems in Network Economics and Mechanism Design Solutions, Springer, 2009 http://www.gametheory.net A rich source of material on game theory and game theory courses http://lcm.csa.iisc.ernet.in/hari Several survey articles can be downloaded http://lcm.csa.iisc.ernet.in/gametheory/index.html Game Theory Course Offered at IISc 54 E-Commerce Lab, CSA, IISc

Questions and Answers Thank You 55 E-Commerce Lab, CSA, IISc