Introduction to Game Theory: Theory, Applications, and Algorithms

Optimizacin Complementaria Felipe Feijoo, Ph.D. Oficina: EII, IBC 6-7. Email: Felipe.Feijoo@pucv.cl

Contenidos Introducci n a teor a de juegos Optimizaci n complementaria (MCP) Mathematical and Equilibrium Programs with Equilibrium Constraints (MPECs o Bilevel) M todos generales de soluci n y algoritmos para problemas variados

Bibliografa Bsica Gabriel, S. A., Conejo, A. J., Fuller, J. D., Hobbs, B. F., & Ruiz, C. (2012). Complementarity modeling in energy markets (Vol. 180). Springer Science & Business Media. Gibbons, R. S. (1992). Game theory for applied economists. Princeton University Press. Murphy, F., Pierru, A., & Smeers, Y. (2016). A tutorial on building policy models as mixed-complementarity problems. Interfaces, 46(6), 465-481. Emissions control via carbon policies and microgrid generation: A bilevel model and Pareto analysis. F Feijoo, TK Das - Energy, 2015 Design of Pareto optimal CO2 cap-and-trade policies for deregulated electricity networks. F Feijoo, TK Das - Applied energy, 2014 Chen, Y., Hobbs, B. F., Leyffer, S., & Munson, T. S. (2006). Leader-follower equilibria for electric power and NO x allowances markets. Computational Management Science, 3(4), 307-330. Hu, X., & Ralph, D. (2007). Using EPECs to model bilevel games in restructured electricity markets with locational prices. Operations research, 55(5), 809-827. Fampa, M., Barroso, L. A., Candal, D., & Simonetti, L. (2008). Bilevel optimization applied to strategic pricing in competitive electricity markets. Computational Optimization and Applications, 39(2), 121-142. Ferris, M. C., & Munson, T. S. (2000). Complementarity problems in GAMS and the PATH solver. Journal of Economic Dynamics and Control, 24(2), 165-188. Gabriel, S. A., Zhuang, J., & Kiet, S. (2005). A large-scale linear complementarity model of the North American natural gas market. Energy economics, 27(4), 639-665. Hobbs, B. F., Metzler, C. B., & Pang, J. S. (2000). Strategic gaming analysis for electric power systems: An MPEC approach. IEEE transactions on power systems, 15(2), 638-645.

Introduction to Game Theory GT is the study of multipersons decision problems GT is the study of multipersons decision making GT is used to study a range of different areas E.g: The study of oligopoly Trading (bargaining and auction models) Human behavior (e.g., patient behavior or mass behavior) Collusions (oil OPEC a collusion?)

Introduction to Game Theory Static games of Complete Information Players simultaneously chose actions, then players receive payoffs that depend on the combination of their actions (Simultaneous moves). More complex forms (probably the most complex) of Static games of complete information are some forms of EPEC problems Complete Information: each player s payoff function is of common knowledge among all players All players are rational agents Sequential Games

Basic theory: Normal-Form representation of games and Nash Equilibrium Normal-Form game representation: Each player simultaneously chooses a strategy Combination of such strategies determine the payoffs (for each player). Classic Example: The prisoner's Dilemma Two suspects are arrested and charged with a crime. The police lack sufficient evidence to convict the suspects, unless at least one confesses. The police hold the suspects in separate cells and explain the consequences that will follow from the actions they take. If neither confesses, then both will be convicted of a minor offense (1 month in jail). If both confess, then both will be sentenced to jail for 6 months. Finally, if one confesses, but the other does not, then the confessor will be released and the other will be sentenced to nine months. What are the resulting actions?

Normal-Form representation of games and Nash Equilibrium Normal form representation of games specifies: The players in the game The strategies available to each player (actions taken simultaneously) The payoff received by each player for each combination of strategies Can be formulated for n-player game, an arbitrary player is called player i. Let Sibe the set of strategies available to player I, where siis an arbitrary strategy that belong to that set. si Si , Si = (s1 sn) Let uidenote the player i s payoff function, where the actual payoff of player i depends on the strategy taken by each of the players Definition: The normal-form representation of an n-player game specifies the players strategy spaces S1, ,Snand their payoff functions u1, ,un. We denote this game by G(S1, ,Sn; u1, ,un)

Basic theory: Normal-Form representation of games and Nash Equilibrium The prisoner's Dilemma

Normal-Form representation of games and Nash Equilibrium How to solve the normal-form game? Based on the elimination of strictly dominated strategies Based on the idea that rational players do not play strictly dominated strategies Definition: In the n-player normal-form game G(S1, ,Sn; u1, ,un), let ?? dominated by strategy ?? other players strategies, i s payoff from playing ?? than i s payoff from playing ?? and ?? be feasible strategies for player i. Strategy ?? if for each feasible combination of the is strictly is strictly less ,??+1, ,?? < ??(?1, ,?? 1,?? ,??+1, ,??) ???1, ,?? 1,?? For each ?1, ,?? 1,??+1, ,?? that can be constructed from the other players strategy spaces ?1, ,?? 1,??+1, ,??.

Normal-Form representation of games and Nash Equilibrium Strictly Dominated Strategies: Rational players do not play strictly dominated strategies There is no belief that a player could hold such that it would be optimal to play such a strategy. Hence, what would the solution of the Prisoners dilemma be? Player 2 Not Confess Confess (fink) Not confess -1, -1 -9, 0 Player 1 Confess (fink) 0, -9 -6, -6

Normal-Form representation of games and Nash Equilibrium Strictly Dominated Strategies: Rational players do not play strictly dominated strategies We need to assume that it is commong knowledge that players are rational Example 2: Player 2 Left Middle Right up 1,0 1,2 0,1 Player 1 0,3 0,1 2,0 Down Player 2 Example 3: L C R No Strictly Dominated solutions T 0,4 4,0 5,3 Player 1 M 4,0 0,4 5,3 Does this mean that there is NO solution to this game? B 3,5 3,5 6,6

Normal-Form representation of games and Nash Equilibrium NASH equilibrium concept A solution concept that produces much tighter predictions in a broad class of games Stronger solution concept than iterated elimination of SD strategies (but not the strongest) Motivation: If game theory is to provide a unique solution to a game-theoretic problem, then the solution must be a Nash equilibrium, if Each player s predicted strategy MUST be that player s best response to the predicted strategies of the other players. Such prediction can be called strategically stable or self-enforcing : No single player wants to deviate from the predicted strategy.

Normal-Form representation of games and Nash Equilibrium Definition: In the n-player normal-form game G(S1, ,Sn; u1, ,un), the strategies (?1 each player i, ?? strategies specified for the n-1 other players (?1 ,??+1 , ,?? ) are a NASH equilibrium if, for is (at least tied) player i s best response to the , ,?? ): , ,?? 1 ,??+1 ??(?1 ) , ,?? 1 , ,?? 1 ???1 ,?? , ,?? ,??,??+1 , ,?? solves That is, for every strategy ?? ??, the strategy ?? , ,?? 1 ) ?? ????(?1 max ,??,??+1 , ,?? Non of the player has an incentive to deviate or choose a different strategy.

Normal-Form representation of games and Nash Equilibrium Example 2: Player 2 Left Middle Right up 1,0 1,2 0,1 Player 1 0,3 0,1 2,0 Down Player 2 Example 3: L C R T 0,4 4,0 5,3 Player 1 M 4,0 0,4 5,3 B 3,5 3,5 6,6 Example 4: Player 2 Opera Fight Opera 2,1 0, 0 Player 1 Fight 0, 0 1, 2

Normal-Form representation of games and Nash Equilibrium Proposition: If iterated elimination of strictly dominated strategies eliminates all but the strategies (?1 are the unique NASH equilibrium of the game. (proof) ), then these strategies , ,?? Proposition: If the strategies (?1 then they survive iterated elimination of strictly dominated strategies, but there can be strategies that survive iterated elimination of strictly dominated strategies bur are not a part of any Nash equilibrium. (proof) ) are a Nash equilibrium, , ,?? Theorem: In any finite game (game in which the number of players and strategies sets are all finite), there exist at least one Nash equilibrium (pure Nash or Mixed Nash strategies) (read proof)

Strictly dominated strategies and Nash Equilibrium Homework: 10 students play the following game: 1) Each student states a number from 1 to 100 2) The winner is the player whose number is closer to the half of the average. 3) Answer?

Cournot Model Consider two firms competing in terms of quantity of a product or good to produce, such that the demand is satisfied. The price of such demand is in the market in place is giving by the inverse demand function P = a-bQ, where Q = q1+q2 is the total demand in the market. There is a cost C for producing one unit of the product (same for both companies). What is the market equilibrium? (how much each firm produces?). How does the NE solution compare to the monopoly case?

Bertrand model of duopoly Consider two firms competing in terms of the price offered of a product. Each firms sells a product that is a substitute of the other firm s product (differentiated products) Each firm must decide the price at which the product is offered. If Firm 1 and Firm 2 choose P1 and P2 as the prices, then the demand for product i is given by ????,?? = ? ??+ ?????? ? > 0. (for now) Assume that there are not fixed costs and that the marginal cost are constant at C, with C<a Both firms choose their prices simultaneously.