اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTaking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules
279
0
0.0
(
0
)
نشر من قبل
Dorothea Baumeister
تاريخ النشر
2011
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Possible Winner problem asks, given an election where the voters preferences over the candidates are specified only partially, whether a designated candidate can become a winner by suitably extending all the votes. Betzler and Dorn [1] proved a result that is only one step away from a full dichotomy of this problem for the important class of pure scoring rules in the case of unweighted voters and an unbounded number of candidates: Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule with vector (2,1,...,1,0), but is solvable in polynomial time for plurality and veto. We take the final step to a full dichotomy by showing that Possible Winner is NP-complete also for the scoring rule with vector (2,1,...,1,0).
قيم البحث
اقرأ أيضاً
The Possible-Winner problem asks, given an election where the voters preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of Possi
ble-Winner under the assumption that the voter preferences are $partitioned$. That is, we assume that every voter provides a complete order over sets of incomparable candidates (e.g., candidates are ranked by their level of education). We consider elections with partitioned profiles over positional scoring rules, with an unbounded number of candidates, and unweighted voters. Our first result is a polynomial time algorithm for voting rules with $2$ distinct values, which include the well-known $k$-approval voting rule. We then go on to prove NP-hardness for a class of rules that contain all voting rules that produce scoring vectors with at least $4$ distinct values.
The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) score of
at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for $Theta_{2}^{P}$. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.
This paper introduces an objective for optimizing proper scoring rules. The objective is to maximize the increase in payoff of a forecaster who exerts a binary level of effort to refine a posterior belief from a prior belief. In this framework we cha
racterize optimal scoring rules in simple settings, give efficient algorithms for computing optimal scoring rules in complex settings, and identify simple scoring rules that are approximately optimal. In comparison, standard scoring rules in theory and practice -- for example the quadratic rule, scoring rules for the expectation, and scoring rules for multiple tasks that are averages of single-task scoring rules -- can be very far from optimal.
We investigate proper scoring rules for continuous distributions on the real line. It is known that the log score is the only such rule that depends on the quoted density only through its value at the outcome that materializes. Here we allow further
dependence on a finite number $m$ of derivatives of the density at the outcome, and describe a large class of such $m$-local proper scoring rules: these exist for all even $m$ but no odd $m$. We further show that for $mgeq2$ all such $m$-local rules can be computed without knowledge of the normalizing constant of the distribution.
Proper scoring rules are commonly applied to quantify the accuracy of distribution forecasts. Given an observation they assign a scalar score to each distribution forecast, with the the lowest expected score attributed to the true distribution. The e
nergy and variogram scores are two rules that have recently gained some popularity in multivariate settings because their computation does not require a forecast to have parametric density function and so they are broadly applicable. Here we conduct a simulation study to compare the discrimination ability between the energy score and three variogram scores. Compared with other studies, our simulation design is more realistic because it is supported by a historical data set containing commodity prices, currencies and interest rates, and our data generating processes include a diverse selection of models with different marginal distributions, dependence structure, and calibration windows. This facilitates a comprehensive comparison of the performance of proper scoring rules in different settings. To compare the scores we use three metrics: the mean relative score, error rate and a generalised discrimination heuristic. Overall, we find that the variogram score with parameter p=0.5 outperforms the energy score and the other two variogram scores.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
