Elliot Anshelevich - Publications

• Approximations for the FireFighter Problem: Cuts over Time and Submodularity.
  Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy.
  To appear in ISAAC 2009.
  
  

  Exact and Approximate Equilibria for Optimal Group Network Formation.

  Elliot Anshelevich and Bugra Caskurlu.

  To appear in ESA 2009.
  
  

  Anarchy, Stability, and Utopia: Creating Better Matchings.

  Elliot Anshelevich, Sanmay Das and Yonatan Naamad.

  To appear in SAGT 2009.
  
  We consider the loss in social welfare caused by individual rationality in matching scenarios. We give both theoretical and experimental results comparing stable matchings with socially optimal ones, forming approximately stable matchings that are close to socially optimal, as well as studying the convergence of various natural algorithms to stable matchings.
  
  

  Equilibria in Dynamic Selfish Routing.

  Elliot Anshelevich and Satish Ukkusuri.

  To appear in SAGT 2009.
  
  We study selfish flows which take a non-negligible amount of time to travel across the network from the source to destination, and where network state like traffic load and congestion can vary during this period. We show that unlike in static selfish flows, equilibria may not exist, and the price of anarchy can be high. If the flow obeys FIFO constraints, however, then there always exists an equilibrium that can be computed efficiently.
  
  

  Price of Stability in Survivable Network Design.

  Elliot Anshelevich and Bugra Caskurlu.

  To appear in SAGT 2009.
  
  We study a survivable version of a network formation game by strategic agents, where each agent wants to connect certain pairs of nodes using at least two disjoint paths. We show that if all nodes correspond to agents, or if an agent is only allowed to deviate by changing the payments on one of her connection paths at a time, instead of both of them at once, then the price of stability is 1, i.e., there always exists a stable solution that is as good as the centralized optimum.
  
  

  Network Formation and Routing by Strategic Agents using Local Contracts.

  Elliot Anshelevich and Gordon Wilfong.

  In Proc. 4th International Workshop On Internet And Network Economics (WINE 2008).
  
  We extend our model from the FOCS'06 paper by addressing the issues of contract formation and routing simultaneously. We study the structure and quality of Nash equilibria, and show that when only the sender benefits (i.e., gains utility) for routed traffic demands, then there is a Nash equilibrium as good as the centralized optimal solution and so the price of stability is 1. When both the sender and receiver benefit from routed demands, however, then the price of stability is at most 2.
  
  

  On Survivable Access Network Design: Complexity and Algorithms.

  Dahai Xu, Elliot Anshelevich, and Mung Chiang.

  In Proc. 27th IEEE Conference on Computer Communications (INFOCOM 2008).
  
  We look at the Terminal Backup problem studied in the STOC07 paper, and greatly improve the efficiency of the algorithms from this paper. By performing simulations, we see that our new algorithms run very quickly, and can be used in practice.
  
  

  Terminal Backup, 3D Matching, and Covering Cubic Graphs.

  Elliot Anshelevich and Adriana Karagiozova.

  In Proc. 39th ACM Symposium on Theory of Computing (STOC 2007).
  
  We define a nontrivial extension of non-bipartite min-cost matching called Simplex Matching, and show how to solve it in polynomial time. While interesting in its own right, its main value lies in many (seemingly very different) problems that can be solved using our algorithm. For example, in a Steiner Forest setting, it can be used to find the cheapest forest with at least 2 terminals in every component. The algorithm we provide is relatively simple to understand and implement, but difficult to prove correct. In the process of this proof we show some powerful new results about covering cubic graphs with simple combinatorial objects.
  
  

  Strategic Network Formation through Peering and Service Agreements. (pdf)

  Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong.

  (Older title: "Local Peering and Service Contracts in Strategic Network Formation.")

  In Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006).
  
  We introduce a noncooperative game in an effort to understand business relationships between entities (enterprises, ISPs, residential customers etc.) in the Internet. Connection contracts are local (ie bilateral) between two entities and may either be of a peer-peer or a customer-provider variety. Entities bid (or demand payment) for the formation of these contracts, and in the resulting network some traffic is routed and other traffic dropped; providers may incur a penalty if their customer's traffic is dropped. Stable solutions to this game have some interesting properties. We consider the structure of such solutions, as well as how to induce good stable solutions given a limited budget.
  
  

  Network Design and Management with Strategic Agents.

  Elliot Anshelevich.

  Ph.D. Thesis, Cornell University, 2005.
  
  Contains many of the results from publications on this page, as well as a good background on algorithmic game theory and strategic network formation.
  
  

  The Price of Stability for Network Design with Fair Cost Allocation. (pdf)

  Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden.

  In SIAM Journal on Computing, Volume 38, Issue 4 (November 2008), pp. 1602-1623.

  Conference version appeared in Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004).
  
  We study the ratio of the best Nash equilibrium with the centralized optimum (the price of stability) in a network design context where independent agents wish to connect certain nodes. The best Nash equilibrium solution has a natural meaning of stability in this context -- it is the optimal solution that can be proposed from which no user will "defect". We show that if the edge cost allocation is done using a Shapley value fair division scheme, then the price of stability is at most O(log k), where k is the number of agents, and that a good Nash can be achieved via best-response dynamics. We also discuss and extend our results to many more general models, such as the case where the network has latencies.
  
  

  Path Decomposition under a New Cost Measure with Applications to Optical Network Design.

  Elliot Anshelevich and Lisa Zhang.

  In ACM Transactions on Algorithms (TALG), Volume 4, Issue 1 (March 2008).

  Conference version appeared in Proc. 12th Annual European Symposium on Algorithms (ESA 2004). © Springer-Verlag
  
  We consider a network design problem with a novel yet simple cost function. The underlying network must be partitioned into disjoint paths, and the cost of a connection is the number of these paths that the connection path intersects. We give a 2-approximation algorithm in the case that the connection routes are fixed, and show an optimal algorithm for that case with maximal network degree 3. For the case where both the path partition and the connection paths must be optimized, we give a log-approximation in the general case and a 3/2-approximation for the ring topology.
  
  

  Near-Optimal Network Design with Selfish Agents.

  Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler.

  In Theory of Computing, Volume 4 (2008), pp. 77-109.

  Conference version appeared in Proc. 35th ACM Symposium on Theory of Computing (STOC 2003).
  
  We study a simple network design game that models how independent selfish agents can build or maintain a large network. We show that in a restricted context, we can force these agents into a stable solution which is no worse than the centralized optimum. We also demonstrate that in a more general context, there is always an approximately stable solution which is no worse than the centralized optimum. Finally, we give poly-time algorithms to find these stable solutions.
  
  

  Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.

  Elliot Anshelevich, David Kempe, and Jon Kleinberg.

  In SIAM Journal on Computing, Volume 37, Issue 5 (January 2008), pp. 1656-1673.

  Conference version appeared in Proc. 34th ACM Symposium on Theory of Computing (STOC 2002).
  
  We study the load balancing and packet routing problems in a dynamic online setting, where an adversary can insert and remove jobs or packets. We give simple proofs of stability for a natural distributed algorithm against rate-1 adversaries, for load balancing with up to 2 commodities, and packet routing with a single sink. A main contribution of the paper is a new proof technique for stability proofs.
  
  

  Deformable Volumes in Path Planning Applications.

  Elliot Anshelevich, Scott Owens, Florent Lamiraux, and Lydia Kavraki.

  IEEE International Conference on Robotics and Automation (ICRA) 2000, 2290-2295.
  
  We use the framework of the PRM (Probabilistic Roadmap Planner) to tackle the problem of path planning for deformable volumes. The underlying geometric model for the volume is provided by a mass-spring representation, augmented with a realistic mechanical model. We present experimental results that illustrate our path planning approach.