Research Interests
Algorithms and theoretical computer science, especially issues at the intersection of Economics and Computation. Algorithms for large decentralized networks, including networks with strategic agents. Particular interests include: social choice and voting algorithms, network formation, networked markets and matching markets, algorithmic game theory, approximation algorithms, graph algorithms, and information propagation in both social and computer networks. If you are a student who wants to work with me, please also read this.
Publications
Last Updated: 11/20/2022
Yue Han, Chris Jerrett, and Elliot Anshelevich. Optimizing Multiple Simultaneous Objectives for Voting and Facility Location. Proc. of 37th Conference on Artificial Intelligence (AAAI 2023).
Elliot Anshelevich, Aris Filos-Ratsikas, and Alexandros A. Voudouris. The Distortion of Distributed Metric Social Choice. Artificial Intelligence (AIJ), Volume 308, July 2022, 103713. Conference version appeared in WINE 2021.
2021
Elliot Anshelevich, Aris Filos-Ratsikas, and Alexandros A. Voudouris. The Distortion of Distributed Metric Social Choice. Proc. of 17th Conference on Web and Internet Economics (WINE 2021).
Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in Social Choice Problems: The First 15 Years and Beyond. Proc. of 30th International Joint Conference on Artificial Intelligence (IJCAI 2021).
Elliot Anshelevich, Zach Fitzsimmons, Rohit Vaish, and Lirong Xia. Representative Proxy Voting. Proc. of 35th Conference on Artificial Intelligence (AAAI 2021).
Elliot Anshelevich and Wennan Zhu. Forming better stable solutions in Group Formation Games inspired by Internet Exchange Points (IXPs). Proc. of 35th Conference on Artificial Intelligence (AAAI 2021).
Elliot Anshelevich and Wennan Zhu. Ordinal Approximation for Social Choice, Matching, and Facility Location Problems given Candidate Positions. ACM Transactions on Economics and Computation (TEAC), Volume 9(2), Article 9. Conference version appeared in WINE 2018.
Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in Social Choice Problems: An Annotated Reading List. Newsletter of the ACM Special Interest Group on Economics and Computation (SIGecom Exchanges), Volume 19.1, June 2021.
2019
Ben Abramowitz, Elliot Anshelevich, and Wennan Zhu. Awareness of Voter Passion Greatly Improves the Distortion of Metric Social Choice. Proc. of 15th Conference on Web and Internet Economics (WINE 2019).
Elliot Anshelevich and Wennan Zhu. Tradeoffs Between Information and Ordinal Approximation for Bipartite Matching. Theory of Computing Systems, 63(7), Pages 1499-1530. Conference version appeared in SAGT 2017.
Elliot Anshelevich, Onkar Bhardwaj, and Koushik Kar. Strategic Network Formation through Intermediaries. Theory of Computing Systems, 63(6), Pages 1314-1335. Conference version appeared in IJCAI 2015.
2018
Elliot Anshelevich and Wennan Zhu. Ordinal Approximation for Social Choice, Matching, and Facility Location Problems given Candidate Positions. Proc. of 14th Conference on Web and Internet Economics (WINE 2018).
Ben Abramowitz and Elliot Anshelevich. Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems using only Ordinal Preferences. Proc. of 32nd AAAI Conference on Artificial Intelligence (AAAI 2018).
Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, Piotr Skowron. Approximating Optimal Social Choice under Metric Preferences. Artificial Intelligence, Volume 264 (November 2018), Pages 27-51. Contains material from conference papers appearing in AAAI 2015 and AAAI 2017.
2017
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).
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). Also appeared at 7th International Workshop on Computational Social Choice (COMSOC 2018).
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).
Elliot Anshelevich, Koushik Kar, Shreyas Sekar, and Zaid Tariq. Balancing Social Utility with Aggregator Profit in Electric Vehicle Charging. Proc. of IEEE International Conference on Smart Grid Communications (SmartGridComm 2017).
Elliot Anshelevich, Koushik Kar, and Shreyas Sekar. Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare. ACM Transactions on Economics and Computation (TEAC), Volume 5, Issue 3, Article 16. Conference version appeared in ICALP 2015.
Elliot Anshelevich and John Postl. Randomized Social Choice Functions Under Metric Preferences. Journal of Artificial Intelligence Research (JAIR), Volume 58, Pages 797-827. Conference version appeared in IJCAI 2016.
Elliot Anshelevich, Onkar Bhardwaj, and Martin Hoefer. Stable Matching with Network Externalities. (slides) Algorithmica, 78(3), 1067-1106. Conference version appeared in ESA 2013.
2016
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, 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).
Elliot Anshelevich and John Postl. Randomized Social Choice Functions Under Metric Preferences. Proc. of 25th International Joint Conference on Artificial Intelligence (IJCAI 2016).
Elliot Anshelevich and Shreyas Sekar. Blind, Greedy, and Random: Algorithms for Matching and Clustering using only Ordinal Information. Proc. of 30th Conference on Artificial Intelligence (AAAI 2016). (See also the arXiv version, which includes many additional results and extensions.)
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.
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 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. Ordinal Approximation in Matching and Social Choice. Newsletter of the ACM Special Interest Group on E-commerce (SIGecom Exchanges), Volume 15.1, July 2016.
2015
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 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).
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, Koushik Kar, and Shreyas Sekar. Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare. Proc of 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015).
Elliot Anshelevich, Onkar Bhardwaj, and John Postl. Approximating Optimal Social Choice under Metric Preferences. Proc. of 29th Conference on Artificial Intelligence (AAAI 2015).
Elliot Anshelevich, Ameya Hate, and Malik Magdon-Ismail. Seeding Influential Nodes in Non-Submodular Models of Information Diffusion. Journal of Autonomous Agents and Multi-Agent Systems, Volume 29, Issue 1 (2015), pages 131-159.
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.
Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich. A Stackelberg Strategy for Routing Flow over Time. Games and Economic Behavior, Volume 92, July 2015, pages 232-247. Conference version appeared in SODA 2011.
2014
Elliot Anshelevich and John Postl. Profit Sharing with Thresholds and Non-monotone Player Utilities. Proc. of 7th International Symposium on Algorithmic Game Theory (SAGT 2014).
Elliot Anshelevich and Shreyas Sekar. Approximate Equilibrium and Incentivizing Social Coordination. Proc. of 28th Conference on Artificial Intelligence (AAAI 2014).
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.
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.
2013
Elliot Anshelevich, Onkar Bhardwaj, and Michael Usher. Friend of My Friend: Network Formation with Two-Hop Benefit. Proc. of 6th International Symposium on Algorithmic Game Theory (SAGT 2013).
Elliot Anshelevich, Onkar Bhardwaj, and Martin Hoefer. Friendship and Stable Matching. (slides) Proc. 21st European Symposium on Algorithms (ESA 2013).
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, 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.
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, 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.
2012
Elliot Anshelevich and Martin Hoefer. Contribution Games in Social Networks. Algorithmica, Volume 63, Issue 1-2 (June 2012), pages 51-90. Conference version appeared in ESA 2010.
Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy. Approximability of the Firefighter Problem: Computing Cuts over Time. Algorithmica, Volume 62, Issue 1 (2012), Pages 520-536. Conference version appeared in ISAAC 2009.
2011
Elliot Anshelevich, Ameya Hate, and Koushik Kar. Strategic Pricing in Next-hop Routing with Elastic Demands. Proc. 4th International Symposium on Algorithmic Game Theory (SAGT 2011). Full version appears in Theory of Computing Systems.
Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich. A Stackelberg Strategy for Routing Flow over Time. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Full version appeared in Games and Economic Behavior.
Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation. Theoretical Computer Science, Volume 412, Issue 39 (September 2011), pp. 5298-5314. Conference version appeared in ESA 2009.
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 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.
Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong. Strategic Network Formation through Peering and Service Agreements. Games and Economic Behavior, Volume 73, Issue 1, September 2011, Pages 17-38. Conference version appeared in FOCS 2006.
Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich. A Competitive Strategy for Routing Flow over Time. Newsletter of the ACM Special Interest Group on E-commerce (SIGecom Exchanges), Volume 10.2, June 2011.
2010
Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate. Strategic Multiway Cut and Multicut Games. Proc. 8th Workshop on Approximation and Online Algorithms (WAOA 2010). Full version appears in Theory of Computing Systems.
Elliot Anshelevich, Bugra Caskurlu, and Ameya Hate. Partition Equilibrium Always Exists in Resource Selection Games. Proc. 3rd International Symposium on Algorithmic Game Theory (SAGT 2010). Full version appears in Theory of Computing Systems.
Elliot Anshelevich and Martin Hoefer. Contribution Games in Social Networks. (slides) Proc. 18th Annual European Symposium on Algorithms (ESA 2010). Full version appears in Algorithmica.
Elliot Anshelevich and Sanmay Das. Matching, Cardinal Utility, and Social Welfare. ACM SIGecom Exchanges, Volume 9.1, June 2010.
2009
Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation. Proc. 17th Annual European Symposium on Algorithms (ESA 2009). Full version appears in Theoretical Computer Science.
Elliot Anshelevich, Sanmay Das and Yonatan Naamad. Anarchy, Stability, and Utopia: Creating Better Matchings. Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT 2009). Full version appears in JAAMAS.
Elliot Anshelevich and Satish Ukkusuri. Equilibria in Dynamic Selfish Routing. Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT 2009).
Elliot Anshelevich and Bugra Caskurlu. Price of Stability in Survivable Network Design. Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT 2009). Full version appears in Theory of Computing Systems.
Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy. Approximations for the FireFighter Problem: Cuts over Time and Submodularity. Â Proc. 20th International Symposium on Algorithms and Computation (ISAAC 2009). Full version appears in Algorithmica.
2008
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).
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, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. SIAM Journal on Computing, Volume 38, Issue 4 (November 2008), pp. 1602-1623. Conference version appeared in FOCS 2004.
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, 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, 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.
2007
Elliot Anshelevich and Adriana Karagiozova. Terminal Backup, 3D Matching, and Covering Cubic Graphs. Proc. 39th ACM Symposium on Theory of Computing (STOC 2007). Full version appears in SIAM Journal on Computing.
2006
Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong. Strategic Network Formation through Peering and Service Agreements. (Older title: "Local Peering and Service Contracts in Strategic Network Formation.") Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006). Full version appears in Games and Economic Behavior.
2005 and earlier
Elliot Anshelevich. Network Design and Management with Strategic Agents. Ph.D. Thesis, Cornell University, 2005.
Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004). Full version appears in SIAM Journal on Computing.
Elliot Anshelevich and Lisa Zhang. Path Decomposition under a New Cost Measure with Applications to Optical Network Design. Proc. 12th Annual European Symposium on Algorithms (ESA 2004). Full version appears in ACM Transactions on Algorithms (TALG).
Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler. Near-Optimal Network Design with Selfish Agents. Proc. 35th ACM Symposium on Theory of Computing (STOC 2003). Full version appears in Theory of Computing.
Elliot Anshelevich, David Kempe, and Jon Kleinberg. Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. Proc. 34th ACM Symposium on Theory of Computing (STOC 2002). Full version appears in SIAM Journal on Computing.
Elliot Anshelevich, Scott Owens, Florent Lamiraux, and Lydia Kavraki. Deformable Volumes in Path Planning Applications. IEEE International Conference on Robotics and Automation (ICRA) 2000, 2290-2295.