7 papers
The Complexity of Justified Representation with Additive Utilities
Carmel Baharav, Jakob de Raaij, Agnès Totschnig
We study the computational complexity of satisfying proportional representation -- in particular proportional, extended, and fully justified representation (PJR, EJR, and FJR) -- i…
Almost perfect graph classes
Cicely Henderson, Hidde Koerts, Taite LaGrange +4
A graph is perfect if for each induced subgraph of . In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem.…
Fair Division of Graphs: Beyond Traceability
Nicolas Bousquet, Frank Connor, Agnès Totschnig +1
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally al…
The Tiered Clinching Auction with Applications to Carbon Offset Markets
Tessa Davis, Agnès Totschnig, Adrian Vetta
Voluntary carbon offsetting is a strategy which has been pursued globally by corporations to reduce their effective carbon emissions. Carbon offset markets currently suffer from lo…
The Popular Dimension of Matchings
Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye +3
We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching problem, (a subset of…
Every graph with no -minor is -colorable
Sergey Norin, Agnes Totschnig
Let denote the graph obtained from the complete graph on seven vertices by deleting two edges with a common end. Motivated by Hadwiger's conjecture, we prove that ever…