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

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

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

Margin of Victory in Tournaments: Structural and Experimental Results

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Brill, Markus Schmidt-Kraepelin, Ulrike Suksompong, Warut Research Group Efficient Algorithms TU Berlin Germany School of Computing National University of Singapore Singapore

Tournament solutions are standard tools for identifying winners based on pairwise comparisons between competing alternatives. The recently studied notion of margin of victory (MoV) offers a general method for refining the winner set of any given tournament solution, thereby increasing the discriminative power of the solution. In this paper, we reveal a number of structural insights on the MoV by investigating fundamental properties such as monotonicity and consistency with respect to the covering relation. Furthermore, we provide experimental evidence on the extent to which the MoV notion refines winner sets in tournaments generated according to various stochastic models. Copyright © 2020, The Authors. All rights reserved.

关键词： Stochastic models

On Mechanism Design without Payments for Throughput Maximization

学校读者我要写书评

暂无评论

On Mechanism Design without Payments for Throughput Maximiza...

IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies

作者： T. Moscibroda S. Schmid Systems & Networking Research Group Microsoft Research Limited Redmond USA Efficient Algorithms Technical University Munich Munich Germany

ISBN: (纸本)9781424435128

It is well-known that the overall efficiency of a distributed system can suffer if the participating entities seek to maximize their individual performance. Consequently, mechanisms have been designed that force the participants to behave more cooperatively. Most of these game-theoretic solutions rely on payments between participants. Unfortunately, such payments are often cumbersome to implement in practice, especially in dynamic networks and where transaction costs are high. In this paper, we investigate the potential of mechanisms which work without payments. We consider the problem of throughput maximization in multi-channel environments and shed light onto the throughput increase that can be achieved with and without payments. We introduce and analyze two different concepts: the worst-case leverage where we assume that players end up in the worst rational strategy profile, and the average-case leverage where player select a random non-dominated strategy. Our theoretical insights are complemented by simulations.

关键词： Throughput Communications Society Algorithm design and analysis USA Councils Costs Government Finance Large-scale systems Spread spectrum communication Wireless networks

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

Spatial Voting with Incomplete Voter Information

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Imber, Aviram Israel, Jonas Brill, Markus Shachnai, Hadas Kimelfeld, Benny Technion - Israel Institute of Technology Haifa Israel Research Group Efficient Algorithms TU Berlin Germany Department of Computer Science University of Warwick United Kingdom

We consider spatial voting where candidates are located in the Euclidean d-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions. © 2023, CC BY.

关键词：

Approval-Based Committee Voting under Incomplete Information

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Imber, Aviram Israel, Jonas Brill, Markus Kimelfeld, Benny Technion – Israel Institute of Technology Haifa Israel Research Group Efficient Algorithms TU Berlin Germany Department of Computer Science University of Warwick United Kingdom

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved, disapproved, and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin–Courant. These problems include determining whether a given set of candidates is a possible or necessary winning committee and whether a given candidate is possibly or necessarily a member of the winning committee. We also consider proportional representation axioms and the problem of deciding whether a given committee is possibly or necessarily representative. Copyright © 2021, The Authors. All rights reserved.

关键词：