Seeking the Equilibrium Situations in Bimatrix Games

Determination of the Nash-equilibria in the bimatrix game was considered by reducing it to its equivalent nonconvex problem of optimization solved by the algorithm of global search based on the theory of global extremum for this problem. Efficiency of this method was illustrated by numerical solution of bimatrix games of sufficiently high dimensions.     

GENERAL GAME-PLAYING AND REINFORCEMENT LEARNING

This paper provides a blueprint for the development of a fully domain-independent single-agent and multiagent heuristic search system. It gives a graph-theoretic representation of search problems based on conceptual graphs and outlines two different learning systems. One, an "informed learner", makes use of the graph-theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other, a "blind learner", is not given access to the rules of a domain but must discover and then exploit the underlying mathematical structure of a given domain. Relevant work of others is referenced within the context of the blueprint.
To illustrate further how one might go about creating general game-playing agents, we show how we can generalize the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. A monitor for such domains has been developed, along with an implementation of a blind and informed learning system known as Morphll. Performance results with MorphK are preliminary but encouraging and provide a few more data points with which to understand and evaluate the blueprint.     

Structured system models Part 2. Directed graphs and boolean matrices

Parameterized system models and their augmented controllability indices are studied. Analytically parameterized system models arc shown to have generic index lists, i.e. lists which arc actual lists for all parameter values except those in a proper analytic variety. For structured system models, as a subset of analytically parameterized system models, there exists a known graph-theoretic method for determining the Hermite indices. A new method for examining both Hermite and Kronecker indices is introduced. The method is based on a necessary graph-theoretic condition for the examined columns of the controllability matrix to be linearly independent. Additional sufficient conditions are given to complete the method. The given graph-theoretic results are also expressed using boolean matrices associated with graphs.     

基于分层路径计算单元与双矩阵博弈的多域光网络静态组播专用保护算法

在预先配置组播业务的多域光网络中,如何保证静态组播业务的生存性已成为广泛关注的问题。针对此问题,通过采用基于分层路径计算单元（PCE）架构的全局拓扑信息调度计算模型,利用双矩阵博弈来生成链路不相交的组播树和组播保护树,最后提出了一种基于分层PCE与双矩阵博弈的多域光网络静态组播专用保护算法,并给出了算法的具体示例。理论分析和实验结果表明,在一定的冗余资源配置下,该算法具有较低的时间复杂度,在优化组播工作树和组播保护树的资源分配结构的同时,可明显提高多域光网络静态组播业务的生存能力。     

基于粒子群优化的混合模糊双矩阵对策求解

针对具有模糊策略集与模糊支付值的不确定性冲突环境,建立了混合模糊双矩阵对策模型。在假定模糊支付值为三角模糊数的情形下,采用了基于单个截集的模糊数线性排序函数,将模型清晰化后转化为双矩阵对策,并应用粒子群优化算法求解。最后,给出一个军事例子说明了模型的实用有效性和粒子群优化算法的高效性。     

A NEW AGENT MATCHING SCHEME USING AN ORDERED FUZZY SIMILARITY MEASURE AND GAME THEORY

In this paper, an agent matching method for bilateral contracts in a multi-agent market is proposed. Each agent has a hierarchical representation of its trading commodity attributes by a tree structure of fuzzy attributes. Using this structure, the similarity between the trees of each pair of buyer and seller is computed using a new ordered fuzzy similarity algorithm. Then, using the concept of Stackelberg equilibrium in a leader–follower game, matchmaking is performed among the sellers and buyers. The fuzzy similarities of each agent with others in its personal viewpoint have been used as its payoffs in a bimatrix game. Through a case study for bilateral contracts of energy, the capabilities of the proposed agent-based system are illustrated.     

Bayesian equilibria for uncertain bimatrix game with asymmetric information

In an uncertain bimatrix game, there are two solution concepts of \((\alpha ,\beta )\)-optimistic equilibrium strategy and \((u,v)\)-maximum chance equilibrium strategy. This paper goes further by assuming that the confidence levels \(\alpha , \beta \) and payoff levels \(u, v\) are private information. Then, the so-called uncertain bimatrix game with asymmetric information is investigated. Two solution concepts of Bayesian optimistic equilibrium strategy and Bayesian maximum chance equilibrium strategy as well as their existence theorems are presented. Moreover, sufficient and necessary conditions are given for finding the Bayesian equilibrium strategies. Finally, a two-firm advertising problem is analyzed for illustrating our modelling idea.     

Probability and possibility models of matrix games of two subjects

Probability models and their possibility counterparts of one-matrix and bimatrix games of two subjects (A and B) were defined and analyzed. For the one-matrix game possibility model, a theorem was proven saying that maximin and minimax fuzzy strategies exist and that possibilities of A winning or losing (B) in relation to these strategies are equal. The concepts of fuzzy and randomized game strategies were defined and analyzed. The problem of statistic modeling of A and B fuzzy strategies was resolved. For possible models of bimatrix games, the existence of equilibrium points was examined. For the problem of maximization of the winning A and B possibility, it was proven that equilibrium points exist. For the problem of minimizing the possibility of losses, it was shown that if equilibrium points exist, some of them are related to clear strategies, A and B.     

A Graph-Theoretic Approach to Default Logic

A network representation of propositional seminormal disjunction-free default theories is presented, leading to a graph-theoretic approach to their analysis. The problem of finding an extension is proved to be equivalent to that of determining a kernel for a corresponding graph, allowing stronger complexity results as well as new conditions for the existence of extensions.     

Bargaining property of nucleolus and τ-value in a class of TU-games

First, we introduce pairwise-bargained consistency with a reference point, and use as reference points the maxmin and the minmax value within pure strategies of a certain constant-sum bimatrix game, and also the game value within mixed strategies of it. Second, we show that the pairwise-bargained consistency with reference point being the maxmin or the minmax value determines the nucleolus in some class of transferable utility games. (This result is known in the bankruptcy games and the pseudoconcave games with respect to supersets of the managers.) This class of games whose element we call a pseudoconcave game with respect to essential coalitions, of course, includes the bankruptcy games and the pseudoconcave games with respect to supersets of the managers. It is proved that this class of games is exactly the same as the class of games which have a nonempty core that is determined only by one-person and (n − 1)-person coalition constraints. And we give a sufficient condition which guarantees that the bargaining set coincides with the core in this class of games. Third, we interpret the τ-value of a quasibalanced transferable utility game by the pairwise-bargained consistency with reference point being the game value. Finally, by combining the second and the third results, if a transferable utility game in this class is also semiconvex, then the nucleolus and the τ-value are characterized by the pairwise-bargained consistency with different reference points which are given by the associated bimatrix game.     

Guard games on graphs: Keep the intruder out!

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the guards and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges. The area protected by the guards is an induced subgraph of the given graph. We investigate the algorithmic aspects of the guarding problem, which is to find the minimum number of guards sufficient to patrol the area. We show that the guarding problem is PSPACE-hard and provide a set of approximation algorithms. All approximation algorithms are based on the study of a variant of the game where the intruder must reach the guarded area in a single step in order to win. This variant of the game appears to be a 2-approximation for the guarding problem, and for graphs without cycles of length 5 the minimum number of required guards in both games coincides. We give a polynomial time algorithm for solving the one-step guarding problem in graphs of bounded treewidth, and complement this result by showing that the problem is W[1]-hard parameterized by the treewidth of the input graph. We also show that the problem is fixed parameter tractable (FPT) parameterized by the treewidth and maximum degree of the input graph. Finally, we turn our attention to a large class of sparse graphs, including planar graphs and graphs of bounded genus, namely apex-minor-free graphs. We prove that the one-step guarding problem is FPT and possess a PTAS on apex-minor-free graphs.     

Game and Information Theory Analysis of Electronic Countermeasures in Pursuit-Evasion Games

Two-player pursuit-evasion games in the literature typically either assume both players have perfect knowledge of the opponent's positions or use primitive sensing models. This unrealistically skews the problem in favor of the pursuer who needs only maintain a faster velocity at all turning radii. In real life, an evader usually escapes when the pursuer no longer knows the evader's position. In our previous work, we modeled pursuit evasion without perfect information as a two-player bimatrix game by using a realistic sensor model and information theory to compute game-theoretic payoff matrices. That game has a saddle point when the evader uses strategies that exploit sensor limitations, whereas the pursuer relies on strategies that ignore the sensing limitations. In this paper, we consider, for the first time, the effect of many types of electronic countermeasures (ECM) on pursuit-evasion games. The evader's decision to initiate its ECM is modeled as a function of the distance between the players. Simulations show how to find optimal strategies for ECM use when initial conditions are known. We also discuss the effectiveness of different ECM technologies in pursuit-evasion games.      

Life in the game of Go

The Oriental game of Go contains a unique method by which pieces, called stones, are captured and made safe from capture. A group of stones safe from capture is called safe, unconditionally alive, or similar terms. Life or its lack can be determined by lookahead through the game tree, at some expense. We present a graph-theoretic static analysis of the board arrangement which determines unconditional life or its lack, together with proofs of its equivalency to look ahead. An algorithm for the static evaluation is given and we argue that it is the preferable method for computer Go play. These results constitute the first realistic theorems in the theory of Go.     

Life in the game of Go

The Oriental game of Go contains a unique method by which pieces, called stones, are captured and made safe from capture. A group of stones safe from capture is called safe, unconditionally alive, or similar terms. Life or its lack can be determined by lookahead through the game tree, at some expense. We present a graph-theoretic static analysis of the board arrangement which determines unconditional life or its lack, together with proofs of its equivalency to look ahead. An algorithm for the static evaluation is given and we argue that it is the preferable method for computer Go play. These results constitute the first realistic theorems in the theory of Go.     

Integrated structure design of a process and its control system

A graph-theoretic method for integration of process and control system (IPCS) syntheses with different controllability notions has been proposed in the present paper. The foundation of this integration is a well-established, graph-theoretic approach to process synthesis in conjunction with the analysis of structural controllability based on digraph-type process models. Unambiguous structural representation of the resultant integrated process and control systems, IPXS structures in brief, has been introduced for unambiguous representation of a process structure, it is rendered possible as an extension of the directed bipartite graph, the P-graph. Different set of axioms are proposed for describing the case of disturbance-rejective regulable and the combinatorially feasible and controllable structures in the special cases considered: the case of structural controllability and the case of fault-tolerant controllability. These axioms make the synthesis computationally more effective by considering very simple engineering knowledge. The maximal controllable structure of an IPXS synthesis problem has been defined as the union of combinatorially feasible and controllable IPXS structures. Thus, the mathematical programming model, e.g. MINLP model, of an IPXS synthesis problem can be and should be derived from the maximal controllable structure. Different versions of a fundamental polynomial time, combinatorial algorithm are presented for identifying the maximal controllable structure. The resultant IPXS structures are compared with the structures synthesized without considering their control systems.     

Optimal multiple-seams search for image resizing with smoothness and shape prior

Content-aware image resizing is of increasing relevance to allow high-quality image and video to be displayed on devices with different resolution. We present a novel method to find multiple seams simultaneously with global optimality for image resizing, incorporating both region smoothness and seam shape prior using a 3-D graph-theoretic approach. The globally optimal seams can be simultaneously achieved by solving a maximum flow problem based on an arc-weighted graph representation. Representing the resizing problem in an arc-weighted graph, we can incorporate a wide spectrum of constraints into the formulation, thus improving resizing results. By removing or inserting those multiple seams, the goal of content-aware image resizing is achieved. Due to simultaneous detection of multiple seams, our algorithm exhibits several good features: the ability to handle both crossing and non-crossing-seam cases, the ability to incorporate various feasible geometry constraints, and the ability to incorporate the seams importance, region smoothness and shape prior information. The proposed method was implemented and experimented on a variety of image data and compared with the state of the art in image resizing.     

A Game-theoretic approach to analyze interacting actors in GRL goal models

Goal-oriented requirements engineering aims to capture desired goals and strategies of relevant stakeholders during early requirements engineering stages, using goal models. Goal-oriented modeling techniques support the analysis of system requirements (especially non-functional ones) from an operationalization perspective, through the evaluation of alternative design options. However, conflicts and undesirable interactions between requirements produced from goals are inevitable, especially as stakeholders often aim for different objectives. In this paper, we propose an approach based on game theory and the Goal-oriented Requirement Language (GRL) to reconcile interacting stakeholders (captured as GRL actors), leading to reasonable trade-offs. This approach consists in building a payoff bimatrix that considers all actor’s valid GRL strategies, and computing its Nash equilibrium. Furthermore, we use two optimization techniques to reduce the size of the payoff bimatrix, hence reducing the computational cost of the Nash equilibrium. The approach goes beyond existing work by supporting nonzero-sum games, multiple alternatives, and inter-actor dependencies. We demonstrate the applicability of our game-theoretic modeling and analysis approach using a running example and two GRL models from the literature, with positive results on feasibility and applicability, including performance results.

     

Dominant sets and pairwise clustering

We develop a new graph-theoretic approach for pairwise data clustering which is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion introduced here which generalizes that of a maximal complete subgraph to edge-weighted graphs. We establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing the use of straightforward and easily implementable continuous optimization techniques from evolutionary game theory. Numerical examples on various point-set and image segmentation problems confirm the potential of the proposed approach     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

最长路径问题研究进展

最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用.参数计算理论产生后,参数化形式的k-Path问题成了研究的热点.介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果.最后,提出了该问题的进一步研究方向.