TY - JOUR
T1 - Computing the minimal covering set
AU - Brandt, Felix
AU - Fischer, Felix
N1 - Funding Information:
This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-1. Earlier versions of this paper were presented at the 5th International Conference on Logic, Game Theory and Social Choice (LGS), the 22nd Conference on Artificial Intelligence (AAAI), and the Dagstuhl Seminar on Computational Issues in Social Choice.
PY - 2008/9
Y1 - 2008/9
N2 - We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set-the minimal upward covering set and the minimal downward covering set-unless P equals NP. Finally, we observe a strong relationship between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.
AB - We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set-the minimal upward covering set and the minimal downward covering set-unless P equals NP. Finally, we observe a strong relationship between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.
KW - Computational complexity
KW - Essential set
KW - Minimal covering set
KW - Social choice theory
KW - Uncovered set
UR - http://www.scopus.com/inward/record.url?scp=48449084604&partnerID=8YFLogxK
U2 - 10.1016/j.mathsocsci.2008.04.001
DO - 10.1016/j.mathsocsci.2008.04.001
M3 - Article
AN - SCOPUS:48449084604
SN - 0165-4896
VL - 56
SP - 254
EP - 268
JO - Mathematical social sciences
JF - Mathematical social sciences
IS - 2
ER -