Participatory budgeting (PB) is an increasingly popular tool for democratically allocating limited budgets to public-good projects. In PB, constituents vote on their preferred projects via ballots, and then an aggregation rule selects a set of projects whose total cost fits within the budget. Recent work studies how to design PB ballots and aggregation rules that yield low-distortion outcomes (informally, outcomes with high social welfare). Existing distortion bounds, however, rely on strong assumptions that restrict voters' latent utilities. We prove that low distortion PB outcomes can be achieved by dropping these assumptions and instead leveraging the established idea that voters can be public-spirited: they may consider others' interests alongside their own when voting. Flanigan, Procaccia, and Wang (2023) prove that in public-spirited single-winner voting (the special case of PB where exactly one project can be funded) with ranking ballots, deterministic aggregation rules can achieve constant distortion. Our first contribution is to extend this analysis to PB; there, we prove that the best distortion permitted by deterministic rules with ranking ballots grows linearly in the number of projects. We find that this impossibility --- a problem in practice, where m is often large --- holds for other known ballots as well. Our second contribution is the design of a new PB ballot format that breaks this linear distortion barrier. This ballot asks voters to rank a predetermined set of entire feasible bundles of projects. We design multiple protocols for implementing these ballots, each striking a different trade-off between the number of bundles voters must rank and the distortion: with m bundles, we get sublinear distortion; with polynomial bundles, we get logarithmic distortion; and with pseudopolynomial bundles, we get constant distortion.

Citizens' assemblies are an increasingly influential form of deliberative democracy, where randomly selected people discuss policy questions. The legitimacy of these assemblies hinges on their representation of the broader population, but participant dropout often leads to an unbalanced composition. In practice, dropouts are replaced by preselected alternates, but existing methods do not address how to choose these alternates. To address this gap, we introduce an optimization framework for alternate selection. Our algorithmic approach, which leverages learning-theoretic machinery, estimates dropout probabilities using historical data and selects alternates to minimize expected misrepresentation. Our theoretical bounds provide guarantees on sample complexity (with implications for computational efficiency) and on loss due to dropout probability mis-estimation. Empirical evaluation using real-world data demonstrates that, compared to the status quo, our method significantly improves representation while requiring fewer alternates.

Among the recent work on designing algorithms for selecting citizens' assembly participants, one key property of these algorithms has not yet been studied: their manipulability. Strategic manipulation is a concern because these algorithms must satisfy representation constraints according to volunteers' self-reported features; misreporting these features could thereby increase a volunteer's chance of being selected, decrease someone else's chance, and/or increase the expected number of seats given to their group. Strikingly, we show that Leximin — an algorithm that is widely used for its fairness — is highly manipulable in this way. We then introduce a new class of selection algorithms that use Lp norms as objective functions. We show that the manipulability of the Lp-based algorithm decreases in O(1/n^(1-1/p)) as the number of volunteers n grows, approaching the optimal rate of O(1/n) as p approaches infinity. These theoretical results are confirmed via experiments in eight real-world datasets.

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.

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 the practical importance of sortition, there has been a recent flurry of computer science research on sortition algorithms, whose task it is to randomly select a panel that satisfies several quotas enforcing representation of key population subgroups. This existing work has contributed an algorithmic approach for sampling a quota-satisfying set of willing participants while ensuring their 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 willing participant. Recent work showed that both of these objectives have key weaknesses: Minimax is highly robust to manipulation, but it is arbitrarily unfair; and oppositely, Leximin is highly fair but arbitrarily manipulable.

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 (the Carnegie Mellon University CS 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)-alongside many members of the CMU community-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 key promise of voting is that, by accounting for all constituents' preferences, it produces decisions that benefit society overall. It is alarming, then, that all deterministic voting rules have unbounded distortion (i.e., arbitrarily suboptimal social welfare). Existing work usually circumvents this stark impossibility by assuming restrictions on voters' possible latent utilities [Anshelevich et al. 2021]; however, it is not clear whether such assumptions reliably hold in practice, because voters' utilities are, to a large degree, inherent.

Sortition is an age-old democratic paradigm, widely manifested today through the random selection of citizens' assemblies. Recently-deployed algorithms select assemblies \textit{maximally fairly}, meaning that subject to demographic quotas, they give all potential participants as equal a chance as possible of being chosen. While these fairness gains can bolster the legitimacy of citizens' assemblies and facilitate their uptake, existing algorithms remain limited by their lack of transparency. To overcome this hurdle, in this work we focus on panel selection by uniform lottery, which is easy to realize in an observable way. By this approach, the final assembly is selected by uniformly sampling some pre-selected set of $m$ possible assemblies.We provide theoretical guarantees on the fairness attainable via this type of uniform lottery, as compared to the existing maximally fair but opaque algorithms, for two different fairness objectives. We complement these results with experiments on real-world instances that demonstrate the viability of the uniform lottery approach as a method of selecting assemblies both fairly and transparently.

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.

Online Social Network (OSN) Users’ demand to increase their account popularity has driven the creation of an underground ecosystem that provides services or techniques to help users manipulate content curation algorithms. One method of subversion that has recently emerged occurs when users form groups, called pods, to facilitate reciprocity abuse, where each member reciprocally interacts with content posted by other members of the group. We collect 1.8 million Instagram posts that were posted in pods hosted on Telegram. We first summarize the properties of these pods and how they are used, uncovering that they are easily discoverable by Google search and have a low barrier to entry. We then create two machine learning models for detecting Instagram posts that have gained interaction through two different kinds of pods, achieving 0.91 and 0.94 AUC, respectively. Finally, we find that pods are effective tools for increasing users’ Instagram popularity, we estimate that pod utilization leads to a significantly increased level of likely organic comment interaction on users’ subsequent posts.