Arrow Research search

Author name cluster

Simon Mackenzie

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
2 author rows

Possible papers

13

STOC Conference 2025 Conference Paper

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

  • Simon Mackenzie
  • Abdallah Saffidine

In communication complexity the input of a function f:X×Y→Z is distributed between two players Alice and Bob. If Alice knows only x∈X and Bob only y∈Y, how much information must Alice and Bob share to be able to elicit the value of f(x,y)? Do we need ℓ more resources to solve ℓ instances of a problem? This question is the direct sum question and has been studied in many computational models. In this paper we focus on the case of 2-party deterministic communication complexity and give a counterexample to the direct sum conjecture in its strongest form. To do so we exhibit a family of functions for which the complexity of solving ℓ instances is less than (1−ϵ)ℓ times the complexity of solving one instance for some small enough ϵ>0. We use a customised method in the analysis of our family of total functions, showing that one can force the alternation of rounds between players. This idea allows us to exploit the integrality of the complexity measure to create an increasing gap between the complexity of solving the instances independently with that of solving them together.

Details

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.

PDF Details DOI

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.

PDF Details

AIJ Journal 2018 Journal Article

Fixing balanced knockout and double elimination tournaments

  • 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. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.

Details DOI

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.

PDF Details

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.

Details

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.

PDF Details

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.

Details

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.

Details

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.

PDF

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.

PDF Details

AIJ Journal 2015 Journal Article

Fair assignment of indivisible objects under ordinal preferences

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

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 stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied for these fairness notions. We also characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.

Details DOI

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.

PDF Details
v2026.09.13