互联网广告拍卖机制及优化方法研究

摘要

作为互联网多媒体市场的一部分，互联网广告以丰富的内容、生动的形式、巨大的浏览量以及指数级增长的市场份额成为新兴广告媒体中最重要的组成部分，其每年为网站的运营商以及参与竞拍的广告商都带来巨额的利润。在互联网广告位销售中，运营商使用拍卖的方法为广告资源制定合理的分配规则及支付规则，使得参与竞拍的广告商能灵活展示自己的偏好、高效便捷的配置广告资源、并且最优化各方利润。在该拍卖系统中，拍卖的组织者通过设计合理的拍卖机制，保证拍卖系统的激励相容性、个体理性、配置效率等有利性质;竞拍的参与者则作为理性的博弈参与者，根据不完全的信息制定出最有利的竞价策略。
　　本文从资源拥有者和竞拍者两个角度，围绕互联网广告组合拍卖机制的理论研究与实际应用，以最优化各方收益为目标展开研究。针对现有拍卖机制的非激励相容性，提出最优收益竞拍策略;对新兴的互联网媒体广告视频网站的广告分配问题进行形式化定义，设计了两种拍卖机制分别提升拍卖者的收益和全局配置效率;针对实际应用中面临最优化目标无法在多项式时间内求解到最优解问题，设计高效演化算法进行优化。本文的主要研究内容和创新点为:
　　(1)首先从资源竞争者的角度出发，提出基于精英保留优化的竞拍者策略模型:针对广义第二价格拍卖中的非激励相容性，提出一种多维多选择背包竞拍模型，并利用基于精英保留策略的协同量子粒子群算法对该问题进行了求解。该算法对粒子之间的运动趋势进行了分析，充分利用粒子的寻优趋势保持种群的多样性。将该算法应用于多维多选择背包标准数据集并与其它进化算法进行了比较，测试算法的求解能力。并将该算法应用于所提出的竞拍模型中，在仿真平台上验证所提出的竞拍模型及优化算法的收益能力。
　　(2)以最大化资源拥有者收益为目标，设计基于嵌钉拍卖的异质多物品预算约束拍卖机制:根据视频广告的特性对该问题进行形式化描述，对投标语言、拍卖机制及性质进行定义。在不限制竞拍者估值的分布条件下，针对带有预算约束的视频广告问题的特点，提出了一种符合激励相容，个体理性和无正向传播的拍卖机制，给出了相应的性质证明。对该机制下拍卖者的分配、支付和收益值的上下限进行了数学分析和证明。最后通过仿真实验对机制的收益情况和社会福利进行了比较分析。
　　(3)以最优化被拍卖标的物的分配效率为目标，改进二进制量子粒子群算法对竞胜标问题的求解:对组合拍卖机制设计的基本问题“竞胜标确定问题(Winner Determination Problem，WDP)”进行了研究。WDP是NP难的问题，且对该问题的求解精度直接影响了机制的收益及其他性质。因此文中提出了一种针对WDP问题的惩罚函数，对基本的二进制量子粒子群算法中的预初始化，局部吸引子和转移函数的选择进行了针对性的改进，根据种群的多样性变化加入位置扰动因子，最后通过一系列的实验验证了算法的有效性。
　　(4)为了实现对视频广告拍卖时长的最优化配置，设计基于VCG机制的视频广告拍卖机制及近似优化求解:放松预算约束的条件，针对视频广告市场环境设计了一种激励相容的拍卖机制，采用最优化社会资源配置为目标，对机制的激励相容性和个体理性等性质进行了证明。随后针对最优化社会福利的分配函数面临的非线性规划问题，应用量子粒子群竞胜标确定算法进行求解，最后对参与竞拍的竞拍者价值函数进行了分析，使用仿真实验对算法的有效性进行了验证。

目录

声明

摘要

第1章绪论

1．1研究的背景和意义

1．2研究现状

1．2．1组合拍卖机制设计

1．2．2关键字广告及广义第二价格拍卖

1．2．3预算约束拍卖机制

1．2．4竞胜标确定问题

1．2．5粒子群进化优化算法

1．3研究中存在的问题

1．4论文的主要研究内容和组织结构

1．4．1论文的研究内容

1．4．2论文的结构安排

第2章精英保留量子粒子群算法的GSP竞拍模型求解

2．1引言

2．2问题的描述

2．2．1关键字竞拍问题

2．2．2多维多选择背包问题

2．2．3量子粒子群算法

2．3关键字广告竞拍模型

2．4精英保留协同量子粒子群算法

2．4．1基于位置信息的粒子可用性度量

2．4．2位置扰动

2．4．3精英保留量子粒子群算法描述

2．5算法的实验与分析

2．5．1最优值比较

2．5．2收敛速度

2．5．3运行时间

2．6仿真实验

2．6．1仿真实验一

2．6．2仿真实验二

2．7小结

第3章基于预算约束的视频广告拍卖机制设计

3．1引言

3．2基于预算约束的视频广告拍卖模型

3．2．1市场定义

3．2．2重要性质

3．3机制设计

3．3．1 VCG模型

3．3．2基本的嵌钉拍卖

3．3．3同质约束嵌钉拍卖

3．3．4异质约束嵌钉拍卖

3．3．5性质

3．3．6算例

3．4收益分析

3．4．1最优收益定价拍卖机制

3．4．2同质物品拍卖机制收益

3．4．3支付和分配分析

3．4．4异质物品拍卖机制收益

3．5算例分析

3．5．1拟线性价值函数对收益影响分析

3．5．2非拟线性价值函数对收益影响

3．5．3预算约束对收益的影响

3．6小结

第4章改进的二进制量子粒子群算法及对WDP的求解

4．1引言

4．2问题的描述及基本方法

4．2．1组合拍卖的表述

4．2．1竞胜标确定问题

4．2．2二进制量子粒子群算法

4．3改进的二进制量子粒子群算法

4．3．1粒子的表示及目标函数

4．3．2罚函数的确定

4．3．3预初始化

4．3．4位置扰动

4．3．5局部吸引子的选择

4．3．6转移函数

4．3．7改进的二进制量子粒子群算法

4．4实验分析

4．4．1标准数据集测试

4．4．2参数测试

4．5小结

第5章最优配置激励相容视频广告拍卖机制设计及求解

5．1引言

5．2视频广告定义

5．2．1市场的形式化定义

5．2．2观看率的计算

5．2．3机制的定义

5．3激励相容的视频广告拍卖机制设计及性质分析

5．3．1机制的社会选择函数

5．3．2机制的支付函数

5．3．3机制的性质

5．4 VWDP的求解

5．4．1粒子的表示

5．4．2适应度函数

5．4．3平均最优位置计算

5．4．4局部吸引子和位置更新

5．4．5量子粒子群算法对VWDP问题的求解

5．5算例分析

5．6小结

结论

参考文献

攻读博士期间发表的与学位论文相关的科研成果目录

致谢