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.     

Majority voting leads to unanimity

We consider a situation where society decides, through majority voting in a secret ballot, between the alternatives of ‘reform’ and ‘status quo’. Reform is assumed to create a minority of winners, while being efficient in the Kaldor–Hicks sense. We explore the consequences of allowing binding transfers between voters conditional on the chosen alternative. In particular, we establish conditions under which the winners wish to compensate all losers, thus leading to unanimity for reform, rather than compensating some losers to form a non-maximal majority. The analysis employs concepts from cooperative game theory.      

How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

On a square haystack game

A haystack game is a hider-seeker zero-sum game of locating a needle in a haystack. Baston and Bostock have obtained partial solutions to this game for the case of a square haystack. This paper supplements their results, thus confirming their belief that a complete solution is difficult.The author would like to thank a referee for his helpful comments, in particular for suggesting Lemma 2.1 which has led to a more concise and transparent treatment of Section 2.     

Search game in a rectangle

We consider a search game in which the searcher (player S) moves along a continuous trajectory in a rectangleQ. The velocity vectogram of player S is a rhombus-type set. In this paper, we construct the strategies of both players which make it possible to find the asymptotic value of the game in the case of small discovery radius.The author would like to thank the referee for considerable simplification of the proof of Theorem 4.1.     

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.     

How to play MetaSquares

The rules of the game MetaSquares as well as computational results suggest to follow a “lattice” strategy. This strategy is presented, and by counting lattice points it is shown to be essentially best possible.      

Singular surfaces in a linear pursuit-evasion game with elliptical vectograms

In a linear pursuit-evasion game with elliptical vectograms, singular surfaces appear in the plane of symmetry containing the ellipses minor axes and, as a consequence, locally nonsmooth isocost tubes are generated. Both dispersal and attractive focal surfaces are encountered. The dispersal surface is a zone of initial conditions for trajectories leaving the plane of symmetry. Optimal trajectories attracted by the focal surface merge tangentially to the plane of symmetry and remain there until the boundary of the dispersal zone is reached. Determination of the saddle-point strategies in the focal surface leads to constructing the isocost surfaces in the entire game space.     

A threshold for the Maker‐Breaker clique game

We study the Maker‐Breaker k‐clique game played on the edge set of the random graph G(n, p). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G(n, p), until all the edges are claimed. Maker wins if he claims all the edges of a k‐clique; Breaker wins otherwise. We determine that the threshold for the graph property that Maker can win this game is at , for all k > 3, thus proving a conjecture from Ref. [Stojakovi? and Szabó, Random Struct Algor 26 (2005), 204–223]. More precisely, we conclude that there exist constants such that when the game is Maker's win a.a.s., and when it is Breaker's win a.a.s. For the triangle game, when k = 3, we give a more precise result, describing the hitting time of Maker's win in the random graph process. We show that, with high probability, Maker can win the triangle game exactly at the time when a copy of K₅ with one edge removed appears in the random graph process. As a consequence, we are able to give an expression for the limiting probability of Maker's win in the triangle game played on the edge set of G(n, p). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 318–341, 2014     

Two-target game model of an air combat with fire-and-forget all-aspect missiles

An air combat duel between similar aggressive fighter aircraft, both equipped with the same type of guided missiles, is formulated as a two-target differential game using the dynamic model of the game of two identical cars. Each of the identical target sets represents the effective firing envelope of an all-aspect fire-and-forget air-to-air missile. The firing range limits depend on the target aspect angle and are approximated by analytical functions. The maximum range, computed by taking into account the optimal missile avoidance maneuver of the target, determines the no-escape firing envelope. The solution consists of the decomposition of the game space into four regions: the respective winning zones of the two opponents, the draw zone, and the region where the game terminates by a mutual kill. The solution provides a new insight for future air combat analysis.This paper is based on the first author's D.Sc. Thesis. The research was supported by NASA Cooperative Agreement NCCW-4.     

A differential game without a qualitative saddle point

Saddle points are defined for two-person differential games in which the players have opposing preference orderings over lotteries on a set of qualitative objectives, rather than numerical payoff functions. A simple example is then given of a game without such a qualitative saddle point.     

On a linear pursuit game with an unknown trap

A linear pursuit game with a trap, the location of which is unknown to the evader, is defined and investigated. The cases in which one of the players has complete energy dominance over his adversary are solved completely. In the general case, when no player dominates, the solution is indicated for the two-stage game.This research was supported in part by the Technion Fund for promotion of research.     

Majority judgment over a convex candidate space

Most voting methods can only deal with a finite number of candidates. In practice, there are important voting applications where the candidate space is continuous. We describe a new voting method by extending the Majority Judgment voting and ranking method to handle a continuous candidate space which is modeled as a convex set. We characterize the structure of the winner determination problem and present a practical iterative voting procedure for finding a (or the) winner when voter preferences are unknown.     

Repeated newsvendor game with transshipments under dual allocations

We study a repeated newsvendor game with transshipments. In every period n retailers face a stochastic demand for an identical product and independently place their inventory orders before demand realization. After observing the actual demand, each retailer decides how much of her leftover inventory or unsatisfied demand she wants to share with the other retailers. Residual inventories are then transshipped in order to meet residual demands, and dual allocations are used to distribute residual profit. Unsold inventories are salvaged at the end of the period. While in a single-shot game retailers in an equilibrium withhold their residuals, we show that it is a subgame-perfect Nash equilibrium for the retailers to share all of the residuals when the discount factor is large enough and the game is repeated infinitely many times. We also study asymptotic behavior of the retailers’ order quantities and discount factors when n is large. Finally, we provide conditions under which a system-optimal solution can be achieved in a game with n retailers, and develop a contract for achieving a system-optimal outcome when these conditions are not satisfied.     

Proportional navigation and the game of two cars

A stochastic version of Isaacs's game of two cars is considered. The motion of the players is confined to the pursuer's effective operation zoneD _P, and the cost function of the game is the probability of the event: {Before the evader enters his safe zone, the evader enters the pursuer's killing zoneK _P, at somet, 0tT, or the evader stays at the domainD _P–K _P, for allt[0,t ₀],t ₀>T}. By numerically solving a nonlinear parabolic boundary-value problem on a generalized torus in ³, it is shown that, for a range of values of some parameter, a proportional navigation guidance law is an optimal feedback pursuit strategy.     

Hedging of game options in discrete markets with transaction costs

Game options introduced in [10] in 2000 were studied, by now, mostly in frictionless both complete and incomplete markets. In complete markets the fair price of a game option coincides with the value of an appropriate Dynkin's game, whereas in markets with friction and in incomplete ones there is a range of arbitrage free prices and superhedging comes into the picture. Here we consider game options in general discrete time markets with transaction costs and construct backward and forward induction algorithms for the computation of their prices and superhedging strategies from both seller's (upper arbitrage free price) and buyer's (lower arbitrage free price) points of view extending to the game options case most of the results from [12].     

A game locating a needle in a circular haystack

A complete solution of the following Hider-Seeker zero-sum game is obtained. The hider hides a needle of lengtha, 0<a2, in the closed unit dise, and the seeker tries to locate it by shooting in a straight line across the disc. The payoff to the seeker is 1 if he hits the needle and 0 otherwise.     

Closed-loop Stackelberg solution to a multistage linear-quadratic game

A new solution of a two-person, nonzero-sum Stackelberg game, with linear dynamics, quadratic performance criteion, and closed-loop information available to both players, is presented. This solution is applicable to all problems where the leader is able to influence the objective function of the follower, and this function is strictly convex with respect to the control variable handled by the follower. The resulting equilibrium strategies adapt to the possible nonoptimal behavior of players at some stages of the game. The strategy of the leader has a simple interpretation of a threat formulated by the leader toward the follower and, if necessary, carried out one stage after the follower has played inconsistently with the leader's wishes.     

A game locating a needle in a square haystack

The following hider-seeker zero-sum game is considered. The hider hides a needle of length , in the closed unit square, and the seeker tries to locate it by shooting in a straight line across the square. The payoff to the seeker is 1 if he hits the needle and 0 otherwise.A solution of the game is obtained when or whena lies in either of the intervals and ; in addition, it is shown that, whenn is a positive integer anda=1/n, the value of the game is 1/2n. The properties of the solutions are in marked contrast to those for the analogous game over the closed unit disc, which the authors solved in a previous paper, and suggest that a complete solution may well be difficult. It is also shown that every member of a whole class of haystack games has a value.