research
∙
05/28/2023
The Computational Complexity of Single-Player Imperfect-Recall Games
We study single-player extensive-form games with imperfect recall, such ...
share
research
∙
05/18/2023
Best-Response Dynamics in Lottery Contests
We study the convergence of best-response dynamics in lottery contests. ...
research
∙
01/24/2023
The Frontier of Intractability for EFX with Two Agents
We consider the problem of sharing a set of indivisible goods among agen...
research
∙
07/20/2022
PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games
Lipschitz games, in which there is a limit λ (the Lipschitz value of the...
research
∙
07/17/2022
Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy
We study a general scenario of simultaneous contests that allocate prize...
research
∙
02/13/2022
Consensus Division in an Arbitrary Ratio
We consider the problem of partitioning a line segment into two subsets,...
research
∙
08/08/2021
Equivalence of Models of Cake-Cutting Protocols
The cake-cutting problem involves dividing a heterogeneous, divisible re...
research
∙
07/08/2021
Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games
Nearly a decade ago, Azrieli and Shmaya introduced the class of λ-Lipsch...
research
∙
11/03/2020
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
We study search problems that can be solved by performing Gradient Desce...
research
∙
07/14/2020
Consensus Halving for Sets of Items
Consensus halving refers to the problem of dividing a resource into two ...
research
∙
05/04/2020
Learning Strong Substitutes Demand via Queries
This paper addresses the computational challenges of learning strong sub...
research
∙
11/13/2019
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
We study the fair allocation of a cake, which serves as a metaphor for a...
research
∙
09/16/2019
Solving Strong-Substitutes Product-Mix Auctions
This paper develops algorithms to solve strong-substitutes product-mix a...
research
∙
02/20/2019
The Hairy Ball Problem is PPAD-Complete
The Hairy Ball Theorem states that every continuous tangent vector field...
research
∙
11/13/2018
Multi-unit Bilateral Trade
We characterise the set of dominant strategy incentive compatible (DSIC)...
research
∙
07/17/2018
Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries
Suppose that an m-simplex is partitioned into n convex regions having di...
research
∙
05/31/2018
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
We resolve the computational complexity of two problems known as NECKLAC...
research
∙
11/13/2017