Games on networks

It is suggested that user selection of service provision on a network of heterogeneous servers be modeled by competitive replicator dynamics. User agents make their requirements known to network agents, which can bid for their execution. The bids initiate a negotiation process between the two groups of agents, at the end of which the user agents make a decision and map their requirements onto a selected set of network servers. The selection process is based on competitive replicator dynamics and attempts to maximize the respective utilities of both agent groups. Various issues resulting from the nonlinearity of the dynamics, such as stability and adaptability, are discussed in some detail. The results of some simulations are presented     

Evolving Best-Response Strategies for Market-Driven Agents Using Aggregative Fitness GA

There are very few existing works that adopt genetic algorithms (GAs) for evolving the most successful strategies for different negotiation situations. Furthermore, these works did not explicitly model the influence of market dynamics. The contribution of this work is developing bargaining agents that can both: 1) react to different market situations by adjusting their amounts of concessions and 2) evolve their best-response strategies for different market situations and constraints using an aggregative fitness GA (AFGA). While many existing negotiation agents only optimize utilities, the AFGA in this work is used to evolve best-response strategies of negotiation agents that optimize their utilities, success rates, and negotiation speed in different market situations. Given different constraints and preferences of agents in optimizing utilities, success rates, and negotiation speed, different best-response strategies can be evolved using the AFGA. A testbed consisting of both: 1) market-driven agents (MDAs)-negotiation agents that make adjustable amounts of concessions taking into account market rivalry, outside options, and time preferences and 2) GA-MDAs-MDAs augmented with an AFGA, was implemented. Empirical results show that GA-MDAs achieved higher utilities, higher success rates, and faster negotiation speed than MDAs in a wide variety of market situations.     

QoS Negotiation and Renegotiation Based on Mobile Agents

The Quality of Service （QoS） has received more and more attention since QoS becomes increasingly important in the Internet development. Mobile software agents represent a valid alternative to the implementation of strategies for the negotiation. In this paper, a QoS negotiation and renegotiation system architecture based on mobile agents is proposed. The agents perform the task in the whole process. Therefore, such a system can reduce the network load, overcome latency, and avoid frequent exchange information between clients and server. The simulation results show that the proposed system could improve the network resource utility about 10%.     

Pricing for enabling forwarding in self-configuring ad hoc networks

The assumption that all nodes cooperate to relay packets for each other may not be realistic for commercial wireless ad hoc networks. An autonomous (selfish) node in a wireless network has two disincentives for forwarding for others: energy expenditure (real cost) and possible delays for its own data (opportunity cost). We introduce a mechanism that "fosters cooperation through bribery" in the context of forwarding in ad hoc networks. Using a microeconomic framework based on game theory, we design and analyze a pricing algorithm that encourages forwarding among autonomous nodes by reimbursing forwarding. Taking a joint network-centric and user-centric approach, the revenue maximizing network and utility (measured in bits-per-Joule) maximizing nodes interact through prices for channel use, reimbursements for forwarding, transmitter power control, as well as forwarding and destination preferences. In a three-node (two-sources, one-access-point) network, the network converges to an architecture that induces forwarding only when the network geometries are such that forwarding is likely to increase individual benefits (network revenue and node utilities). For other geometries, the network converges to architectures that do not favor forwarding. We then generalize to a multinode network, where it is seen that the nodes' willingness to forward decrease for large ratios of the average internodal distance to the smallest distance between the access point and any source node. Pricing with reimbursement generally improves the network aggregate utility (or aggregate bits-per-Joule), as well as utilities and revenue compared with the corresponding pricing algorithm without reimbursement.     

Social utility Functions-part I: theory

The dominant approaches to utility-based multiagent decision theory rely on the premise of individual rationality-the doctrine that each individual is committed to achieving the best outcome for itself, regardless of the effect doing so has on others. This fundamentally asocial concept is the basis of conventional von Neumann-Morgenstern (vN-M) utilities but is inadequate to characterize truly cooperative artificial systems. Social utility functions differ from conventional vN-M utilities in that they are functions of multiple decision-maker preferences, rather than actions, and thus permit individuals to expand their spheres of interest beyond the self. A logical basis for coherent reasoning in multiagent environments must obey exactly the same desiderata as do multivariate probability functions. By taking a dual utilities approach (one to account for effectiveness and one to account for efficiency), a new game-theoretic structure, called satisficing games, provides a decision-making procedure that accounts for both individual and group interest and presents a framework for the design of sophisticated multiagent societies.     

基于概念语义协商的服务Agent划分

 服务参与者Agent之间使用异构的私有本体概念构造消息并进行交互,会由于消息语义的错误理解而影响服务发现的效率和结果的准确性.提出使用概念语义协商的方法改善服务Agent之间的理解能力;定义了服务Agent模型和本体概念解释元组,设计了服务Agent协商行为原语以及协商请求和响应协议;根据概念语义协商结果对私有本体进行更新并根据本体概念理解的相似度对参与服务的Agent进行划分,使功能相近且能互相理解的Agent处于相同的服务社区.实验表明,通过语义协商的服务Agent划分方法,能够有效提高同一服务社区服务Agent之间的概念理解程度,在协商概念数为2和8时,该方法较其他方法能够将概念理解错误率减少平均大约30%.     

Agent behaviors in virtual negotiation environments

A computational prototype of negotiation behavior is presented where the following occurs: (1) agents employ different concession matching tactics; (2) agents are unaware of opponent preferences; (3) agents incur a cost for delaying settlements; (4) agents vary in terms of goal difficulty and initial offer magnitude; and (5) demands and counter-offers are made and evaluated based on the opponent's degree of concession matching. This research explores the impact of the interaction of different agent behaviors on the negotiation process and the outcome of the negotiation. Simulation experiments show that the prototype is able to manifest fundamental patterns and confirms the effectiveness of classical negotiation and mediation strategies, such as ambitious goals and aggressive concession matching tactics. The model reveals some counterintuitive patterns that may shed a new perspective on the effects of time constraints and information availability     

Using Automated Negotiation for Grid Services

The popularity of grid services has widened their application to numerous domains and increased the utilization of computational resources. In order to create more incentives for the resources owners to lease their resources and prevent users from wasting the resources, the introduction of a market-oriented grid is inevitable. However, the issues for the negotiation between service provider and consumer over the supply and demand of resources can be complex, with highly interdependent issues. In this research, a simulated automated negotiation mechanism including a co-evolutionary mechanism and a modified game theory approach is proposed, to assist them in reaching an agreement over the conflicting issues. In the proposed architecture, the co-evolution process is able to reduce the multiple dimensional search space into a two-dimension search space and identify the appropriate negotiation strategies for the negotiating agents to form a payoff matrix which can be used for the game theory related stage of their interaction. The multiple stage negotiation process is introduced to improve the negotiation result. In this paper, an application which requires a large amount of computational resources to process the data generated from mobile devises is used to demonstrate that the proposed system is able to resolve the conflicts and obtain a valid solution.     

An energy-efficient approach to power control and receiver design in wireless data networks

In this paper, the cross-layer design problem of joint multiuser detection and power control is studied, using a game-theoretic approach that focuses on energy efficiency. The uplink of a direct-sequence code-division multiple-access data network is considered, and a noncooperative game is proposed in which users in the network are allowed to choose their uplink receivers as well as their transmit powers to maximize their own utilities. The utility function measures the number of reliable bits transmitted by the user per joule of energy consumed. Focusing on linear receivers, the Nash equilibrium for the proposed game is derived. It is shown that the equilibrium is one where the powers are signal-to-interference-plus-noise ratio-balanced with the minimum mean-square error (MMSE) detector as the receiver. In addition, this framework is used to study power-control games for the matched filter, the decorrelator, and the MMSE detector; and the receivers' performance is compared in terms of the utilities achieved at equilibrium (in bits/joule). The optimal cooperative solution is also discussed and compared with the noncooperative approach. Extensions of the results to the case of multiple receive antennas are also presented. In addition, an admission-control scheme based on maximizing the total utility in the network is proposed.     

A Satisficing Approach to Aircraft Conflict Resolution

Future generations of air traffic management systems may give appropriately equipped aircraft the freedom to change flight paths in real time. This would require a conflict avoidance and resolution scheme that is both decentralized and cooperative. We describe a multiagent solution to aircraft conflict resolution based on satisficing game theory. A key feature of the theory is that satisficing decision makers form their preferences by taking into consideration the preferences of others, unlike conventional game theory that models agents that maximize self-interest metrics. This makes possible situational altruism, a sophisticated form of unselfish behavior in which the preferences of another agent are accommodated provided that the other agent will actually take advantage of the sacrifice. This approach also makes possible the creation of groups in which every decision maker receives due consideration. We present simulation results from a variety of scenarios in which the aircraft are limited to constant-speed heading-change maneuvers to avoid conflicts. We show that the satisficing approach results in behavior that is attractive both in terms of safety and performance. The results underscore the applicability of satisficing game theory to multiagent problems in which self-interested participants are inclined to cooperation.     

一种基于不完全信息环境下多议题协商的最优化

文章探讨了Agent之间双边多议题的协商。主要以议程和协商程序这两个因素研究了其结果．并分析了不完全信息环境下不同议程和程序的协商过程，在此基础上，我们确定了逐一问题和一揽子交易两个协商程序的平衡策略，最后，给出了每个Agent所有可能议程和过程组合优化的协商结局。     

A simulation approach based on negotiation and cooperation betweenagents: a case study

Presents AGENDA (A GENeral testbed for Distributed AI Applications), a simulation tool developed for the simulation and design of applications involving interacting entities. This testbed consists of two different levels, the architecture level and the system development level. The architecture level describes a methodology for designing software agents by providing several important functionalities an agent should have. On the other hand, the system development level provides the basic knowledge representation formalism, general inference mechanisms, and a simulation tool-box supporting visualization and monitoring of agents. Following this, the applicability of AGENDA to the transportation domain is presented in detail. The main challenge of AGENDA in the context of this domain has been to provide different cooperation-scalable methods based on negotiation, leading to different scheduling mechanisms, and to experimentally evaluate these mechanisms. This evaluation shows that: (1) AGENDA is suitable for realistic application in the transportation domain; (2) the mechanisms used for vertical negotiation (between trucks considered as agents) and for horizontal negotiation (between companies considered as agents) are applicable for the real-world transportation domain applications. Finally, a complete study of the scalability of the simulation tool and the algorithms used for the negotiation is presented. This study, along with the evaluation of the different mechanisms, can help designers of transportation companies, particularly in the case of large companies     

An Agent-Based Multiservice Negotiation for eCommerce

Future generations of electronic commerce infrastructures will facilitate multiservice negotiations — negotiations between one customer and several providers regarding the provision of a personalised bundle of services. These negotiations allow the customer to obtain, for example, a complete travel package made up of several flights and hotel reservations, and matching the customer's specific requirements (regarding budget for example).The main issue in a multiservice negotiation is to handle the constraints that tie together the services within the bundle. Another is to design a scalable negotiation protocol, i.e. one that performs well regardless of the size of the bundle of services.A specific multiservice negotiation is proposed that has two distinctive properties. Firstly, its protocol is defined by a dynamic and decentralised constraint satisfaction algorithm. Secondly, the protocol is embedded within a set of mobile software agents, which perform the negotiation on behalf of the customer. The negotiation is tested on a travel agency application, and exhibits several valuable qualities. It is more scalable than traditional centralised facilitator-based solutions. It can also be customised easily (for optimisation purposes for example), without upgrading software on the providers' sides. Additionally, it is very suitable for mobile users, who are intermittently connected to the network.     

Repeated game theory as a framework for algorithm development in communication networks

This article presents a tutorial on how to use repeated game theory as a framework for algorithm development in communication networks. The article starts by introducing the basis of one‐stage games and how the outcome of such games can be predicted, through iterative elimination and Nash equilibrium. In communication networks, however, not all problems can be modeled using one‐stage games. Some problems can be better modeled through multi‐stage games, as many problems in communication networks consist of several iterations or decisions that need to be made over time. Of all the multi‐stage games, the infinite‐horizon repeated games were chosen to be the focus in this tutorial, because optimal equilibrium settings can be achieved, contrarily to the suboptimal equilibria achieved in other types of game. With the theoretical concepts introduced, it is then shown how the developed game theoretical model, and devised equilibrium, can be used as a basis for the behavior of an algorithm, which is supposed to solve a particular problem and will be running at specific network devices. Copyright © 2015 John Wiley & Sons, Ltd.     

Bottleneck Routing Games in Communication Networks

We consider routing games where the performance of each user is dictated by the worst (bottleneck) element it employs. We are given a network, finitely many (selfish) users, each associated with a positive flow demand, and a load-dependent performance function for each network element; the social (i.e., system) objective is to optimize the performance of the worst element in the network (i.e., the network bottleneck). Although we show that such "bottleneck" routing games appear in a variety of practical scenarios, they have not been considered yet. Accordingly, we study their properties, considering two routing scenarios, namely when a user can split its traffic over more than one path (splittable bottleneck game) and when it cannot (unsplittable bottleneck game). First, we prove that, for both splittable and unsplittable bottleneck games, there is a (not necessarily unique) Nash equilibrium. Then, we consider the rate of convergence to a Nash equilibrium in each game. Finally, we investigate the efficiency of the Nash equilibria in both games with respect to the social optimum; specifically, while for both games we show that the price of anarchy is unbounded, we identify for each game conditions under which Nash equilibria are socially optimal.     

Satisficing negotiations

Negotiation procedures that are founded on the doctrine of individual rationality, where each participant is committed to maximizing its own satisfaction, are limited in their ability to accommodate the interests of others, and therefore, may unnecessarily constrain the negotiability of a decision maker, particularly in cooperative environments. Satisficing game theory provides a distinct alternative to the hyperrationality of conventional rational choice by waiving reliance on the individual rationality premise and offering an approach to negotiatory decision making that is based on a well-defined mathematical notion of satisficing, or being good enough, that permits the modeling of complex interrelationships between agents. This approach provides a mechanism to compute the attitude, or degree of conflict or contentedness, of the negotiators. Examples illustrate both single-round and multiround satisficing negotiation protocols.     

Fair-efficient call admission control policies for broadbandnetworks-a game theoretic framework

A fundamental problem in connection oriented multiservice networks (ATM and STM) is finding the optimal policy for call acceptance. One seeks an admission control policy that efficiently utilizes network resources while at the same time being fair to the various call classes being supported. The theory of cooperative games provides a natural and precise framework for formulating such multicriterion problems as well as solution concepts. The authors describe how this framework can be used for analysis and synthesis of call admission strategies in broadband networks. In particular they investigate the Nash (1950), Raiffa-Kalai-Smorodinsky (Raiffa, 1953; Kalai and Smorodinsky, 1975), and modified Thomson (Cao, 1982) arbitration solutions from game theory. The performance of all solutions is evaluated by applying the value iteration algorithm from Markov decision theory. The approach is illustrated on a one-link network example for which the exact solutions can be achieved. The results indicate that the arbitration schemes from game theory provide some attractive features especially when compared to traditional control objectives: blocking equalization and traffic maximization. The authors also compare the optimal solutions with some simplified policies belonging to four different classes: complete sharing, coordinate convex, trunk reservation, and dynamic trunk reservation. The comparison indicates that in many cases, the trunk reservation and dynamic trunk reservation policies can provide fair, efficient solutions, close to the optimal ones     

Load balance in hierarchical routing network

In this article, the problem of load balance in hierarchical routing network is studied. Since conventional shortest path first (SPF) algorithm over aggregated topology in hierarchical routing network may result in worse routing performance, a traffic sharing path selection algorithm and a variable weight scheme are put forward for hierarchical routing network, which can equilibrate the utilities of link resources and reduce the blocking probability of connections with the improvement on survivability. Simulations are conducted to evaluate proposed variable weight and traffics balance (VWTB) algorithm, which combines traffic sharing and variable weight. From the simulation results, it can be found that the proposed VWTB algorithm can balance the traffics and equilibrate the utilities of link resources significantly.     

Moving power through the northeast corridor

Most urban utilities in the northeast and midAtlantic regions lack sufficient generation to meet their peak loads, and in the summer rely on daily imports in the hundreds of megaWatts from other utilities with power to sell. Since extensive transmission networks mean more reactive power losses, utilities are increasingly turning to capacitor banks, which can be installed close to inductive loads, to supply reactive power. Another side effect of long-distance transmission across grids, called wheeling, is caused by a basic law of alternating current networks: the paths over which current is going to flow cannot be chosen for all practical purposes; rather, they are determined by electrical characteristics, namely, the relative voltages, phase angles, and reactance of various points in the network. This results in parallel power flows where part of the power flows into areas that do not want it. A solution to this problem is the phase-angle regulator, a transformerlike device that lets dispatchers change the relative phase angle between two system voltages, thereby helping them control real power transfers between the two systems