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.     

Distributed event-triggered generalized Nash equilibrium seeking in multi-coalition noncooperative games with coupling constraints

This paper is concerned with a multi-coalition noncooperative game with coupling equality constraints. Each coalition is a player consisted of multiple agents in noncooperative games and desire to minimize its own objective function based on local information. Each agent as actual decision maker in the same coalition is to optimize the objective function of the coalition cooperately. To seek a generalized Nash equilibrium (GNE) of the multi-coalition game, a distributed continuous-time algorithm is developed. Moreover, to further reduce the communication among agents and coalitions, an event-triggered mechanism (ETM) is introduced for the multi-coalition game. By using ETM, a novel distributed GNE seeking algorithm is proposed, where agents and coalitions are allowed to exchange estimation information with neighbors only when the triggering condition is satisfied. Remarkably, the proposed event-triggered scheme introduces internal variables to regulate its threshold dynamically, which excludes Zeno behavior. By Lyapunov analysis, it is proved that the coalitions' decision variables converge to a GNE in both algorithms. Finally, the effectiveness of the proposed methods is validated by numerical simulations.     

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.     

Non-cooperative routing in loss networks

The paper studies routing in loss networks in the framework of a non-cooperative game with selfish users. Two solution concepts are considered: the Nash equilibrium, corresponding to the case of a finite number of agents (such as service providers) that take routing decisions, and the Wardrop equilibrium, in which routing decisions are taken by a very large number of individual users. We show that these equilibria do not fall into the standard frameworks of non-cooperative routing games. As a result, we show that uniqueness of equilibria or even of utilizations at equilibria may fail even in the case of simple topology of parallel links. However, we show that some of the problems disappear in the case in which the bandwidth required by all connections is the same. For the special case of a parallel link topology, we obtain some surprisingly simple way of solving the equilibrium for both cases of Wardrop as well as Nash equilibrium.     

A simulation framework for measuring robustness of incentive mechanisms and its implementation in reputation systems

In game theoretical analysis of incentive mechanisms, all players are assumed to be rational. Since it is likely that mechanism participants in the real world may not be fully rational, such mechanisms may not work as effectively as in the idealized settings for which they were designed. Therefore, it is important to evaluate the robustness of incentive mechanisms against various types of agents with bounded rational behaviors. Such evaluations would provide us with the information needed to choose mechanisms with desired properties in real environments. In this article, we first propose a general robustness measure, inspired by research in evolutionary game theory, as the maximal percentage of invaders taking non-equilibrium strategies such that the agents sustain the desired equilibrium strategy. We then propose a simulation framework based on evolutionary dynamics to empirically evaluate the equilibrium robustness. The proposed simulation framework is validated by comparing the simulated results with the analytical predictions based on a modified simplex analysis approach. Finally, we implement the proposed simulation framework for evaluating the robustness of incentive mechanisms in reputation systems for electronic marketplaces. The results from the implementation show that the evaluated mechanisms have high robustness against a certain non-equilibrium strategy, but is vulnerable to another strategy, indicating the need for designing more robust incentive mechanisms for reputation management in e-marketplaces.     

Applying game theory mechanisms in open agent systems with complete information

Game theory is a popular tool for designing interaction protocols for agent systems. It is currently not clear how to extend this to open agent systems. By “open” we mean that foreign agents will be free to enter and leave different systems at will. This means that agents will need to be able to work with previously unseen protocols. There does not yet exist any agreement on a standard way in which such protocols can be specified and published. Furthermore, it is not clear how an agent could be given the ability to use an arbitrary published protocol; the agent would need to be able to work out a strategy for participation. To address this we propose a machine readable language in which a game theory mechanism can be written in the form of an agent interaction protocol. This language allows the workings of the protocol to be made public so that agents can inspect it to determine its properties and hence their best strategy. Enabling agents to automatically determine the game theoretic properties of an arbitrary interaction protocol is difficult. Rather than requiring agents to find the equilibrium of a game, we propose that a recommended equilibrium will be published along with the protocol; agents can then check the recommendation to decide if it is indeed an equilibrium. We present an algorithm for this decision problem. We also develop an equilibrium which simplifies the complexity of the checking problem, while still being robust to unilateral deviations.     

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.     

A Pure Nash Equilibrium-Based Game Theoretical Method for Data Replication across Multiple Servers

This paper proposes a non-cooperative game based technique to replicate data objects across a distributed system of multiple servers in order to reduce user perceived Web access delays. In the proposed technique computational agents represent servers and compete with each other to optimize the performance of their servers. The optimality of a non-cooperative game is typically described by Nash equilibrium, which is based on spontaneous and non-deterministic strategies. However, Nash equilibrium may or may not guarantee system-wide performance. Furthermore, there can be multiple Nash equilibria, making it difficult to decide which one is the best. In contrast, the proposed technique uses the notion of pure Nash equilibrium, which if achieved, guarantees stable optimal performance. In the proposed technique, agents use deterministic strategies that work in conjunction with their self-interested nature but ensure system-wide performance enhancement. In general, the existence of a pure Nash equilibrium is hard to achieve, but we prove the existence of such equilibrium in the proposed technique. The proposed technique is also experimentally compared against some well-known conventional replica allocation methods, such as branch and bound, greedy, and genetic algorithms.     

Largest Consistent Set in International Environmental Agreements

We study the formation and the stability of International Environmental Agreements (IEAs) in a pollution abatement model with a quadratic cost function. Countries play a two-stage game: in the first stage each country decides to join or not the coalition while, in the second stage, the quantity of pollution abatement is chosen. To analyze the stability of coalition structures in a multiple coalition game, we use the notion of the Largest Consistent Set (LCS) which allows players to be farsighted. Chwe (1994) developed the concept of farsighted stability: an outcome is stable and it is in the LCS if and only if deviations from it or potential further deviations are not unanimously preferred to the original outcome by the coalition considering the deviations. Applying this notion of stability in the IEA context we assume that, when a country or a sub-coalition contemplate exiting or joining an agreement, it takes into account the reactions of other countries ignited by its own actions. The goal of this paper is to identify the resulting stable structures and the LCS, examining the cooperation among countries with respect to an indicator of countries’ environmental awareness. We show that large coalitions are possible outcomes of the game if the farsightedness is considered. In particular, we obtain general sufficient conditions that assure the farsighted stability of the Grand Coalition. In a computational way, we prove that if the environmental awareness is larger than a threshold value, the number of coalition structures belonging to LCS goes down with respect to the initial coalition structures and coalitions with singleton countries never exist. Moreover, we present a useful Maple algorithm to compare the cost functions and to determine direct dominance.     

An electricity market game between consumers, retailers and network operators

We consider a simple game-theoretical model in which an electricity retailer and a network owner offer incentives to consumers to shift load from a peak period to an off-peak period. Using a simple example, we compare the market outcomes from collusion with those from the equilibrium of a non-cooperative game and examine the behaviour in this game when it is repeated in a situation in which agents have imperfect information.     

基于时间约束的不完全信息的战略协商模型

在实证的一对一协商中，协商Agent不仅要面临自己的最后期限的压力，同时又要预测协商对手的最后期限和其类型，协商Agent的协商战略必须满足理性与均衡的要求。提出了通过形式化的方法建立轮流出价协商模型，给出了轮流出价协商战略均衡的条件定义，求出了基于时间限制的不完全信息环境下满足均衡组合的协商战略，建立了依据均衡战略的实用化协商算法，最后分析了该算法产生的实验数据，并在相同环境下与Zeus协商模型比较显示，依从本模型的均衡战略的协商Agent能根据对对手的不确定信息的信念动态地采取行动，以获得最大的期望收益。     

理性密钥共享的扩展博弈模型

理性密钥共享体制通过引入惩罚策略使得参与者不会偏离协议,常采用的惩罚是一旦发现有人偏离就立即终止协议.这种惩罚策略有时导致惩罚人自身利益严格受损,从而降低了对被惩罚人的威慑.为了克服这一弱点,本文以扩展博弈为模型分析了理性密钥共享体制.首先给出(2,2)门限的理性密钥共享体制,证明了所给的协议是该博弈的一个序贯均衡,即经过任何历史之后坚持原协议仍然是每一个参与者的最优选择.特别地,在发现有人偏离后,协议所给出的惩罚策略既可以有效惩罚偏离者又能够完全维护惩罚人的利益.这是本文对前人设计的理性密钥共享体制的一个重要改进.然后针对将协议扩展到(t,n)门限情形,实现密钥分发人离线,达到计算的均衡等相关问题给出了一般的解决方案.     

Consensus analysis of hybrid multiagent systems: A game‐theoretic approach

This paper considers a consensus problem for hybrid multiagent systems, which comprise two groups of agents: a group of continuous‐time dynamic agents and a group of discrete‐time dynamic agents. Firstly, a game‐theoretic approach is adopted to model the interactions between the two groups of agents. To achieve consensus for the considered hybrid multiagent systems, the cost functions are designed. Moreover, it is shown that the designed game admits a unique Nash equilibrium. Secondly, sufficient/necessary conditions of solving consensus are established. Thirdly, we find that the convergence speed of the system depends on the game. By the mechanism design of the game, the convergence speed is increased. Finally, simulation examples are given to validate the effectiveness of the theoretical results.     

Analyzing the dynamics of stigmergetic interactions through pheromone games

The concept of stigmergy provides a simple framework for interaction and coordination in multi-agent systems. However, determining the global system behavior that will arise from local stigmergetic interactions is a complex problem. In this paper we propose to use Game Theory to analyze stigmergetic interactions. We show that a system where agents coordinate by sharing local pheromone information can be approximated by a limiting pheromone game in which different pheromone vectors represent player strategies. This game view allows us to use established methods and solution concepts from game theory to describe the properties of stigmergy based systems. Our goal is to provide a new framework to aid in the understanding and design of pheromone interactions. We demonstrate how we can use this system to determine the long term system behavior of a simple pheromone model, by analyzing the convergence properties of the pheromone update rule in the approximating game. We also apply this model to cases where multiple colonies of agents concurrently optimize different objectives. In this case a limiting colony game can be linked to colony level interactions to characterize the global system behavior.     

Order Invariants and the "Environment" Problem for Games with Ordered Outcomes

A property of a game with ordered outcomes is called an order invariant if it does not depend on the addition of unrealizable outcomes. In this paper, some important order invariants are obtained for antagonistic games with ordered outcomes. It is shown that these invariants are connected with equilibrium points in the sense of Nash. For a given game, its so-called majorant extension is constructed so that certain noninvariant properties of the game become its invariants.     

Cooperation in the evolutionary iterated prisoner’s dilemma game with risk attitude adaptation

The Iterated Prisoner’s Dilemma (IPD) game has been commonly used to investigate the cooperation among competitors. However, most previous studies on the IPD focused solely on maximizing players’ average payoffs without considering their risk preferences. By introducing the concept of income stream risk into the IPD game, this paper presents a novel evolutionary IPD model with agents seeking to balance between average payoffs and risks with respect to their own risk attitudes. We build a new IPD model of multiple agents, in which agents interact with one another in the pair-wise IPD game while adapting their risk attitudes according to their received payoffs. Agents become more risk averse after their payoffs exceed their aspirations, or become more risk seeking after their payoffs fall short of their aspirations. The aspiration levels of agents are determined based on their historical self-payoff information or the payoff information of the agent population. Simulations are conducted to investigate the emergence of cooperation under these two comparison methods. Results indicate that agents can sustain a highly cooperative equilibrium when they consider only their own historical payoffs as aspirations (called historical comparison) in adjusting their risk attitudes. This holds true even for the IPD with a short game encounter, for which cooperation was previously demonstrated difficult. However, when agents evaluate their payoffs in comparison with the population average payoff (called social comparison), those agents with payoffs below the population average tend to be dissatisfied with the game outcomes. This dissatisfaction will induce more risk-seeking behavior of agents in the IPD game, which will constitute a strong deterrent to the emergence of mutual cooperation in the population.     

纳什均衡解及其QPSO算法求解

纳什均衡是一种博弈的解的概念,可以对非常广泛类型的博弈作出严格的多的预测。具有量子行为的粒子群算法是一种能够较好的解决优化问题的算法,它是在粒子群算法的基础上发展起来的。本文讨论纳什均衡解,并利用QPSO算法来求解纳什均衡解。通过仿真算法及与几种算法的比较结果验证了算法的有效性,证明了算法的全局收敛性。     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

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.     

基于机制诚实性的显示原理算法比较

机制设计是博弈规则设计的主要的方法。即使假设在博弈中的代理都是自利的，也可以通过机制设计获得一个最佳结果。显示原理是机制设计中一个基本原理。文中论证了在对计算和通信给出一定的合理约束条件下，显示原理就可能无效。研究了最优诚实机制的情况，说明中心处理这个机制的算法是NPC的。当情况变为非诚实机制时，算法也就从中心转移到了一个代理的计算上，从而解决算法的NPC问题的困难。