Simon Mackenzie

STOC Conference 2025 Conference Paper

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity

• Simon Mackenzie
• Abdallah Saffidine

JAIR Journal 2021 Journal Article

Liquid Democracy: An Algorithmic Perspective

• Anson Kahng
• Simon Mackenzie
• Ariel D. Procaccia

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a non-local delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

IJCAI Conference 2019 Conference Paper

The Provable Virtue of Laziness in Motion Planning

• Nika Haghtalab
• Simon Mackenzie
• Ariel D. Procaccia
• Oren Salzman
• Siddhartha Srinivasa

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm such as manipulation in cluttered environments and planning for robots in surgical settings; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

AIJ Journal 2018 Journal Article

Fixing balanced knockout and double elimination tournaments

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Paul Stursberg
• Toby Walsh

AAAI Conference 2018 Conference Paper

Liquid Democracy: An Algorithmic Perspective

• Anson Kahng
• Simon Mackenzie
• Ariel Procaccia

We study liquid democracy, a collective decision making paradigm that allows voters to transitively delegate their votes, through an algorithmic lens. In our model, there are two alternatives, one correct and one incorrect, and we are interested in the probability that the majority opinion is correct. Our main question is whether there exist delegation mechanisms that are guaranteed to outperform direct voting, in the sense of being always at least as likely, and sometimes more likely, to make a correct decision. Even though we assume that voters can only delegate their votes to better-informed voters, we show that local delegation mechanisms, which only take the local neighborhood of each voter as input (and, arguably, capture the spirit of liquid democracy), cannot provide the foregoing guarantee. By contrast, we design a nonlocal delegation mechanism that does provably outperform direct voting under mild assumptions about voters.

ICAPS Conference 2018 Conference Paper

The Provable Virtue of Laziness in Motion Planning

• Nika Haghtalab
• Simon Mackenzie
• Ariel D. Procaccia
• Oren Salzman
• Siddhartha S. Srinivasa

The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along candidate shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.

AAAI Conference 2017 Conference Paper

Complexity of Manipulating Sequential Allocation

• Haris Aziz
• Sylvain Bouveret
• JŽr™me Lang
• Simon Mackenzie

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several nonmanipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.

FOCS Conference 2016 Conference Paper

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

• Haris Aziz 0001
• 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 n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is nnnnnn. Even if we do not run our protocol to completion, it can find in at most n n+1 queries an envy-free partial allocation of the cake in which each agent gets at least 1/n of the value of the whole cake.

STOC Conference 2016 Conference Paper

A discrete and bounded envy-free cake cutting protocol for four agents

• Haris Aziz 0001
• Simon Mackenzie

We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem to obtain a bounded envy-free protocol for more than three agents. The problem has been termed the central open problem in cake cutting. We solve this problem by proposing a discrete and bounded envy-free protocol for four agents.

AAMAS Conference 2016 Conference Paper

Egalitarianism of Random Assignment Mechanisms (Extended Abstract)

• Haris Aziz
• Aris Filos-Ratsikas
• Jiashu Chen
• Simon Mackenzie
• Nicholas Mattei

We consider the egalitarian welfare of random assignment mechanisms when agents have unrestricted cardinal utilities over the objects. We define and give bounds on how well different random assignment mechanisms approximate the optimal egalitarian value (OEV) and investigate the effect that different well-known properties like ordinality, envyfreeness, and truthfulness have on the achievable egalitarian value. Finally, we conduct detailed experiments analyzing the tradeoffs between efficiency with envy-freeness or truthfulness using two prominent random assignment mechanisms — random serial dictatorship and the probabilistic serial mechanism — for different classes of utility functions and distributions.

IJCAI Conference 2015 Conference Paper

Equilibria Under the Probabilistic Serial Rule

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Nina Narodytska
• Toby Walsh

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, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.

AIJ Journal 2015 Journal Article

Fair assignment of indivisible objects under ordinal preferences

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Toby Walsh

AAAI Conference 2014 Conference Paper

Fixing a Balanced Knockout Tournament

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Paul Stursberg
• Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner.