| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428547 | Information Processing Letters | 2013 | 4 Pages |
Abstract
•We consider ranking sets of elements based on their average utility.•We show that deciding whether this ranking is strict is NP-hard.•This problem originates in research on voting manipulation.
We show that, given a set of positive integers, it is NP-complete to decide whether it contains two subsets with the same average. Our interest in this problem is motivated by questions in decision theory that are related to defining preferences on sets of objects given preferences over individual objects.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Edith Elkind, James B. Orlin,