Multi-objective Mechanism Design for Public Good Allocation

多目标公共物品分配的机制设计

祁琦 香港科技大学

      资源分配是一个十分重要的问题。在传统的资源分配问题中，资源的拥有者往往只有单一的最大化目标。然而效率、公平性、和满意度等都是衡量公共资源分配的重要标准，应该都被同时兼顾。祁琦教授的工作讨论了三个不同的实际应用的多目标机制设计：车辆牌照分配，公共住房分配，以及公共物品分配。这个工作考虑了参与者的策略行为，并提出了三种不同的优化和可实施的机制，在平衡这些标准的基础上解决实际问题。报告还讨论了其结果在其他设定下资源分配的可能应用。

Eliciting Information by Information Theory

基于信息论的信息诱导方法

孔雨晴 北京大学

      如今，信息成为原来越重要的资源。然而现实生活中，收集得到的信息往往面临着失真的问题：有的信息主观成分极高，有的信息无法验证真假。因此通过激励机制来获取高质量的信息以及从收集到的信息中提取出有价值的部分，是一个很重要的问题。

      一个解决此问题的方法是在信息论的基础上进行信息的评估与诱导。在无法被验证真伪的信息来源中，通过计算得到信息量最丰富的答案，同时根据信息量的大小来进行奖励信息的提供者。关于衡量信息量的大小，报告提出了数据源的数据结构概念，数据的结构越混乱，那么我们就认为信息量越小。报告最终提出了若干个在此基础上的具体解决方案。

Fair Cake Division under Monotone Likelihood Ratios

在单调似然比下的公平蛋糕分配

Nidhi Rathi，Indian Institute of Science

      “蛋糕”是一个常用的分配模型，通常是可分的、异质的分配模型。蛋糕模型的应用场景有很多，包括土地分配、频谱分配和机器的时间调度。而公平的蛋糕分配（fair cake division）是让每个人都不嫉妒别人的一种分配方案，这一经典问题早在1967年就被 Foley 引进，至今仍是活跃的主题。本次报告给出了在广泛情景下适用的公平蛋糕分配的多项式算法。

      具体来说，这一工作中的蛋糕是一个 [0,1] 闭区间，每个人将要被分配到一段连续的区间。每一个人对区间有一个价值的密度函数。所谓广泛情景是指价值密度函数是具有单调似然比性质（MLRP），也即，对个体 i+1 和 i，他们的价值密度比是 x 的单调增函数。这一概念涵盖了广泛的分布类型：高斯分布、线性分布、二项分布、指数分布等。在这一假设下，“涟漪”分配（ripple divisions）是公平分配。涟漪分配就是指将区间分为 n 段，使得第 i 个人分配第i段的价值等于给第 i 个人分配第 i+1 段的价值。利用 MLRP 可以证明它的公平性。利用连续函数的介值定理可以证明它的存在性。利用二分搜索可以在多项式时间内找到涟漪分配。

Gift Contagion in Online Groups: Evidence from WeChat Red Packets

线上群组中的礼物传播研究：使用微信红包的数据

刘潇 清华大学

      礼物是现代人建立人际关系的重要方式，而新年时送红包作为礼物，不仅是中国的传统文化，在日本、韩国也有类似的传统。如今随着电子支付的发展，微信红包作为一种新的礼物方式，已经成为了我们生活中最普遍的一种赠礼手段。本篇论文中，作者采用微信上3600万个在线红包数据来分析礼物赠与的群体传播效应。作者使用自然实验方法来分析这一效应，并得到了一系列有趣的结论。

      首先作者发现，平均意义上组内红包的接收者会将接受到红包钱数的18%在24小时之内发还给小组。其次，通过对比可以发现，对于那些随机红包获得最佳手气的人，其返还红包的比例会更高。此外，作者还发现发送红包这一行为很大程度上受到群组类别和朋友关系等某些属性的影响，例如在亲戚朋友群中返还红包的比例更高。同时针对个人的社交网络，作者还发现那些参与群组少的人有更多的发红包的倾向。

Incentive Study on Strategic Behaviors to BitTorrent Resource Sharing System

p2p资源共享网络中激励率研究的最新进展

程郁坤 苏州科技大学

      p2p 网络为一个用户相互平等的、可以直接交流的网络。在 p2p 网络中，资源在不同的互相连接的用户之间分享。每个用户既是消费者（consumer），也是提供者（supplier）。以协议 BitTorrent 为例，资源就是带宽，存储容量等，节点效用就是其接收到的总资源数，p2p 网络的思想是效用最大化。带宽资源的模型可以被看成一个典型的纯交换经济模型。资源分享最重要的问题是如何公平且有效的分配资源。为了保证公平，节点更倾向于将资源按比例送给那些给自己传输资源的邻居节点，这样的交换是比较公平的，并且可以达到市场均衡。

      当然，在网络中也有欺骗（cheating）的行为与方法。程教授的报告主要围绕女巫攻击（Sybil attack）这一欺骗手段。在资源分发过程中，一个发动女巫攻击的恶意节点会创造多个节点，成为某个节点的邻居们。而原来传送到多个邻居节点的资源，被传送到了同一个恶意节点。程教授及其合作者在一个资源共享博弈中，通过令虚拟节点分解为多个虚拟节点，来研究发动女巫攻击的激励率（incentive ratio）。这里限制虚拟节点的每个邻居都只连接到一个节点上以简化讨论，使策略只关注节点之间的权重分配，以获得最优值。接下来，讲者通过实例以及数学方法，证明了在 bottleneck decomposition 机制下，对女巫攻击的激励率不大于3，以及在环的条件下，针对女巫攻击的激励率恰好为2。