A computational analysis of the tournament equilibrium set

A recurring theme in the mathematical social sciences is how to select the “most desirable” elements given a binary dominance relation on a set of alternatives. Schwartz’s tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions proposed so far. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive solution concept refining both the Banks set and Dutta’s minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard, and thus does not admit a polynomial-time algorithm unless P equals NP. Furthermore, we propose a heuristic that significantly outperforms the naive algorithm for computing TEQ.     

A smallest tournament for which the Banks set and the Copeland set are disjoint

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T; a Copeland winner of T is a vertex with a maximum out-degree. In this paper, we show that 13 is the minimum number of vertices that a tournament must have so that none of its Copeland winners is a Banks winner: for any tournament with less than 13 vertices, there is always at least one vertex which is a Copeland winner and a Banks winner simultaneously. Received: 2 May 1997 / Accepted: 30 September 1997     

Choosing from a tournament

A tournament is any complete asymmetric relation over a finite set A of outcomes describing pairwise comparisons. A choice correspondence assigns to every tournament on A a subset of winners. Miller's uncovered set is an example for which we propose an axiomatic characterization. The set of Copeland winners (outcomes with maximal scores) is another example; it is a subset of the uncovered set: we note that it can be a dominated subset. A third example is derived from the sophisticated agenda algorithm; we argue that it is a better choice correspondence than the Copeland set.     

A measure of distance between judgment sets

In the literature on judgment aggregation, an important open question is how to measure the distance between any two judgment sets. This is relevant for issues of social choice: if two individuals hold different beliefs then we might want to find a compromise that lies somewhere between them. We propose a set of axioms that determine a measure of distance uniquely. This measure differs from the widely used Hamming metric. The difference between Hamming’s metric and ours boils down to one axiom. Given judgment sets A and B, this axiom says that if the propositions in ${A \cap B}$ jointly imply that the propositions in A?B share the same truth value, then the disagreement between A and B over those propositions in A?B should be counted as a single disagreement. We consider the application of our metric to judgment aggregation, and also use the metric to measure the distance between preference rankings.     

Covering relations,closest orderings and hamiltonian bypaths in tournaments

We show that the Slater's set of a tournament, i.e. the set of the top elements of the closest orderings, is a subset of the top cycle of the uncovered set of the tournament. We also show that the covering relation is related to the hamiltonian bypaths of a strong tournament in that if x covers y, then there exists an hamiltonian bypath from x to y.We thank B. Monjardet and an anonymous editor for helpful suggestions.     

Path independent choice and the ranking of opportunity sets

The indirect utility principle provides an instrumentalist basis for ranking opportunity sets, given an underlying preference ranking on alternatives. Opportunity set A is weakly preferred to B if A includes at least one preference-maximising element from $A\cup B$ . We introduce the Plott consistency principle as a natural extension of this logic to decision-makers who choose amongst alternatives according to a path independent choice function. Such choice functions need not be rationalisable by a preference order. Plott consistency requires that A is an acceptable choice from $\left\{ A, B\right\} $ if A includes at least one element from the set of acceptable choices from $A\cup B$ . We explore necessary and sufficient conditions (imposed on a choice function defined on collections of opportunity sets) for Plott consistency.     

Banks winners in tournaments are difficult to recognize

Given a tournament T, a Banks winner of T is the top vertex of any maximal (with respect to inclusion) transitive subtournament of T. In this technical note, we show that the problem of deciding whether some fixed vertex v is a Banks winner for T is NP-complete. Received: 22 February 2002/Accepted: 20 June 2002 Supported by the START program Y43-MAT of the Austrian Ministry of Science. I would like to thank two thank the referees for a careful reading of the paper, for helpful remarks, and for many suggestions how to improve the presentation.     

A note on “Banks winners in tournaments are difficult to recognize” by G. J. Woeginger

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T. While Woeginger shows that recognizing whether a given vertex of T is a Banks winner is NP-complete, the computation of a Banks winner of T is polynomial, and more precisely linear with respect to the size of T.The article of G.J. Woeginger appeared in Soc Choice Welfare 20: 523–528 (2003)     

A note on contestation-based tournament solutions

In tournaments, one alternative contests another if is a “winner” among only alternatives that beat it. This paper examines the consequences and limitations of the contestation relation by considering a procedure in which alternatives that are contested are iteratively eliminated from consideration. In doing so, a new family of tournament solutions are introduced and related to existing refinements of the Banks set. Findings show that iterated removal of contested alternatives a limited device for choosing from tournaments. These results contrast with results regarding the top-set of the contestation relation. Results highlight the role of the top-set operator for choice from tournaments.     

Still more on the Tournament Equilibrium Set

Schwartz (Soc Choice Welfare 3:271–291, 1990) proposed a solution concept (the Tournament Equilibrium Set) for choosing from a tournament and stated some conjectures about this solution. Laffond et al. (Math Sci Hum 123:37–44, 1993) introduced further conjectures and showed the links between some of them. In this short note, we show that one of the conjectures stated by Schwartz (1990) is false. We also complete a result given in Laffond et al. (1993). I gratefully thank J.-F. Laslier for his remarks and for introducing me to this topic.     

Conditioning the effect of prize on tournament self-selection

This study examines how past performance moderates the effect of the size of the prize on tournament self-selection. We identify two types of trajectories that play simultaneous and unique roles in moderating the influence of prize on an agent’s decision to enter a tournament: within-period trajectory, which reflects an agent’s short-term performance streak in the tournaments recently entered, and across-period trajectory, which reflects an agent’s long-term performance streak in the same tournament across different periods. We find that positive (negative) within-period and across-period trajectories strengthen (weaken) the positive effect of the size of the prize on tournament entry. Although both performance trajectories have a significant and sizable influence, we find that within-period trajectory plays the strongest moderating effect. We draw on the representativeness heuristic and the availability heuristic to explain our findings. We study these notions using 54,915 self-selection decisions that professional golfers have taken over a ten-year period (1996–2006) when entering PGA Tour tournaments. We draw implications for the craft of contest design.     

Systematic analysis of multiple voting rules

For a class of voting rules, which includes Approval and Cumulative Voting, it is shown how to find and analyze all possible outcomes that arise with a specified profile, and, conversely, how to start with a potential region and determine whether there exist supporting profiles. The geometry of these regions is determined by the “Reversal symmetry” portion of a profile; i.e., components of the A\succ B\succ C, C\succ B\succ A{A\succ B\succ C, C\succ B\succ A} type.     

Does the β-measure make empirical sense? A vignette experiment on humans’ judgment of social dominance

Dominance hierarchies play an important role in governing the social interactions of humans and other species of social animals. In a social group, dominance relations can be inferred from the directed network of matchups between actors. Methodologists have proposed different ways to measure social dominance in directed networks. One such measure, the “β-measure” (van den Brink and Gilles, 2000), emphasizes the quality of defeated opponents in a way that an actor is seen as being more dominant when s/he defeats opponents who are more rarely defeated. While insightful in theory, the validity of the measure in people’s perception remains questionable, considering the cognitive complexity imposed by this measure, compared to a simpler measure that merely counts the number of defeated opponents. We conducted a vignette experiment with human subjects (professional athletes) to test their judgments of the dominance relation in a hypothetical tournament. Fitting our parametric model to peoples’ evaluations in the experiment, we found strong evidence in support of the β-measure: Although, in general, contestants who win more in the tournament are regarded as being more dominant, the contents of the winning records matter, such that those who beat more victorious opponents are further regarded as more dominant than those who defeat less victorious opponents. We also found a gender difference, in that men have a stronger propensity than women to adopt the β-measure when judging social dominance.     

Top-Pair and Top-Triple Monotonicity

We say that a social choice function (SCF) satisfies Top-k Monotonicity if the following holds. Suppose the outcome of the SCF at a preference profile is one of the top k-ranked alternatives for voter i. Let the set of these k alternatives be denoted by B. Suppose that i’s preference ordering changes in such a way that the set of first k-ranked alternatives remains the set B. Then the outcome at the new profile must belong to B. This definition of monotonicity arises naturally from considerations of set “improvements” and is weaker than the axioms of strong positive association and Maskin Monotonicity. Our main results are that if there are two voters then a SCF satisfies unanimity and Top-2 or Top-pair Monotonicity if and only if it is dictatorial. If there are more than two voters, then Top-pair Monotonicity must be replaced by Top-3 Monotonicity (or Top-triple Monotonicity) for the analogous result. Our results demonstrate that connection between dictatorship and “improvement” axioms is stronger than that suggested by the Muller–Satterthwaite result (Muller and Satterthwaite in J Econ Theory 14:412–418, 1977) and the Gibbard–Sattherthwaite theorem.     

Implementation in generic environments

In this paper, we study implementation in “economic environments”. It is shown that there is a dense subset of the set of preference profiles such that given an arbitrary social choice function, f, and ε>0, there exists another social choice function, f _ε, within ε of f uniformly and implementable in Nash equilibrium on the dense subset.     

Choice functions over a finite set: A summary

A choice function picks some outcome(s) from every issue (subset of a fixed set A of outcomes). When is this function derived from one preference relation on A (the choice set being then made up of the best preferred outcomes within the issue), or from several preference relations (the choice set being then the Pareto optimal outcome within the issue, or the union of the best preferred outcomes for each preference relation)? A complete and unified treatment of these problems is given based on three functional properties of the choice function. None of the main results is original.     

Affirmative Action Can Increase Effort

Previous theoretical work examining labor tournaments concluded that an affirmative action program will always reduce the effort supplied by agents, thereby reducing output and profit for the tournament administrator; however, experimental results sometime contradict this conclusion. In the context of a labor tournament I demonstrate that there exists an affirmative action program that induces both types of agents to provide greater effort. In some instances the effort maximizing affirmative action program will also give both types of agents an equal chance of winning the tournament.

Gender differences in tournament and flat-wage schemes: An experimental study

We present a new experiment that explores gender differences in both performance and compensation choices. While most of the previous studies have focused on tournament vs. piece-rate schemes, the originality of our study consists in examining the gender gap in the context of a flat wage scheme. Our data indicate that females exert a significantly higher effort than men in fixed payment schemes. We find however no gender difference in performance under the tournament scheme, due to a combination of two effects. On the one hand, men more significantly increase their effort when switching from a flat wage to a tournament scheme. On the other hand, when switching from the flat wage to a tournament scheme, women have less margin to increase performance since their effort was already relatively high with a flat wage. We also find that females are more likely than males to choose a flat-wage scheme than a tournament. This gap however narrows dramatically when feedback on previous experience is provided.