Tournament games and positive tournaments

Given a tournament T, the tournament game on T is as follows: Two players independently pick a node of T. If both pick the same node, the game is tied. Otherwise, the player whose node is at the tail of the arc connecting the two nodes wins. We show that the optimal mixed strategy for this game is unique and uses an odd number of nodes. A tournament is positive if the optimal strategy for its tournament game uses all of its nodes. The uniqueness of the optimal strategy then gives a new tournament decomposition: any tournament can be uniquely partitioned into positive subtournaments P₁, P₂, ?,P_k, so P_i “beats” P_j for all 1 ≤ i > j ≤ k. We count the number of n node positive tournaments and list them for n ≤ 7. © 1995 John Wiley & Sons, Inc.     

An <Emphasis Type="Italic">m</Emphasis><Superscript>th</Superscript> Generation Model for Weak Ranking of Players in a Tournament

The problem of ranking players in a tournament has been studied by a number of authors. The methods developed for ranking players fall under two general headings—direct methods and rating methods. The present paper extends the tournament ranking problem in two directions. First, the usual definition of a tournament is broadened to include ties or draws. Thus, our model determines the best weak ranking of the players. Second, the ranking method presented takes account of player strength in that wins over strong players are valued higher than wins over weak players. To account for player strength, we evaluate both direct or first-order wins of players over opponents (i defeats j) and indirect or higher-order wins (i defeats k, who defeats j). A model which derives a composite score for each player, combining both direct and indirect wins, is used to obtain an overall ranking of the competitors.     

Multiple-elimination knockout tournaments with the fixed-win property

We classify those triples (n,l,w) for which there exists a ‘knockout’ tournament for n players in which the winner always wins exactly w games and each loser loses exactly l games.     

More cyclic triplewhist tournaments

We extend the set of values of n for which it is known that a Z-cyclic triple whist tournament for 4n players exists by proving that if there exists such a tournament for q + 1 players, where q ≡ 3 (mod 4) is prime, then there exists such a tournament for qp^a1₁…p^an_n + 1 players, whenever the p_i are primes ≡ 5 (mod 8). © 1995 John Wiley & Sons, Inc.     

The diameter game

A large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given — usually monotone — property. Here we introduce the d‐diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2‐diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n^1/8/(lnn)^3/8. In addition, we investigate d‐diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Landau's inequalities for tournament scores and a short proof of a theorem on transitive sub‐tournaments

Ao and Hanson, and Guiduli, Gyárfás, Thomassé and Weidl independently, proved the following result: For any tournament score sequence S = (s₁, s₂, … ,s_n) with s₁≤s₂ ≤ … ≤ s_n, there exists a tournament T on vertex set {1,2, …, n} such that the score of each vertex i is s_i and the sub‐tournaments of T on both the even and the odd indexed vertices are transitive in the given order; that is, i dominates j whenever i > j and i ≡ j (mod 2). In this note, we give a much shorter proof of the result. In the course of doing so, we show that the score sequence of a tournament satisfies a set of inequalities which are individually stronger than the well‐known set of inequalities of Landau, but collectively the two sets of inequalities are equivalent. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 244–254, 2001     

On Erdős's Eulerian Trail Game

 Paul Erdős proposed the following graph game. Starting with the empty graph on n vertices, two players, Trailmaker and Breaker, draw edges alternatingly. Each edge drawn has to start at the endpoint of the previously drawn edge, so the sequence of edges defines a trail. The game ends when it is impossible to continue the trail, and Trailmaker wins if the trail is eulerian. For all values of n, we determine which player has a winning strategy. Received: November 6, 1996 / Revised: May 2, 1997     

Score certificates for tournaments

The score of a vertex in a tournament is its out-degree. A score certificate for a labeled tournament T is a labeled subdigraph D of T which together with the score sequence of T allows errorless reconstruction of T. In this paper we prove a general lower bound on the sizes of score certificates. Our main theorem can be stated as follows: Except for the regular tournaments on 3 and 5 vertices, every tournament T on n vertices requires at least n−1 arcs in a score certificate for T. This is best possible since every transitive tournament on n vertices has a score certificate with exactly n−1 arcs. © 1997 John Wiley & Sons, Inc.     

Ordered tournaments and ordered triplewhist tournaments with the three person property

It is well known that an ordered tournament OWh(v) exists if and only if v ≡ 1 (mod 4), v ≥ 5. An ordered triplewhist tournament on v players is said to have the three person property if no two games in the tournament have three common players. We briefly denote such a design as a 3POTWh(v). In this article, we show that a 3POTWh(v) exists whenever v>17 and v ≡ 1 (mod 4) with few possible exceptions. We also show that an ordered whist tournament on v players with the three person property, denoted 3POWh(v), exists if and only if v ≡ 1 (mod 4), v ≥ 9. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 39–52, 2009     

New approach to nonrepetitive sequences

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that three symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of three‐element sets L₁,…,L_n there exists a nonrepetitive sequence s₁,…,s_n with s_i∈L_i. We propose a new non‐constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. The simple double counting in the heart of the argument is inspired by the recent algorithmic proof of the Lovász local lemma due to Moser and Tardos. Furthermore we apply this approach and present game‐theoretic type results on nonrepetitive sequences. Nonrepetitive game is played by two players who pick, one by one, consecutive terms of a sequence over a given set of symbols. The first player tries to avoid repetitions, while the second player, in contrast, wants to create them. Of course, by simple imitation, the second player can force lots of repetitions of size 1. However, as proved by Pegden, there is a strategy for the first player to build an arbitrarily long sequence over 37 symbols with no repetitions of size greater than 1. Our techniques allow to reduce 37–6. Another game we consider is the erase‐repetition game. Here, whenever a repetition occurs, the repeated block is immediately erased and the next player to move continues the play. We prove that there is a strategy for the first player to build an arbitrarily long nonrepetitive sequence over 8 symbols. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph

This paper studies the probability that a random tournament with specified score sequence contains a specified subgraph. The exact asymptotic value is found in the case that the scores are not too far from regular and the subgraph is not too large. An n‐dimensional saddle‐point method is used. As a sample application, we prove that almost all tournaments with a given score sequence (not too far from regular) have a trivial automorphism group. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 47–57, 2000     

On strategy improvement algorithms for simple stochastic games

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n²/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(²0.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.     

Optimal strategies for equal-sum dice games

In this paper, we consider a non-cooperative two-person zero-sum matrix game, called dice game. In an (n,σ) dice game, two players can independently choose a dice from a collection of hypothetical dice having n faces and with a total of σ eyes distributed over these faces. They independently roll their dice and the player showing the highest number of eyes wins (in case of a tie, none of the players wins). The problem at hand in this paper is the characterization of all optimal strategies for these games. More precisely, we determine the (n,σ) dice games for which optimal strategies exist and derive for these games the number of optimal strategies as well as their explicit form.     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

How to compute the volume in high dimension?

 In some areas of theoretical computer science we feel that randomized algorithms are better and in some others we can prove that they are more efficient than the deterministic ones. Approximating the volume of a convex n-dimensional body, given by an oracle is one of the areas where this difference can be proved. In general, if we use a deterministic algorithm to approximate the volume, it requires exponentially many oracle questions in terms of n as n→∞. Dyer, Frieze and Kannan gave a randomized polynomial approximation algorithm for the volume of a convex body K⊆ℝ ⁿ , given by a membership oracle. The DKF algorithm was improved in a sequence of papers. The area is full of deep and interesting problems and results. This paper is an introduction to this field and also a survey. Received: January 28, 2003 / Accepted: April 29, 2003 Published online: May 28, 2003     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

On n-partite Tournaments with Unique n-cycle

An n-partite tournament is an orientation of a complete n-partite graph. An n-partite tournament is a tournament, if it contains exactly one vertex in each partite set. Douglas, Proc. London Math. Soc. 21 (1970) 716–730, obtained a characterization of strongly connected tournaments with exactly one Hamilton cycle (i.e., n-cycle). For n≥3, we characterize strongly connected n-partite tournaments that are not tournaments with exactly one n-cycle. For n≥5, we enumerate such non-isomorphic n-partite tournaments.     

An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.     

Wythoff''s sequence and -Heap Wythoff''s conjectures

Define a Wythoff's sequence as a sequence of pairs of integers (A_n,B_n) _n>n0 such that there exists a finite set of integers T, A_n=mex( A_i,B_i:i<n T), B_n-A_n=n, and B_n ∩T=. Structural properties and behaviors of Wythoff's sequence are investigated. The main result is that for such a sequence, there always exists an integer α such that when n is large enough, |A_n-nφ-α|1, where , the golden section. The value of α can also be easily determined by a relatively small number of pairs in the sequence. As a corollary, the two conjectures on the N-heap Wythoff's game by Fraenkel [Complexity, appeal and challenges of combinatorial Games, Theoret. Comput. Sci. 313 (2004) 393–415] on the N-heaped Wythoff's game are proved to be equivalent.