Modelling negotiated decision making in environmental and natural resource management : A multilateral, multiple issues, non-cooperative bargaining model with uncertainty

The relevance of bargaining to everyday life can easily be ascertained, yet the study of any bargaining process is extremely hard, involving a multiplicity of questions and complex issues. The objective of this paper is to provide new insights on some dimensions of the bargaining process-asymmetries and uncertainties in particular-by using a non-cooperative game theory approach. We develop a computational model which simulates the process of negotiation among more than two players, who bargain over the sharing of more than one pie. Through numerically simulating several multiple issues negotiation games among multiple players, we identify the main features of players’ optimal strategies and equilibrium agreements. As in most economic situations, uncertainty crucially affects also bargaining processes. Therefore, in our analysis, we introduce uncertainty over the size of the pies to be shared and assess the impact on players’ strategic behaviour. Our results confirm that uncertainty affects players’ behaviour and modify the likelihood of a self-enforcing agreement to emerge. The model proposed here can have several applications, in particular in the field of natural resource and environmental management at the national or local level, where conflicts over how to share a resource of a finite size are increasing.     

Cooperative games with multiple attributes

ABSTRACT

In this paper, we introduce the notion of a cooperative game with multiple attributes where players can provide partial participations in multiple attributes and form coalitions. The power or influence of the players due to their multiple attributes is evaluated based on their memberships in the coalitions. Our game therefore, extends the notion of cooperative games with fuzzy coalitions. The Shapley function for this class of games is proposed as a rational and fair solution concept. Every fuzzy game stems out of a specific crisp game under the assumption that the players provide partial memberships in forming multiple coalitions simultaneously. We adopt similar techniques to obtain the cooperative games with multiple attributes from their crisp counterparts and subsequently determine their Shapley functions.     

Ranking games

The outcomes of many strategic situations such as parlor games or competitive economic scenarios are rankings of the participants, with higher ranks generally at least as desirable as lower ranks. Here we define ranking games as a class of n-player normal-form games with a payoff structure reflecting the players' von Neumann-Morgenstern preferences over their individual ranks. We investigate the computational complexity of a variety of common game-theoretic solution concepts in ranking games and deliver hardness results for iterated weak dominance and mixed Nash equilibrium when there are more than two players, and for pure Nash equilibrium when the number of players is unbounded but the game is described succinctly. This dashes hope that multi-player ranking games can be solved efficiently, despite their profound structural restrictions. Based on these findings, we provide matching upper and lower bounds for three comparative ratios, each of which relates two different solution concepts: the price of cautiousness, the mediation value, and the enforcement value.     

Computing the Nash Bargaining Solution for Multiple Players in Discrete-Time Markov Chains Games

Abstract

This paper presents a novel method for computing the Nash bargaining equilibrium for finite, ergodic and controllable Markov chains games. To solve the bargaining process we first set the disagreement point as the Nash equilibrium of the problem, then to find the new agreement point we follow the bargaining model presented by Nash. We exemplify the game formulation in terms of nonlinear programing equations implementing the Lagrange principle. For ensuring the convergence of the game to an equilibrium point we employ the Tikhonov’s regularization method. For solving the bargaining problem we make use of the extraproximal optimization approach. Finally, we validate the proposed method by a numerical example for a three-person bargaining situation.     

A novel approximate method of computing extended Nash equilibria

In this paper, we propose a new method of computing an approximate Nash equilibrium with additional features. Existing algorithms often fail to produce an exact solution for games involving more than 3 players. Similarly, existing algorithms do not permit additional constraints on the problem. The principle idea of this paper involves proposing a methodology for computing approximate solutions through evolutionary computation. To do so, we first provide formal definitions of these problems and their approximate versions. Following which, we present the details of our solution. One of the most important advantages of the proposed solution is flexibility, which provides solutions to problems related to Nash equilibrium extensions. The proposed idea is tested on several types of games that vary with difficulty and size. All test sets are generated based on the well-known Gamut program. Additional comparisons with classical algorithms are also performed. Results indicate that Differential Evolution is capable of obtaining satisfactory solutions to large random and covariant games. The results also demonstrate that there is a high probability that even large games, in which a set of strategies with a non-zero probability of being chosen are very small, have a solution. The computation time depends mainly on the problem size, and the original Nash equilibrium problem is unaffected by additional modifications.     

An agenda-based framework for multi-issue negotiation

This paper presents a new model for multi-issue negotiation under time constraints in an incomplete information setting. The issues to be bargained over can be associated with a single good/service or multiple goods/services. In our agenda-based model, the order in which issues are bargained over and agreements are reached is determined endogenously, as part of the bargaining equilibrium. In this context we determine the conditions under which agents have similar preferences over the implementation scheme and the conditions under which they have conflicting preferences. Our analysis shows the existence of equilibrium even when both players have uncertain information about each other, and each agent's information is its private knowledge. We also study the properties of the equilibrium solution and determine conditions under which it is unique, symmetric, and Pareto-optimal.     

Cooperative network design: A Nash bargaining solution approach

The Network Design problem has received increasing attention in recent years. Previous works have addressed this problem considering almost exclusively networks designed by selfish users, which can be consistently suboptimal. This paper addresses the network design issue using cooperative game theory, which permits to study ways to enforce and sustain cooperation among users. Both the Nash bargaining solution and the Shapley value are widely applicable concepts for solving these games. However, the Shapley value presents several drawbacks in this context.For this reason, we solve the cooperative network design game using the Nash bargaining solution (NBS) concept. More specifically, we extend the NBS approach to the case of multiple players and give an explicit expression for users’ cost allocations. We further provide a distributed algorithm for computing the Nash bargaining solution. Then, we compare the NBS to the Shapley value and the Nash equilibrium solution in several network scenarios, including real ISP topologies, showing its advantages and appealing properties in terms of cost allocation to users and computation time to obtain the solution.Numerical results demonstrate that the proposed Nash bargaining solution approach permits to allocate costs fairly to users in a reasonable computation time, thus representing a very effective framework for the design of efficient and stable networks.     

基于TU动态模糊联盟合作博弈的核心及谈判集

利用模糊数学相关理论,对具有可转移效用的模糊合作博弈进行了研究,分析了TU模糊合作博弈的核心,并在此基础上对谈判集理论进行了研究,分析了谈判集与核心之间的关系。对于全联盟可能存在核心空集的情况,L-Z谈判集很好地解决了TU联盟合作博弈的收敛集问题。最后利用实例对该谈判集的有效性和可行性进行了说明。     

On the complexity of constrained Nash equilibria in graphical games

A widely accepted rational behavior for non-cooperative players is based on the notion of Nash equilibrium. Although the existence of a Nash equilibrium is guaranteed in the mixed framework (i.e., when players select their actions in a randomized manner) in many real-world applications the existence of “any” equilibrium is not enough. Rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained Nash equilibria.In this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player p may directly be interested in some of the other players only, called the neighbors of p. This setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible.Based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players’ interactions. The analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i.e., when players are forced to deterministically choose the action to perform. In particular, for this latter case, restrictions on players’ interactions and on constraints are identified, that make the computation of Nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented.     

Multi-agent discrete-time graphical games and reinforcement learning solutions

This paper introduces a new class of multi-agent discrete-time dynamic games, known in the literature as dynamic graphical games. For that reason a local performance index is defined for each agent that depends only on the local information available to each agent. Nash equilibrium policies and best-response policies are given in terms of the solutions to the discrete-time coupled Hamilton–Jacobi equations. Since in these games the interactions between the agents are prescribed by a communication graph structure we have to introduce a new notion of Nash equilibrium. It is proved that this notion holds if all agents are in Nash equilibrium and the graph is strongly connected. A novel reinforcement learning value iteration algorithm is given to solve the dynamic graphical games in an online manner along with its proof of convergence. The policies of the agents form a Nash equilibrium when all the agents in the neighborhood update their policies, and a best response outcome when the agents in the neighborhood are kept constant. The paper brings together discrete Hamiltonian mechanics, distributed multi-agent control, optimal control theory, and game theory to formulate and solve these multi-agent dynamic graphical games. A simulation example shows the effectiveness of the proposed approach in a leader-synchronization case along with optimality guarantees.     

Distributed Nash Equilibrium Seeking for General Networked Games With Bounded Disturbances

This paper is concerned with anti-disturbance Nash equilibrium seeking for games with partial information. First, reduced-order disturbance observer-based algorithms are proposed to achieve Nash equilibrium seeking for games with first-order and second-order players, respectively. In the developed algorithms, the observed disturbance values are included in control signals to eliminate the influence of disturbances, based on which a gradient-like optimization method is implemented for each player. Second, a signum function based distributed algorithm is proposed to attenuate disturbances for games with second-order integrator-type players. To be more specific, a signum function is involved in the proposed seeking strategy to dominate disturbances, based on which the feedback of the velocity-like states and the gradients of the functions associated with players achieves stabilization of system dynamics and optimization of players’ objective functions. Through Lyapunov stability analysis, it is proven that the players’ actions can approach a small region around the Nash equilibrium by utilizing disturbance observer-based strategies with appropriate control gains. Moreover, exponential (asymptotic) convergence can be achieved when the signum function based control strategy (with an adaptive control gain) is employed. The performance of the proposed algorithms is tested by utilizing an integrated simulation platform of virtual robot experimentation platform (V-REP) and MATLAB.      

Learning machiavellian strategies for manipulation in Stackelberg security games

This paper suggests a new approach for repeated Stackelberg security games (SSGs) based on manipulation. Manipulation is a strategy interpreted by the Machiavellianism social behavior theory, which consists on three main concepts: view, tactics, and immorality. The world is conceptualized by manipulators and manipulated (view). Players employ Machiavelli’s tactics and Machiavellian intelligence in order to manipulate attacker/defender situations. The immorality plays a fundamental role in these games, defenders are able to not be attached to a conventional moral in order to achieve their goals. We consider a security game model involving manipulating defenders and manipulated attackers engaged cooperatively in a Nash game and at the same time restricted by a Stackelberg game. The resulting game is non-cooperative bargaining game. The cooperation is represented by the Nash bargaining solution. We propose an analytical formula for solving the manipulation game, which arises as the maximum of the quotient of two Nash products. The role of the players in the Stackelberg security game are determined by the weights of the players for the Nash bargaining approach. We consider only a subgame perfect equilibrium where the solution of the manipulation game is a Strong Stackelberg Equilibrium (SSE). We employ a reinforcement learning (RL) approach for the implementation of the immorality. A numerical example related to developing a strategic schedule for the efficient use of resources for patrolling in a smart city is handled using a class of homogeneous, ergodic, controllable, and finite Markov chains for showing the usefulness of the method for security resource allocation.

     

多组对策系统非劣Nash策略的最优均衡解算法

多组对策系统中求解组与组之间的非劣Nash策略至关重要.如何针对一般问题解析求出非劣Nash策略还没有有效的方法.本文阐述了一种利用组与组之间的非劣反应集构造求解非劣Nash策略的迭代算法.为此首先引进多组对策系统组内部合作对策的最优均衡值和最优均衡解的概念,然后通过证明最优均衡解是组内部隐含某一权重向量的合作对策的非劣解,得到求解合作对策的单目标规划问题.进一步说明在组内部该问题的解不仅是非劣解而且对所有局中人都优于不合作时的Nash平衡策略.最后给出了验证该算法有效性的一个实际例子.     

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.     

State feedback control design to avoid players going bankrupt

This paper investigates the state feedback control design problem to avoid players going bankrupt for a class of networked evolutionary games. First, an algebraic expression is formulated for the given networked evolutionary games by using the semi‐tensor product of matrices. Then, based on the algebraic form, a necessary and sufficient condition for the existence of state feedback control, which can guarantee that no players will go bankrupt, is presented. Finally, an illustrative example demonstrates the effectiveness of the obtained results.     

Linear-quadratic discrete-time dynamic potential games

Discrete-time game-theoretic models of resource exploitation are treated as dynamic potential games. The players (countries or firms) exploit a common stock on the infinite time horizon. The main aim of the paper is to obtain a potential for the linear-quadratic games of this type. The class of games where a potential can be constructed as a quadratic form is identified. As an example, the dynamic game of bioresource management is considered and the potentials are constructed in the case of symmetric and asymmetric players.     

Equilibrium strategies in dynamic games with multi-levels of hierarchy

This paper considers noncooperative equilibria of three-player dynamic games with three levels of hierarchy in decision making. In this context, first a general definition of a hierarchical equilibrium solution is given, which also accounts for nonunique responses of the players who are not at the top of the hierarchy. Then, a general theorem is proven which provides a set of sufficient conditions for a triple of strategies to be in hierarchical equilibrium. When applied to linear-quadratic games, this theorem provides conditions under which there exists a linear one-step memory strategy for the player (say, $\text{J}$1) at the top of the hierarchy, which forces the other two players to act in such a way so as to jointly minimize the cost function of $\text{J}$1. Furthermore, there exists a linear one-step memory strategy for the second-level player (say, $\text{J}$2), which forces the remaining player to jointly minimize the cost function of $\text{J}$2 under the declared equilibrium strategy of $\text{J}$1. A numerical example included in the paper illustrates the results and the convergence property of the equilibrium strategies, as the number of stages in the game becomes arbitrarily large.     

Exact and approximate equilibria for optimal group network formation

We consider a process called the Group Network Formation Game, which represents the scenario when strategic agents are building a network together. In our game, agents can have extremely varied connectivity requirements, and attempt to satisfy those requirements by purchasing links in the network. We show a variety of results about equilibrium properties in such games, including the fact that the price of stability is 1 when all nodes in the network are owned by players, and that doubling the number of players creates an equilibrium as good as the optimum centralized solution. For the general case, we show the existence of a 2-approximate Nash equilibrium that is as good as the centralized optimum solution, as well as how to compute good approximate equilibria in polynomial time. Our results essentially imply that for a variety of connectivity requirements, giving agents more freedom can paradoxically result in more efficient outcomes.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

On the complexity of core,kernel, and bargaining set

Coalitional games model scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental issue of coalitional games is to single out the most desirable outcomes in terms of worth distributions, usually called solution concepts. Since decisions taken by realistic players cannot involve unbounded resources, recent computer science literature advocated the importance of assessing the complexity of computing with solution concepts. In this context, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonably compact form. The starting points of the investigation are the settings of graph games and of marginal contribution nets, where the worth of any coalition can be computed in polynomial time in the size of the game encoding and for which various open questions were stated in the literature. The paper answers these questions and, in addition, provides new insights on succinctly specified games, by characterizing the computational complexity of the core, the kernel, and the bargaining set in relevant generalizations and specializations of the two settings. Concerning the generalizations, the paper shows that dealing with arbitrary polynomial-time computable worth functions—no matter of the specific game encoding being considered—does not provide any additional source of complexity compared to graph games and marginal contribution nets. Instead, only for the core, a slight increase in complexity is exhibited for classes of games whose worth functions encode NP-hard optimization problems, as in the case of certain combinatorial games. As for specializations, the paper illustrates various tractability results on classes of bounded treewidth graph games and marginal contribution networks.