|
CSE 599m: Algorithms and Economics of Networks
|
|
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 fi(L) = L2.
- 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 Gn,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 = Gn,p
where p = c / n and c is a constant.
- Show that whp G
contains no set of vertices S with s = | S | < n / (20c2)
such that S contains 2s edges.
- Show that whp the maximum degree .
- Show that whp the vertices of degree
exceeding form an independent set.
- Let G = Gn,p
where p = (ln(n2 / c)
/ n)1 / 2 and c
is a constant. What is the limiting probability that the diameter of G is 2?
- Let G = Gn,p
where p = (lnn + c) / n
and c is a constant. What is the
limiting probability that G has exactly k isolated vertices?
- Let G = Gkout
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 .
- 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.