CSE 599m: Algorithms and Economics of Networks

CSE Home

About Us

Search

Contact Info

CSE 599m Projects

Potential project ideas:

1. The load balancing games from Lecture 2 are "overstudied" currently. However, one interesting direction to persue is the effect of alternative scheduling policies (for example, process shortest job first, process longest job first). For which scheduling policies do pure Nash equlibria exist? Some things are already known, and Vahab will be happy to discuss this in more detail with interested students.
2. An interesting topic that we are not currently planning to cover in lecture is cake cutting or the fair division problem. This has been an area of extensive research, so the first part of a project on it is getting up to speed on the current state of the art. Here are two recent papers:
• K. Pruhs and J. Edmonds, Cake cutting is not a piece of cake, SODA, 2006, http://www.cs.pitt.edu/~kirk/papers/soda06.pdf
• K. Pruhs and J. Edmonds, Balanced Allocations of Cake, FOCS, 2006, http://www.cs.pitt.edu/~kirk/papers/focs2006.pdf
3. Here is a very recent paper that explicitly addresses some questions about pure Nash equlibria in graphical games. It has several natural extensions, any of which could be a nice project.
• C. Daskalakis, A. G. Dimakis, E. Mossel, Connectivity and Equilibrium in Random Games, http://arxiv.org/abs/math/0703902
4. An extension to the selfish routing examples from Lecture 4-5 is to incorporate a social network into each agent's utility function. If every agent tries to maximize some linear combination of their own utility and their friends utility, does the price of anarchy decrease? Yes, if the social network is the complete graph. What can you say in more interesting scenarios?
5. Price of Anarchy for average Completion time in Selfish Scheduling: In the class, we learned about the price of anarchy for makespan in selfish scheduling. Most of the questions for the price of anarchy of the similar games for average completion time of players is not known. For details of what's known, and what's not, we can discuss in a meeting.
6. Knapsack market games or distributed caching games are a special case of valid-utility games. They generalize the market sharing game discussed in the class. It is known that the price of anarchy for mixed Nash equilibria of valid-utility games (and in particular the knapsack game) is 1/2. It is also known that there exist nontrivila sink equilibria in these games. The price of anrarchy for sink equilibria (or the price of sinking) in valid-utility games is 1/n. Can we bound the price of anarchy for sink equilibria in knapsack games?
7. Can we define a non-myopic best response dynamics for which the price of anarchy for sink equilibria is a constant (and not 1/n)?
8. Consider the disributed power assignment problem discussed in Lecture 15 in class. Assume that there is a maximum power that can be assigned to each node. Is the power assignment problem in wireless networks solvable in polynomial time?

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Abraham Flaxman]