The distortion of distributed metric social choice Anshelevich, Elliot; Filos-Ratsikas, Aris; Voudouris, Alexandros A.
Artificial intelligence,
July 2022, 2022-07-00, 20220701, Letnik:
308
Journal Article
Recenzirano
Odprti dostop
We consider a social choice setting with agents that are partitioned into disjoint groups, and have metric preferences over a set of alternatives. Our goal is to choose a single alternative aiming to ...optimize various objectives that are functions of the distances between agents and alternatives in the metric space, under the constraint that this choice must be made in a distributed way: The preferences of the agents within each group are first aggregated into a representative alternative for the group, and then these group representatives are aggregated into the final winner. Deciding the winner in such a way naturally leads to loss of efficiency, even when complete information about the metric space is available. We provide a series of (mostly tight) bounds on the distortion of distributed mechanisms for variations of well-known objectives, such as the (average) total cost and the maximum cost, and also for new objectives that are particularly appropriate for this distributed setting and have not been studied before.
Analytic hierarchy process (AHP) is widely used in group decision making (GDM). There are two traditional aggregation methods for the collective preference in AHP-GDM: aggregation of the individual ...judgments (AIJ) and aggregation of the individual priorities (AIP). However, AHP-GDM is sometimes less reliable only under the condition of AIJ and AIP because of the consensus and consistency of the individual pair-wise comparison matrices (PCMs) and prioritization methods. In this paper, we propose aggregation of the nearest consistent matrices (ANCM) with the acceptable consensus in AHP-GDM, simultaneously considering the consensus and consistency of the individual PCMs. ANCM is independent of prioritization methods while complying with the Pareto principal of social choice theory. Moreover, ANCM is easy to program and implement in resolving highly complex group decision making problems. Finally, two numerical examples illustrate the applications and advantages of the proposed ANCM.
We study the problem of fair division when the set of resources contains both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good ...(EF1) cannot be directly applied to this mixed goods setting. In this work, we propose a new fairness notion, envy-freeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents with additive valuations. We also propose efficient algorithms to compute an EFM allocation for two agents with general additive valuations and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-freeness requirement, instead asking for ϵ-envy-freeness for mixed goods (ϵ-EFM), and present an efficient algorithm that finds an ϵ-EFM allocation.
The efficient and fair allocation of limited resources is a classical problem in economics and computer science. In kidney exchanges, a central market maker allocates living kidney donors to patients ...in need of an organ. Patients and donors in kidney exchanges are prioritized using ad-hoc weights decided on by committee and then fed into an allocation algorithm that determines who gets what—and who does not. In this paper, we provide an end-to-end methodology for estimating weights of individual participant profiles in a kidney exchange. We first elicit from human subjects a list of patient attributes they consider acceptable for the purpose of prioritizing patients (e.g., medical characteristics, lifestyle choices, and so on). Then, we ask subjects comparison queries between patient profiles and estimate weights in a principled way from their responses. We show how to use these weights in kidney exchange market clearing algorithms. We then evaluate the impact of the weights in simulations and find that the precise numerical values of the weights we computed matter little, other than the ordering of profiles that they imply. However, compared to not prioritizing patients at all, there is a significant effect, with certain classes of patients being (de)prioritized based on the human-elicited value judgments.
We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are ...further away. In this setting, it is often desirable to select an alternative that minimizes the sum of distances to the voters, i.e., the utilitarian social cost, or other similar measures of social cost. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify an optimal alternative. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of an alternative selected by the rule and that of an optimal alternative. Thus, distortion measures how good a voting rule is at approximating an alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that they form a metric space. The goal of our paper is to quantify the distortion of well-known voting rules. We first establish a lower bound on the distortion of any deterministic voting rule. We then show that the distortion of positional scoring rules cannot be bounded by a constant, and for several popular rules in this family distortion is linear in the number of alternatives. On the other hand, for Copeland and similar rules the distortion is bounded by a factor of 5. These results hold both for the sum of voters' cost and the median voter cost. For Single Transferable Vote (STV), we obtain an upper bound of O(lnm) with respect to the sum of voters' costs, where m is the number of alternatives, as well as a lower bound of Ω(lnm); thus, STV is a reasonable, though not a perfect rule from this perspective. Our results for median voter cost extend to more general objective functions.
Knapsack Voting for Participatory Budgeting Goel, Ashish; Krishnaswamy, Anilesh K.; Sakshuwong, Sukolsak ...
ACM transactions on economics and computation,
08/2019, Letnik:
7, Številka:
2
Journal Article
Recenzirano
Odprti dostop
We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline its drawbacks, and ...introduce a novel scheme tailored to this setting, which we call “Knapsack Voting.” We study its strategic properties—we show that it is strategy-proof under a natural model of utility (a dis-utility given by the ℓ
1
distance between the outcome and the true preference of the voter) and “partially” strategy-proof under general additive utilities. We extend Knapsack Voting to more general settings with revenues, deficits, or surpluses and prove a similar strategy-proofness result. To further demonstrate the applicability of our scheme, we discuss its implementation on the digital voting platform that we have deployed in partnership with the local government bodies in many cities across the nation. From voting data thus collected, we present empirical evidence that Knapsack Voting works well in practice.
Getting Dynamic Implementation to Work Chen, Yi-Chun; Holden, Richard; Kunimoto, Takashi ...
The Journal of political economy,
02/2023, Letnik:
131, Številka:
2
Journal Article
Recenzirano
Odprti dostop
We develop a new class of two-stage mechanisms, which fully implement any social choice function under initial rationalizability in complete information environments. We show theoretically that our ...simultaneous report (SR) mechanisms are robust to small amounts of incomplete information about the state of nature. We also highlight the robustness of the mechanisms to a wide variety of reasoning processes and behavioral assumptions. We show experimentally that an SR mechanism performs well in inducing truth telling in both complete and incomplete information environments and that it can induce efficient investment in a two-sided holdup problem with ex ante investment.
Inspired by impossibility theorems of social choice theory, many democratic theorists have argued that aggregative forms of democracy cannot lend full democratic justification for the collective ...decisions reached. Hence, democratic theorists have turned their attention to deliberative democracy, according to which “outcomes are democratically legitimate if and only if they could be the object of a free and reasoned agreement among equals” (Cohen 1997a, 73). However, relatively little work has been done to offer a formal theory of democratic deliberation. This article helps fill that gap by offering a formal theory of three different modes of democratic deliberation: myopic discussion, constructive discussion, and debate. We show that myopic discussion suffers from indeterminacy of long run outcomes, while constructive discussion and debate are conclusive. Finally, unlike the other two modes of deliberation, debate is path independent and converges to a unique compromise position, irrespective of the initial status quo.
We propose a Condorcet-consistent voting method that we call Split Cycle. Split Cycle belongs to the small family of known voting methods satisfying the anti-vote-splitting criterion of
independence ...of clones
. In this family, only Split Cycle satisfies a new criterion we call
immunity to spoilers
, which concerns adding candidates to elections, as well as the known criteria of
positive involvement
and
negative involvement
, which concern adding voters to elections. Thus, in contrast to other clone-independent methods, Split Cycle mitigates both “spoiler effects” and “strong no show paradoxes.”
The metric distortion of multiwinner voting Caragiannis, Ioannis; Shah, Nisarg; Voudouris, Alexandros A.
Artificial intelligence,
December 2022, 2022-12-00, 20221201, Letnik:
313
Journal Article
Recenzirano
Odprti dostop
We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. The exact distances ...between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a committee of k alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a committee is her distance from the q-th closest alternative in the committee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of k and q: The distortion is unbounded when q⩽k/3, asymptotically linear in the number of agents when k/3<q⩽k/2, and constant when q>k/2.
PDF
