## Warut Suksompong

NUS Presidential Young ProfessorSchool of Computing, National University of Singapore

Email:

*warut*at

*comp.nus.edu.sg*

[CV]

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

**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.

### Working Papers

Closing Gaps in Asymptotic Fair DivisionPasin 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

Consensus Halving for Sets of ItemsPaul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong

In Proceedings of the 16th Conference on Web and Internet Economics (WINE), December 2020, Forthcoming.

[Conference] [PDF]

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong

Journal of Artificial Intelligence Research, Forthcoming.

A preliminary version appeared in Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), February 2020, pp. 1990-1997.

[Conference] [PDF]

How to Cut a Cake Fairly: A Generalization to Groups

Erel Segal-Halevi and Warut Suksompong

American Mathematical Monthly, Forthcoming.

[PDF]

Almost Envy-Freeness in Group Resource Allocation

Maria Kyropoulou, Warut Suksompong, and Alexandros A. Voudouris

Theoretical Computer Science, Vol. 841, November 2020, pp. 110-123.

A preliminary version appeared in Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), August 2019, pp. 400-406.

[Journal] [Conference] [PDF]

Truthful Fair Division Without Free Disposal

Xiaohui Bei, Guangda Huzhang, and Warut Suksompong

Social Choice and Welfare, Vol. 55, No. 3, October 2020, pp. 523-545.

A preliminary version appeared in Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), July 2018, pp. 63-69.

[Journal] [Conference] [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]

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 GroupsWarut 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 ApproachesAyumi Igarashi and Warut Suksompong

Presented at the 28th International Joint Conference on Artificial Intelligence (IJCAI), August 2019.

[Tutorial]

### Miscellaneous

Some problems I have proposedWarut Suksompong

[PDF]