检索结果-内蒙古大学图书馆

Can a few decide for many? the metric distortion of sortition 24

学校读者我要写书评

暂无评论

Can a few decide for many? the metric distortion of sortitio...

Proceedings of the 41st International Conference on Machine Learning

作者： Ioannis Caragiannis Evi Micha Jannik Peters Department of Computer Science Aarhus University Aarhus Denmark Computer Science Harvard University Cambridge Research Group Efficient Algorithms Faculty IV - Electrical Engineering and Computer Science TU Berlin Berlin Germany

Recent works have studied the design of algorithms for selecting representative sortition panels. However, the most central question remains unaddressed: Do these panels reflect the entire population's opinion? We present a positive answer by adopting the concept of metric distortion from computational social choice, which aims to quantify how much a panel's decision aligns with the ideal decision of the population when preferences and agents lie on a metric space. We show that uniform selection needs only logarithmically many agents in terms of the number of alternatives to achieve almost optimal distortion. We also show that Fair Greedy Capture, a selection algorithm introduced recently by Ebadian & Micha (2024), matches uniform selection's guarantees of almost optimal distortion and also achieves constant ex-post distortion, ensuring a "best of both worlds" performance.

关键词：

Online elicitation of necessarily optimal matchings

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Peters, Jannik Research Group Efficient Algorithms TU Berlin Germany

In this paper, we study the problem of eliciting preferences of agents in the house allocation model. For this we build on a recent model of Hosseini et al. (2021)[AAAI’21] and focus on the task of eliciting preferences to find matchings which are necessarily optimal, i.e., optimal under all possible completions of the elicited preferences. In particular, we follow the approach of Hosseini et al. (2021) and investigate the elicitation of necessarily Pareto optimal (NPO) and necessarily rank-maximal (NRM) matchings. Most importantly, we answer their open question and give an online algorithm for eliciting an NRM matching in the next-best query model which is 3/2 -competitive, i.e., it takes at most 3/2 as many queries as an optimal algorithm. Besides this, we extend this field of research by introducing two new natural models of elicitation and by studying both the complexity of determining whether a necessarily optimal matching exists in them, and by giving online algorithms for these models. © 2021, CC BY.

关键词： Pareto principle

Dynamic proportional rankings

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Israel, Jonas Brill, Markus Efficient Algorithms Research Group Technische Universität Berlin

Proportional ranking rules aggregate approval-style preferences of agents into a collective ranking such that groups of agents with similar preferences are adequately represented. Motivated by the application of live Q&A platforms, where submitted questions need to be ranked based on the interests of the audience, we study a dynamic extension of the proportional rankings setting. In our setting, the goal is to maintain the proportionality of a ranking when alternatives (i.e., questions)—not necessarily from the top of the ranking—get selected sequentially. We propose generalizations of well-known aggregation rules to this setting and study their monotonicity and proportionality properties. We also evaluate the performance of these rules experimentally, using realistic probabilistic assumptions on the selection procedure. Copyright © 2021, The Authors. All rights reserved.

关键词： Machine learning

Can a Few Decide for Many? The Metric Distortion of Sortition

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Caragiannis, Ioannis Micha, Evi Peters, Jannik Department of Computer Science Aarhus University Aarhus Denmark Computer Science Harvard University Cambridge United States Research Group Efficient Algorithms Faculty IV - Electrical Engineering and Computer Science TU Berlin Berlin Germany

Recent works have studied the design of algorithms for selecting representative sortition panels. However, the most central question remains unaddressed: Do these panels reflect the entire population's opinion? We present a positive answer by adopting the concept of metric distortion from computational social choice, which aims to quantify how much a panel's decision aligns with the ideal decision of the population when preferences and agents lie on a metric space. We show that uniform selection needs only logarithmically many agents in terms of the number of alternatives to achieve almost optimal distortion. We also show that Fair Greedy Capture, a selection algorithm introduced recently by Ebadian & Micha (2024), matches uniformselection's guarantees of almost optimal distortion and also achieves constant ex-post distortion, ensuring a "best of both worlds" performance. © 2024, CC BY.

关键词：

Selecting Matchings via Multiwinner Voting: How Structure Defeats a Large Candidate Space

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Boehmer, Niclas Brill, Markus Schmidt-Kraepelin, Ulrike Research Group Algorithmics and Computational Complexity TU Berlin Germany Research Group Efficient Algorithms TU Berlin Germany

Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone’s preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of matchings of the agents, and agents’ preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting. Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and its sequential variant (seq-PAV), which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space. Copyright © 2021, The Authors. All rights reserved.

关键词： Polynomial approximation

Strategyproofness and Proportionality in Party-Approval Multiwinner Elections

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Delemazure, Théo Demeulemeester, Tom Eberl, Manuel Israel, Jonas Lederer, Patrick Paris Dauphine University PSL CNRS France Research Center for Operations Research & Statistics KU Leuven Belgium Computational Logic Group University of Innsbruck Austria Research Group Efficient Algorithms Technische Universität Berlin Germany Technical University of Munich Germany

In party-approval multiwinner elections the goal is to allocate the seats of a fixed-size committee to parties based on the approval ballots of the voters over the parties. In particular, each voter can approve multiple parties and each party can be assigned multiple seats. Two central requirements in this setting are proportional representation and strategyproofness. Intuitively, proportional representation requires that every sufficiently large group of voters with similar preferences is represented in the committee. Strategyproofness demands that no voter can benefit by misreporting her true preferences. We show that these two axioms are incompatible for anonymous party-approval multiwinner voting rules, thus proving a far-reaching impossibility theorem. The proof of this result is obtained by formulating the problem in propositional logic and then letting a SAT solver show that the formula is unsatisfiable. Additionally, we demonstrate how to circumvent this impossibility by considering a weakening of strategyproofness which requires that only voters who do not approve any elected party cannot manipulate. While most common voting rules fail even this weak notion of strategyproofness, we characterize Chamberlin–Courant approval voting within the class of Thiele rules based on this strategyproofness notion. Copyright © 2022, The Authors. All rights reserved.

关键词： Formal logic

Dueling bandits with team comparisons

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Cohen, Lee Schmidt-Kraepelin, Ulrike Mansour, Yishay Blavatnik School of Computer Science Tel Aviv University Research Group Efficient Algorithms Technische Universität Berlin Google Research

We introduce the dueling teams problem, a new online-learning setting in which the learner observes noisy comparisons of disjoint pairs of k-sized teams from a universe of n players. The goal of the learner is to minimize the number of duels required to identify, with high probability, a Condorcet winning team, i.e., a team which wins against any other disjoint team (with probability at least 1/2). Noisy comparisons are linked to a total order on the teams. We formalize our model by building upon the dueling bandits setting [23] and provide several algorithms, both for stochastic and deterministic settings. For the stochastic setting, we provide a reduction to the classical dueling bandits setting, yielding an algorithm that identifies a Condorcet winning team within O((n + k log(k)) max(log ∆log2nlog k)) duels, where ∆ is a gap parameter. For deterministic feedback, we additionally present a gap-independent algorithm that identifies a Condorcet winning team within O(nk log(k) + k5) duels. Copyright © 2021, The Authors. All rights reserved.

关键词： Stochastic systems

The Maximin Support Method: An Extension of the D’Hondt Method to Approval-Based Multiwinner Elections 35

学校读者我要写书评

暂无评论

The Maximin Support Method: An Extension of the D’Hondt Met...

35th AAAI Conference on Artificial Intelligence, AAAI 2021

作者： Sánchez-Fernández, Luis García, Norberto Fernández Fisteus, Jesús A. Brill, Markus Dept. Telematic Engineering Universidad Carlos III de Madrid LeganésE-28911 Spain Centro Universitario de la Defensa Escuela Naval Militar MarinE-36920 Spain Research Group Efficient Algorithms Technische Universität Berlin BerlinD-10587 Germany

ISBN: (纸本)9781713835974

We propose the maximin support method, a novel extension of the D’Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D’Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relationship between the maximin support method and alternative D’Hondt extensions due to Phragmén. Copyright © 2021, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词：

An Axiomatic Approach to Formalized Responsibility Ascription

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Hiller, Sarah Israel, Jonas Heitzig, Jobst Free University Berlin Institute for Mathematics Berlin Germany Technical University Berlin Efficient Algorithms Research Group Berlin Germany Potsdam Institute for Climate Impact Research Potsdam Germany

A formalized and quantifiable responsibility score is a crucial component in many aspects of the development and application of multi-agent systems and autonomous agents. We can employ it to inform decision making processes based on ethical considerations, as a measure to ensure redundancy that helps us in avoiding system failure, as well as for verifying that autonomous systems remain trustworthy by testing for unwanted responsibility voids in advance. We follow recent proposals to use probabilities as the basis for responsibility ascription in uncertain environments rather than the deterministic causal views employed in much of the previous formal philosophical literature. Using an axiomatic approach we formally evaluate the qualities of (classes of) proposed responsibility functions. To this end, we decompose the computation of the responsibility a group carries for an outcome into the computation of values that we assign to its members for individual decisions leading to that outcome, paired with an appropriate aggregation function. Next, we discuss a number of intuitively desirable properties for each of these contributing functions. We find an incompatibility between axioms determining upper and lower bounds for the values assigned at the member level. Regarding the aggregation from member-level values to group-level responsibility we are able to axiomatically characterise one promising aggregation function. Finally, we present two maximally axiom compliant group-level responsibility measures - one respecting the lower bound axioms at the member level and one respecting the corresponding upper bound axioms. © 2021, CC BY.

关键词： Function evaluation