臺灣博碩士論文加值系統

在多重代理人的合作或討論時，常會因為認知的不同而發生意見的衝突。為了達成共識，則必須經由協商來解決衝突，以尋求滿足彼此利益的共識。以政治的觀點來看，代理人表示意見、解決衝突與決定決策，可分為半民主與民主的方式。在此我們提出了混合式民主的協商，以達到民主式協商的優點，以及半民主式協商的長處。同時也避免了兩者的缺點。另外，在我們研究了其他相關的協商方法後，提出了我們的協商方法。並根據一些考量，與其他的協商架構做了比較，並將之以表列出。
協商可被視為一種分散式的搜尋動作，而其搜尋的空間則為可能的解決方案。我們的協商方法中，主要提供兩個架構。第一是分組的機制，可將有相近意識的代理人集和在一起，縮小相互討論的範圍，提高協商的效率。第二為分組的討論方法，讓代理人能提出自己的意見，以主動的方式來更快達成協議與提案對整體接受度的增加。並在此兩架構下，使協商複雜度降低。代理人之間是否達成共識可用是否被觸犯到可改變衝突或不可改變衝突而定。而我們的方法，將以偏好是否發生可改變或不可改變的衝突，來做為共識達成與否的考量。
最後我們將協商的方法實現在會議排程，並透過這例子的應用來表現我們方法的優點。

In the Multi-agent negotiation and discussion processes, there are many differences between the preferences of the agents and they get conflicts with each other. In order to reach the consensuses and look for the mutually benefits, agents need to resolve the conflicts through negotiation. As far as the viewpoint of politics are concerned, the agents express comments, resolve conflicts, and make decisions could be classified into democracy and half-democracy. In the thesis, we bring up a mixed-democracy negotiation method with the advantages of democracy and half-democracy and improve the disadvantages of them. After we study the other related negotiation methods, we propose our negotiation method and make a comparison with the other methods in a list according to some viewpoints. Negotiation could be seen as a distributed search process, and the search space includes many possible solutions for the conflicts between the agents. In our method, there are two main frameworks to decrease the complexity of negotiation. One is Grouping that gathers the agents have the similar preferences, and concentrates the negotiated issues. The other is Group Discussion that agents can propose their arguments actively to increase the acceptability of solution. In our negotiation method, the hard and soft conflicts would effect the consensus could be made or not. Finally, we implement our negotiation method on meeting scheduling, and express the advantages of our method through the experiment.

摘要 Ⅰ
目錄 Ⅲ
圖目錄 Ⅴ
表目錄 Ⅵ
1. 簡介 1
2. 相關背景與研究 3
2.1. 代理人協商 3
2.2. 協商的問題與分類 5
2.2.1.獨裁式 5
2.2.2.民主式 6
2.2.3.半民主式 6
2.2.4.問題探討 7
2.2.4.1. 複雜度 7
2.2.4.2. 可接受度 7
2.3. 協商的相關研究 8
2.3.1. 以爭議為基礎的協商 9
2.3.1.1. 有限制的爭議式協商 10
2.3.1.2. 無限制的爭議式協商 11
2.3.2. 說服式協商 12
2.3.3. 投票式協商 14
2.3.4. 賽局理論式協商 17
2.4. 比較說明 18
2.5. 動機 21
3. 以爭議與分組為基礎的多重代理人協商 23
3.1. 協商架構 23
3.2. 架構說明與分析 26
3.2.1分組 26
3.2.2 分組討論 27
3.2.2.1. 集合與佇列 28
3.2.2.2. 分組討論動作流程 31
3.2.2.3. 代理人提出爭議 33
3.2.2.4. 代理人評估提案 35
3.3. 複雜度 36
3.4. 接受度 37
3.5. 與其他方法的比較 39
4. 利用會議排程來實現協商方法 42
4.1. 實作會議流程分析 42
4.2. 實驗環境與結果 46
4.3. 總結 47
5. 結論與後續工作 48
參考文獻 49

[1]、K. Sycara , "Multiagent system". AI Magazine, Vol. 10, No. 2, pp. 79-93,1998.
[2]、Kersten, G. E. and D. Cray . "Perspectives on Representation and Analysis of Negotiations: Towards Cognitive Support Systems." Group Decision and Negotiation,1995.
[3]、Beer, M. and d''Inverno, M. and Jennings, N. and Luck, M. and Preist, C. and Schroeder, M.,”Negotiation in Multi-Agent Systems”. Knowledge Engineering Review 14(3):285-289,1999.
[4]、 N. R. Jennings, P. Faratin, A. R. Lomuscio, S. Parsons, M. Wooldridge, and C. Sierra.“Automated negotiation: prospects, methods and challenges”.International Journal of Group Decision and Negotiation, 10(2):199—215, 2001.
[5]、[Democracy in Open Agent System] Democracy in Open Agent Systems
Peter McBurney, Simon Parsons
[6]、J.K.Pearson and P.G.Jeavons,”A Survey of Tractable Constraint Satisfaction Problems”,Technical Report CSD-TR-97-15, July, 1997.
[7]、A.M. Abbas, E.P.K. Tsang,” Constraint-based timetabling - A case study”, Proceedings of the ACS/IEEE International Conference on Computer Systems and Applications (AICCSA ''01),2001.
[8]、F. Dignum and W. Nuijten and L. Janssen,” Solving a time tabling problem by constraint satisfaction”, F. P. M. Dignum, W. P. M. Nuijten, and L. M. A. Janssen. Solving a time tabling problem by constraint satisfaction. Technical report, Eindhoven University of Technology, 1995.
[9]、T. Shintani and T. Ito and K. Sycara,” Multiple Negotiations among Agents for a Distributed Meeting Scheduler”,In the Proceedings of the Fourth International Conference on Multi Agent Systems (ICMAS2000), 2000.
[10]、Takayuki Ito and Toramatsu Shintani ,“Persuasion among Agents：An Approach to Implementing a Group Decision Support System Based on Multi-Agent Negotiation”, IJCAI (1),pp.592-599,1997.
[11]、S. Parsons, C. Sierra, and N. R. Jennings. "Agents that reason and negotiate by arguing". Journal of Logic and Computation, 8(3):261—292, 1998.
[12]、S. D. Parsons and N. R. Jennings ,”Negotiation through argumentation-a preliminary report”, Proceedings of the Second International Conference Multi-Agent Systems ICMAS''96,1996.
[13]、T. W. Sandholm ,”An Implementation of the Contract Net Protocol Based on Marginal Cost”, Proceedings of the 12th International Workshop on Distributed Artificial Intelligence, pp. 295-308,1993.
[14]、N. R. Jennings and S. Parsons and P. Noriega and C. Sierra,”On Argumentation-Based Negotiation”, Proceedings of the International Workshop on Multi-Agent Systems,1998.
[15]、B. Laasri, H. Laasri, S. Lander and V. Lesser,”A generic model for negotiating agents”, Int. Journal of Intelligent and Cooperative Information Systems, 1(2), pp. 291-317, 1992.
[16]、R. Loui and D. Moore,“Dialogue and Deliberation”, R. Loui and D. Moore Dialogue and Deliberation Negotiation Journal (submitted),1998.
[17]、Miland Tambe and Hyuckchul Jung ,”The Benefits of Arguing in a Team “, The AI Magazine, Vol. 20, No. 4, pp. 85-92 ,1999.
[18]、Qiu, Z. and Tambe, M. ,”Towards Argumentation-based Collaborative Negotiation: A preliminary report”, In International workshop on multi-agent systems, Mass.Institute of Technology, October, 1998.
[19]、Hyuckchul Jung, Milind Tambe, Weixiong Zhang, Wei-min Shen,”On Modeling Argumentation as Distributed Constraint Satisfaction: Initial Results”,Proceedings of the International workshop on Distributed Constraint Satisfaction, 2000.
[20]、Saaty, Th. L.” The Seven Pillars of the Analytic Hierarchy Process. ISAHP Proceedings”,Kobe, pp. 15, 1999.
[21]、K. Sycara,” Negotiation Planning: An AI Approach”,European Journal of Operational Research, Vol. 46, No. 2, May, pp. 216-234, 1990.
[22]、Chris Reed and Derek Long and Maria Fox and Max Garagnani,”Persuasion as a Form of Inter-Agent Negotiation”, DAI, pp.120-136, 1996.
[23]、Tuomas W. Sandholm ,”distributed rational decision making”, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pp. 201-258, 1999.
[24]、Donald G. Saari ,”THE SYMMETRY AND COMPLEXITY OF ELECTIONS”, Complexity 2,pp.13-21, 1997.
[25]、Wellman, Michael P. and Greenwald, Amy and Stone, Peter and
Wurman, Peter R. ,”The 2001 Trading Agent Competition”, Fourteenth Conference on Innovative Applications of Artificial Intelligence, pp. 935-941, 2002.
[26]、Minghua He and Nicholas R. Jennings,”SouthamptonTAC:designing a successful Trading Agent”, In Fifteenth European Conference on Artificial Intelligence, Lyon, France, 2002.
[27]、Dajun Zeng and Katia Sycara ,”Bayesian learning in negotiation”, Human-Computer Studies (1998) 48, pp. 125-141,1998.