Publications (21)
A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
Katie Clinch, Serge Gaspers, Tao Zixu He +2
This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method…
Computational Aspects of Multi-Winner Approval Voting
Haris Aziz, Serge Gaspers, Joachim Gudmundsson +3
We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional appro…
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
Haris Aziz, Simon Mackenzie
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from agents. The problem has received attention in compu…
Best-of-Both-Worlds Fairness for Mixed Goods and Chores
Haris Aziz, Xiaolin Bu, Xinhang Lu +4
We study the fundamental problem of fairly dividing indivisible items among agents with additive utilities. In our model, an item can be a good yielding non-negative utilities to s…
When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations
Simon Mackenzie, Mashbat Suzuki
One of the central questions in discrete fair division is whether fairness and efficiency can be achieved simultaneously. For indivisible goods, a canonical relaxation of envy-free…
Structure and complexity of ex post efficient random assignments
Haris Aziz, Simon Mackenzie, Lirong Xia +1
In the random assignment problem, objects are randomly assigned to agents keeping in view the agents' preferences over objects. A random assignment specifies the probability of an…
Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
Simon Mackenzie, Abdallah Saffidine
In communication complexity the input of a function is distributed between two players Alice and Bob. If Alice knows only and Bob only ,…
Fair Division with Indivisible Goods, Chores, and Cake
Haris Aziz, Xinhang Lu, Simon Mackenzie +1
We study the problem of fairly allocating indivisible items and a desirable heterogeneous divisible good (i.e., cake) to agents with additive utilities. In our paper, each indivisi…
Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices
Xinhang Lu, Simon Mackenzie, Mashbat Suzuki
We study the fair allocation of indivisible items to agents with additive utilities. In our setting, each indivisible item may be a good, yielding non-negative utility to s…
Manipulating the Probabilistic Serial Rule
Haris Aziz, Serge Gaspers, Simon Mackenzie +3
The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. Howe…
Faster Exponential-Time Approximate Counting via Bounded Self-Reductions
Katie Clinch, Serge Gaspers, Simon Mackenzie +1
We give faster exponential-time randomised approximation algorithms for counting problems where polynomial-time approximation is unavailable and exact exponential-time counting rem…
On the Number of Minimal Separators in Graphs
Serge Gaspers, Simon Mackenzie
We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in . We prove that t…
NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
Serge Gaspers, Tao Zixu He, Simon Mackenzie
We prove that computing the deterministic communication complexity of a Boolean function, given its truth table, is \textsf{NP}-complete in the standard protocol-tree-depth model,…
Fair assignment of indivisible objects under ordinal preferences
Haris Aziz, Serge Gaspers, Simon Mackenzie +1
We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stoc…
Counterexamples to EFX for Submodular and Subadditive Valuations
Simon Mackenzie, Mashbat Suzuki
The existence of EFX allocations is a fundamental question in fair division. In this paper, we construct a three-agent, eight-good instance with monotone subadditive valuations suc…
Egalitarianism of Random Assignment Mechanisms
Haris Aziz, Jiashu Chen, Aris Filos-Ratsikas +2
We consider the egalitarian welfare aspects of random assignment mechanisms when agents have unrestricted cardinal utilities over the objects. We give bounds on how well different…
The Fluid Mechanics of Liquid Democracy
Paul Gölz, Anson Kahng, Simon Mackenzie +1
Liquid democracy is the principle of making collective decisions by letting agents transitively delegate their votes. Despite its significant appeal, it has become apparent that a…
The Provable Virtue of Laziness in Motion Planning
Nika Haghtalab, Simon Mackenzie, Ariel D. Procaccia +2
The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along shortest paths between the source and target. These algorithms were desi…
A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents
Haris Aziz, Simon Mackenzie
We consider the well-studied cake cutting problem in which the goal is to identify a fair allocation based on a minimal number of queries from the agents. The problem has attracted…
Equilibria Under the Probabilistic Serial Rule
Haris Aziz, Serge Gaspers, Simon Mackenzie +3
The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties,…
Complexity of Manipulating Sequential Allocation
Haris Aziz, Sylvain Bouveret, Jerome Lang +1
Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns and each agents gets the most preferred item that is still available. It has lo…