Luận án tiến sĩ: Thương lượng hợp đồng trong xã hội đa tác nhân

THE UNIVERSITY OF TULSA THE GRADUATE SCHOOL NEGOTIATING CONTRACTS IN MULTIAGENT SOCIETIES by Sabyasachi Saha A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Discipline of Computer Science The Graduate School The University of ‘Tulsa 2006 UMI Number: 3240312 Copyright 2006 by Saha, Sabyasachi All rights reserved. INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted.

Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3240312 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 THE UNIVERSITY OF TULSA THE GRADUATE SCHOOL NEGOTIATING CONTRACTS IN MULTIAGENT SOCIETIES by Sabyasachi Saha A DISSERTATION APPROVED FOR THE DISCIPLINE OF COMPUTER SCIENCE By Dissertation Committee , Chairperson Professor Sandip Sen Abe Professor AKfilesh Bajaj Professor William Coberly ii COPYRIGHT STATEMENT Copyright ©) 2006 by Sabyasachi Saha All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the author. 1H ABSTRACT Sabyasachi Saha (Doctor of Philosophy in Computer Science) Negotiating Contracts in Multiagent Societies Directed by Professor Sandip Sen (207 pp., Chapter 9) (205 words) In agent-based applications in electronic commerce and other information sys- tems, agents, representing real-life negotiating parties, negotiate resources and ser- vices with other agents or humans.

Self-interested software agents, often with conflict- ing preferences, can negotiate mutually acceptable agreements. In this dissertation, we focus on the following major aspects of such automated negotiations: negotiation frameworks, negotiation strategies, effects of social context and agent attitudes on negotiation outcomes. Additionally, we discuss an agent architecture for effectively using arguments for negotiation and study an automated supply chain as an example application of automated contracting. The primary contributions of this dissertation are the following: i) the development of efficient frameworks for multi-issue negotia- tion with divisible and indivisible issues, ii) the design of a negotiation strategy that models opponent’s preferences in repeated negotiations to improve individual utility of the agent, iii) the analysis of the performance of multiple negotiation strategies under different negotiation environments and their evolution in a society of adaptive agents, and, iv) the development of an architecture and a decision theoretic framework for argumentation-based negotiations.

We have also designed an efficient scheduling and pricing strategy for a supplier in a dynamic electronic supply chain, an appli- cation of automated contracting, where contracts are awarded via an auction-based negotiation protocol. 1V ACKNOWLEDGEMENTS [would like to express my gratitude all those people who supported me during this period of my PhD. First, I would like to thank my advisor, Professor Sandip Sen for his guidance, support and encouragement. He was always there for discussion whenever I needed.

I have learned a lot from him during this period. I would like to express my gratitude to my dissertation committee members, Professor Akhilesh Bajaj, Professor William Coberly, Professor Rose Gamble, Pro- fessor Mauricio Papa, and Professor Roger Wainwright for their insightful comments and valuable suggestions that helped me to improve my dissertation. Tam thankful to Mathematical and Computer Sciences Department of Uni- versity of Tulsa, National Science Foundation grant ITS-0209208 and NASA EPSCoR RIG for providing funding during my dissertation research. I also want to thank ineinbers of our DAI-HARD research group for their valuable comments.

I would particularly thank Stephane Airiau, Dipyarnan Banerjee, Teddy Candale, and Dr. Partha Dutta (University of Southampton) with whom I have done collaborative research and co-authored papers. I would like to thank my parents and my brother for encouraging me for higher education and for their constant support. Last but certainly not least I would like to give my special thanks to my wife Baijayanty Gupta for her endless love and support during my graduate study without which I would not have been able to achieve my goal.

TABLE OP CONTENTS Page COPYRIGHT.v ko iii ABSTRACT. và kg kg KV k kia k va iv ACKNOWLEDGEMENTS. TL II TABLE OF CONTENTS. 2 ee va vi LIST OF TABLES.

Q Q Q Q Q Q Q Q u và k kia 1X LIST OF FIGURES. XIV CHAPTER 1: INTRODUCTION rDOe 1.1 Designing Efficient Protocols for Multi-issue Negotiation 1.2 Learning Opponent Decision Model in Repeated Negotiation 1.3 Negotiation in Multiagent Society .4 Argumentation Based Negotiation.5 Automated Contracting ina Supply Chain. — CHAPTER 2: RELATED RESEARCH 2.1 Designing Negotiation Mechanisms .2 Design of Agent Strategies.3 Argumentation Based Negotiation. 24 CHAPTER 3: MULTI-ISSUE NEGOTIATION PROTOCOLS FOR DIVISIBLE ISSUES 26 3.2 Negotiation with Side Payments .2 Rational Strategy of Agents in SOWPE .3 Efficiency of the Negotiation Outcome Using SOWPE Protocol 35 3.3 Negotiation without Side Payments.

vn kg kg va 36 3.2 Protocol for Exploiting Preference Asymmetry (EPA) .3 Combined E-POSE Protocol. 0 ce ee eee 46 3.5 Outcome Efficiency and Preference Revelation Trade-offs .4 Outcome Efficiency and Preference Revelation with Proposed Protocols. gà va va 59 3. 60 CHAPTER 4: MULTI-ISSUE NEGOTIATION PROTOCOLS FOR INDIVISIBLE ISSUES 63 41 Negotiation Framework.2 Existing Negotiation Protocols .3 Protocol to Reach Optimal Agreement in Negotiation over Multiple Indivisible Resources (PONOMIR) .4 Properties of the PONOMIR Protocol.

00 cee ee es 75 4.1 An Illustration of the PONOMIR Protocol. gu gà vang cv kg va 77 CHAPTER 5: LEARNING OPPONENT DECISION MODEL IN REPEATED NEGOTIATION 79 5.1 Buyer Agent Behaviors.3 Modeling Sample Probability Functions .4 Experimental Framework and Results. và kg và 95 CHAPTER 6: ADAPTIVE NEGOTIATION IN AGENT SOCIETIES 97 6.1 Negotiation in the Marketplace.1 Negotiation with Selective Partners .5 Adaptation by Negotiating Agents.1 Experimental Results with Adapting Agents. và gà v v v va 126 CHAPTER 7: ARGUMENTATION-BASED NEGOTIATION 128 7.3 Architecture of Argumentation Based Agent .4 Bayes Net Model of Opponent’s Belief .1 Bayesian Networks and Influence Diagram .2 An Illustration of the Agent Belief Model.5 Offer or Argument Selection Procedure.

ga kg va 146 CHAPTER 8: AUTOMATED CONTRACTING IN A SUPPLY CHAIN147 8.3 Utility of Scheduling a Task .1 Experiments with Different Scheduling Stralegies.2 Experiments with Different Pricing Strategies. v kg V kia 166 CHAPTER 9: CONCLUSIONS AND FUTURE WORK 172 BIBLIOGRAPHY. 000: y và kg kia 177 APPENDIX A: FINDING PARETO FRONTIER. 189 APPENDIX B: AN ALGORITHM TO APPROXIMATE PROBABILITY FUNCTION.

190 vill LIST OF TABLES Page 3.1 Comparison among the proposed protocols in terms of closeness to Pareto efficiency and preference revelation. # in the subcolumns of 2, 5 and 6 represents the number of issues N involved in the negotiation.2 Qualitative comparison among the proposed protocols.1 Utilities of two agents for different allocations.2 Reduction in search by agents.1 Probabilities of Generating Tasks: the row number gives the length of the task; the column (2 — 1) shows the probability of generating high priority task in the 7** day and the column 2i shows the probability of generating alow priority ta§K. uc eeee 157 ix LIST OF FIGURES Page 3. (d) Bargaining solutions using proposed protocols when preferences of agent 1 and 2 are {0.2 Bargaining solutions when preferences of agent 1 and 2 are {0.3 Bargaining solutions when preferences of agent 1 and 2 are {0.4 Bargaining solutions when preferences of agent 1 and 2 are {0.5 Bargaining solutions when preferences of agent 1 and 2 are {0.6 Bargaining solutions when preferences of agent 1 and 2 are {0.7 Deviation of an agreement from Pareto optimality .8 Maximum deviation from Pareto optimality when agents are using POSE protocol with 4,8 and 12 issues).9 Maximum deviation from Pareto optimality when agents are using E- POSE protocol with 4, 8 and 12 issues.10 Reduction in preference revelation when agents are using E-POSE pro- tocol compared to using the POSE protocol.11 Number of additional revelations, compared to POSE, when agents are using GPOSE protocol.1 Negotiation tree formed for example in Table4.1 Approximating f(z) = 1— ep: Number of Chebychev Polyno- mials used is 5.

Number of Chebychev Polynomials 08 86 543 Approximating f(z) = 1— reals) using different number of Cheby- chev Polynomials. Number of sample size is 400. 87 — 544 Approximating f(z) = 1— Tepes): Number of Chebychev Polyno- mials used is 10.5 Wealth earned by different buyer types. Seller’s decision function is given in Equation 1.6 Wealth earned by different buyer types.

Seller’s decision function is given in Equation 1.7 Wealth earned by different buyer types. Seller’s decision function is given in Equation 2.8 Wealth earned by CB buyers using different exploration time. Seller’s decision function is given in Equation 5. Number of Chebychev’s polynomials is 5.9 Noisy environment with Gaussian noise ~ Gaussian(0,0.

Explo- ration time = 600. vu k k kg kia 94 5.10 Wealth earned by the CB buyers using different inter-exploration interval 95 5.11 Wealth earned by the CB buyers using different exploration-frequency 96 6.1 Average payoff earned by reciprocatives and selfish agents for varying length of negotiation periods.2 Average payoffs of different agent types for varying proportion of NS agents in the population. uc Quà kg ee 108 xi 6.3 Average payoffs of different agent types in four different negotiation scenarios for varying proportion of NS agents in the population.4 Average payoff earned by reciprocatives and VO agents for varying length of negotiation periods.5 Average payoff earned by reciprocatives and differential selfish agents for varying length of negotiation periods.6 Average payoffs earned by NS, R and DS agents for varying proportion of NS agents in the population.7 _Äverage payoff earned by reciprocatives and differential selfish agents for varying proportion of DS agents in the population.8 Average payoffs of different agent types for varying proportion of 5 agents in the population. Average payoffs of different: agent types for varying proportion of NS agents in the populatiON.10 Average payofis of different agent types over time periods when agents interacts fixed number of opponents.

Number of fixed-interactions in each time period is 20.11 Average payoffs of different agent types over time periods when agents interacts fixed number of opponents. Number of fixed-interactions in each time period is 65.12 Proportion of agents of different types over generations. Initially all agents are present in equal number.13 Proportion of agents of different types over generations. Initially all agents are present in equal number.14 Proportion of R and Š agents over generations.15 Proportion of R and S agents over generations.16 For a given initial population distribution of S, NS and R agents, mini- mum € required for reciprocative strategy to be evolutionarily dominant.17 Proportion of agents of diferent types (DS, R, NS) over generations.

Initially all agents are present in equal number.18 For a given initial population distribution of S, NS and R agents, mini- mum € required for reciprocative strategy to be evolutionarily dominant.19 Proportion of agents of different types (DS, NS, and R) over genera- tions. Initially all agents are present in equal number. In each time period, each agent negotiates with a maximum of 50 agents.1 An example of a negotiation using arguments.2 Decision Architecture of the arguing agent.3 Approximate belief model of the opponent.1 Supply chain structure.2 Average Wealth earned by different supplier types. There are 3 sup- pliers using each of four scheduling strategies.

Task distribution is as shown in Table 8.3 Increase in bid prices for high priority tasks over the course of arun.4 Number of contracts won by different supplier types.5 Average Wealth earned by different supplier types with uniform task distribution8. cu gà gà va 163 8.