8 papers
Subquadratic Subsidies for Nonnegative or Nonpositive Valuations
Max Dupré la Tour, Mashbat Suzuki
We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in , we prove that a total subsi…
Balanced Fair Division for Three Agents under General Valuations and Laminar Constraints
Max Dupré la Tour
We study fair allocations of indivisible items under general set valuations. We prove that every instance with three agents and arbitrary real-valued valuations admits a balanced a…
Random Serial Dictatorship is -Envy-Free
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin +4
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem i…
Bad News for Couples: Bounds for Fair Division of Indivisible Items among Groups
Max Dupré la Tour
We consider the problem of fairly allocating indivisible items to couples, where each couple consists of two agents with distinct additive valuations. We show that there exist bina…
-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye +1
A graph is a -leaf power if there is a tree whose leaves are the vertices of with the property that a pair of leaves and induce an edge in if and o…
Faster and Simpler Greedy Algorithm for -Median and -Means
Max Dupré la Tour, David Saulpic
Clustering problems such as -means and -median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In…