Automated Negotiation Among Autonomous Agents in Negotiation Networks Export

@phdthesis{goradia07c, abstract = {Distributed software systems are a norm in today's computing environment. These systems typically comprise of many autonomous components that interact with each other and negotiate to accomplish joint tasks. Today, we can integrate potentially disparate components such that they act coherently by coordinating their actions via message exchanges. Once this integration issue is resolved, the next big challenge in computing is the automation of the negotiation process between the various system components. In this dissertation, we address this automated negotiation problem in environments where there is a conflict of interest among the system components. We present our negotiation model - a negotiation network - where a software system is a network of agents representing individual components in the system. We analyze the software system as a characteristic form game, one of many concepts in this dissertation borrowed from game theory. The agents in our model preserve the selfinterest of the components they represent (their owners), and make decisions that maximize the expected utilities of their owners. These agents accomplish joint tasks by forming coalitions. We show that the problem of computing the optimal solution, where the utilities of all agents are maximized, is hyper-exponential in complexity. We present an approximate algorithm for this hard problem, and evaluate it empirically. The simulation results show that our algorithm has many desirable properties - it is distributed, efficient, stable, scalable, and simple. Our algorithm produces the optimal (social welfare maximizing) solution for 96\% of cases, generates maximal global revenue for 97\% of cases, converges to 90\% of the best found allocation after only 10 rounds of negotiation, and finds a core-stable solution for revenue distribution among the agents for cases with nonempty core. Finally, to ensure stability for all cases, we present a sliding-window algorithm that computes the nucleolus-stable solution under all situations.}, author = {Goradia, Hrishikesh J.}, citeulike-article-id = {1586008}, citeulike-linkout-0 = {http://jmvidal.cse.sc.edu/papers/goradia07c.pdf}, keywords = {bibtex-import, multiagent, negotiation}, posted-at = {2007-08-23 14:42:29}, priority = {2}, school = {University of South Carolina}, title = {Automated Negotiation Among Autonomous Agents in Negotiation Networks}, url = {http://jmvidal.cse.sc.edu/papers/goradia07c.pdf}, year = {2007} }

TY - THES ID - goradia07c L3 - citeulike-article-id:1586008 N2 - Distributed software systems are a norm in today’s computing environment. These systems typically comprise of many autonomous components that interact with each other and negotiate to accomplish joint tasks. Today, we can integrate potentially disparate components such that they act coherently by coordinating their actions via message exchanges. Once this integration issue is resolved, the next big challenge in computing is the automation of the negotiation process between the various system components. In this dissertation, we address this automated negotiation problem in environments where there is a conflict of interest among the system components. We present our negotiation model - a negotiation network - where a software system is a network of agents representing individual components in the system. We analyze the software system as a characteristic form game, one of many concepts in this dissertation borrowed from game theory. The agents in our model preserve the selfinterest of the components they represent (their owners), and make decisions that maximize the expected utilities of their owners. These agents accomplish joint tasks by forming coalitions. We show that the problem of computing the optimal solution, where the utilities of all agents are maximized, is hyper-exponential in complexity. We present an approximate algorithm for this hard problem, and evaluate it empirically. The simulation results show that our algorithm has many desirable properties - it is distributed, efficient, stable, scalable, and simple. Our algorithm produces the optimal (social welfare maximizing) solution for 96\% of cases, generates maximal global revenue for 97\% of cases, converges to 90\% of the best found allocation after only 10 rounds of negotiation, and finds a core-stable solution for revenue distribution among the agents for cases with nonempty core. Finally, to ensure stability for all cases, we present a sliding-window algorithm that computes the nucleolus-stable solution under all situations. TI - Automated Negotiation Among Autonomous Agents in Negotiation Networks PB - University of South Carolina KW - bibtex-import KW - multiagent KW - negotiation AU - Goradia, Hrishikesh PY - 2007/// UR - http://jmvidal.cse.sc.edu/papers/goradia07c.pdf ER -