Fair Enough Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
Journal of the ACM,
03/2018, Letnik:
65, Številka:
2
Journal Article
Recenzirano
We consider the problem of fairly allocating indivisible goods, focusing on a recently introduced notion of fairness called
maximin share guarantee
: each player’s value for his allocation should be ...at least as high as what he can guarantee by dividing the items into as many bundles as there are players and receiving his least desirable bundle. Assuming additive valuation functions, we show that such allocations may not exist, but allocations guaranteeing each player 2/3 of the above value always exist. These theoretical results have direct practical implications.
Globally, there has been a recent surge in 'citizens' assemblies'
, which are a form of civic participation in which a panel of randomly selected constituents contributes to questions of policy. The ...random process for selecting this panel should satisfy two properties. First, it must produce a panel that is representative of the population. Second, in the spirit of democratic equality, individuals would ideally be selected to serve on this panel with equal probability
. However, in practice these desiderata are in tension owing to differential participation rates across subpopulations
. Here we apply ideas from fair division to develop selection algorithms that satisfy the two desiderata simultaneously to the greatest possible extent: our selection algorithms choose representative panels while selecting individuals with probabilities as close to equal as mathematically possible, for many metrics of 'closeness to equality'. Our implementation of one such algorithm has already been used to select more than 40 citizens' assemblies around the world. As we demonstrate using data from ten citizens' assemblies, adopting our algorithm over a benchmark representing the previous state of the art leads to substantially fairer selection probabilities. By contributing a fairer, more principled and deployable algorithm, our work puts the practice of sortition on firmer foundations. Moreover, our work establishes citizens' assemblies as a domain in which insights from the field of fair division can lead to high-impact applications.
We adopt a utilitarian perspective on social choice, assuming that agents have (possibly latent) utility functions over some space of alternatives. For many reasons one might consider mechanisms, or ...social choice functions, that only have access to the ordinal rankings of alternatives by the individual agents rather than their utility functions. In this context, one possible objective for a social choice function is the maximization of (expected) social welfare relative to the information contained in these rankings. We study such optimal social choice functions under three different models, and underscore the important role played by scoring functions. In our worst-case model, no assumptions are made about the underlying distribution and we analyze the worst-case distortion—or degree to which the selected alternative does not maximize social welfare—of optimal (randomized) social choice functions. In our average-case model, we derive optimal functions under neutral (or impartial culture) probabilistic models. Finally, a very general learning-theoretic model allows for the computation of optimal social choice functions (i.e., ones that maximize expected social welfare) under arbitrary, sampleable distributions. In the latter case, we provide both algorithms and sample complexity results for the class of scoring functions, and further validate the approach empirically.
In cooperative multiagent systems an alternative that maximizes the
social welfare—the sum of utilities—can only be selected if each agent reports its full utility function. This may be infeasible in ...environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006)
13 have introduced the concept of
distortion to quantify this gap.
In this paper, we present the notion of
embeddings into voting rules: functions that receive an agentʼs utility function and return the agentʼs vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.
Subset Selection Via Implicit Utilitarian Voting Caragiannis, Ioannis; Nath, Swaprava; Procaccia, Ariel D. ...
The Journal of artificial intelligence research,
01/2017, Letnik:
58
Journal Article
Recenzirano
Odprti dostop
How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach -- which we refer to as implicit utilitarian voting -- assumes ...that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of RoboVote.org, a not-for-profit website that helps users make group decisions via AI-driven voting methods.
The Unreasonable Fairness of Maximum Nash Welfare Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé ...
ACM transactions on economics and computation,
08/2019, Letnik:
7, Številka:
3
Journal Article
Recenzirano
Odprti dostop
The
maximum Nash welfare (MNW)
solution—which selects an allocation that maximizes the product of utilities—is known to provide outstanding fairness guarantees when allocating divisible goods. And ...while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy-free up to one good—a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and—even more so—in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation and demonstrate that it scales well on real data. These results establish MNW as a compelling solution for allocating indivisible goods and underlie its deployment on a popular fair-division website.
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 rethinking 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 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.
This paper was accepted by Yan Chen, decision analysis.
Failure-Aware Kidney Exchange Dickerson, John P; Procaccia, Ariel D; Sandholm, Tuomas
Management science,
04/2019, Letnik:
65, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Algorithmic matches in fielded kidney exchanges do not typically result in an actual transplant. We address the problem of cycles and chains in proposed matches failing
after
the matching algorithm ...has committed to them. We show that failure-aware kidney exchange can significantly increase the expected number of lives saved (i) in theory, on random graph models; (ii) on real data from kidney exchange match runs between 2010 and 2014; and (iii) on synthetic data generated via a model of dynamic kidney exchange. This gain is robust to uncertainty over the true underlying failure rate. We design a branch-and-price–based optimal clearing algorithm specifically for the probabilistic exchange clearing problem and show that this new solver scales well on large simulated data, unlike prior clearing algorithms. Finally, we show that failure-aware matching can increase overall system efficiency and simultaneously increase the expected number of transplants to
highly sensitized
patients, in both static and dynamic models.
This paper was accepted by Yinyu Ye, optimization.
We present two models of how people form beliefs that are based on machine learning theory. We illustrate how these models give insight into observed human phenomena by showing how polarized beliefs ...can arise even when people are exposed to almost identical sources of information. In our first model, people form beliefs that are deterministic functions that best fit their past data (training sets). In that model, their inability to form probabilistic beliefs can lead people to have opposing views even if their data are drawn from distributions that only slightly disagree. In the second model, people pay a cost that is increasing in the complexity of the function that represents their beliefs. In this second model, even with large training sets drawn from exactly the same distribution, agents can disagree substantially because they simplify the world along different dimensions. We discuss what these models of belief formation suggest for improving people's accuracy and agreement.
PDF
