Search

The problem of consistency of a solution over time remains an important issue in cooperative dynamic games. Payoffs to players prescribed by an inconsistent solution may not be achievable since such a solution is extremely sensitive to its revision in the course of a game developing along an agreed upon cooperative behavior. The paper proposes a strong time-consistent payment scheme which is stable to a revision of cooperative set solutions, e.g., the core. Using a linear transformation of the solution, it becomes possible to obtain non-negative payments to players. In the paper, we also deal with a limit linear transformation of the solution whose convergence is proved. Developing a non-negative strong time-consistent payment scheme in a closed form, we guarantee that the solution supported by the scheme will not be revised over time. [ABSTRACT FROM AUTHOR]

Abstract In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if C a minimum edge cut of a connected graph G , then γ g (G) ≤ γ g (G ∖ C) + 2 κ ′ (G). Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved. [ABSTRACT FROM AUTHOR]

Abstract This paper introduces a new variant of the game Nim–Bounded Greedy Nim. This game is a combination of Bounded Nim and Greedy Nim. We present a complete solution to this game, which generalizes the solution of Greedy Nim. [ABSTRACT FROM AUTHOR]

In Guy and Nowakowski’s Unsolved Problems in Combinatorial Games , the following entry is found: “David Gale would like to see an analysis of Nim played with the option of a single pass by either of the players, which may be made at any time up to the penultimate move. It may not be made at the end of the game. Once a player has passed, the game is as in ordinary Nim. The game ends when all heaps have vanished.” This paper investigates the n -person combinatorial game of “Small Nim with Passes”, a variant of Nim, where players must always remove objects from the smallest nonempty pile and are allowed to “pass” their turn for a finite number of times. Let N be the number of piles in the game. When the number of players is greater than N + 1 , we determine all game values for all possible positions. The game values are determined completely when the number of players is equal to N + 1 . We also analyze certain cases of positions when the number of players is smaller than N + 1 , and leave some open problems that could be of interest to future research. [ABSTRACT FROM AUTHOR]

In this paper, we study four games, they are all restrictions of ( s , t ) -Wythoff’s game which was introduced by A.S. Fraenkel. The first one is a modular type restriction of ( s , t ) -Wythoff’s game, where a player is restricted to remove a multiple of K tokens in each move ( K is a fixed positive integer). The others we called rook type restrictions of ( s , t ) -Wythoff’s game, including Odd-Arbitrary-Nim ( s , t ) -Wythoff’s Game, Odd–Odd-Nim ( s , t ) -Wythoff’s Game and Odd–Even-Nim ( s , t ) -Wythoff’s Game. In these three games, the restrictions are only made on horizontal and vertical moves, but not on the extended diagonal moves. For any K , s , t ≥ 1 , the sets of P -positions of our games are given in both normal and misère play. [ABSTRACT FROM AUTHOR]

The lazy cop number is the minimum number of cops needed for the cops to have a winning strategy in the game of Cops and Robbers where at most one cop may move in any round. This variant of the game of Cops and Robbers, called Lazy Cops and Robbers, was introduced by Offner and Ojakian, who provided bounds for the lazy cop number of the hypercube. In this paper, we are interested in the game of Lazy Cops and Robbers on generalized hypercubes. Generalizing existing methods, we will give asymptotic upper and lower bounds on the lazy cop number of the generalized hypercube. [ABSTRACT FROM AUTHOR]

Let γ : E ( G ) ⟶ N ∗ = N ∖ { 0 } be an edge colouring of a graph G and σ γ : V ( G ) ⟶ N ∗ the vertex colouring given by σ γ ( v ) = ∑ e ∋ v γ ( e ) for every v ∈ V ( G ) . A neighbour-sum-distinguishing edge-colouring of G is an edge colouring γ such that for every edge u v in G , σ γ ( u ) ≠ σ γ ( v ) . The neighbour-sum-distinguishing edge-colouring game on G is the 2-player game defined as follows. The two players, Alice and Bob, alternately colour an uncoloured edge of G . Alice wins the game if, when all edges are coloured, the so-obtained edge colouring is a neighbour-sum-distinguishing edge-colouring of G . Otherwise, Bob wins. In this paper we study the neighbour-sum-distinguishing edge-colouring game on various classes of graphs. In particular, we prove that Bob wins the game on the complete graph K n , n ≥ 3 , whoever starts the game, except when n = 4 . In that case, Bob wins the game on K 4 if and only if Alice starts the game. [ABSTRACT FROM AUTHOR]

Abstract: This paper introduces a new combinatorial game, named XT Domineering, together with its mathematical analysis. XT Domineering is modified from the Domineering game in which 1×2 or 2×1 dominos are allowed to be placed on empty squares in an m × n board. This new game allows a player to place a 1×1 domino on an empty square s while unable to place a 1×2 or 2×1 domino in the connected group of empty squares that includes s. After modifying the rule, each position in the game becomes an infinitesimal. This paper calculates the game values of all sub-graphs of 3×3 squares and shows that each sub-graph of 3×3 squares is a linear combination of 8 elementary infinitesimals. These pre-stored game values can be viewed as a knowledge base for playing XT Domineering. Instead of searching the whole game trees, a simple rule for determining the optimal outcome of any sum of these positions is presented. [Copyright &y& Elsevier]

Abstract: This paper is concerned with a class of reflected backward stochastic differential equations (RBSDEs in short) with two barriers. The first purpose of the paper is to establish existence and uniqueness results of adapted solutions for such RBSDEs. Most of existing results on adapted solutions for RBSDEs with two barriers are heavily based on either the Mokobodski condition or other restrictive regularity conditions. In this paper, the two barriers are modeled by stochastic differential equations with coefficients satisfying the local Lipschitz condition and the linear growth condition, which enables us to weaken the regularity conditions on the boundary processes. Existence is proved by a penalization scheme together with a comparison theorem under the Lipschitz condition on the coefficients of RBSDEs. As an application, it is proved that the initial value of an RBSDE with two barriers coincides with the value function of a certain Dynkin game under Knightian uncertainty. [Copyright &y& Elsevier]

In this paper, we analyze a few opinion formation or election game dynamics models. For a simple model with two subpopulations with opposing opinions A and B , if the fraction of committed believers of opinion A (“ A zealots”) is less than a critical value, then the system has two bistable equilibrium points. When the fraction is equal to the critical value, the system undergoes a saddle-node bifurcation. When the fraction is larger than the critical value, a boundary equilibrium point is globally asymptotically stable, suggesting that the entire population reaches a consensus on A . We find a similar bistability property in the model in which both opinions have their own zealots. We also extend the model to include multiple competitors and show the dynamical behavior of multistability. The more competitors subpopulation A has, the fewer zealots opinion A needs to obtain consensus. [ABSTRACT FROM AUTHOR]

We consider biased ( 1 : b ) Walker–Breaker games: Walker and Breaker alternately claim edges of the complete graph K n , Walker taking one edge and Breaker claiming b edges in each round, with the constraint that Walker needs to choose her edges according to a walk. As questioned in a paper by Espig, Frieze, Krivelevich and Pegden, we study how long a cycle Walker is able to create and for which biases b Walker has a chance to create a cycle of given constant length. [ABSTRACT FROM AUTHOR]

Abstract: There have been several papers on the subject of traditional peg solitaire on different boards. However, in this paper we consider a generalization of the game to arbitrary boards. These boards are treated as graphs in the combinatorial sense. We present necessary and sufficient conditions for the solvability of several well-known families of graphs. In the major result of this paper, we show that the cartesian product of two solvable graphs is likewise solvable. Several related results are also presented. Finally, several open problems related to this study are given. [Copyright &y& Elsevier]

Abstract: This paper extends two existent methods, called the blockability relation and the viability relation, for simple games to compare influence of coalitions, to those for games in characteristic function form, and shows that the newly defined relations satisfy transitivity and completeness. It is shown in this paper that for every game in characteristic function form the blockability relation and the viability relation have a complementary interrelationship. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze ternary bicooperative games, which are a refinement of the concept of a ternary voting game introduced by Felsenthal and Machover. Furthermore, majority voting rules based on the difference of votes are simple bicooperative games. First, we define the concepts of the defender and detractor swings for a player. Next, we introduce the Banzhaf power index and the normalized Banzhaf power index. The main result of the paper is an axiomatization of the Banzhaf power index for the class of ternary bicooperative games. Moreover, we study ternary bicooperative games with two lists of weights and compute the Banzhaf power index using generating functions. [Copyright &y& Elsevier]

Abstract: This paper proposes a method to compare bargaining power of coalitions within the framework of games in coalition form with transferable utility. The method is expressed by a relation on the set of all coalitions in a game, the relation which is defined based on the players’ bargaining power. It is shown in this paper that the newly defined relation satisfies acyclicity. Also, it is verified in this paper that the set of all individually rational payoff configurations under which all coalitions have the equal bargaining power coincides with the bargaining set. Some examples demonstrate how the newly proposed method works. [Copyright &y& Elsevier]

Abstract: This paper shows some elementary facts on simple games with respect to blockability relations. It is verified in this paper that fundamental concepts on simple games as null players, dictators, veto players, and so on can be expressed in terms of blockability relations. More, some new concepts as “conflict-free” and so on, are introduced from the viewpoint of blockability relations into the framework of simple games. [Copyright &y& Elsevier]

In this paper we study the computational complexity of a generalized version of the logic puzzle Pete's Pike by Thinkfun [14] . It is shown that generalized Pete's Pike is PSPACE-complete. Moreover, we construct an infinite family of initial configurations with the property that the length of a shortest solution is superpolynomial in the size of the game. [ABSTRACT FROM AUTHOR]

An n - multigraph G = ( V ; E i ∣ i ∈ I ) is a complete graph G = ( V , E ) whose edges are covered by n = | I | sets, E = ∪ i ∈ I E i , some of which might be empty. If this cover is a partition, then G is called an n - graph . We say that an n -graph G ′ = ( V ; E i ′ ∣ i ∈ I ) is an edge subgraph of an n -multigraph G = ( V ; E i ∣ i ∈ I ) if E i ′ ⊆ E i for all i ∈ I . We denote by Δ the n -graph on three vertices with three nonempty sets each containing a single edge, and by Π the four-vertex n -graph with two non-empty sets each of which contains the edges of a P 4 . In this paper, we recognize in polynomial time whether a given n -multigraph G contains a Π - and Δ -free n -subgraph, or not, and if yes, provide a polynomial delay algorithm generating all such subgraphs. The above decision problem can be viewed as a generalization of the sandwich problem for P 4 -free graphs solved by Golumbic et al. (1995). As a motivation and application, we consider the n -person positional game forms, which are known to be in a one-to-one correspondence with the Π - and Δ -free n -graphs. Given a game form g , making use of the above result, we recognize in polynomial time whether g is a subform of a positional (that is, tight and rectangular) game form and, if yes, we generate with polynomial delay all such positional extensions of g . [ABSTRACT FROM AUTHOR]

Baker and Norine introduced a graph-theoretic analogue of the Riemann–Roch theory. A central notion in this theory is the rank of a divisor. In this paper we prove that computing the rank of a divisor on a graph is NP -hard, even for simple graphs. The determination of the rank of a divisor can be translated to a question about a chip-firing game on the same underlying graph. We prove the NP -hardness of this question by relating chip-firing on directed and undirected graphs. [ABSTRACT FROM AUTHOR]

The main purpose of the paper is the proof of a cardinal inequality for a space with points G δ , obtained with the help of a long version of the Menger game. This result improves a similar one of Scheepers and Tall. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of function spaces equipped with topologies of (strong) uniform convergence on bornologies initiated by Beer and Levi [3] . In particular, we investigate some topological properties these function spaces defined by topological games. In addition, we also give further characterizations of metrizability and completeness properties of these function spaces. [ABSTRACT FROM AUTHOR]

This paper studies the incentives for alliance (coalition) formation. It provides an example of an alliance that leads to unlimited seat gains. A full description of a set that guarantees the lack of successful alliance is found. The probability of the lack of successful alliances is evaluated. A game-theoretical approach for alliance formation is applied. [ABSTRACT FROM AUTHOR]

Abstract: This paper discusses the game coloring number of planar graphs. Let be a planar graph and let be the game coloring number of . We prove that is at most 13 if is a planar graph with girth at least 4. We also show that there is a planar graph with girth 4 such that and there is a planar graph with girth 5 such that . [Copyright &y& Elsevier]

Abstract: The problem is to determine the number of ‘cops’ needed to capture a ‘robber’ in a game in which the cops always know the location of the robber, and the cops and robber move alternately along edges of a reflexive graph. The cops capture the robber if one of them occupies the same vertex as the robber at any time in the game. A cop-win graph is one in which a single cop has a winning strategy. A graph is cop-win edge-critical with respect to edge addition (respectively, deletion) when the original graph is not cop-win, but the addition (deletion) of any edge results in a cop-win graph. In this paper, edge-critical planar graphs are characterized. [Copyright &y& Elsevier]

Abstract: For the multi-agent spatial Parrondo’s games, the available theoretical analysis methods based on the discrete-time Markov chain were assumed that the losing and winning states of an ensemble of players were represented to be the system states. The number of system states was types. However, the theoretical calculations could not be carried out when became much larger. In this paper, a new theoretical analysis method based on the discrete-time Markov chain is proposed. The characteristic of this approach is that the system states are described by the number of winning individuals of all the individuals. Thus, the number of system states decreases from types to types. In this study, game and game based on the one-dimensional line and the randomized game are theoretically analyzed. Then, the corresponding transition probability matrixes, the stationary distribution probabilities and the mathematical expectations are derived. Moreover, the conditions and the parameter spaces where the strong or weak Parrondo’s paradox occurs are given. The calculation results demonstrate the feasibility of the theoretical analysis when is larger. [Copyright &y& Elsevier]

Abstract: Minesweeper is a popular single player game. Various strategies have been suggested in order to improve the probability of winning the game. In this paper, we present an optimal strategy for playing Minesweeper on a graph when it is known that exactly one cell is mined. [Copyright &y& Elsevier]

Abstract: In this paper, we study average monotonic fuzzy games—a subclass of monotonic cooperative fuzzy games, and prove that for a continuous average monotonic cooperative fuzzy game which has a crisp maximal coalition of maximum excess at every imputation, its Aubin core coincides with its fuzzy bargaining set. [Copyright &y& Elsevier]

Abstract: On-line Ramsey theory studies a graph-building game between two players. The player called Builder builds edges one at a time, and the player called Painter paints each new edge red or blue after it is built. The graph constructed is the host graph. Builder wins the game if the host graph at some point contains a monochromatic copy of a given goal graph. In the -game variant of the typical game, the host graph is constrained to have maximum degree no greater than . The on-line degree Ramsey number of a graph is the minimum such that Builder wins an -game in which is the goal graph. In this paper, we complete the investigation begun by Butterfield et al. into the on-line degree Ramsey numbers of -cycles. Namely, we show that for . [Copyright &y& Elsevier]

Abstract: In Parrondo’s paradox, a winning strategy is formed either by playing two losing games randomly or alternating them periodically. The paradox is commonly analyzed using stochastic matrices. In this paper, we modify the stochastic matrices to allow a more systematic introduction of bias into fair processes, while retaining the use of simple matrix operations throughout the analysis. [Copyright &y& Elsevier]

Abstract: Sharing damage that has been caused jointly by several tortfeasors is analyzed from a normative point of view. We show how damage can be apportioned on two distinct bases: causation and degree of misconduct. Our analysis uses the concept of potential damage on the basis of which we define a transferable utility game. Its core defines acceptable judgments as allocations of the total damage against which no group of tortfeasors can object. We show that weighted Shapley values define acceptable judgments and, vice versa, acceptable judgments reveal weights. Our paper illustrates how the cooperative approach may bring useful insights into legal questions. In particular, the Shapley value appears of special interest, being founded on axioms that are in line with fundamental principles of tort law. [Copyright &y& Elsevier]

Abstract: Graph pebbling is the study of whether pebbles from one set of vertices can be moved to another while pebbles are lost in the process. A number of variations on the theme have been presented over the years. In this paper we provide a common framework for studying them all, and present the main techniques and results. Some new variations are introduced as well and open problems are highlighted. [Copyright &y& Elsevier]

Abstract: In this paper, we study the strong game colouring number of directed graphs. It is proved that every oriented partial 2-tree has strong game colouring number at most 7 and every oriented planar graph has strong game colouring number at most 15. [Copyright &y& Elsevier]

Abstract: In the analysis of cooperative stochastic dynamic games a stringent condition–subgame consistency–is required for a dynamically stable solution. A cooperative solution is subgame consistent if an extension of the solution policy to a subgame starting at a later time with a feasible state brought about by prior optimal behavior would remain optimal. This paper considers subgame consistent cooperative solutions in randomly furcating stochastic discrete-time dynamic games. Analytically tractable payoff distribution procedures contingent upon specific random realizations of the state and payoff structures are derived. In computer modeling and operations research discrete-time analysis often proved to be more applicable and compatible with actual data than continuous-time analysis. This is the first time that a subgame consistent solution for randomly-furcating stochastic dynamic games has been obtained. It widens the application of cooperative dynamic game theory to discrete-time problems where the evolution of the state and future payoff structures are not known with certainty. [Copyright &y& Elsevier]

Abstract: In this paper we propose methods to compute the Deegan-Packel, the Public Good, and the Shift power indices by generating functions for the particular case of weighted voting games. Furthermore, we define a new power index which combines the ideas of the Shift and the Deegan-Packel power indices and also propose a method to compute it with generating functions. We conclude by some comments about the complexity to compute these power indices. [Copyright &y& Elsevier]

Abstract: The sudoku completion problem is a special case of the latin square completion problem and both problems are known to be NP-complete. However, in the case of a rectangular hole pattern–i.e. each column (or row) is either full or empty of symbols–it is known that the latin square completion problem can be solved in polynomial time. Conversely, we prove in this paper that the same rectangular hole pattern still leaves the sudoku completion problem NP-complete. [Copyright &y& Elsevier]

Abstract: In this paper, a time-varying control problem is solved for a class of linear quantum systems using a dynamic game approach. The methodology adopted involves an equivalence between the quantum problem and an auxiliary classical stochastic problem. Then, by solving the time-varying control problem for the equivalent stochastic systems using some results from a corresponding deterministic problem, following a dynamic game approach, the time-varying control problem for the class of linear quantum systems under consideration is solved. [Copyright &y& Elsevier]

Abstract: Let be a graph and let be a positive integer. Consider the following two-person game which is played on : Alice and Bob alternate turns. A move consists of selecting an unlabeled vertex of and assigning it a number from satisfying the condition that, for all is labeled by the number previously, if , then , and if , then . Alice wins if all the vertices of are successfully labeled. Bob wins if an impasse is reached before all vertices in the graph are labeled. The game -labeling number of a graph is the least for which Alice has a winning strategy. We use to denote the game -labeling number of in the game Alice plays first, and use to denote the game -labeling number of in the game Bob plays first. In this paper, we study the game -labeling numbers of graphs. We give formulas for and , and give formulas for for those with . [Copyright &y& Elsevier]

Abstract: The authors introduce new values which express coalition influence in the situation of coalition formation. Some examples which show how introduced values work are given. Propositions in this paper provide some properties that proposed values satisfy in the framework of games in characteristic function form. [Copyright &y& Elsevier]

Abstract: Game theory has been applied extensively to interpret and solve the complex and interrelated practical decision problems. The solution for these problems depends on the goals pursued by different interested parties, i.e., problems as conflict situations. Decision making approaches based on game theory have been an important and promising research direction in decision science, as well as in real-world practice. Many research approaches within this direction have been developed, but most are limited to the real-valued domain. A great amount of non-real valued domain practical game decision problems, especially the lattice-valued game, remain largely unexplored. This paper investigates the lattice-valued matrix game (including the real-valued matrix game as a special case). For decision purposes, it is an essential and indispensable step in theoretical game decision approaches to find the solutions for a matrix game; hence this work focuses on how to determine solutions of lattice-valued matrix game for decision purposes. Firstly, based on the work on lattice-valued matrix game with pure strategy, a concept of multi-dimension lattice-valued-level strategy is introduced based on a new algebra structure called the l ∗-module, i.e., a lattice-ordered module with two lattice-ordered structures. Next, a concept of a mixed strategy lattice-valued matrix game is introduced and its basic properties are discussed. Finally, the necessary and sufficient condition for the existence of a solution for a mixed strategy lattice-valued matrix game is discussed, along with basic properties for the solution. The approaches and results discussed are mathematical in nature and entail fundamental research in the field of intelligent decision support. They will provide important and fundamental support for the application of a theoretical game approach in rational decisions for conflict situations, and also introduce a new branch of game-theory based decision approaches by extending real-valued game theory into lattice-value game theory. [Copyright &y& Elsevier]

Abstract: In this paper, the proper core and dominance core of a fuzzy game are introduced. To guarantee equality between the proper core and the dominance core, some mild conditions are provided. Another important issue for the convexity of the dominance core is also addressed. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce eight power indices that admit a probabilistic interpretation for voting rules with abstention or with three levels of approval in the input, briefly (3, 2) games. We analyze the analogies and discrepancies between standard known indices for simple games and the proposed extensions for this more general context. A remarkable difference is that for (3, 2) games the proposed extensions of the Banzhaf index, Coleman index to prevent action and Coleman index to initiate action become non-proportional notions, contrarily to what succeeds for simple games. We conclude the work by providing procedures based on generating functions for weighted (3, 2) games, and extensible to (j,k) games, to efficiently compute them. [Copyright &y& Elsevier]

Abstract: In this paper, we extend the concept of the almost convex condition and establish an approximation property for convex continuous correspondences. We use the approximation property to generalize von Neumann’s intersection theorems and related topics. We obtain, as applications, some new equilibrium theorems for the existence of a maximal element, generalized games, and qualitative games of -majorized correspondences. [Copyright &y& Elsevier]

Abstract: Suppose Alice gambles with God who is the dealer. There are total rounds in the game and God can choose any rounds to win and the other rounds to lose. At first Alice has holdings . In each round, Alice can increase her holdings by times the amount she wagers if she wins. So what strategy should Alice take to ensure the maximum total holdings in the end? And how much is the total final holdings? It is called the “Gambling with God” problem. In this paper, a recursive method is proposed to solve the problem, which shows the extensive application of recursive methods. [Copyright &y& Elsevier]

Abstract: It was recently shown that every totally tight two-person game form is acyclic, dominance-solvable, and hence, Nash-solvable too. In this paper, we exhibit an example showing that the first two implications fail for the three-person () game forms. Yet, we show that the last one (total tightness implies Nash-solvability) still holds for leaving the case open. [Copyright &y& Elsevier]

Abstract: In this paper, maximal element theorem on Hadamard manifolds is established. First, we prove the existence of solutions for maximal element theorem on Hadamard manifolds. Further, we prove that most of problems in maximal element theorem on Hadamard manifolds (in the sense of Baire category) are essential and that, for any problem in maximal element theorem on Hadamard manifolds, there exists at least one essential component of its solution set. As applications, we study existence and stability of solutions for variational relation problems on Hadamard manifolds, and existence and stability of weakly Pareto–Nash equilibrium points for -person multi-objective games on Hadamard manifolds. [Copyright &y& Elsevier]

Abstract: The recent application of the diagonal dominance in the development of the optimization algorithms in the wireless sensor networks design, has been done by Yuan and Yu (2006) , extended in Yu et al. (2006) , and surveyed in Machado and Tekinay . In this paper, we will use the concept of generalized diagonal dominance, to improve the obtained results regarding the power control game, in three directions. We also discuss the applicability of such improvements. [Copyright &y& Elsevier]