Author name cluster

Magnus Roos

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

AAMAS Conference 2012 Conference Paper

Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation

Nhan-Tam Nguyen
Trung Thanh Nguyen
Magnus Roos
J
ouml; rg Rothe

An important task in multiagent resource allocation, which provides mechanisms to allocate bundles of (indivisible and nonshareable) resources to agents, is to maximize social welfare. We study the computational complexity of exact social welfare optimization by the Nash product, which can be seen as a sensible compromise between the well-known notions of utilitarian and egalitarian social welfare. When utilitiy functions are represented in the bundle or the k-additive form, for k ≥ 3, we prove that the corresponding computational problems are DP-complete (where DP denotes the second level of the boolean hierarchy over NP), thus confirming two conjectures raised by Roos and Rothe [10]. We also study the approximability of social welfare optimization problems.

PDF

ECAI Conference 2012 Conference Paper

The Possible Winner Problem with Uncertain Weights

Dorothea Baumeister
Magnus Roos
Jörg Rothe
Lena Schend
Lirong Xia

The original possible winner problem is: Given an unweighted election with partial preferences and a distinguished candidate c, can the preferences be extended to total ones such that c wins? We introduce a novel variant of this problem in which not some of the voters' preferences are uncertain but some of their weights. Not much has been known previously about the weighted possible winner problem. We present a general framework to study this problem, both for integer and rational weights, with and without upper bounds on the total weight to be distributed, and with and without ranges to choose the weights from. We study the complexity of these problems for important voting systems such as scoring rules, Copeland, ranked pairs, plurality with runoff, and (simplified) Bucklin and fall-back voting.

Details

AAMAS Conference 2011 Conference Paper

( PcWNA ) problem, which asks, given an election with strict preferences over the candidates, is it possible to make a designated candidate win the election by adding a limited number of new candidates to the election? In the case of unweighted voters we show NP-completeness of PcWNA for a broad class of pure scoring rules. We will also briefly study the case of weighted voters. The second type of possible winner problem we study is Possible Winner/co-Winner under Uncertain Voting System ( PWUVS and PcWUVS ). Here, uncertainty is present not in the votes but in the election rule itself. For example, PcWUVS is the problem of whether, given a set C of candidates, a list of votes over C, a distinguished candidate c &#X131; n C, and a class of election rules, there is at least one election rule from this class under which c wins the election. We study these two problems for a class of systems based on approval voting, the family of Copeland ^α elections, and a certain class of scoring rules. Our main result is that it is NP-complete to determine whether there is a scoring vector that makes c win the election, if we restrict the set of possible scoring vectors for an m-candidate election to those of the form (α _1, .. ., α _{m-4}, x_1, x_2, x_3, 0), with x_i = 1 for at least one i &#X131; n {1, 2, 3}. Computational Complexity of Two Variants of the Possible Winner Problem

Dorothea Baumeister
Magnus Roos
J
ouml; rg Rothe

A possible winner of an election is a candidate that has, in some kind of incomplete-information election, the possibility to win in a complete extension of the election. The first type of problem we study is the Possible co-Winner with respect to the Addition of New Candidates

PDF

AAAI Conference 2011 Conference Paper

How to Calibrate the Scores of Biased Reviewers by Quadratic Programming

Magnus Roos
Jörg Rothe
Björn Scheuermann

Peer reviewing is the key ingredient of evaluating the quality of scientiﬁc work. Based on the review scores assigned by the individual reviewers to the submissions, program committees of conferences and journal editors decide which papers to accept for publication and which to reject. However, some reviewers may be more rigorous than others, they may be biased one way or the other, and they often have highly subjective preferences over the papers they review. Moreover, each reviewer usually has only a very local view, as he or she evaluates only a small fraction of the submissions. Despite all these shortcomings, the review scores obtained need to be aggregrated in order to globally rank all submissions and to make the acceptance/rejection decision. A common method is to simply take the average of each submission’s review scores, possibly weighted by the reviewers’ conﬁdence levels. Unfortunately, the global ranking thus produced often suffers from a certain unfairness, as the reviewers’ biases and limitations are not taken into account. We propose a method for calibrating the scores of reviewers that are potentially biased and blindfolded by having only partial information. Our method uses a maximum likelihood estimator, which estimates both the bias of each individual reviewer and the unknown “ideal” score of each submission. This yields a quadratic program whose solution transforms the individual review scores into calibrated, globally comparable scores. We argue why our method results in a fairer and more reasonable global ranking than simply taking the average of scores. To show its usefulness, we test our method empirically using real-world data.

PDF Details

AAMAS Conference 2010 Conference Paper

Complexity of Social Welfare Optimization in Multiagent Resource Allocation

Magnus Roos
Joerg Rothe

We study the complexity of social welfare optimization in multiagent resource allocation. We assume resources to be indivisibleand nonshareable and agents to express their utilities over bundlesof resources, where utilities can be represented in either the bundleform or the k-additive form. Solving some of the open problemsraised by Chevaleyre et al. and confirming their conjectures, weprove that egalitarian social welfare optimization is NP-completefor both the bundle and the 1-additive form, and both exactutilitarian and exact egalitarian social welfare optimization areDP-complete, each for both the bundle and the 2-additive form, where DP is the second level of the boolean hierarchy over NP. Inaddition, we prove that social welfare optimization with respectto the Nash product is NP-complete for both the bundle and the1-additive form. Finally, we briefly discuss hardness of socialwelfare optimization in terms of inapproximability.

PDF