Probabilistic Choice in Games: Properties of Rosenthal’s t-Solutions

The t-solutions introduced in R. W. Rosenthal (1989, Int J Game Theory 18:273–292) are quantal response equilibria based on the linear probability model. Choice probabilities in t-solutions are related to the determination of leveling taxes in taxation problems. The set of t-solutions coincides with the set of Nash equilibria of a game with quadratic control costs. Evaluating the set of t-solutions for increasing values of t yields that players become increasingly capable of iteratively eliminating never-best replies and eventually only play rationalizable actions with positive probability. These features are not shared by logit quantal response equilibria. Moreover, there exists a path of t-solutions linking uniform randomization to Nash equilibrium     

Weak acyclic coloring and asymmetric coloring games

We introduce the notion of weak acyclic coloring of a graph. This is a relaxation of the usual notion of acyclic coloring which is often sufficient for applications. We then use this concept to analyze the (a,b)-coloring game. This game is played on a finite graph G, using a set of colors X, by two players Alice and Bob with Alice playing first. On each turn Alice (Bob) chooses a (b) uncolored vertices and properly colors them with colors from X. Alice wins if the players eventually create a proper coloring of G; otherwise Bob wins when one of the players has no legal move. The (a,b)-game chromatic number of G, denoted (a,b)-χ_g(G), is the least integer t such that Alice has a winning strategy when the game is played on G using t colors. We show that if the weak acyclic chromatic number of G is at most k then (2,1)-.     

A PGM framework for recursive modeling of players in simple sequential Bayesian games

We consider the situation where two agents try to solve each their own task in a common environment. In particular, we study simple sequential Bayesian games with unlimited time horizon where two players share a visible scene, but where the tasks (termed assignments) of the players are private information. We present an influence diagram framework for representing simple type of games, where each player holds private information. The framework is used to model the analysis depth and time horizon of the opponent and to determine an optimal policy under various assumptions on analysis depth of the opponent. Not surprisingly, the framework turns out to have severe complexity problems even in simple scenarios due to the size of the relevant past. We propose two approaches for approximation. One approach is to use Limited Memory Influence Diagrams (LIMIDs) in which we convert the influence diagram into a set of Bayesian networks and perform single policy update. The other approach is information enhancement, where it is assumed that the opponent in a few moves will know your assignment. Empirical results are presented using a simple board game.     

A dynamic solution in N-person cooperative game theory

We formulate a cooperative game as an extended form game in which each player in turn proposes payoffs to a coalition over M steps. Payoffs at time t are discounted by a penalty function f(t). If all players in a coalition agree to their payoffs, they receive them. Under a convergence hypothesis verified by computer for three players in many cases, we compute the payoffs resulting from a coalition pattern and give necessary conditions for particular patterns. The resulting solution is related to the Nash bargaining solution and the competitive solution.     

Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story

Let C_n,cn^2,k,t be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions. We establish upper bounds for the tightness threshold for C_n,cn^2,k,t to have an exponential resolution complexity. The upper bounds partly answers the open problems regarding the CSP resolution complexity with the tightness between the existing upper and lower bound [1].     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

Differential games with Lipschitz control functions and fixed initial control positions

Differential games in which one or both players are restricted to choosing control functions which are uniformly Lipschitz continuous and which start at fixed initial conditions always have a value. We derive the Hamilton-Jacobi equation which this value satisfies a.e. as a function of the initial time t, the initial state x, and the initial control positions. We also show that a “Lipschitz Game” has an approximate saddle point in pure strategies. The approach of Friedman to differential games is used.     

On supercyclicity of operators from a supercyclic semigroup

We show that for every supercyclic strongly continuous operator semigroup {Tt}_t?0 acting on a complex F-space, every Tt with t>0 is supercyclic. Moreover, the set of supercyclic vectors of each Tt with t>0 is exactly the set of supercyclic vectors of the entire semigroup.     

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.     

A new construction for Hadamard matrices of orders 8t + 4

In Hadamard matrices of orders 8t + 4, there are usually four rows which agree on exactly one column. In fact, for t = 0, 1, 2 such a “Hall set” always occurs. This is obvious for t = 0, 1 and Hall has shown this for t = 2. When t = 3, the evidence indicates that nearly all H(28) have a Hall set. (Nearly the opposite seems to be true for matrices H(8t).) If a Hall set is assumed to exist for some H and some t, the remaining rows fall into 4 sets which determine 16 submatrices of order t. Several well-known techniques may be applied to such a configuration, and give immediate examples for t = 1, 2, 3, 4.     

Rational approximations of trigonometric matrices with application to second-order systems of differential equations

We consider the direct treatment of the second-order system of equations y” (t)+ Ay(t) = tf;(t), such as might arise in finite-element or finite-difference semidiscretizations of the wave equation. We develop the exact solution and some three-term recurrences involving trigonometric matrices. We approximate these trigonometric matrices by rational approximants of Padé type and thus develop a two-parameter family of approximation schemes. We analyze the stability behavior and computational complexity of members of this family and isolate four schemes for numerical experimentation, the results of which we tabulate. We single out as particularly effective the classical Stormer-Numerov method and also a new sixth-order scheme.     

Population solidarity, population fair-ranking, and the egalitarian value

We investigate the implications of two axioms specifying how a value should respond to changes in the set of players for TU games. Population solidarity requires that the arrival of new players should affect all the original players in the same direction: all gain together or all lose together. On the other hand, population fair-ranking requires that the arrival of new players should not affect the relative positions of the original players. As a result, we obtain characterizations of the egalitarian value, which assigns to each player an equal share over an individual utility level. It is the only value satisfying either one of the two axioms together with efficiency, symmetry and strategic equivalence.     

Max-algebraic attraction cones of nonnegative irreducible matrices

It is known that the max-algebraic powers A^r of a nonnegative irreducible matrix are ultimately periodic. This leads to the concept of attraction cone Attr(A, t), by which we mean the solution set of a two-sided system λ^t(A)A^r⊗x=A^r+t⊗x, where r is any integer after the periodicity transient T(A) and λ(A) is the maximum cycle geometric mean of A. A question which this paper answers, is how to describe Attr(A,t) by a concise system of equations without knowing T(A). This study requires knowledge of certain structures and symmetries of periodic max-algebraic powers, which are also described. We also consider extremals of attraction cones in a special case, and address the complexity of computing the coefficients of the system which describes attraction cone.     

Algorithms and the calculation of Nash equilibria for multi-objective control of time-discrete systems and polynomial-time algorithms for dynamic c-games on networks

We consider a multi-objective control problem of time-discrete systems with given starting and final states. The dynamics of the system are controlled by p actors (players). Each of the players intends to minimize his own integral-time cost of the system’s transitions using a certain admissible trajectory. Nash Equilibria conditions are derived and algorithms for solving dynamic games in positional form are proposed in this paper. The existence theorem for Nash equilibria is related to the introduction of an auxiliary dynamic c-game. Stationary and non-stationary cases are described. The paper concludes with a complexity analysis for that decision process.     

Construction of universal one-way hash functions: Tree hashing revisited

We present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t?2, our algorithm extends the domain from the set of all n-bit strings to the set of all ((2^t-1)(n-m)+m)-bit strings, where m is the length of the message digest. The associated increase in key length is 2m bits for t=2; m(t+1) bits for 3?t?6 and m×(t+⌊log₂(t-1)⌋) bits for t?7.     

Multiparameter perturbation theory of Fredholm operators applied to bloch functions

In the present paper, a family of linear Fredholm operators depending on several parameters is considered. We implement a general approach, which allows us to reduce the problem of finding the set Λ of parameters t = (t ₁, ..., t _n ) for which the equation A(t)u = 0 has a nonzero solution to a finite-dimensional case. This allows us to obtain perturbation theory formulas for simple and conic points of the set Λ by using the ordinary implicit function theorems. These formulas are applied to the existence problem for the conic points of the eigenvalue set E(k) in the space of Bloch functions of the two-dimensional Schrödinger operator with a periodic potential with respect to a hexagonal lattice.     

Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths

Given arbitrary source and target nodes s, t and an s–t-flow defined by its flow-values on each arc of a network, we consider the problem of finding a decomposition of this flow with a minimal number of s–t-paths. This problem is issued from the engineering of telecommunications networks for which the task of implementing a routing solution consists in integrating a set of end-to-end paths. We show that this problem is NP-hard in the strong sense and give some properties of an optimal solution. We then propose upper and lower bounds for the number of paths in an optimal solution. Finally we develop two heuristics based on the properties of a special set of solutions called saturating solutions.     

A chain of evolution algebras

We introduce a notion of chain of evolution algebras. The sequence of matrices of the structural constants for this chain of evolution algebras satisfies an analogue of Chapman-Kolmogorov equation. We give several examples (time homogenous, time non-homogenous, periodic, etc.) of such chains. For a periodic chain of evolution algebras we construct a continuum set of non-isomorphic evolution algebras and show that the corresponding discrete time chain of evolution algebras is dense in the set. We obtain a criteria for an evolution algebra to be baric and give a concept of a property transition. For several chains of evolution algebras we describe the behavior of the baric property depending on the time. For a chain of evolution algebras given by the matrix of a two-state evolution we define a baric property controller function and under some conditions on this controller we prove that the chain is not baric almost surely (with respect to Lebesgue measure). We also construct examples of the almost surely baric chains of evolution algebras. We show that there are chains of evolution algebras such that if it has a unique (resp. infinitely many) absolute nilpotent element at a fixed time, then it has unique (resp. infinitely many) absolute nilpotent element any time; also there are chains of evolution algebras which have not such property. For an example of two dimensional chain of evolution algebras we give the full set of idempotent elements and show that for some values of parameters the number of idempotent elements does not depend on time, but for other values of parameters there is a critical time t_c such that the chain has only two idempotent elements if time t?t_c and it has four idempotent elements if time t<t_c.     

Fictitious play applied to sequences of games and discounted stochastic games

In this paper, we show that the iterative method of Brown and Robinson, for solving a matrix game, is also applicable to a converging sequence of matrices, where the players choose at staget a row and a column of thet-th matrix in the sequence. As an application of this result, we describe a new solution method for discounted stochastic games with finite state and action spaces.     

The set of periodic scalar differential equations with cubic nonlinearities

We study the structure induced by the number of periodic solutions on the set of differential equations x^′=f(t,x) where f∈C³(R²) is T-periodic in t, fx³(t,x)<0 for every (t,x)∈R², and f(t,x)→?∞ as x→∞, uniformly on t. We find that the set of differential equations with a singular periodic solution is a codimension-one submanifold, which divides the space into two components: equations with one periodic solution and equations with three periodic solutions. Moreover, the set of differential equations with exactly one periodic singular solution and no other periodic solution is a codimension-two submanifold.