I am a Ph.D. student in Operations Research in the Tepper School of Business at Carnegie Mellon University. I am interested in discrete optimization and computational social choice, and fortunate to work with Ariel D. Procaccia, John Hooker and R. Ravi.

In the summer of 2017 I had the opportunity to work in the supply chain optimization technologies (SCOT) team at Amazon with Andrea Qualizza.

Before coming to CMU I completed an M.Sc. degree under Jan van Vuuren and Alewyn Burger at Stellenbosch University in South Africa.

My CV can be found here.

Working papers

• W3
How to Make Envy Vanish Over Time
By Gerdus Benadè, Aleks Kazachkov, Ariel D. Procaccia and Alex Psomas.
Under review (Feb 2018).
[ | paper ]

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.

• W2
Low-distortion Rankings from Highly Opaque Preferences
By Gerdus Benadè, Ariel D. Procaccia, and Mingda Qiao.
Under review (Jan 2018).
[ | 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.

• W1
Iterative Methods for Ranking Students using Noisy Questions
By Gerdus Benadè, Wolfgang Gatterbauer, Nam Ho-Nguyen and R. Ravi.
Under review (Last update: Feb 2018)
[ | full paper]

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.

Publications

• J2
Optimization Bounds from the Branching Dual
By Gerdus Benadè and John Hooker.
To appear in INFORMS Journal on Computing (Jan 2018).
[ | 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.

• 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 ]

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.

• 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
By Gerdus Benadè.
Master's Thesis, Stellenbosch University. [ thesis ]