Question 1. Three selfish players A,B,C,
need to send messages from s to the bottom nodes
(one message to each target, the target of player j
is node j, for j{A,B,C}). What is the social
optimum cost and what are the Nash equilibrium
routings in the fair cost- sharing model? 2. (25 pts.)
Your answer should distinguish between different ranges of x (0). What is the price of stability and the price of anarchy for each range?
Note: There are 5 different ranges.
2
Question 2.
Consider the following network congestion game.
The edge costs are csa(k)= k, cat(k)=2k, and cst(k)=3k.
For example, if 4 players are using the edge (st) then s each of them pays 12.
Assume that 16 players need to use the network.
2.2. What is the social optimum for this game (with respect to the objective of minimizing the total players’ cost)? Explain your answer.
2.3. What is the price of Stability of this game? Explain your answer.
Question 3. Consider the following local search heuristic for solving P2||Cmax (load
balancing on two machines). It is known that there is no single job for which pj > jpj/2. a. Assign the jobs on the machines arbitrarily.
b. While there exists a job j such that moving j from M1 to M2 or from M2 to M1 decreases the absolute gap between the current loads, |C1-C2|, then perform this move.
Warm up 1: Verify to yourself that the condition in step b is equivalent to j reducing its cost in the corresponding job scheduling game (slides 73+ in the lecture notes).
Warm up 2: Note that if the algorithm is applied on the schedule in slide 79 (jobs of lengths 2,2 on one machine and jobs of lengths 1,1 on the other machine), then no job will migrate in step b.
3.1. Prove that when the algorithm terminates C1/2 C2 2C1. What is the resulting approximation ratio of the algorithm? Explain
3.2. Prove that if in each iteration you select the longest job that can migrate and improve the balance (if there is more than one candidate job), then each job will be moved at most once, and therefore the algorithm terminates after at most n moves.
Note: Questions 4 and 5 consider Online Algorithms – we will cover the relevant material in the
Question 4. Consider the following cow’s algorithm for the Hole in the Fence problem. The difference from the algorithm presented in class is that in this algorithm d is multiplied by two only after the cow walked distance d (and back) on both sides.
1. d=1; current side = right 2. repeat:
- Walk distance d on current side
- if find hole then exit
- else return to starting point
- Flip current side
- Walk distance d on current side
- if find hole then exit
- else return to starting point
- d=2d
- Flip current side
Analyze the competitive ratio of the algorithm.
Question 5. Recall that a matching in a graph G=(V,E) is a set of edges that share no vertices.
A matching M is maximal if there is no matching N such that M N. A matching M is maximum if for every matching N, |M| |N|.
5.1 Prove that a maximal matching is a 2-approximation for the maximum matching.
5.2 Let G=(U,V,E) be a bipartite graph. In the online bipartite matching problem the vertices of V are known in advance, but those of U arrive in an online fashion. When a vertex u U arrives, the edges incident to u are revealed. Give a 2-competitive algorithm for the online bipartite matching problem.
5.3 Prove that every deterministic algorithm for the online bipartite matching problem has competitive ratio at least 2.
