Search

In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make betterinformed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations. For problems such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and Short Cycle Packing, we design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms. Our results extend to problems like k-Constrained Resource Allocation, General Graph k-Matching, and k-Clique Packing, when k is restricted to be any constant. [ABSTRACT FROM AUTHOR]

We study the distributed facility location problem , where a set of agents with positions on the line of real numbers are partitioned into disjoint districts, and the goal is to choose a point to satisfy certain criteria, such as optimize an objective function or avoid strategic behavior. A mechanism in our distributed setting works in two steps: For each district it chooses a point that is representative of the positions reported by the agents in the district, and then decides one of these representative points as the final output. We consider two classes of mechanisms: Unrestricted mechanisms which assume that the agents directly provide their true positions as input, and strategyproof mechanisms which deal with strategic agents and aim to incentivize them to truthfully report their positions. For both classes, we show tight bounds on the best possible approximation in terms of several minimization social objectives, including the well-known average social cost (average total distance of agents from the chosen point) and max cost (maximum distance among all agents from the chosen point), as well as other fairness-inspired objectives that are tailor-made for the distributed setting, in particular, the max-of-average and the average-of-max. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, almost all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data. [ABSTRACT FROM AUTHOR]

Aggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitarian social choice setting, where the agents have explicit numerical values for the alternatives, yet they only report their linear orderings over them. To compare different aggregation mechanisms, Procaccia and Rosenschein introduced the notion of distortion , which quantifies the inefficiency of using only ordinal information when trying to maximize the social welfare, i.e., the sum of the underlying values of the agents for the chosen outcome. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents over the alternatives. In this paper, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds and, in many cases, outperform the best-known randomized ordinal mechanisms. We paint an almost complete picture of the number of queries required by deterministic mechanisms to achieve specific distortion bounds. [ABSTRACT FROM AUTHOR]