McGarvey (Econometrica, 21(4), 608–610, 1953) has shown that any irreflexive and anti-symmetric relation can be obtained as a relation induced by majority rule. We address the analogous issue for dominance relations of finite cooperative games with non-transferable utility (coalitional NTU games). We find any irreflexive relation over a finite set can be obtained as the dominance relation of some finite coalitional NTU game. We also show that any such dominance relation is induced by a non-cooperative game through β-effectivity. Dominance relations (...) obtainable through α-effectivity, however, have to comply with a more restrictive condition, which we refer to as the edge-mapping property. (shrink)

Sparked by a remarkable result due to Hemaspaandra et al. [9], the voting rule attributed to Charles Dodgson has become one of the most studied voting rules in computational social choice. However, the computer science literature often neglects that Dodgson's rule has some serious shortcomings as a choice procedure. This short note contains four examples revealing Dodgson's deficiencies.

Social choice rules are often evaluated and compared by inquiring whether they satisfy certain desirable criteria such as the Condorcet criterion, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise (...) majority relation. These sets include the Copeland set, the Smith set, the Schwartz set, von Neumann-Morgenstern stable sets, the Banks set, and the Slater set. We investigate the relationships between these sets and completely characterize their computational complexity, which allows us to obtain hardness results for entire classes of social choice rules. (shrink)