MY-ASSIGNMENTEXPERT™可以为您提供 inf.ed.ac.uk CS4 Game theory博弈论的代写代考和辅导服务！
这是爱丁堡大学博弈论课程的代写成功案例。
CS4课程简介
This is an MSc (and 4th year) course that runs in Semester 2 (Spring 2023). The lecturer is Kousha Etessami. Some of the information below is still from the prior year, 2022. It will be updated during the course. The lecture times for the course are Mondays and Thursdays, 11:10-12:00 (Edinburgh time). The lectures will be recorded and posted online. There will also be weekly toturials, starting in Week 3. These will cover and discuss the contents of the weekly tutorial sheet. There is also a Piazza Discussion Forum for the course, accessible from the LEARN page, where you can post questions and discuss the course content with fellow students (but DO NOT share answers to coursework). The times are indicated under “Timetable” on the AGTA course DPT on the DRPS web pages the tutorial time slots may be subject change at the beginning of the course.
Prerequisites
No required reading.
Reference texts for the entire course see slides of lecture 1 for a more comprehensive list):
M. Maschler, E. Solan, and S. Zamir, Game Theory , Cambridge U. Press, 2013.
(Available online from the University Library.
K. Leyton-Brown and Y. Shoham, “Essentials of Game Theory”, 2008 . A short book, available electronically from the Edinburgh University Library.
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Algorithmic Game Theory, Cambridge U. Press, 2007.
Available online from the University library.
Y. Shoham and K. Leyton-Brown, “Multi-agent Systems: algorithmic, game-theoretic, and logical foundations”, 2009. (MAS) A longer book on MAS, also available online. The main focus of the book is game theory.
T. Roughgarden. Twenty Lectures on Algorithmic Game Theory, Cambridge U. Press, 2016.
Available online from the University library.
CS4 Game theory HELP（EXAM HELP， ONLINE TUTOR）
Consider the “Guess Half the average game” described as the “food for thought” question on the last slide of Lecture 1. (Each player (indepedently) guesses a whole number between 1 to 1000 . The goal of each of the $n>1$ players is to guess a number that is closest to half the average of all the guessed numbers.)
We described two versions of that game, depending on which tiebreaking rule is used: in the first tie-breaking rule, all players who are closest to half the average split the payoff of 1 equally amongst themselves; in the second tie-break rule, all who are closest to half the average get the full payoff of 1 .
Firstly, discuss how you would play each of these games, if you were playing them against the rest of the students in the AGTA course, and why. Are your assumptions realistic?
Second, find all pure Nash Equilibria (NEs) in both versions of this game. In all cases, argue why the pure NEs that you have found are the only pure NEs in the game.
Let’s first consider the tie-breaking rule in which all players who are closest to half the average split the payoff. We claim that the unique pure NE of the game is when all players guess 1 . This situation is clearly a NE, for any player unilaterally changing their guess will get payoff 0 instead of $1 / n$. To show uniqueness, we show that no other profile is a pure NE. For contradiction, assume $\left(s_1, \ldots, s_n\right)$ is a different pure NE. $k>1$ be be the largest number that any player plays. Let $i$ be a player who plays $k$. Since $k$ is the largest number anyone guesses player $i$ can only get non-zero payoff from guessing $k$ if all players guess $k$, in which case the payoff of 1 is split equally among all players. But since $k>1$, then player $i$ can switch to $k-1$ instead and raise its payoff from $1 / n$ to 1.
Thus, there is no player who plays a number $k>1$ in a pure Nash equilibrium. (In fact, we can also show no player plays a number $k>1$ with positive probability in a mixed NE, in such a game. So, the only NE is the pure NE where everyone plays the number 1. )
Thus, there is no player who plays a number $k>1$ in a pure Nash equilibrium. (In fact, we can also show no player plays a number $k>1$ with positive probability in a mixed NE, in such a game. So, the only NE is the pure NE where everyone plays the number 1.$)$
In the second tie-breaking rule, all players who are closest to half the average get the full payoff of 1 . Intuitively, this means that a player wants to “win”, but doesn’t care about how many other players are winning simultaneously with it, unlike in the previous version, where players prefer to win alone if they can. This means that we get more NEs. Specifically, for any $k \in{1, \ldots 1000}$, all players guessing $k$ is a pure NE, as everyone gets the maximum payoff of 1 and thus cannot improve by switching. We claim that there are no other NEs. Suppose for contradiction that there is some other pure NE. In such a pure NE, at least two different players must play different numbers. Let $k$ be the largest number played, and let $k^{\prime}$ be the next smaller number played. We claim that $k^{\prime}$ must be strictly closer to half the average. That’s because half the average, h, clearly satisfies $h<k / 2$, and thus any number $k^{\prime}$ such that $1 \leq k^{\prime}<k$ is strictly closer to $h$ than $k$. Thus, players playing $k$ are better off switching, and this is not an NE. Thus, no two players can play different numbers in any pure NE.
(In fact, we can show this is also true in a mixed NE.)
Consider the following 2-player finite strategic form game, $G$ :
$$
\left[\begin{array}{llll}
(7,3) & (6,3) & (5,5) & (4,7) \
(4,2) & (5,7) & (8,6) & (5,8) \
(6,1) & (3,8) & (2,4) & (5,9)
\end{array}\right]
$$
This is a “bimatrix”, to be read as follows: Player 1 is the row player, and Player 2 is the column player. If the content of the bimatrix at row $i$ and column $j$ is the pair $(a, b)$, then the payoff to Player 1 , under the combination of pure strategies $(i, j)$ is $u_1(i, j)=a$, likewise for Player 2 the payoff is $u_2(i, j)=b$.
(a) Consider the mixed strategies $x_1=(1 / 4,1 / 2,1 / 4)$ and $x_2=$ $(2 / 3,1 / 3,0,0)$, for player 1 and 2 , respectively. Here, e.g., player 1 is playing row 2 with probability $1 / 2$, etc.
What is the expected payoff to Player 1 under profile $x=\left(x_1, x_2\right)$ ?
(b) Using what you have learned so far in lectures, see if you can find all the Nash Equilbria (pure or mixed) of the game $G$.
(a) The expected payoff for Player 1 is given by
$$
\begin{aligned}
U_1(x) & =\sum_{i, j} x_1(i) x_2(j) u_1(i, j)=\sum_i \sum_j x_1(i) x_2(j) u_1(i, j) \
& =\frac{1}{4}\left(\frac{2}{3} u_1(1,1)+\frac{1}{3} u_1(1,2)\right)+\frac{1}{2}\left(\frac{2}{3} u_1(2,1)+\frac{1}{3} u_1(2,2)\right)+\frac{1}{4}\left(\frac{2}{3} u_1(3,1)+\frac{1}{3} u_1(3,2)\right) \
& =\frac{1}{4}\left(\frac{2}{3} \cdot 7+\frac{1}{3} \cdot 6\right)+\frac{1}{2}\left(\frac{2}{3} \cdot 4+\frac{1}{3} \cdot 5\right)+\frac{1}{4}\left(\frac{2}{3} \cdot 6+\frac{1}{3} \cdot 3\right) \
& =61 / 12
\end{aligned}
$$
(b) Let us first note that the 4th pure strategy of player 2 strictly dominates all other strategies. This is because regardless what (pure) strategy player 1 plays, player 2 is strictly better off (i.e., gets a strictly higher payoff) playing pure strategy 4 , than playing any other pure strategy. Thus, player 2 will necessarily prefer strategy 4 to any other strategy. We can thus “reduce” the game to the residual game in which player 2 only has that single pure strategy, yielding the bimatrix:
$$
\left[\begin{array}{l}
(4,7) \
(5,8) \
(5,9)
\end{array}\right]
$$
In the remaining bimatrix, strategy 1 of Player 1 is strictly dominated by strategy 2 (and by strategy 3 ), so we end up with the bimatrix
$$
\left[\begin{array}{l}
(5,8) \
(5,9)
\end{array}\right]
$$
Player 1 will get expected payoff 5 no matter what it does in this risidual game, whereas Player 2 has no choices remaining. Thus in this reduced game, the set of Nash equilibria is $\left{\left(x_1, x_2\right) \mid x_i\right.$ a mixed strategy for Player $i$ and $\left(x_1, x_2\right)$ is a $\mathrm{NE}}={((p, 1-p), 1) \mid p \in[0,1]}$. This means that in the original game the Nash Equilibria are given by pairs $\left(x_1, x_2\right)$ where $x_1$ is of the form $(0, p, 1-p)$ and $x_2=(0,0,0,1)$. In particular, we have two pure NEs: in one Player 1 plays strategy 2 while Player 2 plays strategy 4 and in the other one Player plays strategy 3 while Player 2 plays strategy 4.
MY-ASSIGNMENTEXPERT™可以为您提供 INF.ED.AC.UK CS4 GAME THEORY博弈论的代写代考和辅导服务！
