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