Game Theory 1. Introduction


 Lynn Garrison
 6 years ago
 Views:
Transcription
1 Game Theory 1. Introduction Dmitry Potapov CERN
2 What is Game Theory? Game theory is about interactions among agents that are selfinterested I ll use agent and player synonymously Selfinterested: Each agent has its own description of what states are desirable Generally model this using utility theory Utility function: maps each state of the world to a real number how much an agent likes that state 2
3 Example: TCP Users Internet traffic is governed by the TCP protocol TCP s backoff mechanism If the rate at which you re sending packets causes congestion, reduce the rate until congestion subsides Suppose that You re trying to finish an important project It s extremely important for you to have a fast connection Only one other person is using the Internet That person wants a fast connection just as much as you do You each have 2 possible actions: C (use a correct implementation) D (use a defective implementation that won t back off) 3
4 Action Profiles and their Payoffs An action profile is a choice of action for each agent You both use C => average packet delay is 1 ms You both use D => average delay is 3 ms (router overhead) One of you uses D, the other uses C: D user s delay is 0 C user s delay is 4 ms Payoff matrix: Your options are the rows The other agent s options are the columns Each cell = an action profile 1st number in the cell is your payoff or utility (I ll use those terms synonymously) In this case, the negative of your delay 2nd number in each cell is the other agent s payoff 1, 1 4, 0 0, 4 3, 3 4
5 Some questions Examples of the kinds of questions game theory attempts to answer: Which action should you use: C or D? Does it depend on what you think the other person will do? What kind of behavior can the network operator expect? Would any two users behave the same? Will this change if users can communicate with each other beforehand? Under what changes to the delays would the users decisions still be the same? 1, 1 4, 0 0, 4 3, 3 How would you behave if you knew you would face this situation repeatedly with the same person? 5
6 Some Fields where Game Theory is Used Economics Auctions Markets Bargaining Fair division Social networks 6
7 Some Fields where Game Theory is Used Government and Politics Voting systems Negotiations International relations War Human rights A trench in World War 1: 7
8 Some Fields where Game Theory is Used Evolutionary Biology Communication Population ratios Territoriality Altruism Parasitism, symbiosis Social behavior 8
9 Some Fields where Game Theory is Used Computer Science Artificial Intelligence Multiagent systems Computer networks Robotics 9
10 Some Fields where Game Theory is Used Engineering Communication networks Control systems Road networks 10
11 Expected utility maximization Games against nature Nature is considered an impartial agent (may be represented by U = const) U = N i=1 p i U i Assume that p = 0.7; p = 0.3 Then: U = (0) (0.7) + (2)(0.3) = U = (5) (0.7) + (10)(0.3) = It is rational to take an umbrella! 11
12 These games are purely competitive Zerosum Games Constantsum game: For every action profile, the sum of the payoffs is the same, i.e., there is a constant c such for every action profile (a 1,, a n ), u 1 (a 1,, a n ) + + u n (a 1,, a n ) = c Any constantsum game can be transformed into an equivalent game in which the sum of the payoffs is always 0 Just subtract c/n from every payoff Thus constantsum games are usually called zerosum games 12
13 Matching Pennies Two agents, each has a penny Each independently chooses to display Heads or Tails Examples If same, agent 1 gets both pennies Otherwise agent 2 gets both pennies Heads Tails Heads Tails 1, 1 1, 1 1, 1 1, 1 Rock, Paper, Scissors (Roshambo) 3action generalization of matching pennies If both choose same, no winner Otherwise, paper beats rock, rock beats scissors, scissors beats paper 13
14 Dominant strategies Now let s assume that weather is a conscious, selfinterested agent Column 2 always gives me less utility, than column 1. There is no use for me choosing it! Surely, Weather will choose to rain, so I better take my umbrella! 0, 0 2, 2 5, 5 10, 10 It is rational for the man to take an umbrella and for Weather to rain! 14
15 Nash Equilibrium If I choose R 1, C is better with C 2, if R 2 with C 1. C will consider worst case scenario and will choose C 1. So I must choose R 1! R will choose R 1, so I must choose C 2! R will choose C 2, so I must choose R 2! R will choose R 2, so I must choose C 1! No dominant strategies: C 1 C 2 Solution: use Nash equilibrium choose R 1 with probability p = 5/7 and R 2 with probability p = 2/7 R 1 R 2 2, 2 0, 01, 1 4, 4 15
16 Nash Equilibrium C 1 C 2 R 1 2, 2 0, 0 R 21, 1 4, 4 16
17 Nonzerosum games The game of chicken 1, 1 10, 10 10, , 100 What is the rational decision? Yank your steering wheel off and throw it out of the window (H. Kahn)  Need to make sure that your opponent sees this  If your opponent uses the same strategy, you have a problem (are killed) Choose maximin strategy (C, C)  Not an equilibrium Choose a pure equilibrium (C, D) or (D, C)  Not symmetric Choose a mixed equilibrium C with p = 10/11, D with p = 1/11  Average payoff is 0, but a nonequilibrium (C, C) gives 1 No satisfactory answer which is the most rational strategy! 17
18 Nonzerosum games The deterrence game S 1 T 1 S 2 T 2 1, 0 0, 1 0, 0 x, y Model: Cuban Missile Crisis S 2 T 2 T 1 S 1 remove Russian missiles keep Russian missiles attack Cuba not attack Cuba How to induce Cuba to choose S 2? Send a threat: If you choose T 2, I am going to choose T 1 Is it a credible threat or a bluff? Assume that Cuba will defy the threat with probability p. Then a solution (T.C. Schelling, 1960) is: It is worthwhile to threaten with some probability π so that: (1 p) > π > 1 px 1+y 18
19 The deterrence game Real world implementation Assume π = 1/6. The problem is: One doesn t release a 1/6th of a nuclear war! He either releases a fullblown nuclear attack or none at all The chances of winning are the same as in Russian roulette The question reduces to the question of how rational it is to play Russian roulette 19
20 The Prisoner s Dilemma The TCP user s game is more commonly called the Prisoner s Dilemma Scenario: two prisoners are in separate rooms For each prisoner, the police have enough evidence for a 1 year prison sentence They want to get enough evidence for a 4 year prison sentence They tell each prisoner, If you testify against the other prisoner, we ll reduce your prison sentence by 1 year C = Cooperate (with the other prisoner): refuse to testify D = Defect: testify against the other prisoner Both prisoners cooperate => both stay in prison for 1 year Both prisoners defect => both stay in prison for 4 1 = 3 years One defects, other cooperates => cooperator stays in prison for 4 years; defector goes free 1, 1 4, 0 0, 4 3, 3 20
21 Prisoner s Dilemma 1, 1 4, 0 0, 4 3, 3 The paradox: strategy (D, D) is a dominant equilibrium (for example, for every strategy of the column player, the row player prefers C to D.) But (C, C) has a bigger payoff. 21
22 Backward Induction To find subgameperfect equilibria, we can use backward induction Identify the equilibria in the bottommost nodes Assume they ll be played if the game ever reaches these nodes For each node x, recursively compute a vector v x = (v x1,, v xn ) that gives every agent s equilibrium utility At each node x, If i is the agent to move, then i s equilibrium action is to move to a child y of x for which i s equilibrium utility v yi is highest C A 2 (3,8) D (3,8) (8,3) 1 (3,8) B 2 (2,10) E F (5,5) 1 (2,10) G H (2,10) (1,0) Thus v x = v y 22
23 The Centipede Game , 100 1, 1 0, 3 2, 2 99, 99 98,101 Two possible moves: C (continue) and S (stop) Agent 1 makes the first move At each terminal node, the payoffs are as shown 23
24 A Problem with Backward Induction The Centipede Game Can extend this game to any length The payoffs are constructed in such a way that for each agent, the only SPE is always to choose S This equilibrium isn t intuitively appealing Seems unlikely that an agent would choose S near the start of the game If the agents continue the game for several moves, they ll both get higher payoffs In lab experiments, subjects continue to choose C until close to the end of the game 24
25 A Problem with Backward Induction Suppose agent 1 chooses C If you re agent 2, what do you do? SPE analysis says you should choose S But SPE analysis also says you should never have gotten here at all How to amend your beliefs and course of action based on this event? Fundamental problem in game theory Differing accounts of it, depending on the probabilistic assumptions made what is common knowledge (whether there is common knowledge of rationality) how to revise our beliefs in the face of an event with probability 0 25
26 Backward Induction in ZeroSum Games Backward induction works much better in zerosum games No zerosum version of the Centipede Game, because we can t have increasing payoffs for both players Only need one number: agent 1 s payoff (= negative of agent 2 s payoff) Propagate agent 1 s payoff up to the root At each node where it s agent 1 s move, the value is the maximum of the labels of its children At each node where it s agent 2 s move, the value is the minimum of the labels of its children The root s label is the value of the game (from the Minimax Theorem) In practice, it may not be possible to generate the entire game tree E.g., extensiveform representation of chess has about nodes Need a heuristic search algorithm 26
27 Summary Basic concepts: payoffs, pure strategies, mixed strategies Some classifications of games based on their payoffs Zerosum Roshambo, Matching Pennies Nonzerosum Prisoner s Dilemma, Game of chicken Backward induction 27
28
Computational Learning Theory Spring Semester, 2003/4. Lecture 1: March 2
Computational Learning Theory Spring Semester, 2003/4 Lecture 1: March 2 Lecturer: Yishay Mansour Scribe: Gur Yaari, Idan Szpektor 1.1 Introduction Several fields in computer science and economics are
More informationI d Rather Stay Stupid: The Advantage of Having Low Utility
I d Rather Stay Stupid: The Advantage of Having Low Utility Lior Seeman Department of Computer Science Cornell University lseeman@cs.cornell.edu Abstract Motivated by cost of computation in game theory,
More informationBackward Induction and Subgame Perfection
Backward Induction and Subgame Perfection In extensiveform games, we can have a Nash equilibrium profile of strategies where player 2 s strategy is a best response to player 1 s strategy, but where she
More information1 Nonzero sum games and Nash equilibria
princeton univ. F 14 cos 521: Advanced Algorithm Design Lecture 19: Equilibria and algorithms Lecturer: Sanjeev Arora Scribe: Economic and gametheoretic reasoning specifically, how agents respond to economic
More informationGame Theory in Wireless Networks: A Tutorial
1 Game heory in Wireless Networks: A utorial Mark Felegyhazi, JeanPierre Hubaux EPFL Switzerland email: {mark.felegyhazi, jeanpierre.hubaux}@epfl.ch EPFL echnical report: LCAREPOR2006002, submitted
More informationGame Theory and Algorithms Lecture 10: Extensive Games: Critiques and Extensions
Game Theory and Algorithms Lecture 0: Extensive Games: Critiques and Extensions March 3, 0 Summary: We discuss a game called the centipede game, a simple extensive game where the prediction made by backwards
More information6.254 : Game Theory with Engineering Applications Lecture 2: Strategic Form Games
6.254 : Game Theory with Engineering Applications Lecture 2: Strategic Form Games Asu Ozdaglar MIT February 4, 2009 1 Introduction Outline Decisions, utility maximization Strategic form games Best responses
More informationThe Basics of Game Theory
Sloan School of Management 15.010/15.011 Massachusetts Institute of Technology RECITATION NOTES #7 The Basics of Game Theory Friday  November 5, 2004 OUTLINE OF TODAY S RECITATION 1. Game theory definitions:
More informationMobLab Game Catalog For Business Schools Fall, 2015
MobLab Game Catalog For Business Schools Fall, 2015 CORE COURSE COVERAGE Economics For Business Principles of Business Microeconomic Analysis Decisions Game Theory Negotiation Strategy Managerial Economics
More information6.207/14.15: Networks Lecture 15: Repeated Games and Cooperation
6.207/14.15: Networks Lecture 15: Repeated Games and Cooperation Daron Acemoglu and Asu Ozdaglar MIT November 2, 2009 1 Introduction Outline The problem of cooperation Finitelyrepeated prisoner s dilemma
More informationAN INTRODUCTION TO GAME THEORY
AN INTRODUCTION TO GAME THEORY 2008 AGIInformation Management Consultants May be used for personal purporses only or by libraries associated to dandelon.com network. MARTIN J. OSBORNE University of Toronto
More information1 Representation of Games. Kerschbamer: Commitment and Information in Games
1 epresentation of Games Kerschbamer: Commitment and Information in Games GameTheoretic Description of Interactive Decision Situations This lecture deals with the process of translating an informal description
More informationGame Theory Perspectives on Client Vendor relationships in offshore software outsourcing
Game Theory Perspectives on Client Vendor relationships in offshore software outsourcing Nilay V. Oza Helsinki University of Technology Software Business Laboratory, P.O. Box 5500, 02015 TKK, Finland Tel:
More information6.254 : Game Theory with Engineering Applications Lecture 1: Introduction
6.254 : Game Theory with Engineering Applications Lecture 1: Introduction Asu Ozdaglar MIT February 2, 2010 1 Introduction Optimization Theory: Optimize a single objective over a decision variable x R
More informationCOMP310 MultiAgent Systems. Chapter 11  MultiAgent Interactions
COMP310 MultiAgent Systems Chapter 11  MultiAgent Interactions What are MultiAgent Systems? KEY organisational relationship interaction agent Environment sphere of influence 2 What are MultiAgent Systems?
More informationCournot s model of oligopoly
Cournot s model of oligopoly Single good produced by n firms Cost to firm i of producing q i units: C i (q i ), where C i is nonnegative and increasing If firms total output is Q then market price is P(Q),
More informationMicroeconomic Theory Jamison / Kohlberg / Avery Problem Set 4 Solutions Spring 2012. (a) LEFT CENTER RIGHT TOP 8, 5 0, 0 6, 3 BOTTOM 0, 0 7, 6 6, 3
Microeconomic Theory Jamison / Kohlberg / Avery Problem Set 4 Solutions Spring 2012 1. Subgame Perfect Equilibrium and Dominance (a) LEFT CENTER RIGHT TOP 8, 5 0, 0 6, 3 BOTTOM 0, 0 7, 6 6, 3 Highlighting
More informationEconomics Instructor Miller Oligopoly Practice Problems
Economics Instructor Miller Oligopoly Practice Problems 1. An oligopolistic industry is characterized by all of the following except A) existence of entry barriers. B) the possibility of reaping long run
More informationDo not open this exam until told to do so.
Do not open this exam until told to do so. Department of Economics College of Social and Applied Human Sciences K. Annen, Winter 004 Final (Version ): Intermediate Microeconomics (ECON30) Solutions Final
More informationEquilibrium computation: Part 1
Equilibrium computation: Part 1 Nicola Gatti 1 Troels Bjerre Sorensen 2 1 Politecnico di Milano, Italy 2 Duke University, USA Nicola Gatti and Troels Bjerre Sørensen ( Politecnico di Milano, Italy, Equilibrium
More informationFINAL EXAM, Econ 171, March, 2015, with answers
FINAL EXAM, Econ 171, March, 2015, with answers There are 9 questions. Answer any 8 of them. Good luck! Problem 1. (True or False) If a player has a dominant strategy in a simultaneousmove game, then
More informationOligopoly. Oligopoly is a market structure in which the number of sellers is small.
Oligopoly Oligopoly is a market structure in which the number of sellers is small. Oligopoly requires strategic thinking, unlike perfect competition, monopoly, and monopolistic competition. Under perfect
More informationSequential lmove Games. Using Backward Induction (Rollback) to Find Equilibrium
Sequential lmove Games Using Backward Induction (Rollback) to Find Equilibrium Sequential Move Class Game: Century Mark Played by fixed pairs of players taking turns. At each turn, each player chooses
More informationWeek 7  Game Theory and Industrial Organisation
Week 7  Game Theory and Industrial Organisation The Cournot and Bertrand models are the two basic templates for models of oligopoly; industry structures with a small number of firms. There are a number
More informationGame Theory and Nash Equilibrium
Game Theory and Nash Equilibrium by Jenny Duffy A project submitted to the Department of Mathematical Sciences in conformity with the requirements for Math 4301 (Honours Seminar) Lakehead University Thunder
More informationGame Theory. CDAM Research Report LSECDAM200109 October 8, 2001. 1 What is game theory? 4. 2 Definitions of games 6.
Game Theory Theodore L. Turocy Texas A&M University Bernhard von Stengel London School of Economics CDAM Research Report LSECDAM29 October 8, 2 Contents What is game theory? 4 2 Definitions of games
More informationA Game Playing System for Use in Computer Science Education
A Game Playing System for Use in Computer Science Education James MacGlashan University of Maryland, Baltimore County 1000 Hilltop Circle Baltimore, MD jmac1@umbc.edu Don Miner University of Maryland,
More informationChapter 16: law of averages
Chapter 16: law of averages Context................................................................... 2 Law of averages 3 Coin tossing experiment......................................................
More informationBayesian Nash Equilibrium
. Bayesian Nash Equilibrium . In the final two weeks: Goals Understand what a game of incomplete information (Bayesian game) is Understand how to model static Bayesian games Be able to apply Bayes Nash
More informationECO 199 B GAMES OF STRATEGY Spring Term 2004 PROBLEM SET 4 B DRAFT ANSWER KEY 1003 9099 21 8089 14 7079 4 069 11
The distribution of grades was as follows. ECO 199 B GAMES OF STRATEGY Spring Term 2004 PROBLEM SET 4 B DRAFT ANSWER KEY Range Numbers 1003 9099 21 8089 14 7079 4 069 11 Question 1: 30 points Games
More informationA Beautiful Mind Meets Free Software: Game Theory, Competition and Cooperation
A Beautiful Mind Meets Free Software: Game Theory, Competition and Cooperation Alexandre Oliva oliva@lsd.ic.unicamp.br, lxoliva@fsfla.org, aoliva@redhat.com Summary Russel Crowe, playing John Nash in Ron
More informationGAMES FOR BUSINESS AND ECONOMICS
GAMES FOR BUSINESS AND ECONOMICS ROY/GARDNER Indiana University Nachrichtentechnische BibliotHek TUD Inv.Nr.: /S.JOtUM John Wiley & Sons, Inc. 5" New York Chichester Brisbane Toronto Singapore Contents
More informationHow to Solve Strategic Games? Dominant Strategies
How to Solve Strategic Games? There are three main concepts to solve strategic games: 1. Dominant Strategies & Dominant Strategy Equilibrium 2. Dominated Strategies & Iterative Elimination of Dominated
More informationAdvanced Game Theory
Advanced Game Theory Herve Moulin Baker Hall 263; moulin@rice.edu Rice University ECO 440 Spring 2007 1 Two person zero sum games 1.1 Introduction: strategic interdependency In this section we study games
More informationLaboratory work in AI: First steps in Poker Playing Agents and Opponent Modeling
Laboratory work in AI: First steps in Poker Playing Agents and Opponent Modeling Avram Golbert 01574669 agolbert@gmail.com Abstract: While Artificial Intelligence research has shown great success in deterministic
More informationGame Theory. An introduction to the concepts of dominant strategies, Nash equilibrium and strategic commitment
Game Theory An introduction to the concepts of dominant strategies, Nash equilibrium and strategic commitment Introduction The theory of games is a theory of economic behaviour in multiperson decision
More informationBonus Maths 2: Variable Bet Sizing in the Simplest Possible Game of Poker (JB)
Bonus Maths 2: Variable Bet Sizing in the Simplest Possible Game of Poker (JB) I recently decided to read Part Three of The Mathematics of Poker (TMOP) more carefully than I did the first time around.
More informationChapter 14. Oligopoly
Chapter 14. Oligopoly Instructor: JINKOOK LEE Department of Economics / Texas A&M University ECON 202 504 Principles of Microeconomics Oligopoly Market Oligopoly: A market structure in which a small number
More informationGAME THEORY. Thomas S. Ferguson
GAME THEORY Thomas S. Ferguson Part III. TwoPerson GeneralSum Games 1. Bimatrix Games Safety Levels. 1.1 GeneralSum Strategic Form Games. 1.2 GeneralSum Extensive Form Games. 1.3 Reducing Extensive
More informationEconomics 159: Introduction to Game Theory. Summer 2015: Session A. Online Course
Economics 159: Introduction to Game Theory Summer 2015: Session A Online Course *Syllabussubjecttochange.Checkcoursewebpageforuptodateinformation* This course is an introduction to game theory and strategic
More information0.0.2 Pareto Efficiency (Sec. 4, Ch. 1 of text)
September 2 Exercises: Problem 2 (p. 21) Efficiency: p. 2829: 1, 4, 5, 6 0.0.2 Pareto Efficiency (Sec. 4, Ch. 1 of text) We discuss here a notion of efficiency that is rooted in the individual preferences
More informationFrom the probabilities that the company uses to move drivers from state to state the next year, we get the following transition matrix:
MAT 121 Solutions to TakeHome Exam 2 Problem 1 Car Insurance a) The 3 states in this Markov Chain correspond to the 3 groups used by the insurance company to classify their drivers: G 0, G 1, and G 2
More informationThéorie de la décision et théorie des jeux Stefano Moretti
héorie de la décision et théorie des jeux Stefano Moretti UMR 7243 CNRS Laboratoire d'analyse et Modélisation de Systèmes pour l'aide à la décision (LAMSADE) Université ParisDauphine email: Stefano.MOREI@dauphine.fr
More information21. Unverifiable Investment, Hold Up, Options and Ownership
21. Unverifiable Investment, Hold Up, Options and Ownership This chapter applies the tools of games with joint decisions and negotiation equilibrium to study the hold up problem in economics. We first
More informationIntroduction Solvability Rules Computer Solution Implementation. Connect Four. March 9, 2010. Connect Four
March 9, 2010 is a tictactoe like game in which two players drop discs into a 7x6 board. The first player to get four in a row (either vertically, horizontally, or diagonally) wins. The game was first
More informationInfinitely Repeated Games with Discounting Ù
Infinitely Repeated Games with Discounting Page 1 Infinitely Repeated Games with Discounting Ù Introduction 1 Discounting the future 2 Interpreting the discount factor 3 The average discounted payoff 4
More informationA Game Theoretical Framework on Intrusion Detection in Heterogeneous Networks Lin Chen, Member, IEEE, and Jean Leneutre
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL 4, NO 2, JUNE 2009 165 A Game Theoretical Framework on Intrusion Detection in Heterogeneous Networks Lin Chen, Member, IEEE, and Jean Leneutre
More information3.2 Roulette and Markov Chains
238 CHAPTER 3. DISCRETE DYNAMICAL SYSTEMS WITH MANY VARIABLES 3.2 Roulette and Markov Chains In this section we will be discussing an application of systems of recursion equations called Markov Chains.
More informationValuation Uncertainty and Imperfect Introspection in SecondPrice Auctions
Valuation Uncertainty and Imperfect Introspection in SecondPrice Auctions by David Robert Martin Thompson A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science
More informationCompetition and Regulation. Lecture 2: Background on imperfect competition
Competition and Regulation Lecture 2: Background on imperfect competition Monopoly A monopolist maximizes its profits, choosing simultaneously quantity and prices, taking the Demand as a contraint; The
More informationT28 OLIGOPOLY 3/1/15
T28 OLIGOPOLY 3/1/15 1. Oligopoly is a market structure in which there are a small number of firms that engage in strategic interactions. If there are only two firms then we refer to the situation as a
More informationKids College Computer Game Programming Exploring Small Basic and Procedural Programming
Kids College Computer Game Programming Exploring Small Basic and Procedural Programming According to Microsoft, Small Basic is a programming language developed by Microsoft, focused at making programming
More informationCOMP30191 The Theory of Games and Game Models
COMP30191 The Theory of Games and Game Models Andrea Schalk A.Schalk@cs.man.ac.uk School of Computer Science University of Manchester August 7, 2008 About this course This is an introduction into the theory
More informationChapter 7. Sealedbid Auctions
Chapter 7 Sealedbid Auctions An auction is a procedure used for selling and buying items by offering them up for bid. Auctions are often used to sell objects that have a variable price (for example oil)
More informationGames Manipulators Play
Games Manipulators Play Umberto Grandi Department of Mathematics University of Padova 23 January 2014 [Joint work with Edith Elkind, Francesca Rossi and Arkadii Slinko] GibbardSatterthwaite Theorem All
More informationECON 459 Game Theory. Lecture Notes Auctions. Luca Anderlini Spring 2015
ECON 459 Game Theory Lecture Notes Auctions Luca Anderlini Spring 2015 These notes have been used before. If you can still spot any errors or have any suggestions for improvement, please let me know. 1
More informationMinimax Strategies. Minimax Strategies. Zero Sum Games. Why Zero Sum Games? An Example. An Example
Everyone who has studied a game like poker knows the importance of mixing strategies With a bad hand, you often fold But you must bluff sometimes Lectures in MicroeconomicsCharles W Upton Zero Sum Games
More informationGame theory and AI: a unified approach to poker games
Game theory and AI: a unified approach to poker games Thesis for graduation as Master of Artificial Intelligence University of Amsterdam Frans Oliehoek 2 September 2005 ii Abstract This thesis focuses
More information6.1 What is a Game? 156 CHAPTER 6. GAMES
From the book Networks, Crowds, and Markets: Reasoning about a Highly Connected World. By David Easley and Jon Kleinberg. Cambridge University Press, 2010. Complete preprint online at http://www.cs.cornell.edu/home/kleinber/networksbook/
More informationWhen Machine Learning Meets AI and Game Theory
1 When Machine Learning Meets AI and Game Theory Anurag Agrawal, Deepak Jaiswal Abstract We study the problem of development of intelligent machine learning applications to exploit the problems of adaptation
More information??? Signaling Games???
??? Signaling Games??? In incomplete information games, one player knows more information than the other player. So far, we have focused on the case where the type of the more informed player was known
More informationProbability and Expected Value
Probability and Expected Value This handout provides an introduction to probability and expected value. Some of you may already be familiar with some of these topics. Probability and expected value are
More information8 Modeling network traffic using game theory
8 Modeling network traffic using game theory Network represented as a weighted graph; each edge has a designated travel time that may depend on the amount of traffic it contains (some edges sensitive to
More informationREWARD System For Even Money Bet in Roulette By Izak Matatya
REWARD System For Even Money Bet in Roulette By Izak Matatya By even money betting we mean betting on Red or Black, High or Low, Even or Odd, because they pay 1 to 1. With the exception of the green zeros,
More informationAMS 5 CHANCE VARIABILITY
AMS 5 CHANCE VARIABILITY The Law of Averages When tossing a fair coin the chances of tails and heads are the same: 50% and 50%. So if the coin is tossed a large number of times, the number of heads and
More informationExpected Value. 24 February 2014. Expected Value 24 February 2014 1/19
Expected Value 24 February 2014 Expected Value 24 February 2014 1/19 This week we discuss the notion of expected value and how it applies to probability situations, including the various New Mexico Lottery
More informationPascal is here expressing a kind of skepticism about the ability of human reason to deliver an answer to this question.
Pascal s wager So far we have discussed a number of arguments for or against the existence of God. In the reading for today, Pascal asks not Does God exist? but Should we believe in God? What is distinctive
More informationWhen other firms see these potential profits they will enter the industry, causing a downward shift in the demand for a given firm s product.
Characteristics of Monopolistic Competition large number of firms differentiated products (ie. substitutes) freedom of entry and exit Examples Upholstered furniture: firms; HHI* = 395 Jewelry and Silverware:
More informationCompact Representations and Approximations for Compuation in Games
Compact Representations and Approximations for Compuation in Games Kevin Swersky April 23, 2008 Abstract Compact representations have recently been developed as a way of both encoding the strategic interactions
More informationLinear Programming: Chapter 11 Game Theory
Linear Programming: Chapter 11 Game Theory Robert J. Vanderbei October 17, 2007 Operations Research and Financial Engineering Princeton University Princeton, NJ 08544 http://www.princeton.edu/ rvdb RockPaperScissors
More informationGames and Strategic Behavior. Chapter 9. Learning Objectives
Games and Strategic Behavior Chapter 9 McGrawHill/Irwin Copyright 2013 by The McGrawHill Companies, Inc. All rights reserved. Learning Objectives 1. List the three basic elements of a game. Recognize
More informationSimple ChannelChange Games for Spectrum Agile Wireless Networks
Simple ChannelChange Games for Spectrum Agile Wireless Networks Roli G. Wendorf and Howard Blum Seidenberg School of Computer Science and Information Systems Pace University White Plains, New York, USA
More informationIn the situations that we will encounter, we may generally calculate the probability of an event
What does it mean for something to be random? An event is called random if the process which produces the outcome is sufficiently complicated that we are unable to predict the precise result and are instead
More informationOligopoly: How do firms behave when there are only a few competitors? These firms produce all or most of their industry s output.
Topic 8 Chapter 13 Oligopoly and Monopolistic Competition Econ 203 Topic 8 page 1 Oligopoly: How do firms behave when there are only a few competitors? These firms produce all or most of their industry
More informationOligopoly markets: The price or quantity decisions by one rm has to directly in uence pro ts by other rms if rms are competing for customers.
15 Game Theory Varian: Chapters 89. The key novelty compared to the competitive (Walrasian) equilibrium analysis is that game theoretic analysis allows for the possibility that utility/pro t/payo s depend
More informationSecurity Games in Online Advertising: Can Ads Help Secure the Web?
Security Games in Online Advertising: Can Ads Help Secure the Web? Nevena Vratonjic, JeanPierre Hubaux, Maxim Raya School of Computer and Communication Sciences EPFL, Switzerland firstname.lastname@epfl.ch
More informationUniversidad Carlos III de Madrid Game Theory Problem Set  Dynamic Games
Universidad Carlos III de Madrid Game Theory Problem Set  Dynamic Games Session Problems 1, 2, 3, 4, 5, 6 1 (no SPNE) 2 7, 8, 9, 10, 11 3 12, 13, 14, 15, 16 4 17, 18, 19 5 Test 1. The next figure shows
More informationChapter 7. Evolutionary Game Theory
From the book Networks, Crowds, and Markets: Reasoning about a Highly Connected World. By David Easley and Jon Kleinberg. Cambridge University Press, 2010. Complete preprint online at http://www.cs.cornell.edu/home/kleinber/networksbook/
More informationAlok Gupta. Dmitry Zhdanov
RESEARCH ARTICLE GROWTH AND SUSTAINABILITY OF MANAGED SECURITY SERVICES NETWORKS: AN ECONOMIC PERSPECTIVE Alok Gupta Department of Information and Decision Sciences, Carlson School of Management, University
More informationDecision Making under Uncertainty
6.825 Techniques in Artificial Intelligence Decision Making under Uncertainty How to make one decision in the face of uncertainty Lecture 19 1 In the next two lectures, we ll look at the question of how
More informationCompetition between Apple and Samsung in the smartphone market introduction into some key concepts in managerial economics
Competition between Apple and Samsung in the smartphone market introduction into some key concepts in managerial economics Dr. Markus Thomas Münter Collège des Ingénieurs Stuttgart, June, 03 SNORKELING
More informationECON 40050 Game Theory Exam 1  Answer Key. 4) All exams must be turned in by 1:45 pm. No extensions will be granted.
1 ECON 40050 Game Theory Exam 1  Answer Key Instructions: 1) You may use a pen or pencil, a handheld nonprogrammable calculator, and a ruler. No other materials may be at or near your desk. Books, coats,
More informationHomework 3, Solutions Managerial Economics: Eco 685
Homework 3, Solutions Managerial Economics: Eco 685 Question 1 a. Second degree since we have a quantity discount. For 2 GB the cost is $15 per GB, for 5 GB the cost is $10 per GB, and for 10 GB the cost
More informationChapter 4 DECISION ANALYSIS
ASW/QMBCh.04 3/8/01 10:35 AM Page 96 Chapter 4 DECISION ANALYSIS CONTENTS 4.1 PROBLEM FORMULATION Influence Diagrams Payoff Tables Decision Trees 4.2 DECISION MAKING WITHOUT PROBABILITIES Optimistic Approach
More informationExtreme cases. In between cases
CHAPTER 16 OLIGOPOLY FOUR TYPES OF MARKET STRUCTURE Extreme cases PERFECTLY COMPETITION Many firms No barriers to entry Identical products MONOPOLY One firm Huge barriers to entry Unique product In between
More informationNash Equilibria and. Related Observations in OneStage Poker
Nash Equilibria and Related Observations in OneStage Poker Zach Puller MMSS Thesis Advisor: Todd Sarver Northwestern University June 4, 2013 Contents 1 Abstract 2 2 Acknowledgements 3 3 Literature Review
More informationUse of Game Theory in Executive Support System
Use of Game Theory in Executive Support System Ashish Sharma, Sarika Jain Amity institute of information technology Amity University, Noida Abstract In today s world competition in every business is increasing
More information1 Introduction. Linear Programming. Questions. A general optimization problem is of the form: choose x to. max f(x) subject to x S. where.
Introduction Linear Programming Neil Laws TT 00 A general optimization problem is of the form: choose x to maximise f(x) subject to x S where x = (x,..., x n ) T, f : R n R is the objective function, S
More informationA Dutch Book for Group DecisionMaking?
A Dutch Book for Group DecisionMaking? Forthcoming in Benedikt Löwe, Eric Pacuit, JanWillem Romeijn (eds.) Foundations of the Formal Sciences VIReasoning about Probabilities and Probabilistic Reasoning.
More informationInternet Advertising and the Generalized Second Price Auction:
Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords Ben Edelman, Harvard Michael Ostrovsky, Stanford GSB Michael Schwarz, Yahoo! Research A Few
More informationLESSON 7. Managing the Trump Suit. General Concepts. General Introduction. Group Activities. Sample Deals
LESSON 7 Managing the Trump Suit General Concepts General Introduction Group Activities Sample Deals 170 Lesson 7 Managing the Trump Suit GENERAL CONCEPTS Play of the Hand Drawing trumps Playing the trump
More information6.042/18.062J Mathematics for Computer Science. Expected Value I
6.42/8.62J Mathematics for Computer Science Srini Devadas and Eric Lehman May 3, 25 Lecture otes Expected Value I The expectation or expected value of a random variable is a single number that tells you
More informationUniversity of Oslo Department of Economics
University of Oslo Department of Economics Exam: ECON3200/4200 Microeconomics and game theory Date of exam: Tuesday, November 26, 2013 Grades are given: December 17, 2013 Duration: 14:3017:30 The problem
More informationGibbs Sampling and Online Learning Introduction
Statistical Techniques in Robotics (16831, F14) Lecture#10(Tuesday, September 30) Gibbs Sampling and Online Learning Introduction Lecturer: Drew Bagnell Scribes: {Shichao Yang} 1 1 Sampling Samples are
More informationDecision Theory. 36.1 Rational prospecting
36 Decision Theory Decision theory is trivial, apart from computational details (just like playing chess!). You have a choice of various actions, a. The world may be in one of many states x; which one
More informationLecture V: Mixed Strategies
Lecture V: Mixed Strategies Markus M. Möbius February 26, 2008 Osborne, chapter 4 Gibbons, sections 1.31.3.A 1 The Advantage of Mixed Strategies Consider the following RockPaperScissors game: Note that
More informationThe UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge,
The UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge, cheapest first, we had to determine whether its two endpoints
More informationI. Noncooperative Oligopoly
I. Noncooperative Oligopoly Oligopoly: interaction among small number of firms Conflict of interest: Each firm maximizes its own profits, but... Firm j s actions affect firm i s profits Example: price
More informationLECTURE #15: MICROECONOMICS CHAPTER 17
LECTURE #15: MICROECONOMICS CHAPTER 17 I. IMPORTANT DEFINITIONS A. Oligopoly: a market structure with a few sellers offering similar or identical products. B. Game Theory: the study of how people behave
More informationThe Influence of Contexts on DecisionMaking
The Influence of Contexts on DecisionMaking The Harvard community has made this article openly available. Please share how this access benefits you. Your story matters. Citation Accessed Citable Link
More information