Game Theory: Understanding Strategies and Cooperation in Decision-Making

Explore the world of game theory, a study of conflict and cooperation among decision-makers. Learn about Nash equilibrium, optimal strategies, and its applications in various fields such as economics, politics, AI, and wildlife conservation.

• Game Theory
• Decision-Making
• Nash Equilibrium
• Cooperation
• Strategy

lac_ea Follow

Uploaded on Oct 10, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. News February 21, 2024 Please read Group Project Specification prior to the lecture on Feb. 26; group forming: Groups of 4 Students can be submitted to Mahin through Feb. 22, 11:59p; Mahin will form groups on Feb. 23 The Task2 Specification has been updated (namely, submission instructions have been updated and a grading rubric has been added) Group B: Will you present an additional 5 minute today or not? Next week s main topic: Reinforcement Learning Today s Teaching Plan Game Theory Some Brief Discussion of Task2 Continue and Conclude Discussion of Evolutionary Computing a. b. c.

2. USC Economics slide show by Shivendra Awasthi ???? An introduction to game theory Today: The fundamentals of game theory, including Nash equilibrium

3. Introduction to Game Theory We can look at market situations with two players (typically firms) or games How can we determine the optimal strategy for each players? Although we will look at situations where each player can make only one of two decisions, theory easily extends to three or more decisions

4. Christoph F. Eick Game Theory2 For introduction see: https://en.wikipedia.org/wiki/Game_theory

5. Christoph F. Eick Russian Hunter 180 km east of Minsk Game Theory Game theory is "the study of mathematical models of conflict and cooperation between intelligent rational decision-makers." Game theory is mainly used in economics, political science, security and psychology, as well as AI, computer science, biology and games. Differences: collaboration is an important aspect, not only in sequential games but also parallel games; there could be many players that can take many actions (e.g. wild life project where protectors defend wildlife against poachers) https://www.engadget.com/2017/05/21/drones-ai-help-stop-poaching-africa/ https://www.youtube.com/watch?v=e44pWdvUwoc&t=3365s http://www.natureworldnews.com/articles/21181/20160425/game-theory-artificial-intelligence-help-wildlife-conservation-outwitting-poachers.htm https://www.zmescience.com/science/news-science/artificial-intelligence-poaching-logging/ https://ui.adsabs.harvard.edu/abs/2020arXiv200612411X/abstract Optional GHC Presentation about this topics maybe in late March/Early April --see website! Game Theory tries to determine the best strategy (ies); strategies can be mixed (probabilistic). Applying Game Theory to challenging AI problems is popular these days.

6. Who is this?

7. John Nash, the person portrayed in A Beautiful Mind https://en.wikipedia.org/wiki/A_Beautiful_Mind_%28film%29

8. John Nash One of the early researchers in game theory His work resulted in a form of equilibrium named after him

9. Three elements in every game Players Two or more for most games that are interesting Strategies available to each player Payoffs Based on your decision(s) and the decision(s) of other(s)

10. Game theory: Payoff matrix Person 2 A payoff matrix shows the payout to each player, given the decision of each player Action C Action D Action A 10, 2 8, 3 Person 1 Action B 12, 4 10, 1

11. How do we interpret this box? The first number in each box determines the payout for Person 1 The second number determines the payout for Person 2 Person 2 Action C 10, 2 Action D 8, 3 Person 1 Action A Action B 12, 4 10, 1

12. How do we interpret this box? Example If Person 1 chooses Action A and Person 2 chooses Action D, then Person 1 receives a payout of 8 and Person 2 receives a payout of 3 Person 2 Action C 10, 2 Action D 8, 3 Person 1 Action A Action B 12, 4 10, 1

13. Back to a Core Principle: Equilibrium The type of equilibrium we are looking for here is called Nash equilibrium Nash equilibrium: Any combination of strategies in which each player s strategy is his or her best choice, given the other players choices (F/B p. 322) Exactly one person deviating from a NE strategy would result in the same payout or lower payout for that person

14. How do we find Nash equilibrium (NE)? Step 1: Pretend you are one of the players Step 2: Assume that your opponent picks a particular action Step 3: Determine your best strategy (strategies), given your opponent s action Underline any best choice in the payoff matrix Step 4: Repeat Steps 2 & 3 for any other opponent strategies Step 5: Repeat Steps 1 through 4 for the other player Step 6: Any entry with all numbers underlined is NE

15. Steps 1 and 2 Person 2 Assume that you are Person 1 Given that Person 2 chooses Action C, what is Person 1 s best choice? Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

16. Step 3: Person 2 Underline best payout, given the choice of the other player Choose Action B, since 12 > 10 underline 12 Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

17. Step 4 Person 2 Now assume that Person 2 chooses Action D Here, 10 > 8 Choose and underline 10 Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

18. Step 5 Person 2 Now, assume you are Person 2 If Person 1 chooses A 3 > 2 underline 3 If Person 1 chooses B 4 > 1 underline 4 Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

19. Step 6 Person 2 Which box(es) have underlines under both numbers? Person 1 chooses B and Person 2 chooses C This is the only NE Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

20. Double check our NE Person 2 What if Person 1 deviates from NE? Could choose A and get 10 Person 1 s payout is lower by deviating Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

21. Double check our NE Person 2 What if Person 2 deviates from NE? Could choose D and get 1 Person 2 s payout is lower by deviating Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

22. Dominant strategy Person 2 A strategy is dominant if that choice is definitely made no matter what the other person chooses Example: Person 1 has a dominant strategy of choosing B Action C Action D Person 1 Action A 10, 2 8, 3 Action B 12, 4 10, 1

23. New example Person 2 Suppose in this example that two people are simultaneously going to decide on this game Yes No Person 1 Yes 20, 20 5, 10 No 10, 5 10, 10

24. New example Person 2 We will go through the same steps to determine NE Yes No Person 1 Yes 20, 20 5, 10 No 10, 5 10, 10

25. Two NE possible Person 2 (Yes, Yes) and (No, No) are both NE Although (Yes, Yes) is the more efficient outcome, we have no way to predict which outcome will actually occur Yes No Person 1 Yes 20, 20 5, 10 No 10, 5 10, 10

26. Two NE possible When there are multiple NE that are possible, economic theory tells us little about which outcome occurs with certainty

27. Two NE possible Additional information or actions may help to determine outcome If people could act sequentially instead of simultaneously, we could see that 20, 20 would occur in equilibrium

28. Sequential decisions Suppose that decisions can be made sequentially We can work backwards to determine how people will behave We will examine the last decision first and then work toward the first decision To do this, we will use a decision tree

29. Decision tree in a sequential game: Person 1 chooses first 20, 20 Person 2 chooses yes Person 1 chooses yes B 5, 10 Person 2 chooses no A Person 2 chooses yes Person 1 chooses no C 10, 5 Person 2 chooses no 10, 10 Note: This is no zero sum game!

30. Decision tree in a sequential game: Person 1 chooses first Given point B, Person 2 will choose yes (20 > 10) 20, 20 Person 2 chooses yes Person 1 chooses yes B 5, 10 Person 2 chooses no A Person 2 chooses yes Person 1 chooses no C 10, 5 Given point C, Person 2 will choose no (10 > 5) Person 2 chooses no 10, 10

31. Decision tree in a sequential game: Person 1 chooses first If Person 1 is rational, she will ignore potential choices that Person 2 will not make Example: Person 2 will not choose yes after Person 1 chooses no 20, 20 Person 2 chooses yes Person 1 chooses yes B 5, 10 Person 2 chooses no A Person 2 chooses yes Person 1 chooses no C 10, 5 Person 2 chooses no 10, 10

32. Decision tree in a sequential game: Person 1 chooses first If Person 1 knows that Person 2 is rational, then she will choose yes, since 20 > 10 Person 2 makes a decision from point B, and he will choose yes also Payout: (20, 20) 20, 20 Person 2 chooses yes Person 1 chooses yes B 5, 10 Person 2 chooses no A Person 2 chooses yes Person 1 chooses no C 10, 5 Person 2 chooses no 10, 10

33. Summary Game theory Simultaneous decisions NE Sequential decisions Some NE may not occur if people are not rational

34. Can you think of ways game theory can be used in these games?