Approximation and online algorithms for game theory
Final Report Abstract
In this project, we examined several problems in the area of algorithmic game theory. On the internet, the default assumption that an algorithm is in complete control of the situation is no longer valid, since there is no central controlling agency. To solve problems which occur, e.g., to utilize bandwidth efficiently (according to some measure), we now not only need to deal with an allocation problem which might be hard enough to solve in itself, but also with the fact that the entities that we are dealing with (e.g. agents that wish to move traffic from one point to the other) do not necessarily “follow our orders” but instead are much more likely to act selfishly in an attempt to optimize their private return (e.g. minimize their latency). In the problems we considered in this project, there is always a set of players (agents). Each agent defines a strategy with the goal of maximizing its payoff. A Nash equilibrium is defined as a vector of strategies where none of the players can benefit by changing their strategy, assuming that all other strategies remain unchanged. In this project, we were first of all interested in comparing Nash equilibria to the optimal solution that could be reached in a centralized setting, where there is a single controller and no freedom for the agents. The price of stability/anarchy (PoS/PoA) is the ratio of best/worst equilibrium and the best optimal design. With these prices we measure the cost of selfishness, i.e., how much the solution to a classical problem can deteriorate if selfish agents are involved. We have given tight bounds for the PoA for several problems: scheduling on related machines with the makespan objective, scheduling on identical machines with the covering objective (maximizing the minimum load, a standard measure of fairness), and selfish routing in rings with the objective of minimizing the maximum latency. In the first two problems, the jobs are controlled by selfish agents and look for a machine where they can complete quickly. We also considered the PoS for network design with fair cost allocation (players share the cost of edges they use equally) for undirected graphs. In algorithmic mechanism design, we want to optimize some function and need to deal with selfish agents that have some private information and only care about their own profit. We need the agents to truthfully report their data in order to approximate any objective. For singleparameter agents, it is necessary and sufficient to give a monotone algorithm, meaning that the load of any agent does not increase when its bid (cost per unit work) increases. We have presented the first truthful mechanism which is a constant approximation for the covering problem mentioned above. Here the machines are controlled by agents, and only they know the speeds of their machines. For inputs that are not too large, we can even achieve arbitrarily good approximations. We have also given near-optimal online algorithms for this problem, in the model where the online algorithm has a buffer (of limited size) where it can store jobs before assigning them to the machines. Finally we have shown improved approximation algorithms for two-dimensional strip and bin packing. Here a list of rectangles is given which need to be packed into bins which are unit squares, or a strip of unbounded height. The goal is to minimize the number of bins or the height of the strip that is used. Our results for bin packing are optimal, since an approximation algorithm with a ratio below 2 cannot exist (unless P=NP). We also gave an online algorithm for rectangle filling. It was originally our goal to also achieve results for truthful online mechanisms, but unfortunately it appears to be very difficult to design truthful mechanisms in the setting where agents may arrive and leave without prior notice.
Publications
- The price of anarchy on uniformly related machines revisited. In First International Symposium on Algorithmic Game Theory (SAGT 2008), LNCS 4997, p. 46–57. Springer, 2008
Leah Epstein and Rob van Stee
- Maximizing the minimum load: the cost of selfishness. In 5th Workshop on Internet and Network Economics (WINE 2009), LNCS 5929, p. 232–243. Springer, 2009
Leah Epstein, Elena Kleiman and Rob van Stee
- A truthful constant approximation for maximizing the minimum load on related machines. In 6th Workshop on Internet and Network Economics (WINE 2010), LNCS 6484, p. 182–193. Springer, 2010
George Christodoulou, Annamaria Kovacs and Rob van Stee
- Maximizing the minimum load for selfish agents. Theoretical Computer Science, 411(1):44–57, 2010
Leah Epstein and Rob van Stee
- On the price of stability for undirected network design. In 7th Intl. Workshop on Approximation and Online Algorithms (WAOA 2009), LNCS 5893, S. 86–97. Springer, 2010
George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga and Rob van Stee
- Max-min online allocations with a reordering buffer. SIAM Journal on Discrete Mathematics, 25:1230–1250, 2011
Leah Epstein, Asaf Levin and Rob van Stee
