Gerdus Benade - Homepage

Working papers

Stability, Fairness and the Pursuit of Happiness
By Gerdus Benadè and Nachiketa Sahoo.
Preliminary versions presented at WITS-22, SCECR-23.
[ | paper | ssrn ]

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.

Ranked Choice Voting and Proportional 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 effectiveness depending on local circumstances.

Publications

Abstract

We study the problem of fairly allocating $m$ indivisible items among $n$ agents. Envy-free allocations, in which each agent prefers her bundle to the bundle of every other agent, need not exist in the worst case. However, when agents have additive preferences and the value $v_{i,j}$ of agent $i$ for item $j$ is drawn independently from a distribution $D_i$, envy-free allocations exist with high probability when $m \in \Omega( n \log n / \log \log n )$.
In this paper, we study the existence of envy-free allocations under stochastic valuations far beyond the additive setting. We introduce a new stochastic model in which each agent's valuation is sampled by first fixing a worst-case function, and then drawing a uniformly random renaming of the items, independently for each agent. This strictly generalizes known settings; for example, $v_{i,j} \sim D_i$ may be seen as picking a random (instead of a worst-case) additive function before renaming.
We prove that random renaming is sufficient to ensure that envy-free allocations exist with high probability in very general settings. When valuations are non-negative and ``order-consistent,'' a valuation class that generalizes additive, budget-additive, unit-demand, and single-minded agents, SD-envy-free allocations (a stronger notion of fairness than envy-freeness) exist for $m \in \omega(n^2)$ when $n$ divides $m$, and SD-EFX allocations exist for all $m \in \omega(n^2)$. The dependence on $n$ is tight, that is, for $m \in O(n^2)$ envy-free allocations don't exist with constant probability. For the case of arbitrary valuations (allowing non-monotone, negative, or mixed-manna valuations) and $n=2$ agents, we prove envy-free allocations exist with probability $1 - \Theta(1/m)$ (and this is tight).

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).

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.

22S	BA 476: Machine Learning for Business Analytics
22S	MK 842: Machine Learning for Business Analytics (winter MBA intensive)
21F	IS 883: Synthesizing Digital Efforts to Deliver Better Outcomes, co-taught with Gene Cornfield.
21F	BA 476: Machine Learning for Business Analytics
21S	BA 476: Machine Learning for Business Analytics
21S	MK 842: Machine Learning for Business Analytics (winter MBA intensive)
20F	IS 883: Synthesizing Digital Efforts to Deliver Better Outcomes, co-taught with Gene Cornfield. (New cloud computing component!)
20F	BA 476: Machine Learning for Business Analytics
20S	MK 842: Machine Learning for Business Analytics (winter MBA intensive)
20S	MK 476: Machine Learning for Business Analytics

22S

BA 476: Machine Learning for Business Analytics

22S

MK 842: Machine Learning for Business Analytics (winter MBA intensive)

21F

IS 883: Synthesizing Digital Efforts to Deliver Better Outcomes, co-taught with Gene Cornfield.

21F

BA 476: Machine Learning for Business Analytics

21S

BA 476: Machine Learning for Business Analytics

21S

MK 842: Machine Learning for Business Analytics (winter MBA intensive)