An incentive-based distributed mechanism for scheduling divisible loads in tree networks

The underlying assumption of Divisible Load Scheduling (DLS) theory is that the processors composing the network are obedient, i.e., they do not “cheat” the scheduling algorithm. This assumption is unrealistic if the processors are owned by autonomous, self-interested organizations that have no a priori motivation for cooperation and they will manipulate the algorithm if it is beneficial to do so. In this paper, we address this issue by designing a distributed mechanism for scheduling divisible loads in tree networks, called DLS-T, which provides incentives to processors for reporting their true processing capacity and executing their assigned load at full processing capacity. We prove that the DLS-T mechanism computes the optimal allocation in an ex post Nash equilibrium. Finally, we simulate and study the mechanism under various network structures and processor parameters.     

Information sharing and exchange in the context of product lifecycle management: Role of standards

This paper introduces a model of the information flows in Product Life cycle Management (PLM), serving as the basis for understanding the role of standards in PLM support systems. Support of PLM requires a set of complementary and interoperable standards that cover the full range of aspects of the products’ life cycle. The paper identifies a typology of standards relevant to PLM support that addresses the hierarchy of existing and evolving standards and their usage and identifies a suite of standards supporting the exchange of product, process, operations and supply chain information. A case study illustrating the use of PLM standards in a large organization is presented. The potential role of harmonization among PLM support standards is described and a proposal is made for using open standards and open source models for this important activity.     

Robust combinatorial auction protocol against false-name bids

This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for combinatorial auctions, we must consider the possibility of a new type of cheating, i.e., an agent tries to profit from submitting several bids under fictitious names (false-name bids). If there exists no false-name bid, the Generalized Vickrey Auction protocol (GVA) satisfies individual rationality, Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is theoretically impossible for a combinatorial auction protocol to simultaneously satisfy these three properties.

Our newly developed Leveled Division Set (LDS) protocol, which is a modification of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bundle or separately. The LDS protocol satisfies individual rationality and incentive compatibility even if agents can submit false-name bids, although it is not guaranteed to achieve a Pareto efficient social surplus. Simulation results show that the LDS protocol can achieve a better social surplus than that for a protocol that always sells goods in one bundle.     

Supporting Internet-scale multi-agent systems

The Internet provides a large-scale environment for (intelligent) software agents. Agents are autonomous (mobile) processes, capable of communication with other agents, interaction with the world, and adaptation to changes in their environment. Current approaches to support agents are not geared for large-scale settings. The near future holds thousands of agents, hosts, messages, and migratory movements of agents. These large-scale aspects require a new approach to facilitate the development of agent applications and support. AgentScape is a scalable agent-based distributed system, described in this paper, that aims at tackling these aspects.     

Selective Smooth Fictitious Play: An approach based on game theory for patrolling infrastructures with a multi-robot system

The multi-robot patrolling problem is defined as the activity of traversing a given environment. In this activity, a fleet of robots visits some places at irregular intervals of time for security purpose. To date, this problem has been solved with different approaches. However, the approaches that obtain the best results are unfeasible for security applications because they are centralized and deterministic. To overcome the disadvantages of previous work, this paper presents a new distributed and non-deterministic approach based on a model from game theory called Smooth Fictitious Play. To this end, the multi-robot patrolling problem is formulated by using concepts of graph theory to represent an environment. In this formulation, several normal-form games are defined at each node of the graph. This approach is validated by comparison with best suited literature approaches by using a patrolling simulator. The results for the proposed approach turn out to be better than previous literature approaches in as many as 88% of the cases of study. Moreover, the novel approach presented in this work has many advantages over other approaches of the literature such distribution, robustness, scalability, and dynamism. The achievements obtained in this work validate the potential of game theory to protect infrastructures.     

Fault tolerant mechanism design

We introduce the notion of fault tolerant mechanism design, which extends the standard game theoretic framework of mechanism design to allow for uncertainty about execution. Specifically, we define the problem of task allocation in which the private information of the agents is not only their costs of attempting the tasks but also their probabilities of failure. For several different instances of this setting we present both, positive results in the form of mechanisms that are incentive compatible, individually rational, and efficient, and negative results in the form of impossibility theorems.     

Game theoretical applications for multi-agent systems

We consider game-theoretic principles for design of cooperative and competitive (non-cooperative self-interested) multi-agent systems. Using economic concepts of tâtonnement and economic core, we show that cooperative multi-agent systems should be designed in games with dominant strategies that may lead to social dilemmas. Non-cooperative multi-agent systems, on the other hand, should be designed for games with no clear dominant strategies and high degree of problem complexity. Further, for non-cooperative multi-agent systems, the number of learning agents should be carefully managed so that solutions in the economic core can be obtained. We provide experimental results for the design of cooperative and non-cooperative MAS from telecommunication and manufacturing industries.     

A game theory framework for ISP streaming traffic management

The overlay/underlay topology mismatch affects the performance of existing P2P platforms that can generate large volumes of unnecessary inter-ISP network traffic. Although recent works have shown the benefits of network awareness P2P solutions, no studies have focused on the investigation of the ISP behavior and their cooperative/non-cooperative attitudes.This paper proposes a game theoretic framework to help the design of techniques promoting the ISP cooperation in P2P streaming platforms and decreasing unnecessary inter-domain streaming traffic.We first analyze some simple scenarios to discuss the existence of Nash equilibria, the Pareto optimality, and a fairness criterion to refine the equilibrium points. Moreover, we apply ideas from Evolutionary Game Theory to design a distributed schemata that the ISPs can use to reach “socially acceptable” equilibrium points in a large ISP population. Furthermore, we develop a discrete event simulation to evaluate the effectiveness of the Evolutionary Game Theory framework.The study presented in the paper shows that the proposed strategies can effectively stimulate ISP cooperation aiming at the minimization of inter-ISP traffic and help to provide reliable P2P streaming service.     

开放系统中互操作技术的发展和前景

经历九十年代的持续实践,采用“开放系统”的思想来集成大型计算机系统,已成为技术界不争的事实。然而,完善的开放系统的实际形成有赖于“互操作性”的实现。本文将以互操作性为对象,探讨近十年来人们对其认识的深化,为有关挑战性难题所作的突破,以及未来发展的前景。     

博弈论在无线自组网技术中的应用

通过对无线Ad Hoc网络的分析,重点建立单、多播地址路由算法机理,分析其路由策略、输出O（A）、开销P（A）、实用性等要素,其要素选择正确与否,它将会得到正确与不正确的结果,通过博弈找到一种正确算法机理,能更好地应用到Ad Hoc网络中。     

Coordinating randomized policies for increasing security of agent systems

We consider the problem of providing decision support to a patrolling or security service in an adversarial domain. The idea is to create patrols that can achieve a high level of coverage or reward while taking into account the presence of an adversary. We assume that the adversary can learn or observe the patrolling strategy and use this to its advantage. We follow two different approaches depending on what is known about the adversary. If there is no information about the adversary we use a Markov Decision Process (MDP) to represent patrols and identify randomized solutions that minimize the information available to the adversary. This lead to the development of algorithms CRLP and BRLP, for policy randomization of MDPs. Second, when there is partial information about the adversary we decide on efficient patrols by solving a Bayesian–Stackelberg games. Here, the leader decides first on a patrolling strategy and then an adversary, of possibly many adversary types, selects its best response for the given patrol. We provide two efficient MIP formulations named DOBSS and ASAP to solve this NP-hard problem. Our experimental results show the efficiency of these algorithms and illustrate how these techniques provide optimal and secure patrolling policies. We note that these models have been applied in practice, with DOBSS being at the heart of the ARMOR system that is currently deployed at the Los Angeles International airport (LAX) for randomizing checkpoints on the roadways entering the airport and canine patrol routes within the airport terminals.

分布式开放超媒体系统DOHMS体系结构的设计与实现

首先讨论了超媒体发展趋势,分析了开放需求,在此基础上讨论了一个符合开放特性的分布式超媒体原型系统&&DOHMS的体系结构     

公共agent请求代理体系结构CARBA开放性验证研究

1 引言八十年代中叶计算机技术界出现了“开放系统”这一名称。在随后的商战中,开放系统日显其威力。高举此旗的厂商日趋兴旺,而反其道者日益衰落。此时用户所面临的困惑问题是:何为开放系统?如何组建自己单位即将构造的开放系统?我们经过近十年的研究,成功地完成了开放系统描述的研     

用于开放式分布处理的中间件的标准和规范

中间件使得开放式分布处理系统中异种机上的应用可以相互协同工作。     

Soft cooperation systems and games

A cooperative game for a set of agents establishes a fair allocation of the profit obtained for their cooperation. In order to obtain this allocation, a characteristic function is known. It establishes the profit of each coalition of agents if this coalition decides to act alone. Originally players are considered symmetric and then the allocation only depends on the characteristic function; this paper is about cooperative games with an asymmetric set of agents. We introduced cooperative games with a soft set of agents which explains those parameters determining the asymmetry among them in the cooperation. Now the characteristic function is defined not over the coalitions but over the soft coalitions, namely the profit depends not only on the formed coalition but also on the attributes considered for the players in the coalition. The best known of the allocation rules for cooperative games is the Shapley value. We propose a Shapley kind solution for soft games.     

An efficient Nash-implementation mechanism for network resource allocation

We propose a mechanism for auctioning bundles of multiple divisible goods in a network where buyers want the same amount of bandwidth on each link in their route. Buyers can specify multiple routes (corresponding to a source-destination pair). The total flow can then be split among these multiple routes. We first propose a one-sided VCG-type mechanism. Players do not report a full valuation function but only a two-dimensional bid signal: the maximum quantity that they want and the per-unit price they are willing to pay. The proposed mechanism is a weak Nash implementation, i.e., it has a non-unique Nash equilibrium that implements the social-welfare maximizing allocation. We show the existence of an efficient Nash equilibrium in the corresponding auction game, though there may exist other Nash equilibria that are not efficient. We then generalize this to arbitrary bundles of various goods. Each buyer submits a bid separately for each good but their utility function is a general function of allocations of bundles of various divisible goods. We then present a double-sided auction mechanism for multiple divisible goods. We show that there exists a Nash equilibrium of this auction game which yields the efficient allocation with strong budget balance.     

对于开放系统内涵的澄清

虽然开放系统是一个流行的名词，但是对于一般用户，它却是一个在实际工作中“无法操作”的事物。本文从计算机开放系统的基本特征出发，通过逻辑推理，导出描述开放系统的轮廓，借助于后者使开放系统一词的内涵得到了澄清，并使它的实现变成了“可操作的”。文中还从ＩＴ实际工作的方便出发，提出了一个简明的开放系统的工作定义。     

Gossip-based aggregation of trust in decentralized reputation systems

Decentralized Reputation Systems have recently emerged as a prominent method of establishing trust among self-interested agents in online environments. A key issue is the efficient aggregation of data in the system; several approaches have been proposed, but they are plagued by major shortcomings. We put forward a novel, decentralized data management scheme grounded in gossip-based algorithms. Rumor mongering is known to possess algorithmic advantages, and indeed, our framework inherits many of their salient features: scalability, robustness, a global perspective, and simplicity. We demonstrate that our scheme motivates agents to maintain a very high reputation, by showing that the higher an agent’s reputation is above the threshold set by its peers, the more transactions it would be able to complete within a certain time unit. We analyze the relation between the amount by which an agent’s average reputation exceeds the threshold and the time required to close a deal. This analysis is carried out both theoretically, and empirically through a simulation system called GossipTrustSim. Finally, we show that our approach is inherently impervious to certain kinds of attacks. A preliminary version of this article appeared in the proceedings of IJCAI 2007.     

A Verification Framework for Agent Communication

In this paper, we introduce a verification method for the correctness of multiagent systems as described in the framework of ACPL (Agent Communication Programming Language). The computational model of ACPL consists of an integration of the two different paradigms of CCP (Concurrent Constraint Programming) and CSP (Communicating Sequential Processes). The constraint programming techniques are used to represent and process information, whereas the communication mechanism of ACPL is described in terms of the synchronous handshaking mechanism of CSP. Consequently, we show how to define a verification method for ACPL in terms of an integration of the verification methods for CCP and CSP. We prove formally the soundness of the method and discuss its completeness.