摘 要

在自动协商竞赛中，代理商的偏好是达成互利协议的极其重要的因素。然而，代理人通常会保守秘密，以避免在谈判过程中被对手利用。从而对手建模在ANAC竞赛中成为极其重要的一部分，对手建模成为整个竞赛相当重要的一部分，在本文中，利用了国内外已经提出的双边多问题中的谈判方法来帮助谈判代理人在对手代理人的偏好是私人信息的情况下最大化他们的效用。在贝叶斯学习，时间序列预测和回归技术，强化学习这几种方法中选用了比较成熟易用的贝叶斯学习方法。贝叶斯算法当下已发展的较为成熟，可以在其原理上不断改造，贝叶斯学习被用来分析对手的历史报价并近似预测对手对谈判问题的偏好。而且，还价计算命题算法可以集成在贝叶斯方法中，以帮助代理商根据偏好学习结果生成互利优惠。另外，实验结果表明了贝叶斯学习方法在效用增益和谈判效率方面的良好性能。

关键词：自动协商，，双边谈判，对手建模，贝叶斯学习

Abstract

In the Automated Negotiating Agents Competition , the agency's preference is an extremely important factor in reaching a mutually beneficial agreement. However, agents often keep secrets to avoid being used by opponents during the negotiation process. Therefore, the modeling of opponents becomes an extremely important part of the ANAC competition. The modeling of opponents becomes a vital part of the entire competition. In this paper, the negotiation methods used in domestic and foreign bilateral issues have been used to help negotiators Opponents' preference is to maximize their utility in the case of private information. In Bayesian learning, time series prediction and regression techniques, and reinforcement learning, Bayesian learning methods that are more mature and easy to use are used. The Bayesian algorithm has been developed more mature now, and it can be continuously reformed on its principle. Bayesian learning is used to analyze the opponent's historical quotation and approximate the opponent's preference for the negotiation problem. Moreover, the counter-validity calculation proposition algorithm can be integrated in the Bayesian method to help agents generate mutually beneficial offers based on preference learning results. In addition, the experimental results show that the Bayesian learning method has good performance in terms of utility gain and negotiation efficiency.

Key Words：Automated negotiation, Bilateral negotiation，opponent modelling, Bayesian learning

目录

摘 要 3

Abstract 4

目录 5

第1章绪论 1

1.1研究的背景和意义 1

1.2国内外研究现状 2

1.3主要研究内容和技术路线 3

1.4论文结构安排 3

第2章ANAC竞赛的平台 4

2.1ANAC概述 4

2.2参赛者要求 4

2.3参赛者遭遇规则 4

2.4 GENIUS 5

第3章基于贝叶斯学习的谈判方法 6

3.1 基本谈判模式 7

3.2谈判特许策略 9

3.3谈判中的贝叶斯学习 9

第4章实验 12

4.1实验参数设置 12

4.2实验结果 13

4.3实验结果讨论 15

第5章结论 19

参考文献 20

致谢 22

第1章绪论

1.1研究的背景和意义

谈判是各方共同解决共同关切以改善现状的过程，谈判是人类社会的核心活动，并且经过各种学科的研究，包括经济学，人工智能，博弈论和社会心理学。传统上，谈判是一项必要但费时且昂贵的活动。因此，在过去的二十年里，人们对谈判和电子谈判系统^[1]的自动化越来越感兴趣，例如在电子商务中。自1980年代初以来，这方面的关注一直在增长，其中包括Smith's Contract Net Protocol ，Sycara的说服者，Robinson's oz以及Rosenschein和Klein。这种兴趣是由自动化代理能够与人类谈判协商以及发现更好的人类协商者的承诺所推动的。自动化的潜在好处包括自动化所带来的时间和谈判成本的降低，用户可以避免社交冲突，提高用户谈判技巧的谈判能力的潜在增加，以及通过探索更有前途的结果空间部分发现更有趣的交易的可能性。自动协商是一种决策形式，代理商共同探讨可能的解决方案以达成协议。自动化谈判的一个重要研究领域是设计谈判方法，以协助谈判代表在谈判过程中达成互利协议。为了实现双赢协议，代理人通常需要发现或预测对手的私人信息，如效用函数，特许策略，谈判期限，预订价格，偏好等。在代理人的私人信息中，对谈判问题的偏好是用于交易问题的重要信息。通过交易问题，谈判结束时代理商可以达成双赢协议的可能性很高。准确地说，在多问题谈判中，代理人通常对不同的谈判问题有不同的偏好。与低优先级问题相比，高优先级问题可以帮助代理商产生更多效用。在多方谈判期间，代理人提出的要约不仅应该使自己的效用最大化，而且不应该减少其对手的效用，因此对手代理人会更愿意接受要约。

为了提出这样一个合适的报价，代理商需要知道他们的对手对谈判问题的偏好。根据对手的偏好，代理商可以交换问题并提出互惠优惠。但是，在正常情况下，自我利益代理人不愿意透露他们的偏好信息。因此，偏好学习已成为促进双赢谈判结果的关键因素在谈判中，贝叶斯学习算法^[2]被用来预测对手的偏好。所提出的方法的主要贡献是（1）所提出的偏好学习算法不需要关于对手初始化学习的任何额外信息。学习程序仅基于对对方的还价分析; （2）所提议的谈判方法综合了一个还价命题算法，该算法能够根据从对手那里学到的偏好有效地交易问题。因此，两家代理商都可以从互利优惠中增加公用事业。利用这些信息来解决对手的问题称为对手建模。拥有好的对手模型是提高谈判结果质量的关键因素，并且可以进一步提高谈判的好处，包括以下内容：达成双赢协议;通过避免非协议来最大限度地降低谈判成;最后，通过适应组织对谈判的偏好避免开发。实验表明，通过使用对手模型，自动代理可以达到比人类谈判更有效的结果。除了提高谈判过程的质量外，对手模型对于自动化谈判过程来说是必不可少的。而且，对于不适合于大型谈判的客户来说，它们不适合于大谈判历史行为的可行性。通过创造使用对手模型来适应其行为的适应性媒介，可以最大限度地减少开拓性贸易壁垒。尽管创造一个对手模型和报价的优势

分布式人工智能(DAI)的研究和网络化分布环境的普及推动了Agent的理论、技术，特别是多Agent的理论^[4]、技术的发展，因为它为分布开放系统的分析、设计和实现提供了一个崭新的途径。自从Minsky在1986年出版的“思维的社会”中提出Agent的概念后，智能代理技术随着计算机科学的发展迅速趋于成熟，在很多应用领域有很好的应用前景。随着多Agent技术的快速发展^[5]，电子商务领域中Agent技术的应用日益广泛。Agent能够代替人类用户更加高效地处理复杂的商务活动，在电子商务活动中，自动协商^[6]是最为核心的部分，因此它成为基于Agent的电子商务研究的重点内容。

1.2国内外研究现状

人工智能技术已经在智能制造领域应用了20多年，特别是近几年分布式人工智能领域中多代理系统具有很好的应用前景。企业数据和应用的动态与分布性的增强要求软件不仅有被动地响应信息需求的能力，而且能以一定程度的智能，主动地预测、适应乃至积极地寻找途径以支持用户需要，并通过自动地合作以完成更加复杂的功能。进入90年代后，软件代理的研究迅猛发展，出现了多种代理类型，各种各样的应用及方法的出现是软件代理逐渐成熟的重要标志。研究人员已经应用代理技术用于制造企业的应用集成、供应链管理、生产计划、调度和执行控制、物料和库存管理，并且开发了很多基于多代理技术的软件系统以支持企业实现智能化业务运作。

而且研究技术日趋成熟：

•2006年高坚提出了一种加速混沌进化算法^[7]；

•2011年孙天昊提出了贝叶斯分类的增强学习方法^[8]；

•2013年陈利红等人提出了基于增强学习的多边多议题并行协商算法^[9]；

•2006年Brzistowski和Kowalczyk提出了只基于历史报价来估计不同模型agent行为的方法^[10]；

•2009年Sim等人提出将Bayesian学习和遗传算法协同作用算法^[11]；

•2010年Nabila Hadidi等人提出基于辩论的交替出价协商协议^[12]。

1.3主要研究内容和技术路线

ANAC竞赛^[3]挑战研究人员开发成功的自动谈判人员，在有不完全信息的对手的情况下。通过这种竞争，研究社区成为自动化谈判的推动者，研究其研究人员，鼓励设计通用的谈判代理，使其能够在各种各样的情况下运行，并提供性能的基准。

拟采用java作为系统中编程语言，对整个系统中的模块进行实现，在实现过程中，Agent既可以扮演propose的角色来发起协商，也可以充当participator参与与其他agent发起的协商^[13]，任意两个agent之间的协商构成一个协商过程；整个系统中的协商问题是该系统内所有协商过程的集合；Agent跟据协商的历史信息及基于知识库的知识概率分布，Agent在每次收到对手新的报价之后，利用贝叶斯法则更新其他环境对其他Agent的主观评价，使用统计的方法得出最优的方案 。

1.4论文结构安排

论文第一章主要介绍所选题目的背景，意义，国内外研究现状以及主要研究内容和技术路线；第二章介绍关于ANAC竞赛平台；第三章介绍了使用的算法贝叶斯学习；第四章介绍了实验的结果和分析；第五章是论文结论；第六章为参考文献；第七章是论文致谢。

第2章ANAC竞赛的平台

2.1ANAC概述

ANAC（Automated Negotiating Agents Competition）竞赛^[3]汇集了来自谈判界的研究人员，并为评估多问题领域的实际谈判策略提供了独特的基准。先前的竞赛在自主代理设计领域引发了人工智能领域的新颖研究，可供更广泛的研究团体使用。其中的的竞争焦点之一在于非线性效用函数^[16]。比赛的目标是：鼓励设计实用的谈判代理人，能够熟练地与不知名的对手进行谈判，并且在各种情况下为客观评估不同谈判策略提供基准，探索不同的学习和适应策略和对手模型，以及收集最先进的谈判代表和谈判场景，并将其提供给更广泛的研究界。

2.2参赛者要求

参赛者必须开发并提交一个在Genius上运行的自主谈判代理。Genius是一个基于Java的谈判平台，您可以在其中创建谈判域和偏好配置文件，并开发谈判代理。该平台允许您模拟谈判会议并运行锦标赛。代理人的表现将在锦标赛设置中进行评估，其中每个代理人与其他提交的代理人相匹配，并且每组代理人将在若干协商场景中进行协商。参赛者的目标是发展自主谈判代理。代理人的表现将在锦标赛设置中进行评估，其中每个代理人都与所有其他提交的代理人相匹配，每对代理人将在多种非线性谈判场景中进行协商。谈判重复多次，以获得统计意义上的显着结果。获胜代理将是总分最高的代理。谈判场景包括通过谈判来解决的目标和问题的说明。这包括谈判双方对可能达成的协议的偏好。一方的偏好使用非线性多问题效用函数进行建模。

2.3参赛者遭遇规则

谈判是双边的，基于交替供应协议。优惠在3分钟后以截止日期实时交换。这意味着在特定时间段内交换的商品数量会有所不同，并取决于代理商所需的计算。如果在截止日期之前没有达成协议，或者任何一方在截止日期前选择终止谈判，那么这两位代理人都会收到冲突的效用。此外，约一半的域名会有折扣因素，协议的价值会随着时间而下降。代理人面临的挑战是在不知道对手的偏好和策略的情况下进行谈判。尽管每个代理商都参与了许多谈判会议，针对不同的对手，并且在各种谈判场景中，代理商不能在谈判之间学习。这意味着谈判代理只能有机会适应并从他们在单个谈判会议中收到的报价中学习。

代理人可能因违反公平游戏的精神而被取消资格。竞争规则允许来自单个机构的多个条目，但要求每个代理独立开发。此外，禁止设计有利于其他特定代理商的代理商。特别是，严禁下列行为：（1）以某种特定的其他代理人的方式设计代理人。（2）在比赛中与代理人进行沟通。（3）在比赛期间更改代理人。参与者可以使用高达2GB的代理记忆，如果他们使用的数量超过了这个数量而系统无法应付，他们的代理将被排除在竞争对手之外。

2.4 GENIUS

谈判比赛使用基于Java的GENIUS谈判平台进行，该谈判平台的开发旨在促进双边多问题谈判领域的研究。它具有开放的架构，可以使用设计模式轻松开发和整合现有的协商代理。GENIUS可用于模拟个别谈判会议以及各种谈判场景中谈判代理之间的比赛。该系统的核心功能包括：（1）谈判领域和偏好简介的规范;（2）模拟代理商之间的双边谈判;（3）分析谈判结果和谈判动态。它还允许通过图形用户界面来指定协商域和偏好配置文件。GENIUS平台以及以前竞赛中的代理和场景可供使用。

第3章基于贝叶斯学习的谈判方法

一般来说，考虑到所有投标的集合，有一小部分投标更优选为两个代理的结果。确定这些特殊出价可能会导致双方达成更好的协议。对于单个代理商而言，最优的出价对代理商来说具有最大的效用。 通常这个出价对另一个出价很低，所以协议的机会很低。 一个更普遍的谈判最优化概念涉及到两种代理的实用程序。有多种方式可以确定一个更全球化的“最优化”。最优化的一种方法是出价不是最优的对于双方来说，如果有另一个出价对一方有更高的效用，并且对另一方至少有相同的效用。则称最优性类型的是帕累托最优，并形成自动化谈判中的一个重要概念。 帕累托最优出价的集合被称为帕累托最优边界。谈判中的一个主要挑战是代理人可以隐藏他们的偏好。 这意味着代理不知道其中对手倾向于给出一组出价。 这个问题可以通过构建对手模型来部分解决，通过分析谈判轨迹来分析对手的偏好。 现在每个代理人都可以获得最佳的出价，对手给予一组类似的优选出价。

预留值是一个实值常数，它设定了一个低于该值的理性代理人不应接受任何角色的阈值。直观上，保留价值是与谈判协议最佳替代方案（BATNA）相关的公用事业。预约价值是代理商在谈判会议中没有达成协议时将获得的效用。 这个如果代理人离开谈判，或者未能在截止日期前达成协议，都可能发生。 换一种说法：或者谈判双方就结果达成一致，并且两个代理人都会收到的相关效用^[18]，或者没有达成协议在这种情况下，两个代理商都会收到他们的预留价值。预留值通常每个都不相同对不同的谈判代理来说。如果在一个文件中没有设置预留值，则假定为0。

谈判持续几秒钟的预定时间，或轮流进行。在Genius中，时间线是正常化的，即：时间t 为[0; 1]，其中t = 0表示谈判的开始，t = 1表示截止日期。操纵剩下的时间可以成为一个因素来提高结果。在基于时间的和基于循环的协议之间有一个重要的区别。在基于时间的协议中代理商的计算成本应该直接在其中考虑减少可以的出价量。相反，对于基于轮次的谈判，时间可以被认为是在一轮内暂停;因此计算成本不起作用。除了截止日期之外，情景还可能包含折扣因素。折扣因素会降低出价的效用随着时间的推移正在谈判。虽然两个代理商共享时间，(中指定的折扣因子代理人介绍;让t 在 [0; 1]范围内是当前规范化时间，如时间线所定义;我们计算折扣实用程序U_D^t的结果来自未折现的效用函数U如下：

如果d = 1，效用不受时间影响，并且这种情况被认为是未折现的，而如果d非常小，代理商达成协议的压力很大。折扣因素是偏好程序的一部分，因此不同的代理商可能有不同的贴现因子。如果存在折扣因子，则保留价值将与其他公用事业的效用完全相同的结果。通过具有折扣的预留价值，代理人可以合理地设定该预留值提前谈判，从而默认为预留价值。

3.1 基本谈判模式
我们的谈判模式部分采用了Faratin等人提出的多问题谈判模式^[15]。
让我表示其中一个谈判代理人，并且i^’表示其对手代理人，并且j（j∈1，...，n）是两个代理人之间协商的问题之一。令x_j=[min_j,max_j]

为问题j的值，[min_j,max_j]代表xj的范围。每个代理人都有一个评估函数Eji：[minj，maxj]→[0,1]，它将问题j的值计算为介于0和1之间的归一化值。对于不同的协商问题，代理人I^’评估函数可能不同。让wji捐赠问题j的代理权重。根据上述条款，代理人的效用函数可以由方程（1）定义：

(1)