On Nash Equilibria for a Network Creation Game
Susanne Albers
Friday, September 8th, 2006, 3:30 pm
Wean Hall 7220
Abstract
We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of alpha per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players. Fabrikant et al. proved an upper bound on the price of anarchy of O(sqrt(alpha)). They also formulated a tree conjecture stating that there exists a constant A such that, for any alpha > A, all non-transient Nash equilibria form a tree. They showed that if the tree conjecture holds, the price of anarchy is constant, for all alpha.
We disprove the tree conjecture, i.e. we construct a family of arbitrarily large graphs that contain cycles and form non-transient Nash equilibria for non-constant alpha. Furthermore, we give improved upper bounds on the price of anarchy. We develop a constant upper bounds for alpha in O(sqrt(n)) and for alpha >= 12n log n. For the intermediate values we show an improved bound of O(1+ min{ alpha^2/n, n^2/alpha }^{1/3}). Additionally, we present characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing.
Joint work with Stefan Eilts (Freiburg) and Eyal Even-Dar, Yishay Mansour and Liam Roditty (Tel-Aviv).
Mor Harchol-Balter
What Analytical Performance Modeling Teaches Us About Computer Systems Design
ABSTRACT:
Computer systems design is based on many commonly-held beliefs and heuristics, many of which have never been challenged:
* Thousands of server farm “load balancing” policies do exactly that — they aim to balance the load among the servers. But is load balancing necessarily a good thing?
* Consider a choice between a single machine with speed s, and n identical machines with speed s/n. Which would you choose? Are you always right?
* Scheduling policies which favor “short” jobs, like Shortest-Remaining-Processing-Time-First (SRPT) are often avoided because it is feared that they starve the “long” jobs. But does favoring “short” jobs necessarily hurt “long” ones?
* Cycle stealing between a “donor” machine and a “beneficiary” machine is a central theme in distributed systems. The donor machine helps the beneficiary machine with jobs, whenever the load at the donor machine is below some threshold. But why are we giving the donor machine all the control?
In this talk, we will consider these and other fundamental questions in system design and look at how new research in analytical performance modeling helps us overturn some age-old beliefs.
When: Tuesday, September 12, 3:00 p.m.
Where: 3305 Newell-Simon Hall
David Eckhardt, Associate Teaching Professor in Computer
Colloquium on Computer Science Pedagogy:
The Herbert A. Simon Award for Teaching Excellence in Computer Science Lecture
Abstract:
Teaching systems courses necessarily bears some resemblance to trench warfare. One’s boots are firmly in the muck and blue sky is seen rarely and briefly. Can we learn things of general value while engaged in such a grimy pursuit?
In this talk, I will attempt to draw lessons about abstraction and debugging from some time spent in the trenches. I will also make a few teaching-strategy suggestions in the hope that they may be of use to others. Finally, I will suggest that we add a data structure to our undergraduate curriculum in an attempt to improve retention of skills and encourage reflective professional development.
