Warut Suksompong

Research Associate
Department of Computer Science, University of Oxford
Email: warut.suksompong at cs.ox.ac.uk
[CV]

I am a postdoctoral researcher in computer science at the University of Oxford, hosted by Edith Elkind. Before coming to Oxford, I completed my PhD at Stanford University, where my advisor was Tim Roughgarden. My research interests include algorithmic game theory, mechanism design, social choice theory, and other problems at the interface between computer science and economics. I received my bachelor's and master's degrees from Massachusetts Institute of Technology.

News: I am co-editing a special issue of the Journal of Autonomous Agents and Multiagent Systems on fair division. Please see the call for papers.

Program Committees: AAAI 2020, AAMAS 2020, EC 2020, ECAI 2020, GAIW 2020, IJCAI 2020, AAAI 2019, EC 2019, IJCAI 2019, WTAF 2019, IJCAI 2018, SAGT 2018

Working Papers

Consensus Halving for Sets of Items
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong
[PDF]

Closing Gaps in Asymptotic Fair Division
Pasin Manurangsi and Warut Suksompong
[PDF]

Dividing a Graphical Cake
Xiaohui Bei and Warut Suksompong
[PDF]

The Price of Connectivity in Fair Division
Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong
[PDF]

Funding Public Projects: A Case for the Nash Product Rule
Florian Brandl, Felix Brandt, Dominik Peters, Christian Stricker, and Warut Suksompong
A preliminary version was presented at the 1st Games, Agents, and Incentives Workshop (GAIW), May 2019.
[PDF]

Publications

Almost Envy-Freeness in Group Resource Allocation
Maria Kyropoulou, Warut Suksompong, and Alexandros A. Voudouris
Theoretical Computer Science, Forthcoming.
A preliminary version appeared in Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), August 2019, pp. 400-406.
[Conference] [PDF]

Truthful Fair Division Without Free Disposal
Xiaohui Bei, Guangda Huzhang, and Warut Suksompong
Social Choice and Welfare, Forthcoming.
A preliminary version appeared in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), July 2018, pp. 63-69.
[Journal] [Conference] [PDF]

How to Cut a Cake Fairly: A Generalization to Groups
Erel Segal-Halevi and Warut Suksompong
American Mathematical Monthly, Forthcoming.
[PDF]

When Do Envy-Free Allocations Exist?
Pasin Manurangsi and Warut Suksompong
SIAM Journal on Discrete Mathematics, Vol. 34, No. 3, 2020, pp. 1505-1521.
A preliminary version appeared in Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), January-February 2019, pp. 2109-2116.
[Journal] [Conference] [PDF]

On the Number of Almost Envy-Free Allocations
Warut Suksompong
Discrete Applied Mathematics, Vol. 284, September 2020, pp. 606-610.
[Journal] [PDF]

Weighted Envy-Freeness in Indivisible Item Allocation
Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick
In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2020, pp. 231-239.
Also presented at the 2nd Games, Agents, and Incentives Workshop (GAIW), May 2020.
[Conference] [PDF] [Blog]

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong
In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), February 2020, pp. 1990-1997.
[Conference] [PDF]

Refining Tournament Solutions via Margin of Victory
Markus Brill, Ulrike Schmidt-Kraepelin, and Warut Suksompong
In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), February 2020, pp. 1862-1869.
[Conference] [PDF]

Pricing Multi-Unit Markets
Tomer Ezra, Michal Feldman, Tim Roughgarden, and Warut Suksompong
ACM Transactions on Economics and Computation, Vol. 7, No. 4, February 2020, Article 20.
A preliminary version appeared in Proceedings of the 14th Conference on Web and Internet Economics (WINE), December 2018, pp. 140-153.
[Journal] [Conference] [PDF]

Robust Bounds on Choosing from Large Tournaments
Christian Saile and Warut Suksompong
Social Choice and Welfare, Vol. 54, No. 1, January 2020, pp. 87-110.
Preliminary versions appeared in Proceedings of the 14th Conference on Web and Internet Economics (WINE), December 2018, pp. 393-407, and Proceedings of the 7th International Workshop on Computational Social Choice (COMSOC), June 2018.
[Journal] [Conference] [Workshop] [PDF]

Democratic Fair Allocation of Indivisible Goods
Erel Segal-Halevi and Warut Suksompong
Artificial Intelligence, Vol. 277, December 2019, Article 103167.
Preliminary versions appeared in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), July 2018, pp. 482-488, and Proceedings of the 7th International Workshop on Computational Social Choice (COMSOC), June 2018.
[Journal] [Conference] [Workshop] [PDF] [Code]

Envy-Freeness in House Allocation Problems
Jiarui Gan, Warut Suksompong, and Alexandros A. Voudouris
Mathematical Social Sciences, Vol. 101, September 2019, pp. 104-106.
[Journal] [PDF]

The Price of Fairness for Indivisible Goods
Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong
In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), August 2019, pp. 81-87.
[Conference] [PDF]

Schelling Games on Graphs
Edith Elkind, Jiarui Gan, Ayumi Igarashi, Warut Suksompong, and Alexandros A. Voudouris
In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), August 2019, pp. 266-272.
[Conference] [PDF]

On Black-Box Transformations in Downward-Closed Environments
Warut Suksompong
Theory of Computing Systems, Vol. 63, No. 6, August 2019, pp. 1207-1227.
An abstract appeared in Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), September 2017, p. XV. The paper was accepted to the conference as a full paper.
[Journal] [Conference] [PDF]

Simple Pricing Schemes for the Cloud
Ian A. Kash, Peter Key, and Warut Suksompong
ACM Transactions on Economics and Computation, Vol. 7, No. 2, August 2019, Article 7.
Preliminary versions appeared in Proceedings of the 13th Conference on Web and Internet Economics (WINE), December 2017, pp. 311-324, and Proceedings of the 12th Workshop on the Economics of Networks, Systems and Computation (NetEcon), June 2017.
[Journal] [Conference] [Workshop] [PDF]

Fairly Allocating Contiguous Blocks of Indivisible Items
Warut Suksompong
Discrete Applied Mathematics, Vol. 260, May 2019, pp. 227-236.
A preliminary version appeared in Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), September 2017, pp. 333-344.
[Journal] [Conference] [PDF]

Computing a Small Agreeable Set of Indivisible Items
Pasin Manurangsi and Warut Suksompong
Artificial Intelligence, Vol. 268, March 2019, pp. 96-114.
Full version of the IJCAI '16 and IJCAI '17 papers.
[Journal] [PDF]

Fairly Allocating Many Goods with Few Queries
Hoon Oh, Ariel D. Procaccia, and Warut Suksompong
In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), January-February 2019, pp. 2141-2148.
Also presented at the 6th Day on Computational Game Theory (DCGT), February 2019.
[Conference] [PDF]

On the Structure of Stable Tournament Solutions
Felix Brandt, Markus Brill, Hans Georg Seedig, and Warut Suksompong
Economic Theory, Vol. 65, No. 2, March 2018, pp. 483-507.
[Journal] [PDF]

Approximate Maximin Shares for Groups of Agents
Warut Suksompong
Mathematical Social Sciences, Vol. 92, March 2018, pp. 40-47.
An abstract appeared in Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), September 2017, p. XIV. The paper was accepted to the conference as a full paper.
[Journal] [Conference] [PDF]

Who Can Win a Single-Elimination Tournament?
Michael P. Kim, Warut Suksompong, and Virginia Vassilevska Williams
SIAM Journal on Discrete Mathematics, Vol. 31, No. 3, 2017, pp. 1751-1764.
Preliminary versions appeared in Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), February 2016, pp. 516-522, and Proceedings of the 6th International Workshop on Computational Social Choice (COMSOC), June 2016.
[Journal] [Conference] [Workshop] [PDF]

Asymptotic Existence of Fair Divisions for Groups
Pasin Manurangsi and Warut Suksompong
Mathematical Social Sciences, Vol. 89, September 2017, pp. 100-108.
An abstract appeared in Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), September 2017, pp. XII-XIII. The paper was accepted to the conference as a full paper.
[Journal] [Conference] [PDF]

Computing an Approximately Optimal Agreeable Set of Items
Pasin Manurangsi and Warut Suksompong
In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), August 2017, pp. 338-344.
The full version, combined with the IJCAI '16 paper, appeared in Artificial Intelligence.
[Conference] [PDF]

Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
Warut Suksompong
In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), July 2016, pp. 489-495.
The full version, combined with the IJCAI '17 paper, appeared in Artificial Intelligence.
[Conference] [PDF]

Asymptotic Existence of Proportionally Fair Allocations
Warut Suksompong
Mathematical Social Sciences, Vol. 81, May 2016, pp. 62-65.
[Journal] [PDF]

The Impossibility of Extending Random Dictatorship to Weak Preferences
Florian Brandl, Felix Brandt, and Warut Suksompong
Economics Letters, Vol. 141, April 2016, pp. 44-47.
[Journal] [PDF] [Corrigendum]

On the Efficiency of Localized Work Stealing
Warut Suksompong, Charles E. Leiserson, and Tao B. Schardl
Information Processing Letters, Vol. 116, No. 2, February 2016, pp. 100-106.
[Journal] [PDF]

Upper Bounds on Number of Steals in Rooted Trees
Charles E. Leiserson, Tao B. Schardl, and Warut Suksompong
Theory of Computing Systems, Vol. 58, No. 2, February 2016, pp. 223-240.
[Journal] [PDF]

An Ordinal Minimax Theorem
Felix Brandt, Markus Brill, and Warut Suksompong
Games and Economic Behavior, Vol. 95, January 2016, pp. 107-112.
Also presented at the 5th World Congress of the Game Theory Society (GAMES), July 2016.
[Journal] [PDF]

Scheduling Asynchronous Round-Robin Tournaments
Warut Suksompong
Operations Research Letters, Vol. 44, No. 1, January 2016, pp. 96-100.
[Journal] [PDF]

Individual and Group Stability in Neutral Restrictions of Hedonic Games
Warut Suksompong
Mathematical Social Sciences, Vol. 78, November 2015, pp. 1-5.
[Journal] [PDF]

On a Subposet of the Tamari Lattice
Sebastian A. Csar, Rik Sengupta, and Warut Suksompong
Order, Vol. 31, No. 3, November 2014, pp. 337-363.
A preliminary version appeared in Proceedings of the 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), July-August 2012, pp. 567-578.
[Journal] [Conference] [PDF]

Theses

Resource Allocation and Decision Making for Groups
Warut Suksompong
PhD Thesis, Stanford University, August 2018.
[Thesis] [PDF]

Bounds on Multithreaded Computations by Work Stealing
Warut Suksompong
Master's Thesis, Massachusetts Institute of Technology, June 2014.
[Thesis] [PDF]

Tutorials

Fair Division of Indivisible Items: Asymptotics and Graph-Theoretic Approaches
Ayumi Igarashi and Warut Suksompong
Presented at the 28th International Joint Conference on Artificial Intelligence (IJCAI), August 2019.
[Tutorial]

Miscellaneous

Some problems I have proposed
Warut Suksompong
[PDF]