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)     

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.     

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.     

Smallest tournaments not realizable by $${\frac{2}{3}}$$-majority voting

Define the predictability number α(T) of a tournament T to be the largest supermajority threshold for which T could represent the pairwise voting outcomes from some population of voter preference orders. We establish that the predictability number always exists and is rational. Only acyclic tournaments have predictability 1; the Condorcet voting paradox tournament has predictability ; Gilboa has found a tournament on 54 alternatives (i.e. vertices) that has predictability less than , and has asked whether a smaller such tournament exists. We exhibit an 8-vertex tournament that has predictability , and prove that it is the smallest tournament with predictability <  . Our methodology is to formulate the problem as a finite set of two-person zero-sum games, employ the minimax duality and linear programming basic solution theorems, and solve using rational arithmetic. D. Shepardson was supported by a NSF Graduate Research Fellowship during the course of this work.     

Uncovered set choice rules

I study necessary and sufficient conditions for a choice function to be rationalized in the following sense: there exists a total asymmetric relation T (a tournament) such that, for each feasible (finite) set, the choice set coincides with the uncovered set of T restricted to that feasible set. This notion of ‘maximization’ offers testable restrictions on observable choice behavior.     

The sensitivity of weight selection on the Condorcet efficiency of weighted scoring rules

A weighted scoring rule, Rule λ, on three alternative elections selects the winner by awarding 1 point to each voter's first ranked candidate, λ points to the second ranked candidate, and zero to the third ranked candidate. The Condorcet winner is the candidate that would defeat each other candidate in a series of pairwise elections by majority rule. The Condorcet efficiency of Rule λ is the conditional probability that Rule λ selects the Condorcet winner, given that a Condorcet winner exists. Borda rule (λ=1/2) is the weighted scoring rule that maximizes Condorcet efficiency. The current study considers the conditional probability that Borda rule selects the Rule λ winner, given that Rule λ elects the Condorcet winner with a large electorate. Received: 21 August 1996 / Accepted: 7 January 1997     

Pivotal voting and the emperor's new clothes

A leading recent line of work in game theory applied to politics exploits the “pivotal voting” insight introduced by Austen-Smith and Banks [1]. The most prominent follow-on papers have been by Feddersen and Pesendorfer [2, 3, 4, 5], where a particularly striking result is that in a large election, the winner with many poorly-informed voters will be identical to the winner under full information. But of course any result whatever can be proven if sufficiently implausible assumptions are allowed. This review provides simple derivations of the elections result for both the FP 1996 model [2] and then for the (generalized) FP 1999 model [4]. The resulting transparency makes it easy to see the relation between the models, but also why neither result is relevant to actual elections. Received: 6 December 1999/Accepted: 28 August 2000     

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.     

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 DESIGNER'S CHOICE BETWEEN SINGLE‐PRIZE AND PARALLEL TOURNAMENTS

In this article, I theoretically and experimentally compare a designer's profits from two tournament designs. The first design is a standard winner‐take‐all tournament with a single prize. The second design features two winner‐take‐all (parallel) tournaments with different prizes where individuals choose which tournament to enter before competing. I develop a simple model that illustrates how the relative performances of these designs change as contestants' abilities differ. The theoretical model shows that the designer's profit is higher (lower) in the parallel tournament when contestants' abilities differ greatly (are similar). I complement these findings with experimental evidence. The experiments show that the parallel tournament is more profitable under high heterogeneity, whereas under low heterogeneity, the designer is better off with the single‐prize tournament. Furthermore, high‐ability agents under‐participate and low‐ability agents over‐participate in the high‐prize tournament relative to the theoretical prediction. (JEL C72, D82, J33, M51, M52)     

Slaters's winners of a tournament may not be in the Banks set

An exemple is given of a tournament in which none of the Kemeny-Slater's winners of the tournament belong to the Banks set.The authors thanks Michel LeBreton, who provided the initial stimulus for this investigation, and an anonymous referee for helpfull comments.     

An extension of a theorem on the aggregation of separable preferences

An Excess-Voting Function relative to a profile π assigns to each pair of alternatives (x,y), the number of voters who prefer x to y minus the number of voters who prefer y to x. It is shown that any non-binary separable Excess-Voting Function can be achieved from a preferences profile when individuals are endowed with separable preferences. This result is an extension of Hollard and Le Breton (1996). Received: 16 December 1996 / Accepted: 8 October 1997     

The number of weak orderings of a finite set

The number of Arrovian constitutions, when N agents are to rank n alternatives, is p(n) ^{p(n) N} , where p(n) is the number of weak orderings of n alternatives. For n≤15, p(n) is the nearest integer to n!/2(log2) ^{n +1}, the dominant term of a series derived by contour integration of the generating function. For large n, about n/17 additional terms in the series suffice to compute p(n) exactly. Received: 29 May 1995 / Accepted: 22 May 1997     

An alternative proof of Gibbard's random dictatorship result

By using a line of reasoning similar to the one used by Gibbard (Gibbard A (1973) Econometrica 41: 587–601) in the deterministic framework, we provide a more transparent and intuitive proof of the following random dictatorship result in the probabilistic framework, which is a corollary credited to H.␣Sonnenschein of the more general result of Gibbard (Gibbard A (1977) Econometrica 45: 665–681): A decision scheme is Pareto optimific ex post and strategy proof if and only if it is a random dictatorship. Received: 13 February 1996 / Accepted: 14 April 1997     

In quest of the banks set in spatial voting games

The Banks set (1(4):295–306, 1985) is one of the more important concepts in voting theory since it tells us about the sophisticated outcomes of standard amendment voting procedures commonly in use throughout the English speaking world (and elsewhere as well). While the properties of the Banks set for finite voting games have been extensively studied, little is known about how to find members of this set for majority rule spatial voting games involving possibly infinite agendas. We look at this question for two-dimensional games where voters have Euclidean preferences, and offer a variety of new results that delimit areas of the space that can be shown to lie within the Banks set, such as the Schattschneider set, the tri-median set, and the Banks line set—geometric constructs which we show to be nested within one another.     

Minimal covering set solutions

We study necessary and sufficient conditions for a multi-valued solution S to be rationalized in the following sense: there exists a complete asymmetric relation T (a tournament) such that, for each feasible (finite) set, the solution set of S coincides with the minimal covering set of T restricted to that feasible set. Our characterization result relies only on properties relating S across feasible choice sets.     

Composition-consistent tournament solutions and social choice functions

This paper introduces a new axiom for choice in preference profiles and tournaments, called composition-consistency. A social choice function is composition-consistent if it is non-sensitive to the cloning of one or several outcomes. The key feature of the composition consistency property is an operation concept called multiple composition product of profiles. The paper provides a brief overview of some social choice functions studied in the literature. Concerning the tournament solutions, it is proved that the Top Cycle, the Slater and the Copeland solutions are not composition-consistent, whereas the Banks, Uncovered Set, TEQ, Minimal Covering Set are composition-consistent. Moreover, we define the composition-consistent hull of a solution as the smallest composition-consistent solution containing . The composition-consistent hulls of the Top cycle and Copeland solutions are specified, and we give some hints about the location of the hull of the Slater set. Concerning social choice functions, it is shown that Kemeny, Borda and Minimax social choice functions are not composition-consistent, whereas the Paretian one is composition-consistent. Moreover, we prove that the latter is the composition-consistent hull of the Borda and Minimax functions.     

Single-peaked preferences with several commodities

We consider the problem of allocating m commodities among n agents with single-peaked preferences. When m≥2 and n=2 any strategy-proof and efficient solution is dictatorial. We propose an extension of the Uniform Rule that (in the two-agents case) is the only one that satisfies strategy-proofness, envy-freeness, and a weak requirement related to efficiency. Alternatively, the envy-freeness property may be replaced by weak-anonymity. Received: 7 November 1997/Accepted: 1 August 2000     

A counterexample to a conjecture of Schwartz

In 1990, motivated by applications in the social sciences, Thomas Schwartz made a conjecture about tournaments which would have had numerous attractive consequences. In particular, it implied that there is no tournament with a partition A, B of its vertex set, such that every transitive subset of A is in the out-neighbour set of some vertex in B, and vice versa. But in fact there is such a tournament, as we show in this article, and so Schwartz’ conjecture is false. Our proof is non-constructive and uses the probabilistic method.     

Ranking opportunity sets on the basis of their freedom of choice and their ability to satisfy preferences: A difficulty

This paper examines a possibility of enlarging the domain of definition of individual preferences suggested by the recent literature on freedom of choice. More specifically, the possibility for an individual to have preferences that depend upon both the opportunity set that she faces and the particular alternative that she chooses from that set is considered. Even more specifically, the possibility for these preferences to value freedom of choice, as defined by the set theoretic relation of inclusion, while being consistent, in a certain sense, with the existence of a preference ordering over the options contained in opportunity sets is investigated. It is shown in the paper that a necessary condition for the existence of any transitive extended preferences of this type is for freedom of choice to be given no intrinsic importance. Received: 22 November 1995 / Accepted: 11 January 1997