\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{xifthen}%
\usepackage{sgame}%
\usepackage{color}%
\usepackage[hidelinks,colorlinks]{hyperref}

\newcounter{question}
\setlength\parindent{0pt}

\newcommand{\question}[2]{%
	\stepcounter{question}
	\vspace{.25in} \textbf{Q\arabic{question}
		\ifthenelse{\isempty{#1}}%
		{}%
		{[#1 Points]\ }%
		#2} \vspace{.10in}
}

\newcommand{\qpart}[2]{%
	\vspace{.10in} \textbf{(#1)}
	\ifthenelse{\isempty{#2}}%
	{}%
	{[#2 Points]}%
}

\newcommand{\solution}[1] {\vspace{.25in} \textbf{Solution to Q#1} \vspace{.10in}}
\newcommand{\solpart}[1] {\vspace{.10in} \textbf{(#1)}}
\newcommand{\set}[1]{\{#1\}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\begin{document}

\medskip
\begin{center}
{\Large CSC304 \,\, Fall'26}\\[0.2cm]
{\Large Assignment 1}\\[0.2cm]
{\large Due: October 16, 2026, by 11:59pm ET}
\end{center}

\textbf{Instructions:}
\begin{enumerate}
	\item Typed assignments are preferred (e.g., using LaTeX or Word), especially if your handwriting is possibly illegible or if you do not have access to a good quality scanner. Please submit a single PDF to MarkUs. You may work in groups of size up to $3$; only one member of each group should submit.
	\item Remember our citation policy. You are free to read online material (though, if you find the exact homework problem, do not read the solution), to discuss any problems with your peers, and to use language models. There are two rules you must follow: You must write the solution in your own words (it helps to not take any pictures or notes from your discussions), and for each question, you must cite any peer (by name), online source (by link), or language model (by chat link) you consulted. There is no penalty for citing, but failing to do so counts as plagiarism.
	\item Attempt to solve each problem, but if you have no clue how to approach a (sub)problem, remember the $20\%$ rule: You get $20\%$ of the points for a (sub)problem if you leave it blank or scratch off everything you have written for it.
\end{enumerate}

\question{20}{Nash Equilibria}

Compute all (mixed) Nash equilibria in each of the following games. At the end of your solution, explicitly write the set of Nash equilibria using the following notation. A Nash equilibrium can be denoted as $((p_1,p_2,p_3),(q_1,q_2,q_3))$, where $p_1$, $p_2$, and $p_3$ are the probabilities of the row player playing $T$, $M$, and $B$ respectively, and $q_1$, $q_2$, and $q_3$ are the probabilities of the column player playing $L$, $C$, and $R$, respectively.

\qpart{a}{5} Game 1:

\medskip\noindent\emph{[Hint: Instead of brute-forcing, apply a trick we learned in class to reduce the size of the game without changing the set of Nash equilibria.]}

\begin{center}
	\begin{game}{3}{3}
				& $L$		& $C$   	& $R$\\
		$T$		& $(5,5)$ 	&$(1,9)$   &$(4,2)$\\
		$M$		& $(3,5)$ 	&$(9,6)$   	&$(6,9)$\\
		$B$ 	& $(6,5)$ 	&$(1,9)$   	&$(5,4)$
	\end{game}
\end{center}

\qpart{b}{15} Game 2: Note that the only differences compared to Game 1 are in the rewards to the row player in (T,C) and (M,R).

\medskip\noindent\emph{[Hint: It is still possible to reduce the size of Game 2 from $3 \times 3$ to $3 \times 2$. Applying the indifference principle to the latter will still result in $(2^3-1) \cdot (2^2-1) = 21$ cases. Instead of writing each one separately, you can club them into four categories: neither player randomizes, only the row player randomizes, only the column player randomizes, and both players randomize. Provide a brief argument for any categories that do not lead to any Nash equilibria, and show detailed calculations only for the remaining categories.]}

\begin{center}
	\begin{game}{3}{3}
		& $L$		& $C$   	& $R$\\
		$T$		& $(5,5)$ 	&$(3,9)$   &$(4,2)$\\
		$M$		& $(3,5)$ 	&$(9,6)$   	&$(1,9)$\\
		$B$ 	& $(6,5)$ 	&$(1,9)$   	&$(5,4)$
	\end{game}
\end{center}

\question{20}{Games Without Pure Nash Equilibria}

Consider a two-player game in which each player has two actions: the row player chooses between $T$ and $B$, and the column player chooses between $L$ and $R$. Let $u_1$ and $u_2$ denote the reward functions of the row player and the column player, respectively. Our goal is to prove the following claim: \emph{If the game has no pure Nash equilibrium, then it has exactly one Nash equilibrium, and in it, both players randomize, i.e., each action of each player is played with a probability strictly between $0$ and $1$.}

\qpart{a}{5} Suppose the row player's action $T$ gives her at least as much reward as her other action $B$ against every action of the column player, i.e., $u_1(T,L) \ge u_1(B,L)$ and $u_1(T,R) \ge u_1(B,R)$. Show that the game has a pure Nash equilibrium. (By symmetry, the same holds if $B$ is at least as good as $T$ against every action of the column player, or if one of the two actions of the column player is at least as good as the other against every action of the row player; you do not need to prove these.)

\qpart{b}{15} Suppose the game has no pure Nash equilibrium. Using part (a), we already know that $u_1(T,L)-u_1(B,L)$ and $u_1(T,R)-u_1(B,R)$ are both nonzero and have opposite signs, and by symmetry, $u_2(T,L)-u_2(T,R)$ and $u_2(B,L)-u_2(B,R)$ are also both nonzero and have opposite signs; you do not need to prove this. Use this information to prove the claim above.

\medskip\noindent\emph{[Hint: Let $x$ and $y$ be the probabilities with which the row player plays $T$ and the column player plays $L$, respectively. First, show that in any Nash equilibrium, if one player plays a pure strategy, then so does the other player, which contradicts the assumption that there are no pure Nash equilibria. Next, apply the indifference principle to find the only possible equilibrium, and verify that it is indeed a Nash equilibrium.]}

\question{20}{Strategic Computing}

In a strategic computing game, there is a set of agents $N=\set{1,\ldots,n}$, and a set of machines $M=\set{1,\ldots,m}$. Each agent $i$ has a job (referred to as job $i$) that requires $p_i$ time to be processed on any single machine. A pure strategy $s_i$ of agent $i$ is a machine on which job $i$ will be processed (i.e., $s_i \in M$). Given a pure strategy profile $\vec{s} = (s_1,\ldots,s_n)$, the load on machine $j$ is the sum of processing times of the jobs assigned to machine $j$:
$$
L_j(\vec{s}) = \textstyle\sum_{i \in N : s_i = j} p_i.
$$

The cost to each agent $i$ is the load on the machine chosen by the agent, i.e., $c_i(\vec{s}) = L_{s_i}(\vec{s})$. The social cost is defined to be the \emph{maximum load on any machine}: $C(\vec{s}) = \max_{j \in M} L_j(\vec{s})$. (Observe that the social cost is not the sum of agent costs, but rather the maximum of agent costs.)

\qpart{a}{4} Consider a strategic computing game with $m=2$ machines and $n=5$ jobs with processing times $p_1=1$, $p_2=2$, $p_3=3$, $p_4=6$, and $p_5=6$. Compute the price of stability and the price of anarchy of this game with respect to pure Nash equilibria. Show your calculation.

\qpart{b}{6} Prove that the price of stability of any strategic computing game is $1$. In other words, you need to show that in every strategic computing game, there is at least one socially optimal pure strategy profile that is also a pure Nash equilibrium.

\medskip\noindent\emph{[Hint: Not every socially optimal pure strategy profile will be a Nash equilibrium. First, observe that in a social optimum, an agent assigned to the machine with the highest load (assuming it is unique) must have no incentive to switch. Then, think about when this would be true for the agents assigned to the other machines.]}

\qpart{c}{10} Prove that the price of anarchy of any strategic computing game with respect to pure Nash equilibria is at most $2-2/(m+1)$.

\medskip\noindent\emph{[Hint: Let $OPT$ be the optimum social cost. You want to prove that the social cost of any pure Nash equilibrium $\vec{s}$ is at most $(2-2/(m+1))\cdot OPT$. Let $j^*$ be a machine with the highest load under $\vec{s}$. First, prove the desired result when $j^*$ has a single job under $\vec{s}$. Next, assume $j^*$ has at least two jobs and $i^*$ is a job on $j^*$ with the minimum processing time among all jobs on $j^*$. To prove the desired result, derive two inequalities: the first relates $OPT$ to the average (not maximum) load across all machines under $\vec{s}$, and the second relates the load on each machine under $\vec{s}$ to the maximum load under $\vec{s}$.]}\\[-0.2cm]

\question{20}{Potential Functions and Cost-Sharing Games}

Recall that in the cost-sharing game, we defined the potential function $\Phi(\vec{P}) = \sum_{e \in E(\vec{P})} \sum_{k=1}^{n_e(\vec{P})} \frac{c_e}{k}$, where $E(\vec{P})$ is the set of edges taken by at least one player in $\vec{P}$, and $n_e(\vec{P})$ is the number of players taking edge $e$ in $\vec{P}$.\\[-0.2cm]

Consider a cost-sharing game with $n$ players on a network with $m$ edges, where the cost of each edge is $1$ (i.e., $c_e = 1$ for each $e$). Suppose we start from an arbitrary pure strategy profile $\vec{P}^1$ and follow an iterative process. The pure strategy profile at the beginning of iteration $t$ is denoted $\vec{P}^t$. In iteration $t$, we find a player $i$ who can change her strategy from $P^t_i$ to $P'_i$ to strictly decrease her cost (i.e., $c_i(P'_i,\vec{P}^t_{-i}) < c_i(\vec{P}^t)$) and set $\vec{P}^{t+1} = (P'_i,\vec{P}^t_{-i})$. If multiple such players exist, we choose an arbitrary one, and if no such players exist, the process ends.\\[-0.2cm]

Our goal is to prove that this process will necessarily converge to a pure Nash equilibrium in finitely many steps, and prove an upper bound on the number of steps required.\\[-0.2cm]

In parts (b), (c), and (d) below, all bounds must be in terms of only $n$ and $m$. Better bounds can fetch higher marks. The best possible bound will receive full marks, but, as in real life, you will not know what this bound is. So, spend a reasonable amount of time trying to improve your bound, and when you cannot find a better one, submit the one you have.

\qpart{a}{2} Show that if this process stops, the final pure strategy profile must be a pure Nash equilibrium.

\qpart{b}{5} Find an upper bound on the initial potential value, i.e., $\Phi(\vec{P}^1)$.

\qpart{c}{10} Find a strictly positive lower bound on the amount by which the potential function must decrease in every iteration, i.e., on $\Phi(\vec{P}^t) - \Phi(\vec{P}^{t+1})$.

\qpart{d}{3} Using parts (b) and (c), prove an upper bound on the number of steps required for the process to converge to a pure Nash equilibrium. Your bound must hold regardless of the choices made during the process (i.e., wherever we said ``arbitrary'' in the process description).

\question{20}{Simultaneous Zero-Sum Games}

There are three players $P1$, $P2$, and $P3$. $P1$ is simultaneously playing two zero-sum games: one with $P2$ in which $P1$'s reward matrix is $A_{12}$, and one with $P3$ in which $P1$'s reward matrix is $A_{13}$. The total reward for $P1$ is the sum of his rewards from the two games. Suppose all three players have the same set of actions $S$. The twist is that $P1$ is required to play the same (possibly mixed) strategy in both games.

\qpart{a}{5} Argue that this can be modeled as a single three-player zero-sum game.

\qpart{b}{15} Using Nash's theorem for the game derived in part (a), argue that an extension of the minimax theorem holds in this situation. Specifically, let $x_1$, $x_2$, and $x_3$ denote mixed strategies of $P1$, $P2$, and $P3$, respectively. Then show that
\begin{equation*}
	\max_{x_1}\ \min_{x_2,x_3}\ (x_1)^T (A_{12} x_2 + A_{13} x_3) = \min_{x_2,x_3}\ \max_{x_1}\ (x_1)^T (A_{12} x_2 + A_{13} x_3).
\end{equation*}

\medskip\noindent\emph{[Hint: Proceed along the line of the proof of minimax theorem we did in the class. To prove the two quantities are equal, we are going to show an inequality in each direction. First, find the ``obvious inequality''. Then, take a Nash equilibrium $(\tilde{x}_1, \tilde{x}_2, \tilde{x}_3)$. Write the three ``best response'' equations that describe each $\tilde{x}_i$ as the best response of player $i$ given the strategies of the other players. Combine the three equations to get the inequality in the reverse direction.]}

\end{document}