Elliot Anshelevich - Selected Publications (sorted by topic)

See the Full Publication List and my Research Statement for more info.

Ordinal Approximation Algorithms

• Elliot Anshelevich, Onkar Bhardwaj, and John Postl. Approximating Optimal Social Choice under Metric Preferences. (slides) Proc. of 29th Conference on Artificial Intelligence (AAAI 2015).
  
• Elliot Anshelevich and John Postl. Randomized Social Choice Functions Under Metric Preferences. Journal of Artificial Intelligence Research (JAIR), to appear. Conference version appeared in IJCAI 2016.
  
• Stephen Gross, Elliot Anshelevich, and Lirong Xia. Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity. Proc. of 31st Conference on Artificial Intelligence (AAAI 2017).
  
  
In these three papers we examine the quality of social choice mechanisms with metric preferences, 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 analysis to various randomized mechanisms as well.


• Elliot Anshelevich and Shreyas Sekar. Blind, Greedy, and Random: Algorithms for Matching and Clustering using only Ordinal Information. (slides) Proc. of 30th Conference on Artificial Intelligence (AAAI 2016). (See also the arXiv version, which includes many additional results and extensions.)
  
• Elliot Anshelevich and Shreyas Sekar. Truthful Mechanisms for Matching and Clustering in an Ordinal World. Proc of 12th Conference on Web and Internet Economics (WINE 2016).
  
• Elliot Anshelevich and Wennan Zhu. Tradeoffs Between Information and Ordinal Approximation for Bipartite Matching. Proc. of 10th International Symposium on Algorithmic Game Theory (SAGT 2017).
  
• Ben Abramowitz and Elliot Anshelevich. Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems using only Ordinal Preferences. Proc. of 32nd Conference on Artificial Intelligence (AAAI 2018).
  
  
In these papers we study Matching and other related problems 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. Using our algorithms for matching as a black-box, we also design new approximation algorithms for other closely related problems: these include a a 3.2-approximation for the problem of clustering agents into equal sized partitions, a 4-approximation algorithm for Densest k-subgraph, and a 2.14-approximation algorithm for Max TSP. These results are the first non-trivial ordinal approximation algorithms for such problems, and indicate that we can design robust algorithms even when we are agnostic to the precise agent utilities. In a followup paper, we extend our techniques to produce truthful algorithms for these problems as well: a 1.76-approximation algorithm for Max-Weight Matching, 2-approximation algorithm for Max k-matching, a 6-approximation algorithm for Densest k-subgraph, and a 2-approximation algorithm for Max Traveling Salesman as long as the hidden weights constitute a metric.

Pricing to Maximize Revenue and Welfare

• Elliot Anshelevich and Shreyas Sekar. Price Doubling and Item Halving: Robust Revenue Guarantees for Item Pricing. Proc. of 18th ACM Conference on Economics and Computation (EC 2017).
  
  
We study approximation algorithms for revenue maximization based on static item pricing, where a seller chooses prices for various goods in the market, and then the buyers purchase utility-maximizing bundles at these given prices. We formulate two somewhat general techniques for designing good pricing algorithms for this setting: Price Doubling and Item Halving. Using these techniques, we unify many of the existing results in the item pricing literature under a common framework, as well as provide several new item pricing algorithms for approximating both revenue and social welfare. For a variety of settings with item pricing, we show that it is possible to obtain a log-approximation for revenue and a constant-approximation for social welfare simultaneously: thus one need not sacrifice revenue if the goal is to still have decent welfare guarantees.
The main technical contribution of this paper is an approximation algorithm for revenue maximization based on the Item Halving technique, for settings where buyers have XoS valuations. Ours is the first known item pricing algorithm with polylogarithmic approximations for such general classes of valuations, and partially resolves an important open question from the algorithmic pricing literature about the existence of item pricing algorithms with logarithmic factors for general valuations.


• Elliot Anshelevich, Koushik Kar, and Shreyas Sekar. Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare. ACM Transactions on Economics and Computation (TEAC), to appear. Conference version appeared in ICALP 2015.
  
• Elliot Anshelevich, Koushik Kar, and Shreyas Sekar. Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets. Proc of 12th Conference on Web and Internet Economics (WINE 2016).
  
  
We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions of this problem have resisted good approximation factors for maximizing revenue; this is true even for the classic unit-demand case. In our first paper above we study envy-free pricing with unit-demand buyers, but unlike previous work we focus on large markets: ones in which the demand of each buyer is infinitesimally small compared to the size of the overall market. We assume that the buyer valuations for the items they desire have a nice (although reasonable) structure, i.e., that the aggregate buyer demand has a monotone hazard rate and that the values of every buyer type come from the same support. For such large markets, our main contribution is a 1.88 approximation algorithm for maximizing revenue, showing that good pricing schemes can be computed when the number of buyers is large. We also give a (e,2)-bicriteria algorithm that simultaneously approximates both maximum revenue and welfare, thus showing that it is possible to obtain both good revenue and welfare at the same time. We further generalize our results by relaxing some of our assumptions, and quantify the necessary tradeoffs between revenue and welfare in our setting. Our results are the first known approximations for large markets, and crucially rely on new lower bounds which we prove for the revenue-maximizing prices. In our follow-up paper, we relax the assumption that the demand has a monotone hazard rate, as well as greatly generalize our results to multi-minded buyers instead of simply unit-demand ones. In general, our results show that when markets are large, it is possible to obtain both high revenue and high welfare simultaneously, and the prices achieving this can be computed efficiently.


• Elliot Anshelevich and Shreyas Sekar. Price Competition in Networked Markets: How do monopolies impact social welfare? Proc of 11th Conference on Web and Internet Economics (WINE 2015).
  
  
We study the efficiency of allocations in large markets with a network structure where every seller owns an edge in a graph and every buyer desires a path connecting some nodes. While it is known that stable allocations in such settings can be very inefficient, the exact properties of equilibria in markets with multiple sellers are not fully understood even in single-source single-sink networks. In this work, we show that for a large class of natural buyer demand functions, we are guaranteed the existence of an equilibrium with several desirable properties. The crucial insight that we gain into the equilibrium structure allows us to obtain tight bounds on efficiency in terms of the various parameters governing the market, especially the number of monopolies M. All of our efficiency results extend to markets without the network structure. While it is known that monopolies can cause large inefficiencies in general, our main results for single-source single-sink networks indicate that for several natural demand functions the efficiency only drops linearly with M. For example, for concave demand we prove that the efficiency loss is at most a factor 1+M/2 from the optimum, for demand with monotone hazard rate it is at most 1+M, and for polynomial demand the efficiency decreases logarithmically with M. In contrast to previous work that showed that monopolies may adversely affect welfare, our main contribution is showing that monopolies may not be as `evil' as they are made out to be; the loss in efficiency is bounded in many natural markets. Finally, we consider more general, multiple-source networks and show that in the absence of monopolies, mild assumptions on the network topology guarantee an equilibrium that maximizes social welfare.

Self-Interested Agents in Network Formation, Matching, and Group Formation

• Elliot Anshelevich, Onkar Bhardwaj, and Martin Hoefer. Stable Matching with Network Externalities. (slides) Algorithmica, to appear. Conference version appeared in ESA 2013.
  
• Elliot Anshelevich, Onkar Bhardwaj, and Michael Usher. Friend of My Friend: Network Formation with Two-Hop Benefit. Theory of Computing Systems, Volume 57, Issue 3 (2015), pages 711-752. Conference version appeared in SAGT 2013.
  
  
We study stable matching problems in networks where players are embedded in a social context, and may incorporate friendship relations or altruism into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. When the benefits from a match are the same for both players, we show that incorporating the well-being of other players into their matching decisions significantly decreases the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the price of stability bound always exists and can be reached in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different utilities from the match. For this more general case, we show that incorporating social context (i.e., "caring about your friends") can make an even larger difference, and greatly reduce the price of anarchy. We show a variety of existence results, and present upper and lower bounds on the prices of anarchy and stability for various matching utility structures. Finally, in a follow-up paper, we consider games on networks where a node tries to maximize its utility taking into account the benefit it gets from the nodes it is directly connected to, as well as the benefit it gets from the nodes it is acquainted with via a two-hop connection. While the addition of two-hop benefit changes the properties of these games significantly, we prove that in many important cases good equilibrium solutions still exist, and bound the change in the price of anarchy due to two-hop benefit.


• Elliot Anshelevich and Martin Hoefer. Contribution Games in Social Networks. (slides) Algorithmica, Volume 63, Issue 1-2 (June 2012), pages 51-90. Conference version appeared in 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.


• Elliot Anshelevich, Meenal Chhabra, Sanmay Das, and Matthew Gerrior. On the Social Welfare of Mechanisms for Repeated Batch Matching. Proc. 27th Conference on Artificial Intelligence (AAAI 2013).
  
• Elliot Anshelevich, Sanmay Das and Yonatan Naamad. Anarchy, Stability, and Utopia: Creating Better Matchings. Journal of Autonomous Agents and Multi-Agent Systems, Volume 26, Issue 1 (January 2013), pages 120-140. Conference version appeared in SAGT 2009.
  
  
We consider the loss in social welfare caused by individual rationality and by online node arrival 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.


• Elliot Anshelevich and Shreyas Sekar. Approximate Equilibrium and Incentivizing Social Coordination. Proc. of 28th Conference on Artificial Intelligence (AAAI 2014).
  
  
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. We then generalize our model to encompass situations where player relationships may exhibit complementarities and present an algorithm to compute an Approximate Equilibrium whose stability factor is linear in the degree of complementarity. Our results imply that a little influence is necessary in order to ensure that selfish players coordinate and form socially efficient solutions.


• Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler. Near-Optimal Network Design with Selfish Agents. Theory of Computing, Volume 4 (2008), pp. 77-109. Conference version appeared in STOC 2003.
  
• Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. (pdf) SIAM Journal on Computing, Volume 38, Issue 4 (November 2008), pp. 1602-1623. Conference version appeared in FOCS 2004.
  
• Elliot Anshelevich and Bugra Caskurlu. Price of Stability in Survivable Network Design. Theory of Computing Systems, Volume 49, Number 1 (July 2011), pp. 98-138. Conference version appeared in SAGT 2009.
  
• Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation. (slides) Theoretical Computer Science, Volume 412, Issue 39 (September 2011), pp. 5298-5314. Conference version appeared in ESA 2009.
  
• Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate. Strategic Multiway Cut and Multicut Games. Theory of Computing Systems, Volume 52, Issue 2 (2013), pages 200-220. Conference version appeared in WAOA 2010.
  
• Elliot Anshelevich, Bugra Caskurlu, Koushik Kar, and Hang Zhang. Capacity Allocation Games for Network-Coded Multicast Streaming. IEEE/ACM Transactions on Networking, Volume 22, Number 2 (April 2014), pages 595-607.
  
  
In our fundamental work from STOC 2003 and FOCS 2004, we considered several important network formation games, and quantified their prices of anarchy and of stability. These were some of the first papers in the field to introduce fundamental techniques for game theoretic analysis such as the concept of the price of stability, and the use of potential games and approximate Nash equilibria. In a line of work following these, we analyzed much more general forms of network formation, including survivable network design, group formation, and cut formation. For all these settings, we were able to greatly extend the original techniques, and in most cases provide tight bounds for price of stability and price of anarchy, as well as algorithms to compute good Nash equilibria.

Game Theoretic Routing, Autonomous Systems, and The Internet

• Onkar Bhardwaj, Elliot Anshelevich, and Koushik Kar. Coalitionally Stable Pricing Schemes for Inter-domain Forwarding. Computer Networks, Volume 97, Issue C (March 2016), Pages 128--146.
  
• Elliot Anshelevich, Onkar Bhardwaj, and Koushik Kar. Strategic Network Formation through Intermediaries. Proc of 24th International Joint Conference on Artificial Intelligence (IJCAI 2015).
  
• Elliot Anshelevich, Ameya Hate, and Koushik Kar. Strategic Pricing in Next-hop Routing with Elastic Demands. Theory of Computing Systems, Volume 54, Issue 3 (2014), pages 407-430. Conference version appeared in SAGT 2011.
  
  
In this work, we model and analyze the problem of stable and efficient pricing for inter-domain traffic routing. We consider a general network topology with multiple sources and sinks of traffic, organized into separate domains managed by Internet Service Providers (ISPs) solely interested in maximizing their own profit. In essence, this is 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. Among other results, we prove that there exists a pricing scheme that attains network-wide efficiency and is yet coalitionally stable, where the coalitions correspond to the ISPs that are acting in self-interest. This implies that this pricing scheme not only maximizes the overall utility of the resulting traffic flows, but is also such that ISPs cannot expect to improve their profit through deviation from it, even if multiple ISPs deviate at the same time.


• Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong. Strategic Network Formation through Peering and Service Agreements. (pdf) Games and Economic Behavior, Volume 73, Issue 1, September 2011, Pages 17-38. Conference version appeared in FOCS 2006.
  
• Elliot Anshelevich and Gordon Wilfong. Network Formation and Routing by Strategic Agents using Local Contracts. Proc. 4th International Workshop On Internet And Network Economics (WINE 2008).
  
  
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 (i.e., 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. In the follow-up paper, we extend our model by addressing the issues of contract formation and routing simultaneously.

Exact and Approximation Algorithms for Network Problems

• Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy. Approximability of the Firefighter Problem: Computing Cuts over Time. (slides) Algorithmica, Volume 62, Issue 1 (2012), Pages 520-536. Conference version appeared in ISAAC 2009.
  
• Elliot Anshelevich and Adriana Karagiozova. Terminal Backup, 3D Matching, and Covering Cubic Graphs. SIAM Journal on Computing, Volume 40, Issue 3 (2011), pp. 678-708. Conference version appeared in STOC 2007.
  
• Dahai Xu, Elliot Anshelevich, and Mung Chiang. On Survivable Access Network Design: Complexity and Algorithms. Proc. 27th IEEE Conference on Computer Communications (INFOCOM 2008).
  
• Elliot Anshelevich and Lisa Zhang. Path Decomposition under a New Cost Measure with Applications to Optical Network Design. ACM Transactions on Algorithms (TALG), Volume 4, Issue 1 (March 2008). Conference version appeared in ESA 2004.
  
• Elliot Anshelevich, David Kempe, and Jon Kleinberg. Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. SIAM Journal on Computing, Volume 37, Issue 5 (January 2008), pp. 1656-1673. Conference version appeared in STOC 2002.
  

Other Work on Self-Interested Agents

• Elliot Anshelevich, John Postl, and Tom Wexler. Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness. Theory of Computing Systems, Volume 59, Issue 3 (October 2016), Pages 440--475.
  
• Elliot Anshelevich and John Postl. Profit Sharing with Thresholds and Non-monotone Player Utilities. Theory of Computing Systems, Volume 59, Issue 4 (2016), Pages 563--580. Conference version appeared in SAGT 2014.
  
• Elliot Anshelevich and Shreyas Sekar. Computing Stable Coalitions: Approximation Algorithms for Reward Sharing. Proc of 11th Conference on Web and Internet Economics (WINE 2015).
  
• Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate. Partition Equilibrium Always Exists in Resource Selection Games. Theory of Computing Systems, Volume 53, Issue 1 (2013), pages 73-85. Conference version appeared in SAGT 2010.