Cooperative strong equilibrium in vehicle routing game

In this paper, a game-theoretic approach is considered for the vehicle routing problem with many distributors. Each customer is characterized by demand and wholesale price. Within such a statement, some customers are possibly not visited by a distributor in the optimal solution. This problem is called the vehicle routing game (VRG) in coordinated strategies. A procedure for determining a strong equilibrium in the VRG is proposed which is stable against coalitional deviations. According to the procedure, the optimization problem is solved iteratively for each distributor. The set of unvisited customers is reduced at each step. The existence of two classes of strong equilibria is proved. The concept of a cooperative strong equilibrium is presented. All results are illustrated by numerical examples.     

The Target Differential Game with Two Defenders

A cooperative aircraft differential game where an Attacker missile pursues an unmanned aerial vehicle (UAV) herein called the Target is addressed. The Target UAV cooperates with up to two Defender missiles which are launched in order to intercept the Attacker before the latter reaches the Target. This is a scenario with important military applications where each one of the agents is an autonomous air vehicle. Each agent plans and corrects its course of action in order to defeat an opposing force while simultaneously optimizing an operational relevant cost/payoff performance measure. The Target and the Defenders cooperate to form a team against the Attacker. The results in this paper build on the solution of a three agent differential game, where the three players are the Target, the Attacker, and one Defender; in this paper, the benefits of firing a second Defender are considered. Indeed, launching two interceptor missiles is a standard procedure by providing redundant backup. Building on the solution of the one-Defender problem, it is possible to address a seemingly intractable problem, where the Target needs to decide which Defender(s) to cooperate with, in addition to obtaining the optimal headings of every player in the game. Given the initial positions of the players, we solve the problem of determining if a second Defender improves the Target/Defender(s) payoff and provide the optimal strategies for each of the agents involved. Finally, we address the game of kind (for the case of one Defender) which provides the safety regions to determine which side will win based on the initial state. These safety regions provides the Target’s area of vulnerability, and using these results, we describe the reduction to the Target’s vulnerability area brought by an additional Defender.     

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

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

Incentive equilibrium in bioresource sharing problem

A dynamic game model of bioresource management problem is considered. The center (referee) which shares a reservoir, and the players (countries) which harvest the fish stock on their territory are the participants of this game. In this paper we investigate the new type of equilibrium—cooperative incentive equilibrium. The equilibria are constructed in the case, when the players punish each other for a deviation from the cooperative equilibrium, and in the case, when the center punishes them for a deviation. Some results of the numerical modelling are given.     

A discrete-time bioresource management problem with asymmetric players

This paper explores the discrete-time game-theoretic model associated with a bioresource management problem (fish catching). The game engages players (countries or fishing firms) that harvest fish stocks on the infinite horizon. The paper aims at defining the cooperative payoff under different discount factors of the players. We propose applying a Nash bargaining solution for constructing the cooperative strategies of the players. The analysis covers two bargaining schemes, namely, the one for the whole duration of the game and the recursive bargaining procedure.     

A Cooperative Coalitional Game in Duopolistic Supply-Chain Competition

Cooperative coalitional games study the selection of chain partners, the formation of supply chains and outcome allocations. The chain value of a coalition depends on the outcome of inter-chain competition. Subsequently, chain partners may accept their payoffs or decide to defect to another coalition that has made a higher tender offer. The formation and defection continues until a stable Cournot-Nash equilibrium is reached. This is the state where no player may unilaterally defect to another coalition and earn a higher profit. We formulate the cooperative coalitional game as a variational inequality problem and propose an iterative diagonalization algorithm to determine the steady state for the game. The computational results illustrated that (1) supply-chain competition may not necessarily preserve the same level of social welfare; (2) internalization of resources and costs may distort the general competition economy; and (3) wielding the power in a supply chain does not necessarily translate into higher profits.     

Proof systems and transformation games

We introduce Transformation Games (TGs), a form of coalitional game in which players are endowed with sets of initial resources, and have capabilities allowing them to derive certain output resources, given certain input resources. The aim of a TG is to generate a particular target resource; players achieve this by forming a coalition capable of performing a sequence of transformations from a combined set of initial resources to the target resource. TGs can model a number of natural settings, such as cooperative proof systems, where a collection of agents having different expertise work together to derive a proof for a target theorem, or supply chains, where agents cooperate to create a target product from base resources. After presenting the TG model, and discussing its interpretation, we consider possible restrictions on the transformation chain, resulting in different coalitional games. Following the basic model, we consider the computational complexity of several problems in TGs, such as testing whether a coalition wins, checking if a player is a dummy or a veto player, computing the core of the game, computing power indices, and checking the effects of possible restrictions on the coalition. Finally, we consider extensions to the model in which transformations have associated costs.     

Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling

In this paper, the decrease in the emission of greenhouse gases is evaluated using the vehicle routing problem with backhauls and time windows by considering the energy required for each route and estimating the load and distance between customers. Using a scatter search, problems from the literature with up to 100 randomly distributed customers were analyzed. Our results indicate that the distance traveled and the transportation costs increase as the required energy decreases, but the amount of fuel consumed also decreases; therefore, the emission of greenhouse gases also decreases. In some cases, the number of vehicles remains the same or increases because a better solution is achieved with shorter, better distributed routes. In addition, using a cooperative game approach, we found that different transportation companies operating jointly results in decreased emissions as well as operating costs.     

Atomic Congestion Games: Fast, Myopic and Concurrent

We study here the effect of concurrent greedy moves of players in atomic congestion games where n selfish agents (players) wish to select a resource each (out of m resources) so that her selfish delay there is not much. The problem of “maintaining” global progress while allowing concurrent play is exactly what is examined and answered here. We examine two orthogonal settings: (i) A game where the players decide their moves without global information, each acting “freely” by sampling resources randomly and locally deciding to migrate (if the new resource is better) via a random experiment. Here, the resources can have quite arbitrary latency that is load dependent. (ii) An “organised” setting where the players are pre-partitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move. Our work considers concurrent selfish play for arbitrary latencies for the first time. Also, this is the first time where fast coalitional convergence to an approximate equilibrium is shown.     

Coalitional game with fuzzy payoffs and credibilistic core

As an important branch of game theory, coalitional game deals with situations that involve cooperation among the players. This paper deals with this topic further by incorporating the fuzzy payoff information. Based on the credibility theory, we introduce two decision criteria to define the preferences of players, which leads to two definitions of credibilistic cores—the solution of coalitional game with fuzzy transferable payoffs. Meanwhile, we give a sufficient and necessary condition to ensure non-emptiness of the credibilistic cores. Finally, an example is provided for illustrating the usefulness of the theory developed in this paper.     

INFLUENCE OF ENVIRONMENTAL CHANGES ON COOPERATIVE BEHAVIOR IN THE PRISONER'S DILEMMA GAME ON AN ARTIFICIAL SOCIAL MODEL

In this paper, by simulations on an artificial social model, we analyze cooperative behavior of agents playing the prisoner's dilemma game, in which each of the agents has the two strategies: cooperate and defect. Because defect yields a better payoff whichever strategy an opponent chooses, it is rational for an agent to choose defect in a single game or a finite number of games. However, it is known that a pair of cooperates can also be a Nash equilibrium pair if the players do not know when the game is over or the game is infinitely repeated. To investigate such cooperative behavior, we employ an artificial social model called the Sugarscape and carry out simulations on the model. Arranging three kinds of environments in the Sugarscape, we examine cooperative behavior of agents who are essentially selfish, in a sense that they maximize their payoffs, and investigate influence of environmental changes on the cooperative behavior.     

Research on pricing and coordination strategy of green supply chain under hybrid production mode

In order to investigate the pricing and coordination issues of single-period green supply chain, we base our work on the market demand that green product and non-green products co-exist with and substitute each other, and examine respectively the equilibrium results for two production modes in cooperative game and non-cooperative game. Theoretical analysis indicates that different production costs will post impact on the choice of production modes by manufacturers when consumers have different valuations of the products. Furthermore, system performance in cooperative game is apparently better than that in non-cooperative game. The cooperative pricing strategy coordinated by Rubinstein bargaining can realize the pareto optimization of supply chain system profits and member profits under different production modes, with a 33.3% increase in system profits from that in non-cooperative game. The numerical examples further validate the validity of this coordinated pricing strategy.     

Partition Equilibrium Always Exists in Resource Selection Games

We consider the existence of Partition Equilibrium in Resource Selection Games. Super-strong equilibrium, where no subset of players has an incentive to change their strategies collectively, does not always exist in such games. We show, however, that partition equilibrium (introduced in (Feldman and Tennenholtz in SAGT, pp. 48–59, 2009) to model coalitions arising in a social context) always exists in general resource selection games, as well as how to compute it efficiently. In a partition equilibrium, the set of players has a fixed partition into coalitions, and the only deviations considered are by coalitions that are sets in this partition. Our algorithm to compute a partition equilibrium in any resource selection game (i.e., load balancing game) settles the open question from (Feldman and Tennenholtz in SAGT, pp. 48–59, 2009) about existence of partition equilibrium in general resource selection games. Moreover, we show how to always find a partition equilibrium which is also a Nash equilibrium. This implies that in resource selection games, we do not need to sacrifice the stability of individual players when forming solutions stable against coalitional deviations. In addition, while super-strong equilibrium may not exist in resource selection games, we show that its existence can be decided efficiently, and how to find one if it exists.     

High-performance simulation of nation-sized smart grids

This paper develops a large scale simulation approach for smart grids with a fine temporal resolution. This permits a detailed simulation of every single smart grid participant facilitating real-time estimates on a realistic scale about load distribution, demand and supply. This is especially interesting when considering the sustainability and efficiency of renewable energy generation. The smart grid model is based on a multi-agent system. Each agent is modelled by an optimisation problem which minimises its costs to meet a prescribed demand. In order to bestow some flexibility to each agent, it can generate energy, by e.g. solar panels, or store energy. All agents participate in a cooperative bargaining game to compute their respective optimal solution. By doing so, the energy prices are dynamically adapted to the agents’ solutions so that an energy market is formed. This bargaining game is designed that a unique Nash equilibrium exists. The computations to obtain the equilibrium point are performed in parallel. To this end, a synchronisation scheme is derived to ensure convergence of the proposed parallel bargaining algorithm. The smart grid structure and capacity limitations are also taken into account. The solutions of the bargaining game are compliant with the smart grid’s capacities by solving a modified network flow problem and forcing the bargaining solution within the capacity limitations in an iterative procedure. The correctness of the presented parallel algorithm is validated in tests along with a parallel performance evaluation. As a proof of concept of the practical applicability of this approach, a smart grid with over 30 million private households and multiple energy types is simulated.     

Strategic stability in linear-quadratic differential games with nontransferable payoffs

We address the problem of strategically supported cooperation for linear-quadratic differential games with nontransferable payoffs. As an optimality principle, we study Pareto-optimal solutions. It is assumed that players use a payoff distribution procedure guaranteeing individual rationality of a cooperative solution over the entire game horizon. We prove that under these conditions a Pareto-optimal solution can be strategically supported by an ε-Nash equilibrium. An example is considered.     

Properties of Nash solutions of a two-stage nonzero-sum game

This paper contains exact expressions for the complete class of uncountably many globally optimal affine Nasb equilibrium strategies for a two-stage two-person nonzero-sum game problem with quadratic objective functionals and with dynamic information for beth players. Existence conditions for each of these Nash equilibrium solutions are derived and it is shown that a recursive Nash solution is not necessarily globally optimal. Cost-uniqueness property of the derived Nash strategies is investigated and it is proven that the game problem under consideration admits a unique Nash cost pair if and only if it can be made equivalent to either a team problem or a zero-sum game. It is also shown that existence conditions of a globally optimal Nash solution will be independent of the parameters characterizing the nonuniques of the Nash strategies only if the game problem can be made equivalent to a team problem.     

On the Complexity of Pareto-Optimal Nash and Strong Equilibria

We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.     

A multistage supergame of downstream pollution

We consider two neighbouring regions whose pollution emissions damage their common environment. Mathematically the problem is formulated as a mull-stage supergame. At each stage, the players decide to cooperate or not during the time interval separating two successive stages. On this time interval, a non zero-suns game is defined. Under a cooperative regime, the players agree to apply the Nash bargaining solution. If a non cooperative regime prevails, the players get the Nash equilibrium outcomes. The structure of the optimal behaviour in the supergame is fully characterised, and time consistency of the solution investigated.     

Graphical Congestion Games

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem.     

Matrix games with missing,interval, and ambiguous lottery payoffs of pure strategy profiles and compound strategy profiles

In a matrix game, the interactions among players are based on the assumption that each player has accurate information about the payoffs of their interactions and the other players are rationally self‐interested. As a result, the players should definitely take Nash equilibrium strategies. However, in real‐life, when choosing their optimal strategies, sometimes the players have to face missing, imprecise (i.e., interval), ambiguous lottery payoffs of pure strategy profiles and even compound strategy profile, which means that it is hard to determine a Nash equilibrium. To address this issue, in this paper we introduce a new solution concept, called ambiguous Nash equilibrium, which extends the concept of Nash equilibrium to the one that can handle these types of ambiguous payoff. Moreover, we will reveal some properties of matrix games of this kind. In particular, we show that a Nash equilibrium is a special case of ambiguous Nash equilibrium if the players have accurate information of each player's payoff sets. Finally, we give an example to illustrate how our approach deals with real‐life game theory problems.