際際滷

際際滷Share a Scribd company logo
Introduction to
Game Theory
General approach
 Brief History of Game Theory
 Payoff Matrix
 Types of Games
 Basic Strategies
 Evolutionary Concepts
 Limitations and Problems
Brief History of Game Theory
 1913 - E. Zermelo provides the first theorem of
game theory; asserts that chess is strictly
determined
 1928 - John von Neumann proves the minimax
theorem
 1944 - John von Neumann & Oskar
Morgenstern write "Theory of Games and
Economic Behavior
 1950-1953 - John Nash describes Nash
equilibrium
Rationality
Assumptions:
 humans are rational beings
 humans always seek the best alternative
in a set of possible choices
Why assume rationality?
 narrow down the range of possibilities
 predictability
Utility Theory
Utility Theory based on:
 rationality
 maximization of utility
 may not be a linear function of income or
wealth
It is a quantification of a person's preferences
with respect to certain objects.
What is Game Theory?
Game theory is a study of how to
mathematically determine the best strategy for
given conditions in order to optimize the
outcome
Game Theory
 Finding acceptable, if not optimal,
strategies in conflict situations.
 Abstraction of real complex situation
 Game theory is highly mathematical
 Game theory assumes all human
interactions can be understood and
navigated by presumptions.
Why is game theory important?
 All intelligent beings make decisions all the time.
 AII needs to perform these tasks as a result.
 Helps us to analyze situations more rationally and
formulate an acceptable alternative with respect to
circumstance.
 Useful in modeling strategic decision-making
 Games against opponents
 Games against "nature
 Provides structured insight into the value of
information
Types of Games
Sequential vs. Simultaneous moves
Single Play vs. Iterated
Zero vs. non-zero sum
Perfect vs. Imperfect information
Cooperative vs. conflict
Zero-Sum Games
 The sum of the payoffs remains constant
during the course of the game.
 Two sides in conflict
 Being well informed always helps a
player
Non-zero Sum Game
 The sum of payoffs is not constant during the
course of game play.
 Players may co-operate or compete
 Being well informed may harm a player.
Games of Perfect Information
 The information concerning an opponents
move is well known in advance.
 All sequential move games are of this type.
Imperfect Information
 Partial or no information concerning the
opponent is given in advance to the players
decision.
 Imperfect information may be diminished
over time if the same game with the same
opponent is to be repeated.
Key Area of Interest
 chance
 strategy
Matrix Notation
(Column) Player II
Strategy A Strategy B
(Row) Player I
Strategy A (P1, P2) (P1, P2)
Strategy B (P1, P2) (P1, P2)
Notes: Player I's strategy A may be different from Player II's.
P2 can be omitted if zero-sum game
Prisoners Dilemma &
Other famous games
A sample of other games:
Marriage
Disarmament (my generals are
more irrational than yours)
Prisoners Dilemma
Notes: Higher payoffs (longer sentences) are bad.
Non-cooperative equilibrium  Joint maximum
Institutionalized solutions (a la criminal organizations, KSM)
NCE
Jt. max.
Games of Conflict
 Two sides competing against each other
 Usually caused by complete lack of
information about the opponent or the game
 Characteristic of zero-sum games
Games of Co-operation
Players may improve payoff through
 communicating
 forming binding coalitions & agreements
 do not apply to zero-sum games
Prisoners Dilemma
with Cooperation
Prisoners Dilemma with Iteration
 Infinite number of iterations
 Fear of retaliation
 Fixed number of iteration
 Domino effect
Basic Strategies
1. Plan ahead and look back
2. Use a dominating strategy if possible
3. Eliminate any dominated strategies
4. Look for any equilibrium
5. Mix up the strategies
Plan ahead and look back
If you have a dominating strategy,
use it
Use
strategy 1
Eliminate any dominated
strategy
Eliminate
strategy 2 as
its dominated
by strategy 1
Look for any equilibrium
Dominating Equilibrium
Minimax Equilibrium
Nash Equilibrium
Maximin & Minimax Equilibrium
 Minimax - to minimize the maximum loss
(defensive)
 Maximin - to maximize the minimum gain
(offensive)
 Minimax = Maximin
Maximin & Minimax
Equilibrium Strategies
Definition: Nash Equilibrium
If there is a set of strategies with the property
that no player can benefit by changing her
strategy while the other players keep their
strategies unchanged, then that set of
strategies and the corresponding payoffs
constitute the Nash Equilibrium. 
Source: http://www.lebow.drexel.edu/economics/mccain/game/game.html
Is this a Nash Equilibrium?
Cost to press
button = 2 units
When button is pressed,
food given = 10 units
Boxed Pigs Example
Decisions, decisions...
Time for "real-life" decision making
 Holmes & Moriarity in "The Final Problem"
 What would you do
 If you were Holmes?
 If you were Moriarity?
 Possibly interesting digressions?
 Why was Moriarity so evil?
 What really happened?
What do we mean by reality?
What changed the reality?
Mixed Strategy
Mixed Strategy Solution
Value in
Safe
Probability
of being
Guarded
Expected
Loss
Safe 1 10,000
$ 1 / 11 9,091
$
Safe 2 100,000
$ 10 / 11 9,091
$
Both 110,000
$
The Payoff Matrix
for Holmes & Moriarity
P
l
a
y
e
r
#
1
Player #2
Strategy #1 Strategy #2
Strategy #1
Strategy #2
Payoff (1,1) Payoff (1,2)
Payoff (2,1) Payoff (2,2)
Where is game theory
currently used?
Ecology
Networks
Economics
Limitations & Problems
 Assumes players always maximize their
outcomes
 Some outcomes are difficult to provide a
utility for
 Not all of the payoffs can be quantified
 Not applicable to all problems
Summary
 What is game theory?
 Abstraction modeling multi-person interactions
 How is game theory applied?
 Payoff matrix contains each persons utilities for
various strategies
 Who uses game theory?
 Economists, Ecologists, Network people,...
 How is this related to AI?
 Provides a method to simulate a thinking agent
Sources
 Much more available on the web.
 These slides (with changes and additions) adapted
from:
http://pages.cpsc.ucalgary.ca/~jacob/Courses/Winter2000/CPSC533/Pages/i
ndex.html
 Three interesting classics:
 John von Neumann & Oskar Morgenstern, Theory of
Games & Economic Behavior (Princeton, 1944).
 John McDonald, Strategy in Poker, Business & War
(Norton, 1950)
 Oskar Morgenstern, "The Theory of Games," Scientific
American, May 1949; translated as "Theorie des Spiels,"
Die Amerikanische Rundschau, August 1949.

More Related Content

Similar to Introduction to Game Theory for engineering.ppt (20)

Econ
EconEcon
Econ
KUWAILITH
Game Theory Economics
Game Theory EconomicsGame Theory Economics
Game Theory Economics
Siliguri Institute of Technology ( A unit of Techno India Group)
Gamec Theory
Gamec TheoryGamec Theory
Gamec Theory
Mr. Vikram Singh Slathia
Game theory
Game theoryGame theory
Game theory
amaroks
navingameppt-191018085333.ppt, game thoery
navingameppt-191018085333.ppt, game thoerynavingameppt-191018085333.ppt, game thoery
navingameppt-191018085333.ppt, game thoery
SHIBABAWZEWDU
Lecture OverviewSolving the prisoners dilemmaInstrumental r.docx
Lecture OverviewSolving the prisoners dilemmaInstrumental r.docxLecture OverviewSolving the prisoners dilemmaInstrumental r.docx
Lecture OverviewSolving the prisoners dilemmaInstrumental r.docx
SHIVA101531
Game Theory_1.pptx
Game Theory_1.pptxGame Theory_1.pptx
Game Theory_1.pptx
ssuser8c2631
Game Theory_ 2.pptx
Game Theory_ 2.pptxGame Theory_ 2.pptx
Game Theory_ 2.pptx
ssuser8c2631
Game Theory Introduction
Game Theory IntroductionGame Theory Introduction
Game Theory Introduction
Robin Anderson
An introduction to Game Theory
An introduction to Game TheoryAn introduction to Game Theory
An introduction to Game Theory
Paul Trafford
Cdam 2001-09
Cdam 2001-09Cdam 2001-09
Cdam 2001-09
Naa Adom
Game theory
Game theoryGame theory
Game theory
Lalit Sharma
OR PPT 280322 maximin final - nikhil tiwari.pptx
OR PPT 280322 maximin final - nikhil tiwari.pptxOR PPT 280322 maximin final - nikhil tiwari.pptx
OR PPT 280322 maximin final - nikhil tiwari.pptx
VivekSaurabh7
Unit_V.Game theory.pptx abcdefghijlkmncnc
Unit_V.Game theory.pptx abcdefghijlkmncncUnit_V.Game theory.pptx abcdefghijlkmncnc
Unit_V.Game theory.pptx abcdefghijlkmncnc
NamitaSingh876884
Unit_V.Game theory.pptxzxnbxjjbXjbM mBBM
Unit_V.Game theory.pptxzxnbxjjbXjbM mBBMUnit_V.Game theory.pptxzxnbxjjbXjbM mBBM
Unit_V.Game theory.pptxzxnbxjjbXjbM mBBM
NamitaSingh876884
Game Theory-happy-PC.pchcgjhjhmghmghghghjptx
Game Theory-happy-PC.pchcgjhjhmghmghghghjptxGame Theory-happy-PC.pchcgjhjhmghmghghghjptx
Game Theory-happy-PC.pchcgjhjhmghmghghghjptx
SarthakVarma4
Game Theory
Game TheoryGame Theory
Game Theory
Ali Salek
Game theory
Game theoryGame theory
Game theory
Pankaj Sabherwal
TermPaper
TermPaperTermPaper
TermPaper
Karl Lassy
Ssrn a brief inrtoduction to the basic of game theory
Ssrn a brief inrtoduction to the basic of game theorySsrn a brief inrtoduction to the basic of game theory
Ssrn a brief inrtoduction to the basic of game theory
Ying wei (Joe) Chou
Game theory
Game theoryGame theory
Game theory
amaroks
navingameppt-191018085333.ppt, game thoery
navingameppt-191018085333.ppt, game thoerynavingameppt-191018085333.ppt, game thoery
navingameppt-191018085333.ppt, game thoery
SHIBABAWZEWDU
Lecture OverviewSolving the prisoners dilemmaInstrumental r.docx
Lecture OverviewSolving the prisoners dilemmaInstrumental r.docxLecture OverviewSolving the prisoners dilemmaInstrumental r.docx
Lecture OverviewSolving the prisoners dilemmaInstrumental r.docx
SHIVA101531
Game Theory_1.pptx
Game Theory_1.pptxGame Theory_1.pptx
Game Theory_1.pptx
ssuser8c2631
Game Theory_ 2.pptx
Game Theory_ 2.pptxGame Theory_ 2.pptx
Game Theory_ 2.pptx
ssuser8c2631
Game Theory Introduction
Game Theory IntroductionGame Theory Introduction
Game Theory Introduction
Robin Anderson
An introduction to Game Theory
An introduction to Game TheoryAn introduction to Game Theory
An introduction to Game Theory
Paul Trafford
Cdam 2001-09
Cdam 2001-09Cdam 2001-09
Cdam 2001-09
Naa Adom
OR PPT 280322 maximin final - nikhil tiwari.pptx
OR PPT 280322 maximin final - nikhil tiwari.pptxOR PPT 280322 maximin final - nikhil tiwari.pptx
OR PPT 280322 maximin final - nikhil tiwari.pptx
VivekSaurabh7
Unit_V.Game theory.pptx abcdefghijlkmncnc
Unit_V.Game theory.pptx abcdefghijlkmncncUnit_V.Game theory.pptx abcdefghijlkmncnc
Unit_V.Game theory.pptx abcdefghijlkmncnc
NamitaSingh876884
Unit_V.Game theory.pptxzxnbxjjbXjbM mBBM
Unit_V.Game theory.pptxzxnbxjjbXjbM mBBMUnit_V.Game theory.pptxzxnbxjjbXjbM mBBM
Unit_V.Game theory.pptxzxnbxjjbXjbM mBBM
NamitaSingh876884
Game Theory-happy-PC.pchcgjhjhmghmghghghjptx
Game Theory-happy-PC.pchcgjhjhmghmghghghjptxGame Theory-happy-PC.pchcgjhjhmghmghghghjptx
Game Theory-happy-PC.pchcgjhjhmghmghghghjptx
SarthakVarma4
Game Theory
Game TheoryGame Theory
Game Theory
Ali Salek
Ssrn a brief inrtoduction to the basic of game theory
Ssrn a brief inrtoduction to the basic of game theorySsrn a brief inrtoduction to the basic of game theory
Ssrn a brief inrtoduction to the basic of game theory
Ying wei (Joe) Chou

More from ashaby (20)

Kuliah_7-Basic 7 Tools of Quallity.ppt (1).pdf
Kuliah_7-Basic 7 Tools of Quallity.ppt (1).pdfKuliah_7-Basic 7 Tools of Quallity.ppt (1).pdf
Kuliah_7-Basic 7 Tools of Quallity.ppt (1).pdf
ashaby
Chap013.-Network Design for engineer .ppt
Chap013.-Network Design for engineer .pptChap013.-Network Design for engineer .ppt
Chap013.-Network Design for engineer .ppt
ashaby
NETWORK PROJECT for engineering manufactur.ppt
NETWORK PROJECT for engineering manufactur.pptNETWORK PROJECT for engineering manufactur.ppt
NETWORK PROJECT for engineering manufactur.ppt
ashaby
Algoritma Pencarian Heuristik (TM 12a).pptx
Algoritma Pencarian Heuristik (TM 12a).pptxAlgoritma Pencarian Heuristik (TM 12a).pptx
Algoritma Pencarian Heuristik (TM 12a).pptx
ashaby
3-Pengantar-SCM for engineering manufacture.ppt
3-Pengantar-SCM for engineering manufacture.ppt3-Pengantar-SCM for engineering manufacture.ppt
3-Pengantar-SCM for engineering manufacture.ppt
ashaby
Total Quality Management for engineering
Total Quality Management  for engineeringTotal Quality Management  for engineering
Total Quality Management for engineering
ashaby
Production activity control - schedulling
Production activity control - schedullingProduction activity control - schedulling
Production activity control - schedulling
ashaby
Manajemen Supply Chain for industrial.pptx
Manajemen Supply Chain for industrial.pptxManajemen Supply Chain for industrial.pptx
Manajemen Supply Chain for industrial.pptx
ashaby
Pengertian_ISO untuk teknik industri.pptx
Pengertian_ISO untuk teknik industri.pptxPengertian_ISO untuk teknik industri.pptx
Pengertian_ISO untuk teknik industri.pptx
ashaby
502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx
502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx
502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx
ashaby
ch06 solution design of experiment for eng
ch06 solution design of experiment for engch06 solution design of experiment for eng
ch06 solution design of experiment for eng
ashaby
Model Persediaan Deterministik for planning
Model Persediaan Deterministik for planningModel Persediaan Deterministik for planning
Model Persediaan Deterministik for planning
ashaby
2. Manajemen Supply Chain for industrial
2. Manajemen Supply Chain for industrial2. Manajemen Supply Chain for industrial
2. Manajemen Supply Chain for industrial
ashaby
Pengantar SCM for industrial engineering
Pengantar SCM for industrial engineeringPengantar SCM for industrial engineering
Pengantar SCM for industrial engineering
ashaby
SUPPLY CHAIN MANAGEMENT for industrial engineering
SUPPLY CHAIN MANAGEMENT for industrial engineeringSUPPLY CHAIN MANAGEMENT for industrial engineering
SUPPLY CHAIN MANAGEMENT for industrial engineering
ashaby
Aggregate Planning for industrial engineering
Aggregate Planning for industrial engineeringAggregate Planning for industrial engineering
Aggregate Planning for industrial engineering
ashaby
Strategi_Tata_Letak dan layout teknik industri
Strategi_Tata_Letak dan layout teknik industriStrategi_Tata_Letak dan layout teknik industri
Strategi_Tata_Letak dan layout teknik industri
ashaby
materi Statistik Sosial dan analisis data .ppt
materi Statistik Sosial dan analisis data .pptmateri Statistik Sosial dan analisis data .ppt
materi Statistik Sosial dan analisis data .ppt
ashaby
TIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptxTIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptx
ashaby
TIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptxTIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptx
ashaby
Kuliah_7-Basic 7 Tools of Quallity.ppt (1).pdf
Kuliah_7-Basic 7 Tools of Quallity.ppt (1).pdfKuliah_7-Basic 7 Tools of Quallity.ppt (1).pdf
Kuliah_7-Basic 7 Tools of Quallity.ppt (1).pdf
ashaby
Chap013.-Network Design for engineer .ppt
Chap013.-Network Design for engineer .pptChap013.-Network Design for engineer .ppt
Chap013.-Network Design for engineer .ppt
ashaby
NETWORK PROJECT for engineering manufactur.ppt
NETWORK PROJECT for engineering manufactur.pptNETWORK PROJECT for engineering manufactur.ppt
NETWORK PROJECT for engineering manufactur.ppt
ashaby
Algoritma Pencarian Heuristik (TM 12a).pptx
Algoritma Pencarian Heuristik (TM 12a).pptxAlgoritma Pencarian Heuristik (TM 12a).pptx
Algoritma Pencarian Heuristik (TM 12a).pptx
ashaby
3-Pengantar-SCM for engineering manufacture.ppt
3-Pengantar-SCM for engineering manufacture.ppt3-Pengantar-SCM for engineering manufacture.ppt
3-Pengantar-SCM for engineering manufacture.ppt
ashaby
Total Quality Management for engineering
Total Quality Management  for engineeringTotal Quality Management  for engineering
Total Quality Management for engineering
ashaby
Production activity control - schedulling
Production activity control - schedullingProduction activity control - schedulling
Production activity control - schedulling
ashaby
Manajemen Supply Chain for industrial.pptx
Manajemen Supply Chain for industrial.pptxManajemen Supply Chain for industrial.pptx
Manajemen Supply Chain for industrial.pptx
ashaby
Pengertian_ISO untuk teknik industri.pptx
Pengertian_ISO untuk teknik industri.pptxPengertian_ISO untuk teknik industri.pptx
Pengertian_ISO untuk teknik industri.pptx
ashaby
502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx
502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx
502159311-Tugas-PPT-Pengantar-ISO-Standardisasi-Nur-Safitriani-ITERA.pptx
ashaby
ch06 solution design of experiment for eng
ch06 solution design of experiment for engch06 solution design of experiment for eng
ch06 solution design of experiment for eng
ashaby
Model Persediaan Deterministik for planning
Model Persediaan Deterministik for planningModel Persediaan Deterministik for planning
Model Persediaan Deterministik for planning
ashaby
2. Manajemen Supply Chain for industrial
2. Manajemen Supply Chain for industrial2. Manajemen Supply Chain for industrial
2. Manajemen Supply Chain for industrial
ashaby
Pengantar SCM for industrial engineering
Pengantar SCM for industrial engineeringPengantar SCM for industrial engineering
Pengantar SCM for industrial engineering
ashaby
SUPPLY CHAIN MANAGEMENT for industrial engineering
SUPPLY CHAIN MANAGEMENT for industrial engineeringSUPPLY CHAIN MANAGEMENT for industrial engineering
SUPPLY CHAIN MANAGEMENT for industrial engineering
ashaby
Aggregate Planning for industrial engineering
Aggregate Planning for industrial engineeringAggregate Planning for industrial engineering
Aggregate Planning for industrial engineering
ashaby
Strategi_Tata_Letak dan layout teknik industri
Strategi_Tata_Letak dan layout teknik industriStrategi_Tata_Letak dan layout teknik industri
Strategi_Tata_Letak dan layout teknik industri
ashaby
materi Statistik Sosial dan analisis data .ppt
materi Statistik Sosial dan analisis data .pptmateri Statistik Sosial dan analisis data .ppt
materi Statistik Sosial dan analisis data .ppt
ashaby
TIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptxTIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 2), Kls. KK_D3, 02-23.24.pptx
ashaby
TIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptxTIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptx
TIN103_PTI Intro. to IE, (Session 1), Kls. KK_D3, 02-23.24.pptx
ashaby

Recently uploaded (20)

UHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptx
UHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptxUHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptx
UHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptx
ariomthermal2031
DBMS Notes selection projection aggregate
DBMS Notes selection projection aggregateDBMS Notes selection projection aggregate
DBMS Notes selection projection aggregate
Sreedhar Chowdam
Caddlance PortfolioMixed Projects 2024.pdf
Caddlance PortfolioMixed Projects 2024.pdfCaddlance PortfolioMixed Projects 2024.pdf
Caddlance PortfolioMixed Projects 2024.pdf
sonam254547
FIRST Tech Challenge/Robotics: Scouting out the competition
FIRST Tech Challenge/Robotics: Scouting out the competitionFIRST Tech Challenge/Robotics: Scouting out the competition
FIRST Tech Challenge/Robotics: Scouting out the competition
FTC Team 23014
Call for Papers - 6th International Conference on Big Data and Machine Learni...
Call for Papers - 6th International Conference on Big Data and Machine Learni...Call for Papers - 6th International Conference on Big Data and Machine Learni...
Call for Papers - 6th International Conference on Big Data and Machine Learni...
IJDKP
Requirements Engineering for Secure Software
Requirements Engineering for Secure SoftwareRequirements Engineering for Secure Software
Requirements Engineering for Secure Software
Dr Sarika Jadhav
UHV UNIT-I INTRODUCTION TO VALUE EDUCATION .pptx
UHV UNIT-I INTRODUCTION TO VALUE EDUCATION  .pptxUHV UNIT-I INTRODUCTION TO VALUE EDUCATION  .pptx
UHV UNIT-I INTRODUCTION TO VALUE EDUCATION .pptx
ariomthermal2031
Ktor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascio
Ktor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascioKtor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascio
Ktor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascio
infogdgmi
Production Planning & Control and Inventory Management.pptx
Production Planning & Control and Inventory Management.pptxProduction Planning & Control and Inventory Management.pptx
Production Planning & Control and Inventory Management.pptx
VirajPasare
Protecting Secrets in Transparent Systems
Protecting Secrets in Transparent SystemsProtecting Secrets in Transparent Systems
Protecting Secrets in Transparent Systems
LucaBarbaro3
Urban Design and Planning Portfolio .pdf
Urban Design and Planning Portfolio .pdfUrban Design and Planning Portfolio .pdf
Urban Design and Planning Portfolio .pdf
sonam254547
module-4.1-Class notes_R and DD_basket-IV -.pdf
module-4.1-Class notes_R and DD_basket-IV -.pdfmodule-4.1-Class notes_R and DD_basket-IV -.pdf
module-4.1-Class notes_R and DD_basket-IV -.pdf
ritikkumarchaudhury7
GIS Mapping Caddlance Portfolio 2025 .pdf
GIS Mapping Caddlance Portfolio 2025 .pdfGIS Mapping Caddlance Portfolio 2025 .pdf
GIS Mapping Caddlance Portfolio 2025 .pdf
sonam254547
CCNA_Product_OverviewCCNA_Productsa.pptx
CCNA_Product_OverviewCCNA_Productsa.pptxCCNA_Product_OverviewCCNA_Productsa.pptx
CCNA_Product_OverviewCCNA_Productsa.pptx
UdayakumarAllimuthu
Software security: Security a Software Issue
Software security: Security a Software IssueSoftware security: Security a Software Issue
Software security: Security a Software Issue
Dr Sarika Jadhav
UHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptx
UHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptxUHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptx
UHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptx
ariomthermal2031
Artificial-Intelligence-in-Cybersecurity.pptx
Artificial-Intelligence-in-Cybersecurity.pptxArtificial-Intelligence-in-Cybersecurity.pptx
Artificial-Intelligence-in-Cybersecurity.pptx
Vigneshwarar3
Mastering Secure Login Mechanisms for React Apps.pdf
Mastering Secure Login Mechanisms for React Apps.pdfMastering Secure Login Mechanisms for React Apps.pdf
Mastering Secure Login Mechanisms for React Apps.pdf
Brion Mario
Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜
Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜
Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜
ssuserb91a20
Unit-03 Cams and Followers in Mechanisms of Machines.pptx
Unit-03 Cams and Followers in Mechanisms of Machines.pptxUnit-03 Cams and Followers in Mechanisms of Machines.pptx
Unit-03 Cams and Followers in Mechanisms of Machines.pptx
Kirankumar Jagtap
UHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptx
UHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptxUHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptx
UHV unit-2UNIT - II HARMONY IN THE HUMAN BEING.pptx
ariomthermal2031
DBMS Notes selection projection aggregate
DBMS Notes selection projection aggregateDBMS Notes selection projection aggregate
DBMS Notes selection projection aggregate
Sreedhar Chowdam
Caddlance PortfolioMixed Projects 2024.pdf
Caddlance PortfolioMixed Projects 2024.pdfCaddlance PortfolioMixed Projects 2024.pdf
Caddlance PortfolioMixed Projects 2024.pdf
sonam254547
FIRST Tech Challenge/Robotics: Scouting out the competition
FIRST Tech Challenge/Robotics: Scouting out the competitionFIRST Tech Challenge/Robotics: Scouting out the competition
FIRST Tech Challenge/Robotics: Scouting out the competition
FTC Team 23014
Call for Papers - 6th International Conference on Big Data and Machine Learni...
Call for Papers - 6th International Conference on Big Data and Machine Learni...Call for Papers - 6th International Conference on Big Data and Machine Learni...
Call for Papers - 6th International Conference on Big Data and Machine Learni...
IJDKP
Requirements Engineering for Secure Software
Requirements Engineering for Secure SoftwareRequirements Engineering for Secure Software
Requirements Engineering for Secure Software
Dr Sarika Jadhav
UHV UNIT-I INTRODUCTION TO VALUE EDUCATION .pptx
UHV UNIT-I INTRODUCTION TO VALUE EDUCATION  .pptxUHV UNIT-I INTRODUCTION TO VALUE EDUCATION  .pptx
UHV UNIT-I INTRODUCTION TO VALUE EDUCATION .pptx
ariomthermal2031
Ktor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascio
Ktor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascioKtor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascio
Ktor - Definizioni di Path, Integrazioni, Plugin e build fino al rilascio
infogdgmi
Production Planning & Control and Inventory Management.pptx
Production Planning & Control and Inventory Management.pptxProduction Planning & Control and Inventory Management.pptx
Production Planning & Control and Inventory Management.pptx
VirajPasare
Protecting Secrets in Transparent Systems
Protecting Secrets in Transparent SystemsProtecting Secrets in Transparent Systems
Protecting Secrets in Transparent Systems
LucaBarbaro3
Urban Design and Planning Portfolio .pdf
Urban Design and Planning Portfolio .pdfUrban Design and Planning Portfolio .pdf
Urban Design and Planning Portfolio .pdf
sonam254547
module-4.1-Class notes_R and DD_basket-IV -.pdf
module-4.1-Class notes_R and DD_basket-IV -.pdfmodule-4.1-Class notes_R and DD_basket-IV -.pdf
module-4.1-Class notes_R and DD_basket-IV -.pdf
ritikkumarchaudhury7
GIS Mapping Caddlance Portfolio 2025 .pdf
GIS Mapping Caddlance Portfolio 2025 .pdfGIS Mapping Caddlance Portfolio 2025 .pdf
GIS Mapping Caddlance Portfolio 2025 .pdf
sonam254547
CCNA_Product_OverviewCCNA_Productsa.pptx
CCNA_Product_OverviewCCNA_Productsa.pptxCCNA_Product_OverviewCCNA_Productsa.pptx
CCNA_Product_OverviewCCNA_Productsa.pptx
UdayakumarAllimuthu
Software security: Security a Software Issue
Software security: Security a Software IssueSoftware security: Security a Software Issue
Software security: Security a Software Issue
Dr Sarika Jadhav
UHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptx
UHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptxUHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptx
UHV UNIT-3 HARMONY IN THE FAMILY AND SOCIETY.pptx
ariomthermal2031
Artificial-Intelligence-in-Cybersecurity.pptx
Artificial-Intelligence-in-Cybersecurity.pptxArtificial-Intelligence-in-Cybersecurity.pptx
Artificial-Intelligence-in-Cybersecurity.pptx
Vigneshwarar3
Mastering Secure Login Mechanisms for React Apps.pdf
Mastering Secure Login Mechanisms for React Apps.pdfMastering Secure Login Mechanisms for React Apps.pdf
Mastering Secure Login Mechanisms for React Apps.pdf
Brion Mario
Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜
Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜
Chapter1-Introduction 旅留粒粒旅虜劉 劉僚僚凌旅竜
ssuserb91a20
Unit-03 Cams and Followers in Mechanisms of Machines.pptx
Unit-03 Cams and Followers in Mechanisms of Machines.pptxUnit-03 Cams and Followers in Mechanisms of Machines.pptx
Unit-03 Cams and Followers in Mechanisms of Machines.pptx
Kirankumar Jagtap

Introduction to Game Theory for engineering.ppt

  • 2. General approach Brief History of Game Theory Payoff Matrix Types of Games Basic Strategies Evolutionary Concepts Limitations and Problems
  • 3. Brief History of Game Theory 1913 - E. Zermelo provides the first theorem of game theory; asserts that chess is strictly determined 1928 - John von Neumann proves the minimax theorem 1944 - John von Neumann & Oskar Morgenstern write "Theory of Games and Economic Behavior 1950-1953 - John Nash describes Nash equilibrium
  • 4. Rationality Assumptions: humans are rational beings humans always seek the best alternative in a set of possible choices Why assume rationality? narrow down the range of possibilities predictability
  • 5. Utility Theory Utility Theory based on: rationality maximization of utility may not be a linear function of income or wealth It is a quantification of a person's preferences with respect to certain objects.
  • 6. What is Game Theory? Game theory is a study of how to mathematically determine the best strategy for given conditions in order to optimize the outcome
  • 7. Game Theory Finding acceptable, if not optimal, strategies in conflict situations. Abstraction of real complex situation Game theory is highly mathematical Game theory assumes all human interactions can be understood and navigated by presumptions.
  • 8. Why is game theory important? All intelligent beings make decisions all the time. AII needs to perform these tasks as a result. Helps us to analyze situations more rationally and formulate an acceptable alternative with respect to circumstance. Useful in modeling strategic decision-making Games against opponents Games against "nature Provides structured insight into the value of information
  • 9. Types of Games Sequential vs. Simultaneous moves Single Play vs. Iterated Zero vs. non-zero sum Perfect vs. Imperfect information Cooperative vs. conflict
  • 10. Zero-Sum Games The sum of the payoffs remains constant during the course of the game. Two sides in conflict Being well informed always helps a player
  • 11. Non-zero Sum Game The sum of payoffs is not constant during the course of game play. Players may co-operate or compete Being well informed may harm a player.
  • 12. Games of Perfect Information The information concerning an opponents move is well known in advance. All sequential move games are of this type.
  • 13. Imperfect Information Partial or no information concerning the opponent is given in advance to the players decision. Imperfect information may be diminished over time if the same game with the same opponent is to be repeated.
  • 14. Key Area of Interest chance strategy
  • 15. Matrix Notation (Column) Player II Strategy A Strategy B (Row) Player I Strategy A (P1, P2) (P1, P2) Strategy B (P1, P2) (P1, P2) Notes: Player I's strategy A may be different from Player II's. P2 can be omitted if zero-sum game
  • 16. Prisoners Dilemma & Other famous games A sample of other games: Marriage Disarmament (my generals are more irrational than yours)
  • 17. Prisoners Dilemma Notes: Higher payoffs (longer sentences) are bad. Non-cooperative equilibrium Joint maximum Institutionalized solutions (a la criminal organizations, KSM) NCE Jt. max.
  • 18. Games of Conflict Two sides competing against each other Usually caused by complete lack of information about the opponent or the game Characteristic of zero-sum games
  • 19. Games of Co-operation Players may improve payoff through communicating forming binding coalitions & agreements do not apply to zero-sum games Prisoners Dilemma with Cooperation
  • 20. Prisoners Dilemma with Iteration Infinite number of iterations Fear of retaliation Fixed number of iteration Domino effect
  • 21. Basic Strategies 1. Plan ahead and look back 2. Use a dominating strategy if possible 3. Eliminate any dominated strategies 4. Look for any equilibrium 5. Mix up the strategies
  • 22. Plan ahead and look back
  • 23. If you have a dominating strategy, use it Use strategy 1
  • 24. Eliminate any dominated strategy Eliminate strategy 2 as its dominated by strategy 1
  • 25. Look for any equilibrium Dominating Equilibrium Minimax Equilibrium Nash Equilibrium
  • 26. Maximin & Minimax Equilibrium Minimax - to minimize the maximum loss (defensive) Maximin - to maximize the minimum gain (offensive) Minimax = Maximin
  • 28. Definition: Nash Equilibrium If there is a set of strategies with the property that no player can benefit by changing her strategy while the other players keep their strategies unchanged, then that set of strategies and the corresponding payoffs constitute the Nash Equilibrium. Source: http://www.lebow.drexel.edu/economics/mccain/game/game.html
  • 29. Is this a Nash Equilibrium?
  • 30. Cost to press button = 2 units When button is pressed, food given = 10 units Boxed Pigs Example
  • 32. Time for "real-life" decision making Holmes & Moriarity in "The Final Problem" What would you do If you were Holmes? If you were Moriarity? Possibly interesting digressions? Why was Moriarity so evil? What really happened? What do we mean by reality? What changed the reality?
  • 34. Mixed Strategy Solution Value in Safe Probability of being Guarded Expected Loss Safe 1 10,000 $ 1 / 11 9,091 $ Safe 2 100,000 $ 10 / 11 9,091 $ Both 110,000 $
  • 35. The Payoff Matrix for Holmes & Moriarity P l a y e r # 1 Player #2 Strategy #1 Strategy #2 Strategy #1 Strategy #2 Payoff (1,1) Payoff (1,2) Payoff (2,1) Payoff (2,2)
  • 36. Where is game theory currently used? Ecology Networks Economics
  • 37. Limitations & Problems Assumes players always maximize their outcomes Some outcomes are difficult to provide a utility for Not all of the payoffs can be quantified Not applicable to all problems
  • 38. Summary What is game theory? Abstraction modeling multi-person interactions How is game theory applied? Payoff matrix contains each persons utilities for various strategies Who uses game theory? Economists, Ecologists, Network people,... How is this related to AI? Provides a method to simulate a thinking agent
  • 39. Sources Much more available on the web. These slides (with changes and additions) adapted from: http://pages.cpsc.ucalgary.ca/~jacob/Courses/Winter2000/CPSC533/Pages/i ndex.html Three interesting classics: John von Neumann & Oskar Morgenstern, Theory of Games & Economic Behavior (Princeton, 1944). John McDonald, Strategy in Poker, Business & War (Norton, 1950) Oskar Morgenstern, "The Theory of Games," Scientific American, May 1949; translated as "Theorie des Spiels," Die Amerikanische Rundschau, August 1949.

Editor's Notes

  • #3: http://william-king.www.drexel.edu/top/class/histf.html
  • #4: Based on the assumption that human beings are absolutely rational in their economic choices. Specifically, the assumption is that each person maximizes her or his rewards -- profits, incomes, or subjective benefits -- in the circumstances that she or he faces. This hypothesis serves a double purpose in the study of the allocation of resources. First, it narrows the range of possibilities somewhat. Absolutely rational behavior is more predictable than irrational behavior. Second, it provides a criterion for evaluation of the efficiency of an economic system. If the system leads to a reduction in the rewards coming to some people, without producing more than compensating rewards to others (costs greater than benefits, broadly) then something is wrong. Pollution, the overexploitation of fisheries, and inadequate resources committed to research can all be examples of this. Source:http://www.lebow.drexel.edu/economics/mccain/game/game.html
  • #5: Few people would risk a sure gain of $1,000,000 for an even chance of gaining $10,000,000, for example. In fact, many decisions people make, such as buying insurance policies, playing lottery games, and gambling in a casino, indicate that they are not maximizing their average profits. Game theory does not attempt to indicate what a player's goal should be; instead, it shows the player how to attain his goal, whatever it may be. Von Neumann and Morgenstern understood this distinction, and so to accommodate all players, whatever their goals, they constructed a theory of utility. They began by listing certain axioms that they felt all "rational" decision makers would follow (for example, if a person likes tea better than milk, and milk better than coffee, then that person should like tea better than coffee). They then proved that for such rational decision makers it was possible to define a utility function that would reflect an individual's preferences; basically, a utility function assigns to each of a player's alternatives a number that conveys the relative attractiveness of that alternative. Maximizing someone's utility automatically determines his most preferred option. In recent years, however, some doubt has been raised about whether people actually behave in accordance with these rational rules. Source: http://search.britannica.com/bcom/eb/article/5/0,5716,117275+6,00.html Values assigned to alternatives is based on the relative attractiveness to an individual.
  • #6: game theory focuses on how groups of people interact. Game theory focuses on how players in economic games behave when, to reach their goals, they have to predict how their opponents will react to their moves. CONCLUSION: As a conclusion Game theory is the study of competitive interaction; it analyzes possible outcomes in situations where people are trying to score points off each other, whether in bridge, politics of war. You do this by trying to anticipate the reaction of your competitor to your next move and then factoring that reaction into your actual decision. It teaches people to think several moves ahead. From now on , Whoever it was who said it doesnt matter if you win or lose but how you play the game, missed the point. It matters very much. According to game theory, its how you play the game that usually determines whether you win or lose. Source:http://www.ug.bcc.bilkent.edu.tr/~zyilmaz/proposal.html
  • #7: It is highly mathematical in order to emulated human value judgement (mental rules, fuzzy input of good or bad) ex. Chess play
  • #8: WHY GAME THEORY IS IMPORTANT? Game theory is both easy and excruciatingly difficult. People use it all the time, average people, in their daily lives. It comes into play in mundane deals like buying a car, where a certain skill in haggling is required. The buyers offer is usually formulated on the basis of what he or she presumes the seller will take. The seller is guided by a presumption about how high the buyer will go. The outcome of this negotiation could be totally positive (if the deal satisfies both parties), totally negative (if it falls through), or positive for one party and less so for the other (depending on how much is paid.) It is used to describe any relationship and interaction, economic, social or political. And its useful in creating strategies for negotiators. It can help you win, and that is why companies and governments hire game theorists to write strategies against other players in whatever game theyre in. Mathematics and statistics are the tools they use. For example, during the Cold War the Pentagon became interested in game theory to help develop its nuclear strategy, and with some success. You dont make a move in chess without first trying to figure out how your opponent will react to it. Game theory assumes that all-human interactions, personal, institutional, economic, can be understood and navigated by presumptions similar to those of the chess player. Source:http://www.ug.bcc.bilkent.edu.tr/~zyilmaz/proposal.html
  • #10: In zero-sum games it never helps a player to give an adversary information, and it never harms a player to learn an opponent's strategy in advance. These rules do not necessarily hold true for nonzero-sum games, however. Source: http://search.britannica.com/bcom/eb/article/5/0,5716,117275+6,00.html
  • #11: Nonzero-sum game includes all games which are not constant-sum. In non-zero-sum game, the sum of the payoffs are not the same for all outcomes. Nonzero-sum games are mixed motive games. The interests of the players are neither strictly coincident nor strictly opposed. They generate intrapersonal and interpersonal conflicts. They are not always completely soluble but they provide insights into important areas of interdependent choice. In these games, one player's losses do not always equal another player's gains. Some nonzero-sum games are positive sum and some are negative sum: Negative sum games are competitive, but nobody really wins, rather, everybody loses. For example, a war or a strike. Positive sum games are cooperative, all players have one goal that they contribute together as in an educational game. For example, school newspapers or plays, building blocks, or a science exhibit. One major example of a two-person nonzero-sum game is the prisoner's dilemma. It is a non cooperative game because the players can not communicate their intentions. (See topic 'Automata & Games Theory') Source: http://artsci-ccwin.concordia.ca/edtech/ETEC606/conceptprinciples.html A player may want his opponent to be well-informed. In a labour-management dispute, for example, if the labour union is prepared for a strike, it behooves it to inform management and thereby possibly achieve its goal without a long, costly conflict. In this example, management is not harmed by the advance information (it, too, benefits by avoiding the costly strike), but in other nonzero-sum games a player can be at a disadvantage if he knows his opponent's strategy. A blackmailer, for example, benefits only if he informs his victim that he will harm the victim unless his terms are met. If he does not give this information to the intended victim, the blackmailer can still do damage but he has no reason to. Thus, knowledge of the blackmailer's strategy works to the victim's disadvantage. Source: http://search.britannica.com/bcom/eb/article/5/0,5716,117275+6,00.html
  • #12: A class of Game in which players move alternately and each player is completely informed of previous moves. Finite, Zero-Sum, two-player Games with perfect information (including checkers and chess) have a Saddle Point, and therefore one or more optimal strategies. However, the optimal strategy may be so difficult to compute as to be effectively impossible to determine (as in the game of Chess). Source:http://mathworld.wolfram.com/PerfectInformation.html
  • #20: It might seem that the paradox inherent in the prisoners' dilemma could be resolved if the game were played repeatedly. Players would learn that they do best when both act unselfishly and cooperate; if one player failed to cooperate in one game, the other player could retaliate by not cooperating in the next game and both would lose until they began to cooperate again. When the game is repeated a fixed number of times, however, this argument fails. According to the argument, when the two shopkeepers described above set up their stores at a 10-day county fair, each should maintain a high price, knowing that if he does not, his competitor will retaliate the next day. On the 10th day, however, each shopkeeper realizes that his competitor can no longer retaliate (the fair will be closed so there is no next day); therefore each shopkeeper should lower his price on the last day. But if each shopkeeper knows that his rival will lower the price on the 10th day, he has no incentive to maintain the high price on the ninth day. Continuing this reasoning, one concludes that "rational" shopkeepers will have a price war every day. It is only when the game is played repeatedly and neither player knows when the sequence will end that the cooperative strategy succeeds. Source:http://search.britannica.com/bcom/eb/article/5/0,5716,117275+6,00.html Lead to ESS.
  • #21: 1. Each player need to figure out the other players future responses and use them in calculating his/her best move. In AI sense, this involves the evaluation of all possible outcomes for all possible actions. (Charlie Brown Story) 2. Dominating strategy: A dominating strategy occurs if there exists a action whose associated outcome is always favorable regardless what action the other player makes. Ex. Football game again 3. Dominated strategy: A dominated strategy occurs if there exists an action whose associated outcome is always not in favor of the player regardless what action the other player makes. Ex. Football game again. Give a example where dominating strategy doesnt always associates with a dominated strategy.
  • #28: a unique outcome that satisfied conditions: (1) the solution must be independent of the choice of utility function (if a player prefers x to y and one function assigns x a utility of 10 and y a utility of 1 while a second function assigns them the values 20 and 2, the solution should not change); (2) it must be impossible for both players to simultaneously do better than the Nash solution (a condition known as Pareto optimality); (3) the solution must be independent of irrelevant alternatives (if unattractive options are added to or dropped from the list of alternatives, the Nash solution should not change); and (4) the solution must be symmetrical (if the players reverse their roles, the solution remains the same except that the payoffs are reversed). Source: http://search.britannica.com/bcom/eb/article/5/0,5716,117275+6,00.html