一种基于多Agent系统的在线广告竞价模型

张文明 王小平

(同济大学电子与信息工程学院 上海 200092)

一种基于多Agent系统的在线广告竞价模型

张文明 王小平

(同济大学电子与信息工程学院 上海 200092)

针对在线广告竞价这一具体应用场景，本文在价高者得的传统竞价原则上，结合竞价双方的相似度阈值控制，提出一种适用于在线广告交易的竞价模型，即SMOBM(the Similarity-based Multi-agent Online-advertising Bidding Model)模型。该模型使用多Agent系统建模，根据市场角色设计相应Agent，并设计出需求聚合Agent组织和资源聚合Agent组织。买卖双方使用回合制的拍卖协商方法进行连续叫价，并在系统全局时钟的控制下产生交易结果。最后，使用Repast Simphony仿真软件对模型进行实现，将基于组织模型和不基于组织模型这两种情况进行对比，结果表明在选择合适的相似度阈值时，基于组织模型的交易成功率高，且在存在恶性竞争时整体交易表现出较好的鲁棒性。

多Agent系统 在线广告竞价 Agent组织 相似度

0 引 言

在线广告不同于传统线下广告，后者方式单一且受众用户面狭窄;前者不仅为广告主创造了多样化的广告方式，且带来了精准的受众用户广告投放技术，也为互联网媒体服务商提供了流量变现的手段，其媒体形态和交互方式上的差异使得它们的交易方式也呈现分化。近年来，随着媒体商不断提高的流量变现的需求，以及广告主的广告投放向精细化发展，在线广告交易从早期的广告位合约和展示量合约方式，发展到搜索广告中的一般竞价方式，再到实时竞价交易方式，使得竞价成为了在线广告交易的主要手段。稳定的市场规则、良好的出价策略和高效率的买卖双方匹配机制能够带来一个健壮、均衡的在线广告交易市场，而如何设计这些市场规则和策略是一个困难的问题。

在线广告的竞价是双边拍卖的一种具体应用，而拍卖是经济学规律在日常经济生活中的一种直观体现，卖方有需要拍卖的物品，买方有购买物品的需求，双方根据市场规则出价协商交易，并且通过相应匹配策略确定最后的交易成功者和成交价。拍卖交易因其简单易行、公平高效等特性而逐渐受到学术界和业界的广泛关注，针对在线拍卖的特性，研究者们提出了一系列新的拍卖方法，多Agent系统中使用拍卖的方式来解决任务与资源分配、虚拟数字产品的定价等问题，已经有很多研究成果。如AbdolkarimSadrieh[1]提出了一种回合制的双边拍卖协商方法，卖方和买方交易一定数量的同种物品，双方分别按回合来轮次叫价，直至价格匹配交易成功；Shi B等[2-3]分析了双边拍卖市场中连续类型的交易智能体的报价行为，使用泛化的fictitious play算法来解决贝叶斯博弈问题，并详细分析了市场智能体的收费行为对报价策略的影响。当今社会的一些问题存在较大复杂性，对抗与合作并存，多Agent系统能利用组织的形式去体现这类行为，如徐晋晖等[4]提出了一种面向结构的组织形成方法和体现组织中个体的思维倾向的演化机制；张伟等[5]提出了一种Agent组织的递归模型，继承并进一步拓宽了以角色为中心的组织建模方式；Renna P[6]使用多Agent技术去模拟在竞争和合作关系下的可动态变化的网络，以及组织协作。在线广告中的广告位的拍卖交易有其自身特性，即为了保证最后投放广告的点击率，竞价成功的广告主所投放的广告需与受众用户具有较高的相似度，同时，在线广告的竞价具有较高的时效性，其以广告位和人群为标的的拍卖方式也不同与其它传统双边拍卖。

考虑在线广告的双边拍卖这一具体应用场景的上述特性，本文提出一种基于相似度的多Agent在线广告竞价模型SMOBM。计算广告主投放目标人群和广告位受众用户之间的相似度，大于相似度阈值的双方进行拍卖协商，在该模型中，广告主和互联网媒体商能够使用回合制的双边拍卖协商方法达成交易，并提高个体与整个市场的收益和交易效率。

1 SMOBM模型

所有互联网媒体商需要发布的广告位和人群标的AP(Advertising and People)统称为资源，所有广告主的广告投放要求(目标人群信息)统称为需求。AP的固有特性分为两个方面，广告位本身的价值和受众信息，可将量化后的自身价值和人群属性值相同的AP看作是同一种资源。买方的投放需求是根据自身的广告选择需要投放的人群，可将投放人群相同的需求看作同一种需求。本文包括四种独立Agent，分别是广告主Agent、互联网媒体商Agent、交易平台Agent和中介Agent。它们在模型中分别承担相应的角色，而Agent组织是Agent的集合，用于描述Agent间的合作与对抗等交互关系和行为，本文定义了两种Agent组织，分别是需求聚合Agent组织和资源聚合Agent组织。前者是一个买方组织，买方可选择加入该组织，并聚合到同需求小组，委托买方中介代为协商，后者是一个卖方组织，卖方可选择加入该组织，并聚合到同资源小组，委托卖方中介代替协商。

本文提出的SMOBM模型结构如图1所示。互联网媒体商是拍卖的发起者，可以加入资源聚合Agent组织中的同资源小组，并承担委托者角色。中介将拍卖信息发布到交易平台中，代替小组成员进行拍卖协商。广告主有投放广告创意的需求(选择需要投放的人群)，可以加入需求聚合Agent组织中的同需求小组。中介将需求发布到交易平台中，交易平台计算买卖双方需求与资源的相似度，只有相似度大于给定阈值的双方才能进行协商(广告主若同时参加多个协商需先进行预算分配)，协商方法为双方回合制连续叫价，直到协商成功或超时。

图1 SMOBM模型结构

SMOBM模型可以描述为一个十元组的形式。

SMOBM=

(1)

其中：

1)T为拍卖协商双方参与者的集合。包括买方M1和卖方M2，即广告主、卖方和买方中介，以及互联网媒体商。

2)G为互联网媒体商所提供的竞拍标的集合。即广告位和人群标的。

3)O为竞价前的AP所属关系。表明每个AP在竞价前属于哪个互联网媒体商，表示形式为G→M2。

4)S为相似度集合。每个AP拍卖前，需计算其与每个广告主需求的相似度。即∀g∈G，m∈M1，所有的AP和广告主需求的相似度集合S={Sgm|S(g×m)=Sgm}。

5)R为拍卖协商结果集合。包括每个AP最后的交易成功者和交易价格，表示形式为G→M1(c)|M2(0)。交易的结果有两种，交易成功时AP所属关系发生改变，AP由卖方转为买方，c表示交易价格；交易未成功时AP所属关系不变，交易价格默认为0。

6)P为回合制拍卖协商规则。本文使用有限状态机来定义，记拍卖协商过程中的所有状态集合为Status，包括开始状态Ss_start、中间状态Sb_mid和Ss_mid、结束状态Stimeout和Ssuccess，即Status={Ss_start,Sb_mid,Ss_mid,Stimeout,Ssuccess}。Status中定义的Agent可采取的通信动作原语分为四种，分别为Start(开始)，Accept(接受)，Refuse(拒绝)和Timeout(超时失败)。每个Agent的后继状态和采取的动作由当前状态和输入决定。

7)K为模型知识库。主要包含模型参数，卖方和买方的知识：

(1) 可以调节的模型参数。如，相似度控制的阈值θ等，针对不同的应用场合需设定不同的参数。

(2) 买卖双方知识。买方知识库保存买方关于其它买方的出价概率分布(信念)，卖方知识库保存卖方关于其他卖方的出价概率分布(信念)，双方在每回合出价中都会更新信念，即每回合的出价是基于当前知识。双方的出价策略均是采用贝叶斯博弈的方式，使用泛化的FP(Fictitiousplay)算法，算法思想是在买卖双方当前回合的出价概率分布基础上，通过计算回合最优反应出价函数得到回合最优出价，并且更新下一回合FP信念。

8)U是期望效用函数。对于卖方和买方Agent都存在一个期望效用函数，如式(6)所示，它们出价的目的都是为了使得期望效用最大。

9)H是拍卖协商交易历史信息的集合。拍卖历史集合保存了每次拍卖协商的交易结果，包括买卖双方的出价、组合的数量和最终交易状态(原语Timeout和Accept)。

10)C是模型限制条件的集合。限制条件为协商的最长交易时间。

1.1 相似度计算与阈值调控

SMOBM模型应用于在线广告拍卖这一具体场景，其中需要计算需求与资源的相似度。而在线广告中的受众用户信息与广告投放需求之间的相似度由其属性值的相似程度计算得来，本文模型采用相似系统理论[7-9]来计算，将广告位的受众用户信息和广告主的投放需求人群信息看作两个相似系统，具体的属性要素如地域、性别、年龄段和兴趣类别。在相似度的计算中，记某个广告位的受众用户信息为A，某位广告主的投放需求人群为B，A和B之间的相似属性个数为n，对于不同类型的属性其相似度计算方法也不同。

(1) 对于模型中区间类型的属性，假设其A和B的某一区间属性i(如年龄段)的值为[a1,b1]和[a2,b2]，其中a1,b1,a2,b2∈[y1,y2]，则根据文献[10]中的相似度计算方法来计算相似度Si：

(2)

(2) 对于模型中概念类型的属性(如地域)，则采用文献[11]的概念语义相似度计算方法来计算相似度Si：

(3)

其中，Lcs(i1,i2)表示距i1和i2最近的共同父概念，Deepth(Lcs(i1,i2))表示A和B的该属性的特征值i1和i2距离最近的共同父概念的深度，Deepth(Ci1)和Deepth(Ci2)表示i1和i2各自父概念的深度。

(3) 对于枚举类型的属性，根据枚举值是否相同来确定相似度，若其枚举值相同，则相似度为k，若不同，则相似度为0。

(4) 对于布尔类型的属性，可看作枚举类型的特例，若其布尔值相同，则相似度定为b，若不同，则相似度为0。

最后，A和B的整体相似度SAB为：

(4)

本文模型的属性有地域、性别、年龄段和兴趣类别，一般而言，广告投放首先考虑投放人群的兴趣类别，其次考虑地域，最后考虑性别和年龄段。可通过设定不同的相似度阈值来调节系统中参与拍卖的Agent的个数和买卖双方的相似程度，即，若SAB≥θ，则A和B匹配成功，可以进行本次拍卖协商；若SAB<θ，则A和B匹配不成功，不能进行协商。

1.2 独立Agent和期望效用

SMOBM模型中的四种独立Agent各自承担相应的社会功能，分别是：

(1) 卖方：互联网媒体商Agent和卖方中介Agent

拍卖协商的发起者，拥有大量互联网媒体广告位和用户信息，能够根据自身信念进行多回合内独立出价进行协商，并能自主选择加入或退出资源聚合Agent组织。卖方中介为卖方组织管理者，目的是使协商双方尽可能达成交易，调控市场供需平衡。

(2) 交易平台Agent

买方和卖方的交易平台，对卖方的AP和买方的需求计算相似度，并能够调节相似度阈值，初始化最长协商时间等全局参数，进行系统全局调控。

(3) 买方：广告主Agent和买方中介Agent

拍卖协商的参与者，有需要投放的广告创意，能够根据自身信念和预算进行多回合内独立出价协商，并能够委托中介Agent代为竞价，自主选择加入或退出需求聚合Agent组织。买方中介是买方组织管理者，能够代替买方交易协商，调控市场。

U(k,i,βb,λb,Ψb,Ψs,vk,Ski)=

(5)

其中，α1、α2、α3为不同的权值因子，且(α1+α2+α3)=1。在实际应用中，交易者通常优先考虑预算，其次考虑广告位的固有价值，本文模型中设计了一个需求与资源之间的相似度，因为买卖双方开始协商之前已经进行了相似度的阈值控制，双方的相似度不再是出价考虑的主要因素，因此交易者最后考虑的是相似度。

上面仅考虑了买方i在某一固定出价位置下的期望效用。因此，考虑i所有可能的出价(出价不能高于预算)位置集合Posi，计算其他买方的出价比其低的概率，若买方i不出价，则效用为0，则此时考虑所有情形下的买方i的期望效用如下所示：

(6)

卖方的期望效用与买方类似，出价目标都是使期望效用最大化。

1.3 基于需求聚合和资源聚合的Agent组织

卖方和买方为了获取更多的利益和减少冗余繁杂的拍卖市场开销，买方可自主选择加入或退出需求聚合Agent组织，卖方可自主选择加入或者退出资源聚合Agent组织，买卖双方均可在组织内加入同需求或同资源小组，组织内采用委托中介的方式统一协商拍卖。本文的Agent组织结构为树状模式[12]，如图2所示，每一颗子树为一个子组织，叶子节点为不可再分的特殊子组织，将其称为角色(角色也包括其它非叶节点，非叶节点为各子组织或组织的管理者)，角色由具体的Agent来实例化。

SMOBM模型中的资源聚合Agent组织的管理者角色由卖方中介Agent来承担，媒体商Agent可以加入资源聚合Agent组织，并加入到同资源的小组，承担委托者角色，委托卖方中介Agent代为拍卖其AP，而一个递归的树状组织结构可描述为如式(7)所示：

(7)

图2 树状组织结构

每一个媒体商Agent的目标都是拍卖其AP，但为了获取更多利益和避免自身冗余繁杂的拍卖协商操作，这些Agent可以有选择地加入资源聚合Agent组织，由卖方中介代售。将媒体商Agent的目标记为T，则任务T可以分解完成，即首先确定同资源小组中的所有AP的心理最低价中的最高价，记为T1，然后由卖方中介与买方进行回合制协商，记为T2。则T的分解结构为{(T,(seq,T1,T2))},其中seq表示任务顺序执行。由此可知，资源聚合Agent组织的角色Ro={R,R1,R2}，其中R为最高管理者角色，R1为委托者角色，R2为小组管理者角色，角色关系集合Re={(cmd,R,T,R1,T1),(cmd,R,T,R2,T2),(bef,R1,T1,R2,T2)}，如图3所示。其中cmd表示两个角色在完成角色目标时的父子关系，前者对后者拥有控制权，bef表示两个角色在完成角色目标时需要进行异步协调，后者需要在前者完成之后开始，目标集合O_g={T}，管理者角色集合Ma={R,R2}，其中R和R2分别为最高管理者和小组管理者。

图3 角色关系说明

资源聚合Agent组织是由媒体商Agent和卖方中介Agent按照组织结构组成的整体，媒体商Agent和卖方中介Agent分别对资源聚合Agent组织中的角色进行实例化，承担相应的任务，因此，一个完整的资源聚合Agent组织应为一个四元组形式，如式(8)所示：

Org=

(8)

其中，Org_id是用于唯一标识组织；Agents是Agent的集合，这里具体包括媒体商Agent和卖方中介Agent；OS为组织结构描述；Ins为具体的Agent与角色的实例化对应关系。

需求聚合Agent组织是由广告主Agent和买方中介Agent组成的联合买方交易整体，广告主Agent和买方中介Agent分别承担相应的角色，并负责完成相应的子任务，需求聚合Agent组织的四元组形式与资源聚合Agent组织相同。

1.4 回合制的双边拍卖协商方法

本文使用回合制的双边拍卖协商方法，即对于互联网媒体商发布的某一AP(广告位和人群标的)，由相似度大于某一阈值参数的广告主和中介来进行竞价，卖方和买方轮流叫价，直至一个买方和卖方达成交易，或者因超时未协商成功而交易失败，导致流拍。

回合制拍卖的协商过程可以概括为：媒体商通过向交易平台发布一个AP来发起一次协商，或者加入资源聚合Agent组织，由卖方中介发起协商。首先由交易平台计算该AP与所有的买方需求的相似度，媒体商或卖方中介再向所有相似度大于某一阈值的买方发送一个提议的价格，每个买方收到这一议价之后则轮到买方回合，由买方对卖方的议价作出反馈，接受或提交自己的出价，卖方收到所有买方反馈后再进入卖方回合，卖方处理所有买方的反馈后，对买方作出反馈，经过这样多轮回合协商之后会产生协商结果。

回合制的拍卖协商规则如图4所示。

图4 拍卖协商规则状态图

共有五种状态，Ss_start表示协商开始，由卖方(媒体商或卖方中介)发起一次协商，是卖方的第0回合；Sb_mid和Ss_mid分别表示买方和卖方中间回合；结束状态包括Stimeout和Ssuccess。协商过程中的通信原语有四种，分别为Start、Refuse、Accept和Timeout，其中Start表示发起一次协商，使用在卖方第0回合，参数包括(发送方，轮次0，出价，接收方)；Refuse表示拒绝对方的提议，并给出自己的出价，用在卖方除第0回合之外的回合和买方的所有回合，参数包括(发送方，轮次i，出价，接收方)；Accept表示接受对方的提议，用在卖方除第0回合之外的回合和买方所有回合，参数包括(发送方，轮次i，接收方)；Timeout表示超时，在全局时钟下达到最长交易时间时强制发送，参数包括(发送方，轮次i，接收方)，此时则协商失败。

对于买方和卖方的出价，本文使用泛化的FP算法[13]来计算，以买方为例，在某一FP信念(Ψb和Ψs)下，买方的出价是为了使期望效用最大，因此对应的最优出价函数如式(9)所示：

F(βb,Ψb,Ψs,vk,Ski)=argmaxλb∈ΛU(βb,λb,Ψb,Ψs,vk,Ski)

(9)

因为拍卖协商有最长交易时间的限制，协商进度应随着时间增长而相对加快，因此对于买方每回合的出价，本文在最佳反应报价的基础上加上一个时间增强项t，其初始值为0，并且随着交易时间的增大而增大，本文取t为时间的线性函数值(对于卖方，t为时间衰退项，初始值为0，并且随着时间的增大而减小)，则回合最优出价如式(10)所示：

G(t,βb,Ψb,Ψs,vk,Ski)=t+F(βb,Ψb,Ψs,vk,Ski)

(10)

综合上述分析，给出SMOBM模型的回合制拍卖协商算法，如算法1所示。

算法1 回合制拍卖协商算法

输入 广告位的固有价值V，AP和需求属性值，初始FP信念Ψb和Ψs，初始轮次h=0

输出 协商结果(交易双方，最终交易价格，最终交易回合)

Do

1.进入卖方第h回合，在当前FP信念Ψs下，计算回合最优报价函数G(t,βs,Ψb,Ψs,νk,Ski)；

2.产生最优回合报价λs对应的预算段，并计算λs为所有卖方出价最低的概率Prob(Ψs)；

5.若λb>λs，则协商成功，达成交易，并结束；否则执行下一步；

6.进入买方第h回合，在当前FP信念Ψb下，计算回合最优出价函数G(t,βb,Ψb,Ψs,νk,Ski)；

7.产生回合最优出价λb对应的预算段，并计算λb为所有买方出价最高的概率Prob(Ψb)；

10.h=h+ 1；

While(λb<λs&&未到最长协商交易时间)

2 实验分析

2.1 实验环境和数据

本文使用Repast Simphony 2.3仿真软件[14]和Matlab2014b来对模型进行实验验证。Repast软件由芝加哥大学的社会科学计算研究所与美国Argonne国家实验室的研究人员共同开发，主要用于多Agent系统的离散建模仿真。实验数据本文采用iPinYou公司发布的数据集[15]，此数据用于其自身算法优化[16-17]，包含较全的展示类广告数据。数据集分为三轮，其格式稍有不同，本文选用第一轮的数据，其采集区间为一个星期，共记录了7天的真实数据，主要包括竞价日志、展示日志和点击日志，特征属性共有22个，主要包括时间戳、地理位置(如所在城市)、参与竞价的出价价格和最终成交价(RMB/CPM)(iPinYou发布数据集时对出价进行了修改，在价格上乘了一个因子进行线性变换，因此与真实数据可能有所偏差，但本文是在出价概率分布上计算回合最优出价，并得出整体交易成功率，因此价格的线性变换对本文并无影响)等。本文从第一轮数据集中选取部分数据进行实验，并去掉无关的属性，如iPinyou ID和IP等，在此基础上进行实验仿真。

2.2 模型初始化

使用Repast软件来执行本文的SMOBM模型，需先设置一些参数并对其初始化，本文模型需设置的参数主要分为以下四个方面：

(1) 各种Agent的个数，SMOBM模型中的Agent有媒体商Agent、广告主Agent、交易平台Agent、以及买方和卖方中介Agent，分别设置其Agent个数。本文根据数据集中的买卖双方比例分布来选取部分数据进行实验。在数据集中，对于每个广告位平均约有10个广告主参与竞价，因此按照买卖双方10∶1的比例来选取数据，取媒体商Agent和广告主Agent数量分别为50个和500个，交易平台Agent数量对实验无影响，设为1个即可，而买卖双方中介Agent则根据需求和资源数量分别取100个和10个。

(2) 设置限制集，模型中主要有交易时间限制，即最长拍卖协商时间。在本文中，由于实验方式为计算机软件来模拟拍卖协商，协商交易在很短的时间内完成，因此本文实验对最长拍卖协商时间不作限制。

(3) 设置模型相似度阈值和预算分配参数值，分别用来控制参与交易的买卖双方的最低相似度和广告主同时参与多个协商的预算分配情况。在本模型中对预算分配策略不作优化，设定预算分配参数为1，即φ=1时，表示按照相似度S和广告位固有价值V的大小来按比例分配预算。而相似度阈值θ的取值根据图7获得。

(4) 交易者期望效用函数的权值因子和相似度属性权值。根据本文模型和实际应用情况，通常优先考虑交易者的预算，其次考虑广告位的固有价值，最后考虑相似度，因此本文实验分别设定其权值因子为0.45、0.35和0.2。而相似度属性一般先考虑人群兴趣类别，其次考虑地域，最后考虑性别和年龄段，因此分别设定其权值分别为0.35、0.25、0.2和0.2。部分模型参数设置如表1所示。

表1 模型参数值设置

2.3 模型组织演化

在对模型初始化后，就可以执行模型。本文SMOBM模型中存在需求聚合Agent组织和资源聚合Agent组织，它们分别由买方和卖方聚合形成，广告主和媒体商可委托中介代替进行拍卖协商，即这些Agent可以加入组织并聚合到某个子组织，中介进行统一协商。本文模型初始化后开始执行时Agent分布如图5所示。

图5 模型开始执行时Agent分布示意图

图5中分别使用圆形表示买方中介Agent，方形表示卖方中介Agent，星形表示媒体商Agent，三角形表示广告主Agent，为了便于观察组织演化，其他Agent未予以显示。在模型执行之初，由图5可知模型未发生任何演化且Agent间未进行任何交互。

图6 模型执行后的Agent分布示意图

Repast软件是以tick数来表示时间，在模型执行了1 975个Tick后，Agent组织分布如图6所示。可以看到，一些买方中介Agent和广告主Agent发生了聚合(即图6中圆形和三角形)，广告主选择加入需求聚合Agent组织并聚合到同需求子组织，相同的，也有一些媒体商选择了加入资源聚合Agent组织(即图6中方形和星形)。但是，仍有部分单个的红色方形和蓝色方形游离，这是因为有些广告主和媒体商没有选择加入Agent组织来委托中介协商，以上是对本文SMOBM模型中组织演化的一种直观表示。

2.4SMOBM模型拍卖协商分析

本文采用的是回合制的拍卖协商方法，由卖方发起一次拍卖，经过相似度计算和阈值控制后选出参与拍卖的买方，然后卖方和买方回合制连续叫价，直到交易结束。本文利用相似度阈值控制，统计所有进行了拍卖协商的媒体商的AP，得出不同阈值下的模型整体拍卖交易成功率。本文利用整体拍卖交易成功率来进行性能评价，整体交易成功率的计算如式(11)所示：

(11)

其中，As表示模型中的拍卖成功的次数，Aa表示模型总的拍卖次数，γ表示成功次数占总次数的比例。且分别仿真了基于组织(资源聚合Agent组织和需求聚合Agent组织)的模型和不基于组织的模型，并对比它们在不同相似度阈值下的整体拍卖交易成功率。

不同的相似度阈值下的整体拍卖交易成功率如图7所示，基于组织模型和不基于组织模型整体交易成功率均呈现先上升后下降的趋势，这是因为随着阈值θ的逐渐增大，拍卖经过筛选后去掉了低相似度的交易者，相似度较高的交易者有更大的机会协商成功，而随着θ增大到一定程度时，会导致参与拍卖的交易者数量急剧减少，使得整体交易成功率降低。当θ在0.5到0.6区间附近时，交易成功率达到峰值且相对稳定，如图7所示。

图7 SMOBM的基于组织和不基于组织交易成功率

由图7可知，在回合制协商实际出价基础上，基于组织相比不基于组织的SMOBM模型在一定程度上增加了整体拍卖交易成功率，整体交易成功率的提高率的计算如式(12)所示：

(12)

其中，γo表示基于组织模型的交易成功率，γwo表示不基于组织模型的交易成功率。本文根据θ=0.5和θ=0.6时的交易成功率的提高率的平均值来得到基于组织相对不基于组织模型的提高率，因此，在选取了合适的相似度阈值的情况下，本文基于组织的SMOBM模型比不基于组织的SMOBM模型交易成功率提高了约8.22%。

在实际拍卖中，可能存在某些卖者个体通过恶意出价来哄抬价格或者某些买者联合其他部分买者压低价格，这是一种恶性竞争的现象。本文为了模拟这一市场行为对模型的影响，在部分媒体商个体和广告主个体的回合制协商出价中，通过对出价进行一定比例的线性变换来达到篡改部分卖方和买方的行为的效果，即对于买方和卖方出价，修改方法对应的计算如式(13)所示：

(13)

图8 不同异常出价比例下的交易成功率

从图8可见，本文分别选取了不同比例的出价进行变换，达到异常出价的目的，并得到不同比例异常出价时基于组织模型和不基于组织模型的整体交易成功率。两种模型的成功率曲线走势大致相同，其中基于组织的SMOBM模型要比不基于组织的模型更加稳定。这是因为组织在模型中起到一个调控市场的作用，尽管有部分卖方和买方个体出价异常，但是对于加入组织的买卖双方都能尽可能地达成一致，使得协商成功率相对稳定。在异常出价占5%时，前者比后者交易成功率增加了9.59%，异常出价占30%时，交易成功率增加了24.85%。由此可知，当市场存在恶性竞争时，基于组织的SMOBM模型相比不基于组织更加稳定，且至少能提高约9.59%的整体拍卖交易成功率。

综上所述，在选择合适的相似度阈值时，能提高一定比例的整体交易成功率，并对比基于组织的模型和不基于组织的模型，前者相比后者约能提高8.22%的整体交易成功率，并且在存在恶性竞争的情况下，前者能保持相对稳定，一般至少能提高9.59%的成功率。

3 结 语

本文将多Agent系统应用到在线广告竞价这一具体场景，基于在线广告竞价交易的特点，设计出SMOBM模型，采用相似度阈值控制与拍卖协商相结合的方式，使得在价高者得这一传统竞价模式下，还能在一定程度上保证投放广告与投放人群和广告位之间的相关性。SMOBM模型模拟人类社会中实际双边拍卖方式，使用Agent组织来交互演化，模型中设计出资源聚合Agent组织和需求聚合Agent组织，将买卖双方聚合，委托中介协商，其交易方式采用回合制的拍卖协商使得买卖双方轮次连续叫价，叫价策略采用泛化的FP算法，在每一回合计算出最佳反应出价，多回合后在全局时钟的控制下产生交易结果。实验结果表明在选定合适的相似度阈值时，基于组织的模型相比不基于组织的模型整体交易成功率更高，且鲁棒性更好。

下一阶段的工作将会对SMOBM模型进一步细化，本文的SMOBM模型简化了一些方面复杂度，如广告主同时参与多个竞价时的预算分配，本文按照相似度和广告位固有价值来按比例分配，未来的工作中会对其进行策略优化。模型中设置了较多参数，后期工作会对其进一步调优，同时，对组织模型进行更深入的研究。

[1]SadriehA.TheAlternatingDoubleAuctionMarket:AGameTheoreticandExperimentalInvestigation[J].LectureNotesinEconomicsandMathematicalSystems,2001,71(1):84-86.

[2]ShiB,GerdingEH,VytelingumP,etal.Anequilibriumanalysisofcompetingdoubleauctionmarketplacesusingfictitiousplay[C]//Proc.ofthe19thEuropeanConf.onArtificialIntelligence,2010:575-580.

[3] 石兵.双边拍卖市场中交易者报价策略和市场收费策略的博弈论分析[J].多智能体系统及应用,2015:149-160.

[4] 徐晋晖,张伟,石纯一,等.面向结构的组织形成和演化机制[J].计算机研究与发展,2001,38(8):897-903.

[5] 张伟,石纯一.Agent组织的一种递归模型[J].软件学报,2002,13(11):2149-2154.

[6]RennaP.Dynamicco-opetitivenetworkorganizationsupportedbymultiagentarchitecture[M]//BusinessOrganizationsandCollaborativeWeb:Practices,StrategiesandPatterns,PA:IGIGlobal,2011.

[7] 周美立,王浣尘.相似系统的分析与度量[J].系统工程,1996,14(4):1-6.

[8] 周美立.相似系统工程[J].系统工程理论与实践,1997,17(9):37-43.

[9] 刘晓文,韩冰,蒋永辉,等.支持需求聚合的C2B旅游电子商务自动谈判系统研究[J].计算机应用与软件,2015,32(8):52-55.

[10] 任凯,浦金云.基于案例属性特征区间相似度的改进算法研究[J].控制与决策,2010,25(2):307-310.

[11]BergmannR,StahlA.Similaritymeasuresforobject-orientedcaserepresentations[C]//Proceedingofthe4thEuropeanWorkshoponAdvancesinCase-BasedReasoning,1998:25-36.

[12] 石纯一,张伟.基于Agent的计算[M].北京:清华大学出版社,2007:275-320.

[13]RabinovichZ,GerdingEH,PolukarovM,etal.Generalisedfictitiousplayforacontinuumofanonymousplayers[C]//Proc.ofthe21stJointConf.onArtificialIntelligence,2009:245-250.

[14]NorthMJ,CollierNT,OzikJ,etal.ComplexadaptivesystemsmodelingwithRepastSimphony[EB/OL].[2013-01-03].http://www.casmodeling.com/content/1/1/3.pdf.

[15]iPinYou.GlobalBiddingAlgorithmCompetition[DB/OL].http://contest.ipinyou.com/data.shtml.2013.

[16]PerlichC,DalessandroB,HookR,etal.BidOptimizingandInventoryScoringinTargetedOnlineAdvertising[C]//Proceedingsofthe18thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining,2012:804-812.

[17]ZhangC,ZhangE.Optimizedbiddingalgorithmofrealtimebiddinginonlineadsauction[C]//2014InternationalConferenceonManagementScienceandEngineering(ICMSE),2014:33-42.

AN ONLINE ADVERTISING BIDDING MODEL BASED ON MULTI-AGENT SYSTEM

Zhang Wenming Wang Xiaoping

(SchoolofElectronicsandInformationEngineering,TongjiUniversity,Shanghai200092,China)

Since the online advertising auction is becoming a new application scene, the SMOBM model based on the traditional principle of success of highest-price-offer and two sides of the transaction similarity threshold controlhave been proposed in this paper.This model uses Multi-Agent system to design, according to the market role, the corresponding Agent and Agent organization are designed, including the demands aggregation Agent organization and resources aggregation Agent organization, the buyers and sales uses a round-based negotiation method to bid for the auction, and produce the results of transactions under the control of global clock. The paper used the Repast Simphony simulation software to realize the model, the model is compared in two cases, one used the organization and the other didn’t. In the choice of a suitable similarity threshold, the results show that the former has higher transaction success rate and overall transaction showed robust in the existence of malicious competition.

Multi-Agent system Online advertising auction Agent organization Similarity

2016-05-24。张文明，硕士生，主研领域：机器学习和社会计算。王小平，教授。

TP399

A

10.3969/j.issn.1000-386x.2017.02.023