Elliot Anshelevich - Publications

• Price of Stability in Survivable Network Design.
  E. Anshelevich, B. Caskurlu.
  Submitted.
  
  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.
  
  

  On Survivable Access Network Design: Complexity and Algorithms.

  D. Xu, E. Anshelevich, and M. Chiang.

  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.

  E. Anshelevich, A. 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)

  E. Anshelevich, B. Shepherd, and G. 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.

  E. 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)

  E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden.

  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. (pdf)

  E. Anshelevich and L. Zhang.

  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.

  E. Anshelevich, A. Dasgupta, E. Tardos, and T. Wexler.

  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. (pdf)

  E. Anshelevich, D. Kempe, and J. Kleinberg.

  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.

  E. Anshelevich, S. Owens, F. Lamiraux, and L. 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.