WWW 2022 | 超级加倍！让比赛惊喜最大化
关键词：惊喜，规则设计
导 读
本文是 WWW 2022入选论文《BONUS! Maximizing Surprise》的解读。该论文由北京大学前沿计算研究中心孔雨晴课题组与清华大学刘潇副教授、密歇根大学 Grant Schoenebeck 副教授合作完成，论文作者中，黄致焕、许晟伟为北京大学图灵班21届毕业生。文章研究了在多轮双人对抗比赛中应该如何设置最后一轮的（额外）得分以最大化观众的惊喜。
*根据理论计算领域惯例，作者按姓名首字母排序。
论文链接：https://arxiv.org/abs/2107.08207
01
引 言
“凶手是谁？”
“作案动机是什么？”
“怎么才能解除循环？”
在悬疑电视剧《开端》中，随着信息抽丝剥茧般地向观众释放，观众心中答案的信念也在不断发生这改变。然而对于一个故事而言，在逻辑性的约束下，信息的总量是有限的，“XX 竟然是凶手！”这样信息量巨大的意外反转，不可能发生多次。因此，如何设计信息释放的策略，也就是信息流，是一个值得研究的问题。本论文作者之一孔雨晴博士创作的科幻小说《倒数》也是以信息流为灵感。
这是我们信息流系列工作的第二篇论文，在我们之前 IJCAI-21的工作《SURPRISE! and How to Schedule It》中，通过实验，研究了电子竞技赛事中的信息流对于观众感知质量的影响。本文从理论层面，进一步分析了如何设计比赛规则，可以获得期望惊喜值最高的信息流，以提高观众在观看对战时的体验。
一个普遍的尝试方向是：赋予比赛后期对抗在决定胜负上更高的权重，以产生更多惊喜和意外。例如：在多人在线战斗竞技场（multiplayer online battle arena，MOBA）的经典游戏《DOTA2》中，玩家控制的英雄在后期阵亡后的复活时间将会更长，对局势影响更大；游戏《英雄联盟》在20分钟开始会出现“纳什男爵”，成功击杀“纳什男爵”的一方将会得到显著的加成，因此往往是双方争夺的重点；微信小游戏《头脑王者》的最后一个问题会给玩家“双倍分数”的奖励；此外，《哈利波特》里“魁地奇”比赛中，获得“金色飞贼”的一方也会获得数倍于平常的得分；甚至，一些体育赛事也尝试过将最后一站比赛的得分提高，例如国际田联钻石联赛，印地赛车，世界一级方程式等。
这些设计的目的之一是提高观众的惊喜和意外程度：当人们观看比赛时，他们对谁会获得最终胜利的信念会随着比赛的进行而改变。我们此前的工作[1] 和一系列其他工作[2,3,4] 显示，人们观看比赛的感知质量部分源于内容令人惊讶的程度。在这种情况下，理论和实践的工作都将面临一个有趣的问题，即如何设计积分方案以最大程度地提高比赛过程的惊讶程度，从而提高节目的娱乐效用并增加其收益。
我们主要关注多轮对抗比赛（例如《头脑王者》），正如我们之前描述的，一种常见的做法是将玩家最后一轮可以赢得的积分增加一倍或二倍，作为额外奖励。但是，目前还没有工作从理论上分析如何设计最后一轮的积分，而这是规则设计者需要考量的重要问题。为了解决这个问题，本文从理论上分析了如何选择最后一轮的积分以最大化惊喜。
02
模 型
考虑一个持续 n 轮的比赛，两个参与者分别为 Alice 和 Bob；每一轮中，胜者能获得分数，在 n 轮结束后，分数高的一方获得胜利。在我们的设定中，前 n-1 轮的分数都为1，最后一轮的分数则是 x。不失一般性地，我们只要考虑最后一轮的积分不超过总轮数 n 的情况。并且，为了避免平局，我们规定 x 为和 n 奇偶相同的整数。
惊喜是什么？
简单来说，我们定义惊喜为期望上观众观看比赛时对其中一方队伍，例如 Alice，获胜的信念的变化的绝对值之和[2]。如下图中，红色曲线具有的惊喜值比紫色曲线的更高。
观众的信念取决于他的先验，我们介绍一下我们先验的模型。
先验是什么？
在现实中，很多时候观众在事前对于比赛双方的实力并不确定，而是在观看比赛的同时更新他们对于两个选手实力的估计。观众对于 Alice 获胜的概率判断并不是 Alice 真正获胜的概率，而是基于他们对于 Alice 实力的认识。
因此，我们需要将观众对于选手实力的先验信念进行建模。首先考虑两种特殊情况：
第一种特殊情况是观众对参赛双方实力的信念不会随着比赛的过程改变（确定情况），例如，诸葛亮第七次擒孟获，或已经交手过多次的夏洛克福尔摩斯和詹姆斯莫里亚蒂。
第二种特殊情况是观众对参赛双方的实力没有先验知识（均匀情况）。例如，关公战秦琼，或夏洛克福尔摩斯和赫尔克里波洛。
Beta 分布可以在包含这两种情况的基础上，推广到更一般的情况。因此我们使用 Beta 分布作为先验的模型。
如何选择最后一轮的积分？
我们先给出根据我们的理论结果推导出来的三个洞见。
洞见1：双方实力差距越大，需要越多的奖励积分。有趣的是，我们发现最优奖励积分约为 (2p-1)n，这是较弱的玩家翻盘需要的分数，我们称其为“翻盘系数”。因此在观众认为两个玩家的能力相差巨大的比赛中，我们应该设置较高的奖励积分。否则，这场比赛能带来的惊讶会迅速减少，从而导致大量的“垃圾时间”。相反，如果两个玩家实力相当，则不应该设置额外的奖励积分。
洞见2：在观众的先验并不偏向某一方时，更多的不确定性使得最优奖励积分更高。我们发现，在对称的情况下，当先验更不确定时，最优奖励积分越大。值得注意的是，这与第一种情况中两个玩家实力相当的情况不同。原因是在前一种情况中不会更新对双方实力的信念，而在后一种情况中会更新对双方实力的信念。在这种情况下，随着比赛的进行，观众不止会更新对于最后获胜者的信念，还会更新对参赛双方实力的信念。从信息流的角度来看，更多的信息会在比赛前期释放，因此我们需要给最后一轮设置一些奖励积分来平衡整个信息释放过程。
洞见3：更多的回合会需要更高的最优奖励积分。我们发现，随着回合数的增加，最优奖励积分会变大。直觉上，“翻盘系数”与回合数成正相关，因此当回合数变大时，我们需要增加奖励积分以扩大落后者的获胜率，否则比赛可能很快就没有任何悬念。
更详细的理论结果：
上表中给出了在有限轮（Finite）和无穷多轮（Asymptotic）情况下，分别在对称情况（Symmetric），确定情况（Certain）以及一般情况下的最后一轮最优积分。其中 alpha，beta 为先验的参数。
对称情况：当观众的先验信念不偏向任何玩家时，是清晰的封闭式公式；
确定情况：当观众在赛前对参赛双方实力完全确定时，是一个特定函数的解，约等于“翻盘系数”，即弱者想要翻盘需要的期望分数;
一般情况：可以通过线性算法获得，当 n 趋向于无穷时，是一个特定函数的解。
03
证明概要
主要挑战：我们面临的主要挑战是，计算每一轮的惊喜值是困难的。甚至，在非对称的情况下，计算 Alice 初始的胜率都不容易。一个简单的想法是从后向前推导出每个状态的胜率，再以此计算出惊喜值。然而，通过这种方法计算最优的奖励 x 需要 O(n3) 的复杂度。
为了克服这个挑战，我们需要用到 Beta 分布的一些性质。首先，我们通过主引理证明只需要分析最后两轮的信念值，把问题简化为最后一轮和倒数第二轮之间的权衡；第二，我们研究了一些重要的特殊情况（对称、确定、无穷），它们可以进一步简化最后两轮的分析；第三，我们不实际计算实际的期望惊喜值，而只分析其如何随最后一轮积分变化。更多的证明细节请参考论文。
04
总结与展望
我们的工作求解了如何在 n 回合的两人对抗比赛中设计最优的末轮积分，从而来最大程度地提高观众的整体期望惊喜。我们将观众对两个玩家能力水平的先验信念建模为 Beta 分布，并发现最优奖励积分很大程度上取决于先验信念。我们观察到，具有较高偏度的先验会导致最优奖励积分较大，并且对称情况下不确定性较高的先验也会导致较高的最优奖励积分。这符合我们的直觉，因为高度不对称的先验需要很高的“翻盘系数”，而高度不确定的先验在比赛前几轮会释放很多的信息，因此需要在最后增加分数来进行补偿。
在未来的工作中，一个可行的方向是用我们现有的理论针对传统体育赛事的规则进行分析，并寻找可以改进的方向。此外，针对非完全信息游戏的规则，我们可以引入强化学习算法，从玩家视角、观众视角分别计算游戏能带来的期望惊喜，并基于此改良规则。最后，由于之前的工作证明，释放惊喜的时间也会影响观众的体验[1]，因此我们可以在模型中引入时间因素。
参考文献
[1] Zhihuan Huang, Shengwei Xu, You Shan, Yuxuan Lu, Yuqing Kong, Tracy Liu, and Grant Schoenebeck. 2021. SURPRISE! and When to Schedule It. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 252-260.
[2] Jeffrey Ely, Alexander Frankel, and Emir Kamenica. 2015. Suspense and surprise.Journal of Political Economy123, 1 (2015), 215–260.
[3] Paolo Bizzozero, Raphael Flepp, and Egon Franck. 2016. The importance of suspense and surprise in entertainment demand: Evidence from Wimbledon.Journal of Economic Behavior & Organization130 (2016), 47–63.
[4] Babatunde Buraimo, David Forrest, Ian G McHale, and JD Tena. 2020. Unscripteddrama: soccer audience response to suspense, surprise, and shock.EconomicInquiry58, 2 (2020), 881–896.
图文 | 黄致焕、许晟伟、孔雨晴
北京大学孔雨晴课题组
孔雨晴课题组
孔雨晴课题组主要研究计算机和经济、社会科学的交叉方向，包含同伴预测，机制设计，信息设计，认知等级等等，尤其感兴趣和日常生活有紧密联系的研究课题。
CFCS近期科研动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”转论文链接