机制设计论文提纲

关键词： 乘车 单车 共享 充电

论文题目：共享经济中的博弈模型与机制设计研究

摘要：随着各类移动设备的完善和发展,共享经济在实际中取得了很大的成功。共享乘车,共享单车,共享充电宝等应用节约了资源,给社会和个人都带来了很大的便利。与此同时,作为新的共享经济模式,目前还有很多的问题亟需研究。共享经济不同于传统的市场,不论是滴滴、优步等共享乘车平台还是其它各类共享经济平台,都往往不直接管理或者拥有资源提供方或者资源使用方,而作为一个资源调度中介的角色存在,平台需要综合考虑供求两方的协调和均衡,实现整体效益的最大化。这也衍生出了双边市场经济模型,在这样的模型下,涌现了很多需要研究的问题。以商业模式上最为成熟、时间最久的共享乘车为例,司机和乘客参与共享乘车完全是自愿的,平台不对他们具有强制约束力。双边市场中双边的参与度对整个市场的良好运转和平台的整体收益有很大影响。因此,如何设计有效的激励机制吸引乘客/司机的参与,是非常重要且核心的问题。在复杂的共乘系统中,由于成本函数的复杂性,传统的博弈论和机制设计的经典的模型和策略往往不能适用,需要针对具体场景进行新的问题建模和算法设计。本文主要针对共享经济中的典型应用:共享乘车系统、共享单车等进行激励机制的设计和分析,提高资源的利用效率,实现系统整体的收益最大化,供需双方的互利共赢,并且从理论分析和实验验证两个方面对机制的性能进行了验证。具体来说,这篇论文主要包括以下四个方面的研究内容和研究成果:首先,针对共享乘车中成本的复杂性问题,结合在资源配置方面有独特优势的博弈论理论,进行了动态成本下的博弈问题的建模,这是不同于经典模型中成本相同或者被忽略的一种全新的场景,我们想要设计在满足收支平衡的约束下的高效的、防策略的博弈机制。对该模型进行进一步研究后,我们提出了可变保留价格的博弈问题,我们发现在这样的约束下,没有任何机制能够在满足收支均衡、个人理性和防策略性的同时,实现最大的社会福利。在这一否定性结论的限制下,我们探索设计出了一个满足2近似比的机制,并且可以证明这是理论上最好的近似比保证。我们将该近似机制在实际出租车数据集上进行了验证,实验结果表明虽然理论上只能达到2近似比,但由于实际数据集中数据的特性,实验结果好于理论结果,并且虽然我们在设计时没有将收入的优化考虑在内,机制仍然在这一维度表现出了很好的实际效果。我们的机制是针对这类普遍的可变保留价格场景而设计的,具有一定的通用性,我们尝试将该模型扩展到共享单车系统中,解决共享单车的定点停放激励问题,我们将机制进行了适当的改进和变形以适用共享单车场景,结果表明理论和实验效果良好,进一步证明了这种建模方式和机制设计的有效性和普适性。其次,实际中的共享经济场景往往是实时的、在线的,需要对随时到来的顾客的请求即时做出反应和决策,这就表明了平台在进行决策时往往是不能够拥有全局信息的,传统的线下分配模式不能够适应这种需求,同时这种未来信息的缺乏也使得在线场景的算法设计面临很大的挑战,尤其是在以全局指标作为优化目标时。针对在线共享乘车的场景,由于不同的指标会给设计带来不同的困难,我们重点考虑了几个常见的指标,包括:度量系统整体效益的社会福利指标、关注乘客体验的服务乘客数量指标和度量平台整体收益的平台效用指标,不同的指标在优化方面的困难是不相同的,我们证明了在防乘客策略行为、收支均衡、个人理性和计算高效性等的约束下,社会福利指标没办法得到有限的近似比,而另外两种指标均可以在一定程度上得到良好的近似比保证。我们分别对针对这几种优化目标作出了努力,设计出了合适的机制和算法,给出了理论分析和实验验证。再次,现实中的共享乘车应用中,往往存在多人共乘一辆车的场景,线路规划的复杂性,使得成本的分配、价格的分摊、整体效益的优化变得复杂,并且还要考虑乘客的公平性体验,这并不是一个容易的问题,我们针对这一场景,对经典算法机制的不适用性进行了讨论,并且提出了我们自己的有全局表现近似比保证的机制。最后,共享经济由于涉及到多参与者共享资源,参与者之间的互相影响往往是不能够避免的,这属于一种博弈中的外部性,也就是参与者获得分配的价值也受到其他参与者分配结果的影响。外部性博弈的研究相对比较缺少,我们从一种简化的负外部性场景出发,对具有良好性质的机制设计进行了探索,针对单竞争图、平面图、一般图等不同的影响图模型,设计了高效的、防策略的、多项式时间的近似机制。在这一成果的激励下,我们探索了复杂的共享乘车系统中,共乘一辆车、有座位偏好性的乘客座位分配和定价问题。由于共享乘车路径规划、成本函数等的复杂性,我们很难对原始的模型进行求解,于是考虑了一种简化的、固定经停点、暂不考虑绕路的场景,并且针对此场景设计了可以应用于在线和离线模型的无嫉妒座位分配机制。

关键词：共享经济;博弈论;机制设计;算法博弈论;近似算法设计;成本分配

学科专业：计算机科学与技术

摘要

abstract

第一章 绪论

1.1 研究背景与意义

1.2 研究问题与研究现状

1.2.1 共享经济中的动态成本博弈

1.2.2 共享乘车在线分配与定价

1.2.3 共享乘车成本分摊机制设计

1.2.4 考虑外部性的博弈模型及机制设计

1.3 研究内容与研究贡献

1.4 论文结构

第二章 相关研究工作

2.1 博弈论简介

2.2 双边市场简介

2.3 基础定价理论与实践

2.4 动态成本机制设计

2.5 在线博弈机制设计

2.6 成本分配算法理论

2.7 博弈外部性理论及应用

2.8 本章小结

第三章 动态成本博弈模型与机制设计

3.1 概述

3.2 共乘问题定义与模型介绍

3.3 经典VCG机制的不适用性

3.4 动态保留价格机制设计

3.4.1 资源分配和定价

3.4.2 理论分析

3.4.3 实验验证与性能评估

3.5 共享单车定点停放激励中的应用

3.5.1 背景与动机

3.5.2 问题建模

3.5.3 设计核心思想

3.6 本章小结

第四章 共享乘车在线场景下分配定价

4.1 概述

4.2 社会福利优化系统设计

4.2.1 问题定义

4.2.2 抢占禁止策略

4.2.3 允许抢占策略

4.3 系统吞吐量最大化

4.3.1 问题定义

4.3.2 定价策略

4.3.3 调度策略

4.3.4 分配算法与竞争比分析

4.4 平台整体效用最大化

4.5 本章小结

第五章 共享乘车中的成本分配机制设计

5.1 概述

5.2 符号定义与模型介绍

5.3 现有机制分析

5.3.1 简化实例

5.3.2 广义的第二价格机制

5.3.3 关键价格技术

5.3.4 VCG机制

5.4 成本分配机制设计与理论分析

5.4.1 关于收支均衡实现的有益尝试

5.4.2 关于社会福利最大化的否定性结论

5.4.3 社会成本最小化目标下的近似算法

5.4.4 简化实例下的机制设计

5.4.5 一般情形下的机制设计

5.5 仿真实验结果

5.5.1 实验设定

5.5.2 实验结果

5.5.3 应用讨论

5.6 本章小结

第六章 考虑外部性的博弈模型及机制设计

6.1 概述

6.2 基于身份的外部性博弈机制设计

6.2.1 模型介绍与问题定义

6.2.2 单竞争者图机制设计

6.2.3 平面竞争图机制设计

6.2.4 一般竞争图机制设计

6.2.5 实验验证

6.2.6 总结与未来方向

6.3 考虑座位偏好的共享乘车分配机制

6.3.1 符号定义

6.3.2 系统模型

6.3.3 无嫉妒分配机制设计

6.4 本章小结

第七章 总结与展望

7.1 工作总结

7.2 研究展望

参考文献

致谢