Learning in multilevel games with incomplete information. I

A model is presented of learning automata playing stochastic games at two levels. The high level represents the choice of the game environment and corresponds to a group decision. The low level represents the choice of action within the selected game environment. Both of these decision processes are affected by delays in the information state due to inherent latencies or to the delayed broadcast of state changes. Analysis of the intrinsic properties of this Markov process is presented along with simulated iterative behavior and expected iterative behavior. The results show that simulation agrees with expected behavior for small step lengths in the iterative map. A Feigenbaum diagram and numerical computation of the Lyapunov exponents show that, for very small penalty parameters, the system exhibits chaotic behavior.     

不完全信息下开发商Markov博弈均衡的最优策略

房地产开发商对于资源的争夺存在零和博弈的特点,在信息不对称条件下对开发商经济博弈模型的研究具有重要价值。该研究考虑到市场上存在开发商Cartel联盟的情形,以Markov博弈模型为核心,针对不完全信息下的Cartel联盟与竞争者的Markov博弈均衡进行研究,得到了博弈双方的最优策略及演算方法。最后,利用实例对该模型的有效性和可行性进行了说明。     

Learning implicit information in Bayesian games with knowledge transfer

In this paper, we consider to learn the inherent probability distribution of types via knowledge transfer in a two-player repeated Bayesian game, which is a basic model in network security. In the Bayesian game, the attacker''s distribution of types is unknown by the defender and the defender aims to reconstruct the distribution with historical actions. It is difficult to calculate the distribution of types directly since the distribution is coupled with a prediction function of the attacker in the game model. Thus, we seek help from an interrelated complete-information game, based on the idea of transfer learning. We provide two different methods to estimate the prediction function in different concrete conditions with knowledge transfer. After obtaining the estimated prediction function, the defender can decouple the inherent distribution and the prediction function in the Bayesian game, and moreover, reconstruct the distribution of the attacker''s types. Finally, we give numerical examples to illustrate the effectiveness of our methods.     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

Lower bounds for multiplayer noncooperative games of incomplete information

This paper (see also [1]) extends the alternating Turing machine (A-TM) of Chandra, Kozen and Stockmeyer [2], the private and the blind alternating machines of Reif [3,4] to model multiplayer games of incomplete information. We use these machines to provide matching lower bounds for our decision algorithms described in our companion paper [5]. We also apply multiple person alternation to other machine types.We show that multiplayer games of incomplete information can be undecidable general. However, one form of incomplete information games that is decidable we term as hierarchical games (defined later in this paper). In hierarchical multiplayer games, each additional clique (subset of players with same information) increases the complexity of the outcome problem by a further exponential. Consequently, if a multiplayer game of incomplete information with k cliques has a space bound of S(n), then its outcome can be k repeated exponentials harder than games of complete information with the same space bound S(n). This paper proves that this exponential blow-up must occur in the worst case.We define TEAM-PRIVATE-PEEK and TEAM-BLIND-PEEK, extending the previous models of PEEK. These new games can be shown to be complete for their respective classes. We use these games to establish lower bounds on complexity of multiplayer games of incomplete information and blindfold multiplayer games.We analyze the time bounded alternating machines, and conclude that time is not a very critical resource for multiplayer alternation. We also show DQBF (a variant of QBF) to be complete in NEXPTIME.     

Constrained automated mechanism design for infinite games of incomplete information

We present a functional framework for automated Bayesian and worst-case mechanism design, based on a two-stage game model of strategic interaction between the designer and the mechanism participants. At the core of our framework is a black-box optimization algorithm which guides the process of evaluating candidate mechanisms. We apply the approach to several classes of two-player infinite games of incomplete information, producing optimal or nearly optimal mechanisms using various objective functions. By comparing our results with known optimal mechanisms, and in some cases improving on the best known mechanisms, we provide evidence that ours is a promising approach to parametrized mechanism design for infinite Bayesian games.     

A probabilistic approach to quantum Bayesian games of incomplete information

A Bayesian game is a game of incomplete information in which the rules of the game are not fully known to all players. We consider the Bayesian game of Battle of Sexes that has several Bayesian Nash equilibria and investigate its outcome when the underlying probability set is obtained from generalized Einstein–Podolsky–Rosen experiments. We find that this probability set, which may become non-factorizable, results in a unique Bayesian Nash equilibrium of the game.     

Search in games with incomplete information: a case study using Bridge card play

We examine search algorithms in games with incomplete information, formalising a best defence model of such games based on the assumptions typically made when incomplete information problems are analysed in expert texts. We show that equilibrium point strategies for optimal play exist for this model, and define an algorithm capable of computing such strategies. Using this algorithm as a reference we then analyse search architectures that have been proposed for the incomplete information game of Bridge. These architectures select strategies by analysing some statistically significant collection of complete information sub-games. Our model allows us to clearly state the limitations of such architectures in producing expert analysis, and to precisely formalise and distinguish the problems that lead to sub-optimality. We illustrate these problems with simple game trees and with actual play situations from Bridge itself.     

Bargaining with incomplete information

This paper analyses the process and outcomes of competitive bilateral negotiation for a model based on negotiation decision functions. Each agent has time constraints in the form of a deadline and a discounting factor. The importance of information possessed by participants is highlighted by exploring all possible incomplete information scenarios – both symmetric and asymmetric. In particular, we examine a range of negotiation scenarios in which the amount of information that agents have about their opponent’s parameters is systematically varied. For each scenario, we determine the equilibrium solution and study its properties. The main results of our study are as follows. Firstly, in some scenarios agreement takes place at the earlier deadline, while in others it takes place near the beginning of negotiation. Secondly, in some scenarios the price surplus is split equally between the agents while in others the entire price surplus goes to a single agent. Thirdly, for each possible scenario, the equilibrium outcome possesses the properties of uniqueness and symmetry – although it is not always Pareto optimal. Finally, we also show the relative impacts of the opponent’s parameters on the bargaining outcome.     

Data Dependencies in Database with Incomplete Information

To get more meaning of incomplete information,a predicate way is proposed torepresent the nulls.The concepts of functional and multivalued dependencies areextended in the environment which allows nulls in a database relation.The inferencerules which can be applied to the extended dependencies are investigated.Finally it isshown that the rules are complete for the family of extended functional and multivalueddependencies.     

Multistage network games with perfect information

We consider multistage network games with perfect information. At each time instant, a current network structure connecting the players is specified. It is assumed that each edge has some utility value (player’s benefit from being linked to another player), and players can change the network structure at each stage. We propose a method for finding optimal behavior for players in games of this type.     

Hierarchical games with deliberately distorted information

Consideration was given to the hierarchical two-person game where the lower-level player informs the principal about his decisions, and at that it can communicate invalid information. The principal, however, can verify at random the presented information and penalize its partner for the distorted information. Calculation of the maximal guaranteed result in a corresponding game is a complicated variational game. The present paper reduced this problem to calculation of multiple maximins in the “finite-dimensional” spaces. This result enables one to gain an insight into the logical structure of the optimal strategy of the upper-level player.     

Differential games with imperfect state information

Nondeterministic differential games of imperfect information are considered, with particular emphasis on the case of a linear system, a quadratic cost functional, and independent white Gaussian noises additively corrupting the observable output measurements. Solutions are presented for a number of particular cases of this problem, including those in which one of the two controllers has either no information or, under certain additional restrictions, perfect measurements of the state vector. In each case the optimal control for each controller is shown to be closely related to that which would result by assuming a separation theorem to hold. Furthermore, the various terms in the resulting optimal cost are shown to be readily assignable to the appropriate contributing source, such as the optimal cost that would result if the problem were instead a deterministic one with perfect information, the effect of estimation errors, or the effect of measurement errors.     

Inference control in statistical databases with incomplete information

The paper deals with the problem of inference control in statistical databases. We consider the case when database contains incomplete information and we study consequences of that fact. We propose the interpretation of a query language as ranges to protect confidential information and give a method for protecting statistical databases with incomplete information from a disclosure.