I am an Assistant Professor of Information Systems in the Questrom School of Business and a Junior Faculty Fellow at the Rafik B. Hariri Institute for Computing and Computational Science & Engineering at Boston University.

I am interested in computational social choice, fair division and discrete optimization, especially problems with real-world applications like participatory budgeting and gerrymandering.

Before coming to Boston, I completed my PhD in Operations Research in the Tepper School of Business at Carnegie Mellon University, where I was fortunate to be advised by Ariel D. Procaccia and John Hooker. I also had the opportunity to work with Andrea Qualizza in the supply chain optimization technologies (SCOT) team at Amazon in the summer of 2017. Before moving to the US I completed an MSc degree under Jan van Vuuren and Alewyn Burger at Stellenbosch University in South Africa.

# Working papers

• W3
Fair and Efficient Online Allocations
By Gerdus Benadè, Aleks Kazachkov, Ariel D. Procaccia, Alex Psomas and David Zeng. (Jun 2022, under review)
[ | paper ]

#### Abstract

We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another's allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries we find a sharp trade-off: no allocation algorithm can simultaneously provide both non-trivial fairness and non-trivial efficiency guarantees. In a slightly weaker adversary regime where item values are drawn from (potentially correlated) distributions it is possible to achieve the best of both worlds. We give an algorithm that is Pareto efficient ex post and either envy-free up to one good or envy-free with high probability. Neither guarantee can be improved, even in isolation. En route, we give a constructive proof for a structural result of independent interest. Specifically, there always exists a Pareto efficient fractional allocation that is strongly envy-free with respect to pairs of agents with substantially different utilities, while allocating identical bundles to agents with identical utilities (up to multiplicative factors).

• W2
You can have your cake and redistrict it too
By Gerdus Benadè, Jamie Tucker-Foltz, Ariel D. Procaccia. (Jan 2023)
[ | paper ]

#### Abstract

The design of algorithms for political redistricting generally takes one of two approaches: optimize an objective such as compactness or, drawing on fair division, construct a protocol whose outcomes guarantee partisan fairness. We aim to have the best of both worlds by optimizing an objective subject to a binary fairness constraint. As the fairness constraint we adopt the geometric target, which requires the number of seats won by each party to be at least the average (rounded down) of its outcomes under the worst and best partitions of the state; but we extend this notion to allow the two parties to compute their targets with respect to different election datasets. Our theoretical contribution is twofold: we introduce a new model of redistricting that closely mirrors the classic model of cake-cutting and we prove the feasibility of the geometric target in this model. Our empirical results, which use real election data and maps of six US states, demonstrate that the geometric target is feasible in practice and that imposing it as a fairness constraint comes at almost no cost to three well-studied optimization objectives.

• W1
Ranked Choice Voting and Minority Representation
By Gerdus Benadè, Ruth Buck, Moon Duchin, Dara Gold, Thomas Weighill. (Feb 2021)
*Mentioned in The Washington Post, 6 July 2021.
[ | paper ]

#### Abstract

We outline and demonstrate a data-driven methodology that voting rights advocates can use to compare the likely effectiveness of a single transferable vote system (STV) to single-member districts (SMD) for securing minority representation in local government. We incorporate both election data and demographics, and can apply variable assumptions on candidate availability and voter turnout. The core of our STV analysis uses four models of voter ranking behavior that take racial polarization into account; to assess districts, we use random district-generation algorithms developed at the MGGG Redistricting Lab. We demonstrate this method on four case studies: judicial elections in Terrebonne Parish, Louisiana; the county commission of Jones County, North Carolina; and the city councils of Cincinnati, Ohio and Pasadena, Texas. We find that STV provides proportional or slightly better representation for the relevant minority group in each case, while districts vary widely in their eectiveness depending on local circumstances.

# Publications

• C9
Participatory Budgeting Design for the Real World
By Gerdus Benadè, Roy Fairstein and Ya'akov (Kobi) Gal.
AAAI-2023: Proc. of the 37th AAAI Conference on Artificial Intelligence, Feb 2023.
[ | paper ]

#### Abstract

Participatory budgeting engages the public in the process of allocating public money to different types of projects. PB designs differ in how voters are asked to express their preferences over candidate projects and how these preferences are aggregated to determine which projects to fund. This paper studies two fundamental questions in PB design. Which voting format and aggregation method to use, and how to evaluate the outcomes of these design decisions? We conduct an extensive empirical study in which 1800 participants vote in four participatory budgeting elections in a controlled setting to evaluate the practical effects of the choice of voting format and aggregation rule. We find that k-approval leads to the best user experience. With respect to the aggregation rule, greedy aggregation leads to outcomes that are highly sensitive to the input format used and the fraction of the population that participates. The method of equal shares, in contrast, leads to outcomes that are not sensitive to the type of voting format used, and these outcomes are remarkably stable even when the majority of the population does not participate in the election. These results carry valuable insights for PB practitioners and social choice researchers.

• C8
Stability, Fairness and the Pursuit of Happiness
By Gerdus Benadè and Nachiketa Sahoo.
WITS-2022: Proc. of the 32nd Workshop on Information Technologies and Systems, Dec 2022. (Updated Jan 2023)
[ | paper ]

#### Abstract

Top-k recommendations are ubiquitous, but are they stable? We study whether, given complete information, buyers and sellers prefer to be in a platform using top-k recommendations rather than pursuing off-platform transactions. When there are no constraints on the number of exposures, we show that top-k recommendations are stable. However, stable k-recommendations may not exist when exposures are constrained (e.g., due to limited inventory or exposure opportunities). We show that maximizing total buyer welfare under exposure constraints is stable in three restricted preference domains: orthogonal buyers, identical buyers, and buyers with dichotomous valuations. Experiments on three real-world datasets find that common recommendation strategies exhibit substantial instability and envy. Among them, maximizing total buyers' welfare leads to the most stable outcomes. Though welfare maximization and round robin lead to envious buyers, their envy is nearly eliminated by a single item swap.

• C7
Dynamic Fair Division with Partial Information
By Gerdus Benadè, Daniel Halpern, Alex Psomas.
NeurIPS-2022: Proc. of the 36th Conference on Neural Information Processing Systems, Nov 2022.
[ | paper ]

#### Abstract

We consider the fundamental problem of fairly and efficiently allocating T indivisible items among n agents with additive preferences. The items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents’ valuations for the items are drawn from known distributions, it is possible (under mild technical assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex-post. We study a partial-information setting, where it is possible to elicit ordinal but not cardinal information. When a new item arrives, the algorithm can query each agent for the relative rank of this item with respect to a subset of the past items. When values are drawn from i.i.d. distributions, we give an algorithm that is envy-free and (1 − \eps)-welfare-maximizing with high probability. We provide similar guarantees (envy-freeness and a constant approximation to welfare with high probability) even with minimally expressive queries that ask for a comparison to a single previous item. For independent but non-identical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. We prove that all our results are asymptotically tight.

• J4
Political Districting without Geography
By Gerdus Benadè, Nam Ho-Nguyen, John Hooker.
Operations Research Perspectives: 9 (2022). doi:10.1016/j.orp.2022.100227
[ | paper ]

#### Abstract

Geographical considerations such as contiguity and compactness are necessary elements of political districting in practice. Yet an analysis of the problem without such constraints yields mathematical insights that can inform real-world model construction. In particular, it clarifies the sharp contrast between proportionality and competitiveness and how it might be overcome in a properly formulated objective function. It also reveals serious weaknesses of the much-discussed efficiency gap as a criterion for gerrymandering.

• J3
Preference Elicitation for Participatory Budgeting
By Gerdus Benadè, Swaprava Nath, Nisarg Shah and Ariel D. Procaccia.
Management Science 67(5): 2813-2827 (2020). doi: 10.1287/mnsc.2020.3666 *(Supercedes C2)
[ | paper ]

#### Abstract

Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable real-world impact. But making the most of this new paradigm requires a rethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We attempt to maximize social welfare by using the observed votes as proxies for voters' unknown underlying utilities, and analytically compare four preference elicitation methods: knapsack votes, rankings by value or value for money, and threshold approval votes. We find that threshold approval voting is qualitatively superior, and also performs well in experiments using data from real participatory budgeting elections.

• C6
No Stratification without Representation
By Gerdus Benadè, Paul Gölz and Ariel D. Procaccia.
EC-2019: Proc. of the 20th ACM Conference on Economics and Computation, June 2019 (pp. 281--314).
*Mentioned in Bloomberg, 6 Sept 2019.
[ | paper | 🎞 Paul at EC ]

#### Abstract

Sortition is a novel approach to democracy, in which representatives are not elected but randomly selected from the population. Most electoral democracies fail to accurately represent even a handful of protected groups. By contrast, sortition guarantees that every subset of the population will in expectation fill their fair share of the available positions. This fairness property remains satisfied when the sample is stratified based on known features. Moreover, stratification can greatly reduce the variance in the number of positions filled by any unknown group, as long as this group correlates with the strata. Our main result is that stratification cannot increase this variance by more than a negligible factor, even in the presence of indivisibilities and rounding. When the unknown group is unevenly spread across strata, we give a guarantee on the reduction in variance with respect to uniform sampling. We also contextualize stratification and uniform sampling in the space of fair sampling algorithms. Finally, we apply our insights to an empirical case study.

• T2
Equity and efficiency in computational social choice
[ Thesis ]
• C5
Low-distortion Social Welfare Functions
By Gerdus Benadè, Ariel D. Procaccia, and Mingda Qiao.
AAAI-2019: Proc. of 33rd AAAI Conference on Artificial Intelligence, Jan 2019.
[ | paper ]

#### Abstract

Work on implicit utilitarian voting advocates the design of voting rules that maximize utilitarian social welfare with respect to latent utility functions, based only on observed rankings of the alternatives. This approach has been successfully deployed in order to help people choose a single alternative or a subset of alternatives, but it has previously been unclear how to apply the same approach to the case where the desired output is a ranking. We propose to address this problem by assuming that voters' utilities for rankings are induced by unknown weights and unknown utility functions, which, moreover, have a combinatorial (subadditive) structure. Despite the extreme lack of information about voters' preferences, we show that it is possible to choose rankings such that the worst-case gap between their social welfare and that of the optimal ranking, called distortion, is no larger (up to polylogarithmic factors) than the distortion associated with much simpler problems. Through experiments, we identify practical methods that achieve near-optimal social welfare on average.

• C4
How to Make Envy Vanish Over Time
By Gerdus Benadè, Aleks Kazachkov, Ariel D. Procaccia and Alex Psomas.
EC-2018: Proc. of the 19th ACM Conference on Economics and Computation, June 2018.
[ | paper | 🎞 at EC ]

#### Abstract

We study the dynamic fair division of indivisible goods. Suppose $$T$$ items arrive online and must be allocated upon arrival to one of $$n$$ agents, each of whom has a value in $$[0,1]$$ for the current item. Our goal is to design allocation algorithms that minimize the maximum envy at time $$T$$, $$\text{Envy}_T$$, defined as the maximum difference between any agent's overall value for items allocated to another agent and to herself. We say that an algorithm has vanishing envy if the ratio of envy over time, $$\text{Envy}_T/T$$, goes to zero as $$T$$ goes to infinity. We design a polynomial-time, deterministic algorithm that achieves $$\text{Envy}_T \in \tilde{O}( \sqrt{T/n})$$, and show that this guarantee is asymptotically optimal. We also derive tight (in $$T$$) bounds for a more general setting where items arrive in batches.

• J2
Optimization Bounds from the Branching Dual
By Gerdus Benadè and John Hooker.
INFORMS Journal on Computing 32(1): 3-15 (2019). doi:10.1287/ijoc.2018.0884
[ | paper ]

#### Abstract

We present a general method for obtaining strong bounds for discrete optimization problems that is based on a concept of branching duality. It can be applied when no useful integer programming model is available, and we illustrate this with the minimum bandwidth problem. The method strengthens a known bound for a given problem by formulating a dual problem whose feasible solutions are partial branching trees. It solves the dual problem with a `worst-bound' local search heuristic that explores neighboring partial trees. After proving some optimality properties of the heuristic, we show that it substantially improves known combinatorial bounds for the minimum bandwidth problem with a modest amount of computation. It also obtains significantly tighter bounds than depth-first and breadth-first branching, demonstrating that the dual perspective can lead to better branching strategies when the object is to find valid bounds.

• U2
Efficiency and Usability of Participatory Budgeting Methods
By Gerdus Benadè, Nevo Itzhak, Nisarg Shah, Ariel D. Procaccia, and Ya'akov (Kobi) Gal.
[ | paper ]

#### Abstract

Participatory budgeting is an influential paradigm that engages residents in the process of allocating a city’s budget. Different implementations vary in the input format they use to elicit participants’ preferences on potential projects. Our goal is to compare input formats on two dimensions: efficiency, which is measured in terms of the social welfare of the resulting outcomes, and usability, which is evaluated through a combination of objective and subjective indicators. To this end, we conduct an extensive empirical study, in which morethan 1200 voters used different methods in a controlled setting. Our results suggest that a popular input format known as k-approval imposes low cognitive burden and is strikingly efficient, but is not necessarily perceived as such

• C3
Making Right Decisions Based on Wrong Opinions
By Gerdus Benadè, Anson Kanhg and Ariel D. Procaccia.
EC-2017: Proc. of the 18th ACM Conference on Economics and Computation, June 2017 (pp. 267--284).
[ | paper | 🎞 Anson at EC ]

#### Abstract

We revisit the classic problem of designing voting rules that aggregate objective opinions, in a setting where voters have noisy estimates of a true ranking of the alternatives. Previous work has replaced structural assumptions on the noise with a worst-case approach that aims to choose an outcome that minimizes the maximum error with respect to any feasible true ranking. This approach underlies algorithms that have recently been deployed on the social choice website RoboVote.org. We take a less conservative viewpoint by minimizing the average error with respect to the set of feasible ground truth rankings. We derive (mostly sharp) analytical bounds on the expected error and establish the practical benefits of our approach through experiments.

• C2
Preference Elicitation for Participatory Budgeting
By Gerdus Benadè, Swaprava Nath, Nisarg Shah and Ariel D. Procaccia.
AAAI-2017: Proc. of 31st AAAI Conference on Artificial Intelligence, Feb 2017, pp. 376--382.
[ | full paper ]

#### Abstract

Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable real-world impact. But making the most of this new paradigm requires a rethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We analytically compare four preference elicitation methods --- knapsack votes, rankings by value or value for money, and threshold approval votes --- through the lens of implicit utilitarian voting, and find that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections.

• U1
Iterative Methods for Ranking Students using Noisy Questions
By Gerdus Benadè, Wolfgang Gatterbauer, Nam Ho-Nguyen and R. Ravi. 2017.
[ ]

#### Abstract

We study the problem of ranking students by their abilities, solely based on responses to student-sourced multiple-choice questions. This addresses the crucial problem of scaling automatic assessment of students to very large class sizes. Existing methods assume student responses obey a parameterized model, were designed for situations with trusted questions and may not be scalable. Furthermore, we observe empirically that the running time is quadratic in the number of students. In this paper, we define an axiomatic framework for robust ranking algorithms, as well as a new model for simulating ill-posed questions. We marry ideas from work in truth discovery with properties from IRT to devise several new algorithms with strong axiomatic guarantees and linear scalability. We prove that translation invariant and anti-symmetric ranking methods are not affected by ill-posed questions, and that our new methods satisfy these properties. Computational experiments demonstrate the viability of these algorithms.

• C1
The Enumeration of k-sets of Mutually Orthogonal Latin Squares
By Gerdus Benadè, Alewyn Burger and Jan van Vuuren.
ORSSA-2013: Proc. of 42nd Annual Conference of ORSSA, Stellenbosch, South Africa: pp. 40-49.
[ | paper ]

#### Abstract

Latin squares and sets of k mutually orthogonal Latin squares (k-MOLS) have application to various scheduling problems, from providing effective ways to access parallel memory structures to scheduling transmissions from sensor arrays. MOLS also play an important role in sports tournament scheduling where every structurally different MOLS provides the scheduler with an additional degree of freedom. The existence of 3-MOLS have been resolved for all orders of Latin squares, except for order 10. We consider a backtracking algorithm for the enumeration of structurally different MOLS which partitions the search space in such a way that it is possible to estimate bounds for the enumeration of higher order MOLS. A contribution towards the celebrated question of the existence of a 2-MOLS of order 10 is made by investigating the feasibility of using this algorithm in conjunction with specific computing paradigms in search of such a design.

• J1
Non-Negative Matrix Factorization for Learning Alignment-Specific Models of Protein Evolution
By Ben Murrell, Thomas Weighill, Jan Buys, Robert Ketteringham, Sasha Moola, Gerdus Benadè, Lise du Buisson, Daniel Kaliski, Tristan Hands and Konrad Scheffler.
PLoS ONE: 6 (12) e28898. doi:10.1371/journal.pone.0028898.
[ | paper ]

#### Abstract

Models of protein evolution currently come in two flavors: generalist and specialist. Generalist models adopt a one-size-fits-all approach, where a single model is estimated from a number of different protein alignments. Specialist models can be estimated when a large quantity of data are available for a single organism or gene, and are intended for use on that organism or gene only. Unsurprisingly, specialist models outperform generalist models, but in most instances there simply are not enough data available to estimate them. We propose a method for estimating alignment-specific models of protein evolution in which the complexity of the model is adapted to suit the richness of the data. Our method uses non-negative matrix factorization (NNMF) to learn a set of basis matrices from a general dataset containing a large number of alignments of different proteins, thus capturing the dimensions of important variation. It then learns a set of weights that are specific to the organism or gene of interest and for which only a smaller dataset is available. Thus the alignment-specific model is obtained as a weighted sum of the basis matrices. Having been constrained to vary along only as many dimensions as the data justify, the model has far fewer parameters than would be required to estimate a specialist model. We show that our NNMF procedure produces models that outperform existing methods on all but one of 50 test alignments. The basis matrices we obtain confirm the expectation that amino acid properties tend to be conserved, and allow us to quantify, on specific alignments, how the strength of conservation varies across different properties. We also apply our new models to phylogeny inference and show that the resulting phylogenies are different from, and have improved likelihood over, those inferred under standard models.

• T1
A Distributed System for Enumerating Main Classes of Mutually Orthogonal Latin Squares