CS代考 Algorithmic Game Theory and Applications

Algorithmic Game Theory and Applications
Lecture 1: What is game theory?

Basic course information
Lecturer: ; Office: IF 5.20; Phone: 650 5197.
Lecture times: Monday&Thursday, 11:10-12:00; Mondays: Med School Building, Teviot Lecture Theatre– Doorway 5; Thursdays: , Lecture Theatre 1. Tutorials: weekly; Starts in week 3, there will be several tutorial sections to choose from.
Course web page (with lecture notes/reading list): http://www.inf.ed.ac.uk/teaching/courses/agta/
K. Etessami
AGTA: Lecture 1

No required textbook. Course based on lecture notes + assigned readings. Some reference texts:
M. Maschler, E. Solan, & S. Zamir, Game Theory, 2013.
M. Osborne and A. Rubinstein, A Course in Game Theory, 1994.
R. Myerson, Game Theory: Analysis of conflict, 1991.
A. Mas-Colell, M. Whinston, and J. Green, Microeconomic Theory, 1995.
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (editors), Algorithmic Game Theory, 2007. (Available for free online.)
T. Roughgarden Twenty Lectures on Algorithmic Game Theory, Cambridge U. Press, 2016. (Available online from Library.)
Y. Shoham & K. Leyton-Brown, Essentials of Game theory, 2008. and Multiagent systems: algorithmic, game-theoretic, and logical foundations, 2009. (Both available from Library online.)
V. Chvátal, Linear Programming, 1980.
K. Etessami
AGTA: Lecture 1

What is Game Theory?
A general and vague definition:
“Game Theory is the formal study of interaction between ‘goal-oriented’ ’agents’ (or ’players’), and the strategic scenarios that arise in such settings.”
What is Algorithmic Game Theory?
“Concerned with the computational questions that arise in game theory, and that enlighten game theory. In par- ticular, questions about finding efficient algorithms to ’solve’ games.”
These vague sentences are best illustrated by looking at examples.
K. Etessami
AGTA: Lecture 1

A simple 2-person game: Rock-Paper-Scissors
This is a “zero-sum” game: whatever Player I wins, Player II loses, and vice versa.
What is an “optimal strategy” in this game?
How do we compute such “optimal strategies” for 2-person zero-sum games?
K. Etessami
AGTA: Lecture 1

A non-zero-sum 2-person game: Prisoner’s Dilemma
For both players Defection is a “Dominant Strategy” (regardless what the other player does, you’re better off Defecting).
But if they both Cooperate, they would both be better off. Game theorists/Economists worry about this kind of situation as a real problem for society.
Often, there are no “dominant strategies”. What does it mean to “solve” such games?
K. Etessami
AGTA: Lecture 1

A (NE) is a pair (n-tuple) of strategies for the 2 players (n players) such that no player can benefit by unilaterally deviating from its strategy.
K. Etessami
AGTA: Lecture 1

A (NE) is a pair (n-tuple) of strategies for the 2 players (n players) such that no player can benefit by unilaterally deviating from its strategy.
Nash’s Theorem: Every (finite) game has a mixed (i.e., randomized) Nash equilibrium.
Example 1: The pair of dominant strategies (Defect, Defect) is a pure NE in the Prisoner’s Dilemma game. (In fact, it is the only NE.)
In general, there may be many NE, none of which are pure. Example 2: In Rock-Paper-Scissors, the pair of mixed strategies: ( (R=1/3, P=1/3,S=1/3), (R=1/3, P=1/3,S=1/3)) is a . (And, we will learn, it is also a minimax solution to this zero-sum game. The “minimax value” is 0, as it must be because the game is “symmetric”.)
Question: How do we compute a for a given game?
K. Etessami
AGTA: Lecture 1

Multiple equilibria
Many games have > 1 NE. Example: A “Coordination Game”:
There are two pure : (A, A) and (B, B). Are there any other NEs?
Yes, there’s one other mixed (randomized) NE.
K. Etessami
AGTA: Lecture 1

Games in “Extensive Form”
So far, we have only seen games in “strategic form” (also called “normal form”), where all players choose their strategy simultaneously (independently).
What if, as is often the case, the game is played by a sequence of moves over time? (Think, e.g., Chess.)
Consider the following 2-person game tree:
Player II:
K. Etessami
AGTA: Lecture 1

How do we analyze and compute “solutions” to such extensive form games?
What is their relationship to strategic form games?

chance, and information
Some tree nodes may be chance (probabilistic) nodes, controlled by neither player. (Poker, Backgammon.)
Also, a player may not be able to distinguish between several of its “positions” or “nodes”, because not all information is available to it. (Think Poker, with opponent’s cards hidden.) Whatever move a player employs at a node must be employed at all nodes in the same “information set”.
Player II:
information−set LRLRLRLR
K. Etessami
AGTA: Lecture 1

A game where every information set has only 1 node is called a game of perfect information.
Theorem Any finite n-person extensive game of perfect information has an “equilibrium in pure strategies”.
Again, how do we compute equilibrium solutions for such games?
K. Etessami
AGTA: Lecture 1

Extensive games on Graphs
Player II:
Does Player I have a strategy to “force” the play to reach the “Goal”?
Such games have lots of applications.
Again, how do we compute winning strategies in such games?
What if some nodes are chance nodes?
K. Etessami
AGTA: Lecture 1

Mechanism Design
Suppose you are the game designer. How would you design the game so that the “solutions” will satisfy some “objectives”?
Example: Auctions: (think EBay, or Google Ads) Think of an auction as a multiplayer game between several bidders. If you are the auctioneer, how could you design the auction rules so that, for every bidder, bidding the maximum that an item is worth to them will be a “dominant strategy”?
A answer: second price, sealed bid Vickrey auctions.
How would you design protocols (such as network protocols), to encourage “cooperation” (e.g., diminish congestion)?
Many computational questions arise in the study of “good” mechanisms for various goals.
This is an extremely active area of research (we will only get to scratch its surface).
K. Etessami
AGTA: Lecture 1

But why study this stuff?
GT is a core foundation of mathematical economics.
But what does it have to do with Computer Science? More than you might think: GT ideas have played an important role in CS:
Games in AI: modeling “rational agents” and their interactions. (Similar to Econ. view.)
Games in Modeling and analysis of reactive systems: computer-aided verification: formulations of model checking via games, program inputs viewed “adversarially”, etc.
Games in Algorithms: several GT problems have a very interesting algorithmic status (e.g., in NP, but not known to be NP-complete, etc).
Games in Logic in CS: GT characterizations of logics, including modal and temporal logics (Ehrenfeucht-Fraisse games and bisimulation).
K. Etessami
AGTA: Lecture 1

Games in Computational Complexity: Many computational complexity classes are definable in terms of games: Alternation, Arthur-Merlin games, the Polynomial Hierarchy, etc.. Boolean circuits, a core model of computation, can be viewed as games (between AND and OR).
More recently:
Games, the Internet, and E-commerce: An extremely active research area at the intersection of CS and Economics. Basic idea: “The internet is a HUGE experiment in interaction between agents (both human and automated)”. How do we set up the rules of this game to harness “socially optimal” results?
I hope you are convinced: knowledge of the principles and algorithms of game theory will be useful to you for carrying on future work in many CS diciplines.
K. Etessami
AGTA: Lecture 1

Ok, let’s get started
Definition A strategic form game Γ, with n players, consists of:
A set N = {1,…,n} of players.
For each i ∈ N, a set Si of (pure) strategies. LetS=S1 ×S2 ×…×Sn bethesetofpossible combinations of (pure) strategies.
For each i ∈ N, a payoff (utility) function
ui : S 􏰎→ R, describes the payoff ui(s1,…,sn) to player i under each combination of strategies.
(Each player prefers to maximize its own payoff.) Definition A zero-sum game Γ, is one in which for all
s = (s1,…,sn) ∈ S,
u1(s) + u2(s) + . . . + un(s) = 0.
K. Etessami
AGTA: Lecture 1

Some “food for thought”
Food for Thought (the “guess half the average game”): Consider a strategic-form game Γ with n-players. Each player has to guess a whole number from 1 to 1000. The player who guesses a number that is closest to half of the average guess of all players wins a payoff of 1. All other players get a payoff of 0. (If there are ties for who is closest, those who are closest share the payoff of 1 equally amongst themselves; alternatively, all who are closest get payoff 1.)
Question: What would your strategy be in such a game? Question: What is a “ ” of such a game?
K. Etessami
AGTA: Lecture 1

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts