Elliot Anshelevich - Publications
Last Updated: 07/27/2012

• Strategic Pricing in Next-hop Routing with Elastic Demands.
  Elliot Anshelevich, Ameya Hate, and Koushik Kar.
  In Proc. 4th International Symposium on Algorithmic Game Theory (SAGT 2011).
  
  We analyze a model of next-hop routing by self-interested agents. In this model, nodes make pricing decisions of how much to charge for forwarding traffic from each of their upstream neighbors, and routing decisions of which downstream neighbors to forward traffic to (i.e., choosing the next hop). Traffic originates at a subset of these nodes that derive a utility when the traffic is routed to its destination node; the traffic demand is elastic and the utility derived from it can be different for different source nodes.
  
  

  Capacity Allocation Games for Network-Coded Multicast Streaming.

  Elliot Anshelevich, Bugra Caskurlu, Koushik Kar, and Hang Zhang.

  In Proc. 2nd International ICST Conference on Game Theory for Networks (GameNets 2011).
  
  We formulate and study a fractional capacity-allocation game in the context of multicast network-coded transmissions. We give theoretical results about existence and computational complexity of Nash equilibrium in this game, bounds on the price of anarchy, as well as results about approximate equilibrium. Our simulation studies show that our algorithms generate efficient Nash equilibrium allocation solutions for a vast majority of randomly generated network topologies.
  
  

  A Stackelberg Strategy for Routing Flow over Time.

  Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich.

  In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2011).
  
  Most prior work on routing games uses a simplified model of network flow where all flow exists simultaneously, and users care about either their maximum delay or their total delay. Both of these measures are surrogates for measuring how long it takes to get all of a user's traffic through the network. We attempt a more direct study of how competition affects network efficiency by examining routing games in a flow over time model. We give an efficiently computable Stackelberg strategy for this model and show that the competitive equilibrium under this strategy is no worse than a small constant times the optimum, for two natural measures of optimality.
  
  

  Strategic Multiway Cut and Multicut Games.

  Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate.

  Theory of Computing Systems, to appear.

  Conference version appeared in Proc. 8th Workshop on Approximation and Online Algorithms (WAOA 2010).
  
  We consider cut games where players want to cut themselves off from different parts of a network. These games arise when players want to secure themselves from areas of potential infection. For the game-theoretic version of Multiway Cut, we prove that the price of stability is 1, i.e., there exists a Nash equilibrium as good as the centralized optimum. For the game-theoretic version of Multicut, we show that there exists a 2-approximate equilibrium as good as the centralized optimum. We also give poly-time algorithms for finding exact and approximate equilibria in these games.
  
  

  Partition Equilibrium Always Exists in Resource Selection Games.

  Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate.

  In Proc. 3rd International Symposium on Algorithmic Game Theory (SAGT 2010).
  
  We prove the existence of, and give an algorithm to compute, Partition Equilibrium in Resource Selection Games. In a partition equilibrium, the set of players has a fixed partition into coalitions, and the only deviations considered are by coalitions that are sets in this partition. Moreover, we show how to always find a partition equilibrium which is also a Nash equilibrium. This implies that in resource selection games, we do not need to sacrifice the stability of individual players when forming solutions stable against coalitional deviations.
  
  

  Contribution Games in Social Networks. (slides)

  Elliot Anshelevich and Martin Hoefer.

  Algorithmica, to appear.

  Conference version appeared in Proc. 18th Annual European Symposium on Algorithms (ESA 2010).
  
  We consider network contribution games, where each agent in a social network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved.
  
  

  Matching, Cardinal Utility, and Social Welfare.

  Elliot Anshelevich and Sanmay Das.

  In ACM SIGecom Exchanges, Volume 9.1, June 2010.
  
  A short note on using cardinal utility to measure social welfare in various types of market and matching scenarios. Contains discussion of the papers "Anarchy, Stability, and Utopia: Creating Better Matchings.", "Contribution Games in Social Networks.", among others.
  
  

  Approximability of the Firefighter Problem: Computing Cuts over Time. (slides)

  Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy.

  (Older title: "Approximations for the FireFighter Problem: Cuts over Time and Submodularity.")

  Algorithmica, Volume 62, Issue 1 (2012), Pages 520-536.

  Conference version appeared in Proc. 20th International Symposium on Algorithms and Computation (ISAAC 2009).
  
  The Firefighter problem models the case where a diffusive process such as an infection (or an idea, a computer virus, a fire) is spreading through a network, and our goal is to contain this infection by using targeted vaccinations. We consider two versions of the Firefighter problem: a non-spreading model, where vaccinating a node means only that this node cannot be infected; and a spreading model where the vaccination itself is an infectious process, such as in the case where the infection is a harmful idea, and the vaccine to it is another infectious beneficial idea. We look at several objective functions, and study the approximability of these problems.
  
  

  Exact and Approximate Equilibria for Optimal Group Network Formation. (slides)

  Elliot Anshelevich and Bugra Caskurlu.

  Theoretical Computer Science, Volume 412, Issue 39 (September 2011), pp. 5298-5314.

  Conference version appeared in Proc. 17th Annual European Symposium on Algorithms (ESA 2009).
  
  This paper considers network formation games where players attempt to form groups that satisfy their connectivity requirements. We provide results about existence and computation of Nash equilibrium that is as good as the centrally optimum solution. For versions of our game where equilibria may not exist, we instead show how to construct an approximate equilibrium.
  
  

  Anarchy, Stability, and Utopia: Creating Better Matchings.

  Elliot Anshelevich, Sanmay Das and Yonatan Naamad.

  Journal of Autonomous Agents and Multi-Agent Systems, to appear.

  Conference version appeared in Proc. 2nd International Symposium on Algorithmic Game Theory (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.

  In Proc. 2nd International Symposium on Algorithmic Game Theory (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.

  Theory of Computing Systems, Volume 49, Number 1 (July 2011), pp. 98-138.

  Conference version appeared in Proc. 2nd International Symposium on Algorithmic Game Theory (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 SIAM Journal on Computing, Volume 40, Issue 3 (2011), pp. 678-708.

  Conference version appeared 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.")

  Games and Economic Behavior, Volume 73, Issue 1, September 2011, Pages 17-38.

  Conference version appeared 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.