CSE 599m Homework

By May 21st, there will be 10 homework problems here.

Please submit solutions to 5 of these problems (your choice which) on May 28th.

In the load balancing game from Lecture 2, give upper and lower bounds on the price of anarchy (for pure Nash equlibrium, and social cost given by maximum latency) when the delay functions are all of the form $f i (L) = L 2$ .
In graph $G = (V, E)$ , an independent set $S$ is a subset of vertices which contain no edges (i.e. for all $u, v$ in $S$ , ${u, v}$ is not in $E$ ). Use the First Moment Method and Second Moment Method to find precise bounds on the size of a maximum independent set in $G n,1 / 4$ .
Consider an instance of the unrelated machine scheduling (R||C_max). In the class, we talked about some local ordering policies. Here, we give a different policy. Consider a fixed total ordering $J_1, J_2, ..., J_n$ on all jobs. Consider the following local policy on each machine: Order jobs in the same order as a fixed total ordering (without looking at the real processing time of each job on each machine). Is the corresponding game a potential game? Does it always contain pure Nash equilibria?
Let $G = G n, p$ where $p = c / n$ and $c$ is a constant.

Show that whp $G$ contains no set of vertices $S$ with $s = | S | < n / (20 c 2)$ such that $S$ contains $2 s$ edges.
Show that whp the maximum degree $\Delta \leq \ln n/\ln\ln n$ .
Show that whp the vertices of degree exceeding $\frac{2}{3} \ln n/\ln \ln n$ form an independent set.

Let $G = G n, p$ where $p = (ln(n 2 / c) / n) 1 / 2$ and $c$ is a constant. What is the limiting probability that the diameter of $G$ is 2?
Let $G = G n, p$ where $p = (ln n + c) / n$ and $c$ is a constant. What is the limiting probability that $G$ has exactly $k$ isolated vertices?
Let $G = G k out$ be a random graph with vertex set $[n]$ and edges generated by every vertex choosing $k$ neighbors uniformly at random. Show that $G$ is connected whp for $k \geq 2$ .
Consider the load balancing game from Lecture 2 with linear delay functions. Give a lower and upper bound for the price of anarchy after one round of best responses of players.