Search

Sortition, the random selection of political representatives, is increasingly being used around the world to choose participants of deliberative processes like Citizens' Assemblies. Motivated by sortition's practical importance, there has been a recent flurry of research on sortition algorithms, whose task it is to select a panel from among a pool of volunteers. This panel must satisfy quotas enforcing representation of key population subgroups. Past work has contributed an algorithmic approach for fulfilling this task while ensuring that volunteers' chances of selection are maximally equal, as measured by any convex equality objective. The question, then, is: which equality objective is the right one? Past work has mainly studied the objectives Minimax and Leximin, which respectively minimize the maximum and maximize the minimum chance of selection given to any volunteer. Recent work showed that both of these objectives have key weaknesses: Minimax is highly robust to manipulation but is arbitrarily unfair; oppositely, Leximin is highly fair but arbitrarily manipulable. In light of this gap, we propose a new equality objective, Goldilocks, that aims to achieve these ideals simultaneously by ensuring that no volunteer receives too little or too much chance of selection. We theoretically bound the extent to which Goldilocks achieves these ideals, finding that in an important sense, Goldilocks recovers among the best available solutions in a given instance. We then extend our bounds to the case where the output of Goldilocks is transformed to achieve a third goal, Transparency. Our empirical analysis of Goldilocks in real data is even more promising: we find that this objective achieves nearly instance-optimal minimum and maximum selection probabilities simultaneously in most real instances -- an outcome not even guaranteed to be possible for any algorithm.

A common explanation for negative user impacts of content recommender systems is misalignment between the platform's objective and user welfare. In this work, we show that misalignment in the platform's objective is not the only potential cause of unintended impacts on users: even when the platform's objective is fully aligned with user welfare, the platform's learning algorithm can induce negative downstream impacts on users. The source of these user impacts is that different pieces of content may generate observable user reactions (feedback information) at different rates; these feedback rates may correlate with content properties, such as controversiality or demographic similarity of the creator, that affect the user experience. Since differences in feedback rates can impact how often the learning algorithm engages with different content, the learning algorithm may inadvertently promote content with certain such properties. Using the multi-armed bandit framework with probabilistic feedback, we examine the relationship between feedback rates and a learning algorithm's engagement with individual arms for different no-regret algorithms. We prove that no-regret algorithms can exhibit a wide range of dependencies: if the feedback rate of an arm increases, some no-regret algorithms engage with the arm more, some no-regret algorithms engage with the arm less, and other no-regret algorithms engage with the arm approximately the same number of times. From a platform design perspective, our results highlight the importance of looking beyond regret when measuring an algorithm's performance, and assessing the nature of a learning algorithm's engagement with different types of content as well as their resulting downstream impacts., Comment: Authors listed in alphabetical order. Accept as poster at AISTATS 2024

A key promise of democratic voting is that, by accounting for all constituents' preferences, it produces decisions that benefit the constituency overall. It is alarming, then, that all deterministic voting rules have unbounded distortion: all such rules - even under reasonable conditions - will sometimes select outcomes that yield essentially no value for constituents. In this paper, we show that this problem is mitigated by voters being public-spirited: that is, when deciding how to rank alternatives, voters weigh the common good in addition to their own interests. We first generalize the standard voting model to capture this public-spirited voting behavior. In this model, we show that public-spirited voting can substantially - and in some senses, monotonically - reduce the distortion of several voting rules. Notably, these results include the finding that if voters are at all public-spirited, some voting rules have constant distortion in the number of alternatives. Further, we demonstrate that these benefits are robust to adversarial conditions likely to exist in practice. Taken together, our results suggest an implementable approach to improving the welfare outcomes of elections: democratic deliberation, an already-mainstream practice that is believed to increase voters' public spirit.

Computer science (CS) has historically struggled with issues related to diversity, equity, and inclusion (DEI). Based on how these issues were affecting PhD students in our department, we identified required DEI education for PhD students as a potentially high-impact approach to improving the PhD student experience in our program. Given that no existing curriculum met the desired criteria, we (PhD students) - along with many others at our school - developed and implemented CS-JEDI: Justice, Equity, Diversity, and Inclusion in Computer Science. CS-JEDI is a 6-week DEI curriculum that is now taken by all first-year PhD students in our department. This paper covers CS-JEDI's motivation and goals; describes how its evidence-based curriculum is tailored to these goals and to the CS PhD context; and gives a data-driven evaluation of the extent to which CS-JEDI's first offering, in Spring 2022, achieved these goals.

A canonical problem in social choice is how to aggregate ranked votes: given $n$ voters' rankings over $m$ candidates, what voting rule $f$ should we use to aggregate these votes into a single winner? One standard method for comparing voting rules is by their satisfaction of axioms - properties that we want a "reasonable" rule to satisfy. Unfortunately, this approach leads to several impossibilities: no voting rule can simultaneously satisfy all the properties we want, at least in the worst case over all possible inputs. Motivated by this, we consider a relaxation of these worst case requirements. We do so using a "smoothed" model of social choice, where votes are perturbed with small amounts of noise. If, no matter which input profile we start with, the probability (post-noise) of an axiom being satisfied is large, we will consider the axiom as good as satisfied - called "smoothed-satisfied" - even if it may be violated in the worst case. Our model is a mild restriction of Lirong Xia's, and corresponds closely to that in Spielman and Teng's original work on smoothed analysis. Much work has been done so far in several papers by Xia on axiom satisfaction under such noise. In our paper, we aim to give a more cohesive overview on when smoothed analysis of social choice is useful. Within our model, we give simple sufficient conditions for smoothed-satisfaction or smoothed-violation of several previously-unstudied axioms and paradoxes, plus many of those studied by Xia. We then observe that, in a practically important subclass of noise models, although convergence eventually occurs, known rates may require an extremely large number of voters. Motivated by this, we prove bounds specifically within a canonical noise model from this subclass - the Mallows model. Here, we present a more nuanced picture on exactly when smoothed analysis can help.

Sortition is a political system in which decisions are made by panels of randomly selected citizens. The process for selecting a sortition panel is traditionally thought of as uniform sampling without replacement, which has strong fairness properties. In practice, however, sampling without replacement is not possible since only a fraction of agents is willing to participate in a panel when invited, and different demographic groups participate at different rates. In order to still produce panels whose composition resembles that of the population, we develop a sampling algorithm that restores close-to-equal representation probabilities for all agents while satisfying meaningful demographic quotas. As part of its input, our algorithm requires probabilities indicating how likely each volunteer in the pool was to participate. Since these participation probabilities are not directly observable, we show how to learn them, and demonstrate our approach using data on a real sortition panel combined with information on the general population in the form of publicly available survey data., Comment: Code is located at https://github.com/pgoelz/endtoend