Strategies in competing subset selection

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential procedure consisting in a fixed number of rounds. In every round each agent submits one item that may be included in its solution set. We study two natural rules to decide which item between the two will be included. We address the problem from a strategic point of view, that is finding the best moves for one agent against the opponent, in two distinct scenarios. We consider preventive or minimax strategies, optimizing the objective of the agent in the worst case, and best-response strategies, where the items submitted by the opponent are known in advance in each round.     

On (strong) α-favorability of the Wijsman hyperspace

The Banach-Mazur game as well as the strong Choquet game are investigated on the Wijsman hyperspace from the nonempty player's (i.e. α's) perspective. For the strong Choquet game we show that if X is a locally separable metrizable space, then α has a (stationary) winning strategy on X iff it has a (stationary) winning strategy on the Wijsman hyperspace for each compatible metric on X. The analogous result for the Banach-Mazur game does not hold, not even if X is separable, as we show that α may have a (stationary) winning strategy on the Wijsman hyperspace for each compatible metric on X, and not have one on X. We also show that there exists a separable 1st category metric space such that α has a (stationary) winning strategy on its Wijsman hyperspace. This answers a question of Cao and Junnila (2010) [6].     

On (strong) α-favorability of the Vietoris hyperspace

For a normal space X, α (i.e. the nonempty player) having a winning strategy (resp. winning tactic) in the strong Choquet game Ch(X) played on X is equivalent to α having a winning strategy (resp. winning tactic) in the strong Choquet game played on the hyperspace CL(X) of nonempty closed subsets endowed with the Vietoris topology τ _V . It is shown that for a non-normal X where α has a winning strategy (resp. winning tactic) in Ch(X), α may or may not have a winning strategy (resp. winning tactic) in the strong Choquet game played on the Vietoris hyperspace. If X is quasi-regular, then having a winning strategy (resp. winning tactic) for α in the Banach-Mazur game BM(X) played on X is sufficient for α having a winning strategy (resp. winning tactic) in BM(CL(X), τ _V ), but not necessary, not even for a separable metric X. In the absence of quasi-regularity of a space X where α has a winning strategy in BM(X), α may or may not have a winning strategy in the Banach-Mazur game played on the Vietoris hyperspace.     

Proof and refutation in MALL as a game

We present a setting in which the search for a proof of B or a refutation of B (i.e., a proof of ¬B) can be carried out simultaneously: in contrast, the usual approach in automated deduction views proving B or proving ¬B as two, possibly unrelated, activities. Our approach to proof and refutation is described as a two-player game in which each player follows the same rules. A winning strategy translates to a proof of the formula and a counter-winning strategy translates to a refutation of the formula. The game is described for multiplicative and additive linear logic (MALL). A game theoretic treatment of the multiplicative connectives is intricate and our approach to it involves two important ingredients. First, labeled graph structures are used to represent positions in a game and, second, the game playing must deal with the failure of a given player and with an appropriate resumption of play. This latter ingredient accounts for the fact that neither player might win (that is, neither B nor ¬B might be provable).     

Bifurcation analysis of a non-cooperative differential game with one weak player

We study a bifurcation problem for a system of two differential equations in implicit form. For each value of the parameter θ, the solution yields a pair of Nash equilibrium strategies in feedback form, for a non-cooperative differential game. When θ=0, the second player has no power to influence the dynamics of the system, and his optimal strategy is myopic. The game thus reduces to an optimal control problem for the first player. By studying the bifurcation in the solutions to the corresponding system of Hamilton-Jacobi equations, one can establish existence and multiplicity of solutions to the differential game, as θ becomes strictly positive.     

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.     

On a class of balancing games

A balancing game is a perfect information two-person game. Given a set V?R^d, in the ith round Player I picks a vector vⁱ?V, and then Player II picks ?_i = +1 or ?1. Player II tries to minimize sup {| Σ_i=1ⁿ?_ivⁱ | : n = 0, 1, 2,…}. In this paper we generalize this game and give necessary and sufficient conditions for the existence of a winning strategy for Player I and Player II in the generalized game. Later we give upper and lower bounds to the value of the original game; the bounds in many cases are equal. Further we present simple strategies for both players.     

Atomic weights and the combinatorial game of bipass

We define an all-small ruleset, bipass, within the framework of normal play combinatorial games. A game is played on finite strips of black and white stones. Stones of different colors are swapped provided they do not bypass one of their own kind. We find a simple surjective function from the strips to integer atomic weights (Berlekamp, Conway and Guy 1982) that measures the number of units in all-small games. This result provides explicit winning strategies for many games, and in cases where it does not, it gives narrow bounds for the canonical form game values. We find game values for some parametrized families of games, including an infinite number of strips of value ?, and we prove that the game value ?2 does not appear as a disjunctive sum of bipass. Lastly, we define the notion of atomic weight tameness, and prove that optimal misére play bipass resembles optimal normal play.     

Rothberger bounded groups and Ramsey theory

We show that:

(1)

Rothberger bounded subgroups of σ-compact groups are characterized by Ramseyan partition relations (Corollary 4).

(2)

For each uncountable cardinal κ there is a T₀ topological group of cardinality κ such that ONE has a winning strategy in the point-open game on the group and the group is not a closed subspace of any σ-compact space (Theorem 8).

(3)

For each uncountable cardinal κ there is a T₀ topological group of cardinality κ such that ONE has a winning strategy in the point-open game on the group and the group is σ-compact (Corollary 17).

     

Multiple unit auctions with economies and diseconomies of scale

This paper discusses multiple unit auctions for industrial procurement where the cost structures of suppliers capture economies and diseconomies of scale caused by the nature of the production cost and the opportunity value of suppliers’ capacities. The problem of winner determination and demand allocation is proven to be NP-complete. We propose a binary tree algorithm with bounds (BTB) which efficiently exploits the model’s optimality properties. BTB outperforms general integer optimization software in computational time, especially with existence of substantial economies and diseconomies of scale. The algorithm complexity is linear in demand volume. This property allows for efficient handling of high volume auctions and thus leads to increased benefit for the overall system. Under the assumption of the myopic best response strategies, we investigate the behavior of suppliers and price dynamics for iterative (multiple round) bidding with appropriate allocation and stopping rules. The allocation rules, featured by several tie breakers for multiple optimal solutions to the allocation model in each round, are proposed to induce suppliers’ dominant strategies and to improve the system’s performance.     

Complexities of Winning Strategies in Diophantine Games

This paper considers the computational complexity of computing winning strategies in diophantine games, where two players take turns choosing natural numbers x₁, x₂, x₃, . . . , x_n and the win condition is a polynomial equation in the variables x₁, x₂, . . . , x_n. A diophantine game G₄ of length 4 is constructed with the propertythat neither player has a polynomial time computable winning strategy. Also a diophantine game G₆ of length 6 is constructed with the property that one of the players has a polynomial time computable winning strategy in G₆ iff P = NP. Finally a diophantine game N_b of length 6 is constructed such that one of the players has a polynomial time computable winning strategy in it iff co-NP = NP.     

A certain clifford-like algebra and quantum vertex algebras

We show a new game characterizing various types of σ-porosity for Souslin sets in terms of winning strategies. We use the game to prove and reprove some new and older inscribing theorems for σ-ideals of σ-porous type in locally compact metric spaces.     

Two-player Tower of Hanoi

The Tower of Hanoi game is a classical puzzle in recreational mathematics (Lucas 1883) which also has a strong record in pure mathematics. In a borderland between these two areas we find the characterization of the minimal number of moves, which is \(2^n-1\), to transfer a tower of n disks. But there are also other variations to the game, involving for example real number weights on the moves of the disks. This gives rise to a similar type of problem, but where the final score seeks to be optimized. We study extensions of the one-player setting to two players, invoking classical winning conditions in combinatorial game theory such as the player who moves last wins, or the highest score wins. Here we solve both these winning conditions on three pegs.     

Algebraic games—playing with groups and rings

Two players alternate moves in the following impartial combinatorial game: Given a finitely generated abelian group A, a move consists of picking some \(0 \ne a \in A\). The game then continues with the quotient group \(A/\langle a \rangle \). We prove that under the normal play rule, the second player has a winning strategy if and only if A is a square, i.e. \(A \cong B \times B\) for some abelian group B. Under the misère play rule, only minor modifications concerning elementary abelian groups are necessary to describe the winning situations. We also compute the nimbers, i.e. Sprague–Grundy values of 2-generated abelian groups. An analogous game can be played with arbitrary algebraic structures. We study some examples of non-abelian groups and commutative rings such as R[X], where R is a principal ideal domain.     

The complexity of node blocking for dags

We consider the following modification of annihilation games called node blocking. Given a directed graph, each vertex can be occupied by at most one token. There are two types of tokens, each player can move only tokens of his type. The players alternate their moves and the current player i selects one token of type i and moves the token along a directed edge to an unoccupied vertex. If a player cannot make a move then he loses. We consider the problem of determining the complexity of the game: given an arbitrary configuration of tokens in a planar directed acyclic graph (dag), does the current player have a winning strategy? We prove that the problem is PSPACE-complete.     

Optimal strategies for node selection games on oriented graphs: Skew matrices and symmetric games

In the node selection game Γ_D each of the two players simultaneously selects a node from the oriented graph D. If there is an arc between the selected nodes, then there is a payoff from the “dominated” player to the “dominating” player. We investigate the set of optimal strategies for the players in the node selection game Γ_D. We point out that a classical theorem from game theory relates the dimension of the polytope of optimal strategies for Γ_D to the nullity of certain skew submatrix of the payoff matrix for Γ_D. We show that if D is bipartite (with at least two nodes in each partite set), then an optimal strategy for the node selection game Γ_D is never unique. Our work also implies that if D is a tournament, then there is a unique optimal strategy for each player, a result obtained by Fisher and Ryan [Optimal strategies for a generalized “scissors, paper, and stone” game, Amer. Math. Monthly 99 (1992) 935–942] and independently by Laffond, Laslier, and Le Breton [The bipartisan set of a tournament game, Games Econom. Behav. 5 (1993) 182–201].     

Some undecidable determined games

Computing machines using algorithms play games and even learn to play games. However, the inherent finiteness properties of algorithms impose limitations on the game playing abilities of machines. M. Rabin illustrated this limitation in 1957 by constructing a two-person win-lose game with decidable rules but no computable winning strategies. Rabin's game was of the type where two players take turns choosing integers to satisfy some decidable but very complicated winning condition. In the present paper we obtain similar theorems of this type but the winning conditions are extremely simple relations (polynomial equations). Specific examples are given.     

Simple games and weighted games: A theoretical and computational viewpoint

It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough.We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve.     

Choosing fair lotteries to defeat the competition

We study the following game: each agent i chooses a lottery over nonnegative numbers whose expectation is equal to his budget b _i . The agent with the highest realized outcome wins (and agents only care about winning). This game is motivated by various real-world settings where agents each choose a gamble and the primary goal is to come out ahead. Such settings include patent races, stock market competitions, and R&D tournaments. We show that there is a unique symmetric equilibrium when budgets are equal. We proceed to study and solve extensions, including settings where agents choose their budgets (at a cost) and where budgets are private information.