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.
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:
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.
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?
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.
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?
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)?
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]