Elliot Anshelevich

JAAMAS Journal 2026 Journal Article

Metric distortion under group-fair objectives

• Georgios Amanatidis
• Elliot Anshelevich
• Alexandros A. Voudouris

Abstract We consider a voting problem in which a set of agents have metric preferences over a set of alternatives, and are also partitioned into disjoint groups. Given information about the preferences of the agents and their groups, our goal is to decide an alternative to approximately minimize an objective function that takes the groups of agents into account. We consider two natural group-fair objectives known as Max-of-Avg and Avg-of-Max which are different combinations of the max and the average cost in and out of the groups. We show tight bounds on the best possible distortion that can be achieved by various classes of mechanisms depending on the amount of information they have access to. In particular, we consider full-information group-oblivious mechanisms that do not know the groups but have access to the exact distances between agents and alternatives in the metric space, ordinal-information group-oblivious mechanisms that again do not know the groups but are given the ordinal preferences of the agents, and group-aware mechanisms that have full knowledge of the structure of the agent groups and also ordinal information about the metric space.

AIJ Journal 2025 Journal Article

Improved metric distortion via threshold approvals

• Elliot Anshelevich
• Aris Filos-Ratsikas
• Christopher Jerrett
• Alexandros A. Voudouris

AAAI Conference 2025 Conference Paper

Metric Distortion of Line-up Elections: The Right Person for the Right Job

• Christopher Jerrett
• Yue Han
• Elliot Anshelevich

We provide mechanisms and new metric distortion bounds for line-up elections. In such elections, a set of n voters, k candidates, and ell positions are all located in a metric space. The goal is to choose a set of candidates and assign them to different positions, so as to minimize the total cost of the voters. The cost of each voter consists of the distances from itself to the chosen candidates (measuring how much the voter likes the chosen candidates, or how similar it is to them), as well as the distances from the candidates to the positions they are assigned to (measuring the fitness of the candidates for their positions). Our mechanisms, however, do not know the exact distances, and instead produce good outcomes while only using a smaller amount of information, resulting in small distortion. We consider several different types of information: ordinal voter preferences, ordinal position preferences, and knowing the exact locations of candidates and positions, but not those of voters. In each of these cases, we provide constant distortion bounds, thus showing that only a small amount of information is enough to form outcomes close to optimum in line-up elections.

AAAI Conference 2024 Conference Paper

Improved Metric Distortion via Threshold Approvals

• Elliot Anshelevich
• Aris Filos-Ratsikas
• Christopher Jerrett
• Alexandros A. Voudouris

We consider a social choice setting in which agents and alternatives are represented by points in a metric space, and the cost of an agent for an alternative is the distance between the corresponding points in the space. The goal is to choose a single alternative to (approximately) minimize the social cost (cost of all agents) or the maximum cost of any agent, when only limited information about the preferences of the agents is given. Previous work has shown that the best possible distortion one can hope to achieve is 3 when access to the ordinal preferences of the agents is given, even when the distances between alternatives in the metric space are known. We improve upon this bound of 3 by designing deterministic mechanisms that exploit a bit of cardinal information. We show that it is possible to achieve distortion 1+sqrt(2) by using the ordinal preferences of the agents, the distances between alternatives, and a threshold approval set per agent that contains all alternatives for whom her cost is within an appropriately chosen factor of her cost for her most-preferred alternative. We show that this bound is the best possible for any deterministic mechanism in general metric spaces, and also provide improved bounds for the fundamental case of a line metric.

AAAI Conference 2023 Conference Paper

Optimizing Multiple Simultaneous Objectives for Voting and Facility Location

• Yue Han
• Christopher Jerrett
• Elliot Anshelevich

We study the classic facility location setting, where we are given n clients and m possible facility locations in some arbitrary metric space, and want to choose a location to build a facility. The exact same setting also arises in spatial social choice, where voters are the clients and the goal is to choose a candidate or outcome, with the distance from a voter to an outcome representing the cost of this outcome for the voter (e.g., based on their ideological differences). Unlike most previous work, we do not focus on a single objective to optimize (e.g., the total distance from clients to the facility, or the maximum distance, etc.), but instead attempt to optimize several different objectives simultaneously. More specifically, we consider the l-centrum family of objectives, which includes the total distance, max distance, and many others. We present tight bounds on how well any pair of such objectives (e.g., max and sum) can be simultaneously approximated compared to their optimum outcomes. In particular, we show that for any such pair of objectives, it is always possible to choose an outcome which simultaneously approximates both objectives within a factor of 1 plus square root of 2, and give a precise characterization of how this factor improves as the two objectives being optimized become more similar. For q>2 different centrum objectives, we show that it is always possible to approximate all q of these objectives within a small constant, and that this constant approaches 3 as q increases. Our results show that when optimizing only a few simultaneous objectives, it is always possible to form an outcome which is a significantly better than 3 approximation for all of these objectives.

AIJ Journal 2022 Journal Article

The distortion of distributed metric social choice

• Elliot Anshelevich
• Aris Filos-Ratsikas
• Alexandros A. Voudouris

IJCAI Conference 2021 Conference Paper

Distortion in Social Choice Problems: The First 15 Years and Beyond

• Elliot Anshelevich
• Aris Filos-Ratsikas
• Nisarg Shah
• Alexandros A. Voudouris

The notion of distortion in social choice problems has been defined to measure the loss in efficiency---typically measured by the utilitarian social welfare, the sum of utilities of the participating agents---due to having access only to limited information about the preferences of the agents. We survey the most significant results of the literature on distortion from the past 15 years, and highlight important open problems and the most promising avenues of ongoing and future work.

AAAI Conference 2021 Conference Paper

Forming Better Stable Solutions in Group Formation Games Inspired by Internet Exchange Points (IXPs)

• Elliot Anshelevich
• Wennan Zhu

We study a coordination game motivated by the formation of Internet Exchange Points (IXPs), in which agents choose which facilities to join. Joining the same facility as other agents you communicate with has benefits, but different facilities have different costs for each agent. Thus, the players wish to join the same facilities as their “friends”, but this is balanced by them not wanting to pay the cost of joining a facility. We first show that the Price of Stability (PoS) of this game is at most 2, and more generally there always exists an α-approximate equilibrium with cost at most 2 α of optimum. We then focus on how better stable solutions can be formed. If we allow agents to pay their neighbors to prevent them from deviating (i. e. , a player i voluntarily pays another player j so that j joins the same facility), then we provide a payment scheme which stabilizes the solution with minimum social cost s∗, i. e. PoS is 1. In our main technical result, we consider how much a central coordinator would have to pay the players in order to form good stable solutions. Let ∆ denote the total amount of payments needed to be paid to the players in order to stabilize s∗, i. e. , these are payments that a player would lose if they changed their strategy from the one in s∗. We prove that there is a tradeoff between ∆ and the Price of Stability: ∆ cost(s∗) ≤ 1− 2 5 PoS. Thus when there are no good stable solutions, only a small amount of extra payment is needed to stabilize s∗; and when good stable solutions already exist (i. e. , PoS is small), then we should be happy with those solutions instead. Finally, we consider the computational complexity of finding the optimum solution s∗, and design a polynomial time O(log n) approximation algorithm for this problem.

AAAI Conference 2021 Conference Paper

Representative Proxy Voting

• Elliot Anshelevich
• Zack Fitzsimmons
• Rohit Vaish
• Lirong Xia

We study a model of proxy voting where the candidates, voters, and proxies are all located on the real line, and instead of voting directly, each voter delegates its vote to the closest proxy. The goal is to find a set of proxies that is θrepresentative, which entails that for any voter located anywhere on the line, its favorite candidate is within a distance θ of the favorite candidate of its closest proxy. This property guarantees a strong form of representation as the set of voters is not required to be fixed in advance, or even be finite. We show that for candidates located on a line, an optimal proxy arrangement can be computed in polynomial time. Moreover, we provide upper and lower bounds on the number of proxies required to form a θ-representative set, thus showing that a relatively small number of proxies is enough to capture the preferences of any set of voters. An additional beneficial property of a θ-representative proxy arrangement is that for strict-Condorcet voting rules, the outcome of proxy voting is similarly close to the outcome of direct voting.

AIJ Journal 2018 Journal Article

Approximating optimal social choice under metric preferences

• Elliot Anshelevich
• Onkar Bhardwaj
• Edith Elkind
• John Postl
• Piotr Skowron

AAAI Conference 2018 Conference Paper

Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems Using Only Ordinal Preferences

• Ben Abramowitz
• Elliot Anshelevich

We consider ordinal approximation algorithms for a broad class of utility maximization problems for multi-agent systems. In these problems, agents have utilities for connecting to each other, and the goal is to compute a maximumutility solution subject to a set of constraints. We represent these as a class of graph optimization problems, including matching, spanning tree problems, TSP, maximum weight planar subgraph, and many others. We study these problems in the ordinal setting: latent numerical utilities exist, but we only have access to ordinal preference information, i. e. , every agent specifies an ordering over the other agents by preference. We prove that for the large class of graph problems we identify, ordinal information is enough to compute solutions which are close to optimal, thus demonstrating there is no need to know the underlying numerical utilities. For example, for problems in this class with bounded degree b a simple ordinal greedy algorithm always produces a (b + 1)-approximation; we also quantify how the quality of ordinal approximation depends on the sparsity of the resulting graphs. In particular, our results imply that ordinal information is enough to obtain a 2-approximation for Maximum Spanning Tree; a 4-approximation for Max Weight Planar Subgraph; a 2-approximation for Max-TSP; and a 2approximation for various Matching problems.

JAIR Journal 2017 Journal Article

Randomized Social Choice Functions Under Metric Preferences

• Elliot Anshelevich
• John Postl

We determine the quality of randomized social choice algorithms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the algorithms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between the expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized algorithms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic algorithms.

AAAI Conference 2017 Conference Paper

Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity

• Stephen Gross
• Elliot Anshelevich
• Lirong Xia

To design social choice mechanisms with desirable utility properties, normative properties, and low sample complexity, we propose a new randomized mechanism called 2-Agree. This mechanism asks random voters for their top alternatives until at least two voters agree, at which point it selects that alternative as the winner. We prove that, despite its simplicity and low sample complexity, 2-Agree achieves almost optimal distortion on a metric space when the number of alternatives is not large, and satisfies anonymity, neutrality, ex-post Pareto efficiency, very strong SD-participation, and is approximately truthful. We further show that 2-Agree works well for larger number of alternatives with decisive agents.

AAAI Conference 2016 Conference Paper

Blind, Greedy, and Random: Algorithms for Matching and Clustering Using Only Ordinal Information

• Elliot Anshelevich
• Shreyas Sekar

We study the Maximum Weighted Matching problem in a partial information setting where the agents’ utilities for being matched to other agents are hidden and the mechanism only has access to ordinal preference information. Our model is motivated by the fact that in many settings, agents cannot express the numerical values of their utility for different outcomes, but are still able to rank the outcomes in their order of preference. Specifically, we study problems where the ground truth exists in the form of a weighted graph, and look to design algorithms that approximate the true optimum matching using only the preference orderings for each agent (induced by the hidden weights) as input. If no restrictions are placed on the weights, then one cannot hope to do better than the simple greedy algorithm, which yields a half optimal matching. Perhaps surprisingly, we show that by imposing a little structure on the weights, we can improve upon the trivial algorithm significantly: we design a 1. 6-approximation algorithm for instances where the hidden weights obey the metric inequality. Our algorithm is obtained using a simple but powerful framework that allows us to combine greedy and random techniques in unconventional ways. These results are the first non-trivial ordinal approximation algorithms for such problems, and indicate that we can design robust matchings even when we are agnostic to the precise agent utilities.

IJCAI Conference 2016 Conference Paper

Randomized Social Choice Functions under Metric Preferences

• Elliot Anshelevich
• John Postl

We determine the quality of randomized social choice mechanisms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the mechanisms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i. e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized mechanisms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic mechanisms.

AAAI Conference 2015 Conference Paper

Approximating Optimal Social Choice under Metric Preferences

• Elliot Anshelevich
• Onkar Bhardwaj
• John Postl

We examine the quality of social choice mechanisms using a utilitarian view, in which all of the agents have costs for each of the possible alternatives. While these underlying costs determine what the optimal alternative is, they may be unknown to the social choice mechanism; instead the mechanism must decide on a good alternative based only on the ordinal preferences of the agents which are induced by the underlying costs. Due to its limited information, such a social choice mechanism cannot simply select the alternative that minimizes the total social cost (or minimizes some other objective function). Thus, we seek to bound the distortion: the worst-case ratio between the social cost of the alternative selected and the optimal alternative. Distortion measures how good a mechanism is at approximating the alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that the agent costs form a metric space, which is a natural assumption in many settings. We quantify the distortion of many well-known social choice mechanisms. We show that for both total social cost and median agent cost, many positional scoring rules have large distortion, while on the other hand Copeland and similar mechanisms perform optimally or near-optimally, always obtaining a distortion of at most 5. We also give lower bounds on the distortion that could be obtained by any deterministic social choice mechanism, and extend our results on median agent cost to more general objective functions.

IJCAI Conference 2015 Conference Paper

Strategic Network Formation through an Intermediary

• Elliot Anshelevich
• Onkar Bhardwaj
• Koushik Kar

Settings in which independent self-interested agents form connections with each other are extremely common, and are usually modeled using network formation games. We study a natural extension of network formation games in which the nodes cannot form connections themselves, but instead must do it through an intermediary, and must pay the intermediary to form these connections. The price charged by the intermediary is assumed to be determined by its operating costs, which in turn depend on the total amount of connections it facilitates. We investigate the existence and worstcase efficiency (price of anarchy) of stable solutions in these settings, and especially when the intermediary uses common pricing schemes like proportional pricing or marginal cost pricing. For both these pricing schemes we prove existence of stable solutions and completely characterize their structure, as well as generalize these results to a large class of pricing schemes. Our main results are on bounding the price of anarchy in such settings: we show that while marginal cost pricing leads to an upper bound of only 2, i. e. , stable solutions are always close to optimal, proportional pricing also performs reasonably well as long as the operating costs of the intermediary are not too convex.

AAAI Conference 2014 Conference Paper

Approximate Equilibrium and Incentivizing Social Coordination

• Elliot Anshelevich
• Shreyas Sekar

We study techniques to incentivize self-interested agents to form socially desirable solutions in scenarios where they benefit from mutual coordination. Towards this end, we consider coordination games where agents have different intrinsic preferences but they stand to gain if others choose the same strategy as them. For non-trivial versions of our game, stable solutions like Nash Equilibrium may not exist, or may be socially inefficient even when they do exist. This motivates us to focus on designing efficient algorithms to compute (almost) stable solutions like Approximate Equilibrium that can be realized if agents are provided some additional incentives. Our results apply in many settings like adoption of new products, project selection, and group formation, where a central authority can direct agents towards a strategy but agents may defect if they have better alternatives. We show that for any given instance, we can either compute a high quality approximate equilibrium or a near-optimal solution that can be stabilized by providing small payments to some players. Our results imply that a little influence is necessary in order to ensure that selfish players coordinate and form socially efficient solutions.

JAAMAS Journal 2014 Journal Article

Seeding influential nodes in non-submodular models of information diffusion

• Elliot Anshelevich
• Ameya Hate
• Malik Magdon-Ismail

Abstract We consider the model of information diffusion in social networks from Hui et al. (Agentbased simulation of the diffusion of warnings, 2010 ) which incorporates trust (weighted links) between actors, and allows actors to actively participate in the spreading process, specifically through the ability to query friends for additional information. This model captures how social agents transmit and act upon information more realistically as compared to the simpler threshold and cascade models. However, it is more difficult to analyze, in particular with respect to seeding strategies. We present efficient, scalable algorithms for determining good seed sets—initial nodes to inject with the information. Our general approach is to reduce our model to a class of simpler models for which provably good sets can be constructed. By tuning this class of simpler models, we obtain a good seed set for the original more complex model. We call this the projected greedy approach because a model is ‘projected’ onto a class of simpler models where the greedy seed set selection is near-optimal. We demonstrate the effectiveness of our seeding strategy on synthetic graphs as well as a realistic San Diego evacuation network constructed during the 2007 fires, and the DBLP network of collaborations.

AAAI Conference 2013 Conference Paper

On the Social Welfare of Mechanisms for Repeated Batch Matching

• Elliot Anshelevich
• Meenal Chhabra
• Sanmay Das
• Matthew Gerrior

We study hybrid online-batch matching problems, where agents arrive continuously, but are only matched in periodic rounds, when many of them can be considered simultaneously. Agents not getting matched in a given round remain in the market for the next round. This setting models several scenarios of interest, including many job markets as well as kidney exchange mechanisms. We consider the social utility of two commonly used mechanisms for such markets: one that aims for stability in each round (greedy), and one that attempts to maximize social utility in each round (max-weight). Surprisingly, we find that in the long term, the social utility of the greedy mechanism can be higher than that of the max-weight mechanism. We hypothesize that this is because the greedy mechanism behaves similarly to a soft threshold mechanism, where all connections below a certain threshold are rejected by the participants in favor of waiting until the next round. Motivated by this observation, we propose a method to approximately calculate the optimal threshold for an individual agent to use based on characteristics of the other agents participating, and demonstrate experimentally that social utility is high when all agents use this strategy. Thresholding can also be applied by the mechanism itself to improve social welfare; we demonstrate this with an example on graphs that model pairwise kidney exchange.

AAMAS Conference 2013 Conference Paper

Seeding Influential Nodes in Non-Submodular Models of Information Diffusion

• Elliot Anshelevich
• Ameya Hate
• Malik Magdon-Ismail

We consider the model of information diffusion in social networks from [2] which incorporates trust (weighted links) between actors, and allows actors to actively participate in the spreading process, specifically through the ability to query friends for additional information. This model captures how social agents transmit and act upon information more realistically as compared to the simpler threshold and cascade models. However, it is more difficult to analyze, in particular with respect to seeding strategies. We present efficient, scalable algorithms for determining good seed sets – initial nodes to inject with the information. Our general approach is to reduce our model to a class of simpler models for which provably good sets can be constructed. By tuning this class of simpler models, we obtain a good seed set for the original more complex model. We call this the projected greedy approach because you ‘project’ your model onto a class of simpler models where a greedy seed set selection is nearoptimal. We demonstrate the effectiveness of our seeding strategy on synthetic graphs as well as a realistic San Diego evacuation network constructed during the 2007 fires.

AAMAS Conference 2012 Conference Paper

On the Social Welfare of Mechanisms for Repeated Batch Matching

• Elliot Anshelevich
• Meenal Chhabra
• Sanmay Das
• Matthew Gerrior

We study hybrid online-batch matching problems, where agents arrive continuously, but are only matched in periodic rounds, when many of them can be considered simultaneously. Agents not getting matched in a given round remain in the market for the next round. This setting models several scenarios of interest, including many job markets as well as kidney exchange mechanisms. We consider the social utility of two commonly used mechanisms for such markets: one that aims for stability in each round (greedy), and one that attempts to maximize social utility in each round (maxweight). Surprisingly, we find that in the long term, the social utility of the greedy mechanism can be higher than that of the max-weight mechanism. We hypothesize that this is because the greedy mechanism behaves similarly to a soft threshold mechanism, where all connections below a certain threshold are rejected by the participants in favor of waiting until the next round. Motivated by this observation, we propose a method to approximately calculate the optimal threshold for an individual agent, based on characteristics of the other agents, and demonstrate empirically that social utility is high when all agents use this strategy.

SODA Conference 2011 Conference Paper

A Stackelberg Strategy for Routing Flow over Time

• Umang Bhaskar
• Lisa Fleischer
• Elliot Anshelevich

Routing games are used to to understand the impact of individual users’ decisions on network efficiency. 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 optimal, for two natural measures of optimality.

JAAMAS Journal 2011 Journal Article

Anarchy, stability, and utopia: creating better matchings

• Elliot Anshelevich
• Sanmay Das
• Yonatan Naamad

Abstract Historically, the analysis of matching has centered on designing algorithms to produce stable matchings as well as on analyzing the incentive compatibility of matching mechanisms. Less attention has been paid to questions related to the social welfare of stable matchings in cardinal utility models. We examine the loss in social welfare that arises from requiring matchings to be stable, the natural equilibrium concept under individual rationality. While this loss can be arbitrarily bad under general preferences, when there is some structure to the underlying graph corresponding to natural conditions on preferences, we prove worst case bounds on the price of anarchy. Surprisingly, under simple distributions of utilities, the average case loss turns out to be significantly smaller than the worst-case analysis would suggest. Furthermore, we derive conditions for the existence of approximately stable matchings that are also close to socially optimal, demonstrating that adding small switching costs can make socially (near-)optimal matchings stable. Our analysis leads to several concomitant results of interest on the convergence of decentralized partner-switching algorithms, and on the impact of heterogeneity of tastes on social welfare.

TCS Journal 2011 Journal Article

Exact and approximate equilibria for optimal group network formation

• Elliot Anshelevich
• Bugra Caskurlu

STOC Conference 2007 Conference Paper

Terminal backup, 3D matching, and covering cubic graphs

• Elliot Anshelevich
• Adriana Karagiozova

FOCS Conference 2006 Conference Paper

Strategic Network Formation through Peering and Service Agreements

• Elliot Anshelevich
• F. Bruce Shepherd
• Gordon T. Wilfong

We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e. g. , Autonomous Systems, enterprise networks, residential customers). This system is at the heart of Internet connectivity. In our model we are given a network topology of nodes and links where the nodes (modeling the various Internet entities) act as the players of the game, and links represent potential contracts. Nodes wish to satisfy their demands, which earn potential revenues, but nodes may have to pay (or be paid by) their neighbors for links incident to them. By incorporating some of the qualities of Internet business relationships, we hope that our model will have predictive value. Specifically, we assume that contracts are either customer-provider or peering contracts. As often occurs in practice, we also include a mechanism that penalizes nodes if they drop traffic emanating from one of their customers. For a natural objective function, we prove that the price of stability is at most 2. With respect to social welfare, however, the prices of anarchy and stability can both be unbounded, leading us to consider how much we must perturb the system to obtain good stable solutions. We thus focus on the quality of Nash equilibria achievable through centralized incentives: solutions created by an "altruistic entity" (e. g. , the government) able to increase individual payouts for successfully routing a particular demand. We show that if every payout is increased by a factor of 2, then there is a Nash equilibrium as good as the original centrally defined social optimum. We also show how to find equilibria efficiently in multicast trees. Finally, we give a characterization of Nash equilibria as flows of utility with certain constraints, which helps to visualize the structure of stable solutions and provides us with useful proof techniques.

FOCS Conference 2004 Conference Paper

The Price of Stability for Network Design with Fair Cost Allocation

• Elliot Anshelevich
• Anirban Dasgupta 0001
• Jon M. Kleinberg
• Éva Tardos
• Tom Wexler
• Tim Roughgarden

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions - the Nash equilibria - may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. 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 consider the price of stability for network design with respect to one of the most widely-studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value, and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is O(log k), where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game.

STOC Conference 2003 Conference Paper

Near-optimal network design with selfish agents

• Elliot Anshelevich
• Anirban Dasgupta 0001
• Éva Tardos
• Tom Wexler

We introduce a simple network design game that models how independent selfish agents can build or maintain a large network. In our game every agent has a specific connectivity requirement, i.e. each agent has a set of terminals and wants to build a network in which his terminals are connected. Possible edges in the network have costs and each agent's goal is to pay as little as possible. Determining whether or not a Nash equilibrium exists in this game is NP-complete. However, when the goal of each player is to connect a terminal to a common source, we prove that there is a Nash equilibrium as cheap as the optimal network, and give a polynomial time algorithm to find a (1+ε) -approximate Nash equilibrium that does not cost much more. For the general connection game we prove that there is a 3-approximate Nash equilibrium that is as cheap as the optimal network, and give an algorithm to find a (4.65+ε) -approximate Nash equilibrium that does not cost much more.

STOC Conference 2002 Conference Paper

Stability of load balancing algorithms in dynamic adversarial systems

• Elliot Anshelevich
• David Kempe 0001
• Jon M. Kleinberg

ICRA Conference 2000 Conference Paper

Deformable Volumes in Path Planning Applications

• Elliot Anshelevich
• Scott Owens
• Florent Lamiraux
• Lydia E. Kavraki

This paper addresses the problem of path planning for a class of deformable volumes under fairly general manipulation constraints. The underlying geometric model for the volume is provided by a mass-spring representation. It is augmented by a realistic mechanical model. The latter permits the computation of the shape of the considered object with respect to the grasping constraints by minimizing the energy function of the deformation of the object. Previous research in planning for deformable objects considered the case of elastic plates and proposed a randomized framework for planning paths for plates under manipulation constraints. The present paper modifies and extends the previously proposed framework to handle simple volumes. Our planner builds a roadmap in the configuration space. The nodes of the roadmap are equilibrium configurations of the considered volume under the manipulation constraints, while its edges correspond to quasi-static equilibrium paths. Paths are found by searching the roadmap. We present experimental results that illustrate our approach.