The Rényi–Ulam pathological liar game with a fixed number of lies

The q-round Rényi–Ulam pathological liar game with k lies on the set [n]{1,…,n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A[n] and Carole either assigns 1 lie to each element of A or to each element of [n]A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is dual to the original Rényi–Ulam liar game for which the winning condition is that at most one element has k or fewer lies. Define to be the minimum n such that Paul can win the q-round pathological liar game with k lies and initial set [n]. For fixed k we prove that is within an absolute constant (depending only on k) of the sphere bound, ; this is already known to hold for the original Rényi–Ulam liar game due to a result of J. Spencer.     

Two-batch liar games on a general bounded channel

We consider an extension of the 2-person Rényi-Ulam liar game in which lies are governed by a channel C, a set of allowable lie strings of maximum length k. Carole selects x∈[n], and Paul makes t-ary queries to uniquely determine x. In each of q rounds, Paul weakly partitions [n]=A₀∪?∪At−1 and asks for a such that x∈Aa. Carole responds with some b, and if a≠b, then x accumulates a lie (a,b). Carole's string of lies for x must be in the channel C. Paul wins if he determines x within q rounds. We further restrict Paul to ask his questions in two off-line batches. We show that for a range of sizes of the second batch, the maximum size of the search space [n] for which Paul can guarantee finding the distinguished element is as q→∞, where Ek(C) is the number of lie strings in C of maximum length k. This generalizes previous work of Dumitriu and Spencer, and of Ahlswede, Cicalese, and Deppe. We extend Paul's strategy to solve also the pathological liar variant, in a unified manner which gives the existence of asymptotically perfect two-batch adaptive codes for the channel C.     

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.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

Avoider-Enforcer: The rules of the game

An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F⊆X². The players claim previously unoccupied elements of the board X in turns. Enforcer wins if Avoider claims all vertices of some element of F, otherwise Avoider wins. In a more general version of the game a bias b is introduced to level up the players' chances of winning; Avoider claims one element of the board in each of his moves, while Enforcer responds by claiming b elements. This traditional set of rules for Avoider-Enforcer games is known to have a shortcoming: it is not bias monotone.We relax the traditional rules in a rather natural way to obtain bias monotonicity. We analyze this new set of rules and compare it with the traditional ones to conclude some surprising results. In particular, we show that under the new rules the threshold bias for both the connectivity and Hamiltonicity games, played on the edge set of the complete graph Kn, is asymptotically equal to n/logn. This coincides with the asymptotic threshold bias of the same game played by two “random” players.     

Nash equilibria of Cauchy-random zero-sum and coordination matrix games

We consider zero-sum games (A,  − A) and coordination games (A,A), where A is an m-by-n matrix with entries chosen independently with respect to the Cauchy distribution. In each case, we give an exact formula for the expected number of Nash equilibria with a given support size and payoffs in a given range, and also asymptotic simplications for matrices of a fixed shape and increasing size. We carefully compare our results with recent results of McLennan and Berg on Gaussian random bimatrix games (A,B), and describe how the three situations together shed light on random bimatrix games in general.     

Avoider-Enforcer games

Let p and q be positive integers and let H be any hypergraph. In a (p,q,H) Avoider-Enforcer game two players, called Avoider and Enforcer, take turns selecting previously unclaimed vertices of H. Avoider selects p vertices per move and Enforcer selects q vertices per move. Avoider loses if he claims all the vertices of some hyperedge of H; otherwise Enforcer loses. We prove a sufficient condition for Avoider to win the (p,q,H) game. We then use this condition to show that Enforcer can win the (1,q) perfect matching game on K2n for every q?cn/logn for an appropriate constant c, and the (1,q) Hamilton cycle game on Kn for every q?cnloglogloglogn/lognlogloglogn for an appropriate constant c. We also determine exactly those values of q for which Enforcer can win the (1,q) connectivity game on Kn. This result is quite surprising as it substantially differs from its Maker-Breaker analog. Our method extends easily to improve a result of Lu [X. Lu, A note on biased and non-biased games, Discrete Appl. Math. 60 (1995) 285-291], regarding forcing an opponent to pack many pairwise edge disjoint spanning trees in his graph.     

A new look at the role of players’ weights in the weighted Shapley value

everal new families of semivalues for weighted n-person transferable utility games are axiomatically constructed and discussed under increasing collections of axioms, where the weighted Shapley value arises as the resulting one member family. A more general approach to such weighted games defined in the form of two components, a weight vector λ and a classical TU-game v, is provided. The proposed axiomatizations are done both in terms of λ and v. Several new axioms related to the weight vector λ are discussed, including the so-called “amalgamating payoffs” axiom, which characterizes the value of a weighted game in terms of another game with a smaller number of players. They allow for a new look at the role of players’ weights in the context of the weighted Shapley value for the model of weighted games, giving new properties of it. Besides, another simple formula for the weighted Shapley value is found and examples illustrating some surprising behavior of it in the context of players’ weights are given. The paper contains a wide discussion of the results obtained.     

Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

On the uniqueness of the tetrahedral association schemes

Let V be the set of (₃⁴) 3- sets in {1 … n}. Say p, q ∈ V are ith associates, (p, q) ∈ A_i, if 3 = i + |p ∩ q|. An association scheme is tetrahedral if it is isomorphic to the scheme {A₀, A₁, A₂, A₃} and a graph is tetrahedral if it is isomorphic to A₁. Aigner [1] and Bose and Laskar [2] have shown that the tetrahedral graphs are characterized by their characteristic equations, provided n < 9 or n > 16. The present paper extends methods of Hoffman [7] to show that the tetrahedral association schemes are characterized by their structural constants, provided n > 10.