導 讀
本文是 WWW 2022入選論文《BONUS! Maximizing Surprise》的解讀。該論文由北京大學前沿計算研究中心孔雨晴課題組與清華大學劉潇副教授、密歇根大學 Grant Schoenebeck 副教授合作完成，論文作者中，黃緻煥、許晟偉為北京大學圖靈班21屆畢業生。文章研究了在多輪雙人對抗比賽中應該如何設定最後一輪的（額外）得分以最大化觀衆的驚喜。
圖文 | 黃緻煥、許晟偉、孔雨晴
北京大學孔雨晴課題組
根據理論計算領域慣例，作者按姓名首字母排序。
論文連結：https://arxiv.org/abs/2107.08207
1 引 言
“兇手是誰？”
“作案動機是什麼？”
“怎麼才能解除循環？”
在懸疑電視劇《開端》中，随着資訊抽絲剝繭般地向觀衆釋放，觀衆心中答案的信念也在不斷發生這改變。然而對于一個故事而言，在邏輯性的限制下，資訊的總量是有限的，“XX 竟然是兇手！”這樣資訊量巨大的意外反轉，不可能發生多次。是以，如何設計資訊釋放的政策，也就是資訊流，是一個值得研究的問題。本論文作者之一孔雨晴博士創作的科幻小說《倒數》也是以資訊流為靈感。
這是我們資訊流系列工作的第二篇論文，在我們之前 IJCAI-21的工作《SURPRISE! and How to Schedule It》中，通過實驗，研究了電子競技賽事中的資訊流對于觀衆感覺品質的影響。本文從理論層面，進一步分析了如何設計比賽規則，可以獲得期望驚喜值最高的資訊流，以提高觀衆在觀看對戰時的體驗。
一個普遍的嘗試方向是：賦予比賽後期對抗在決定勝負上更高的權重，以産生更多驚喜和意外。例如：在多人線上戰鬥競技場（multiplayer online battle arena，MOBA）的經典遊戲《DOTA2》中，玩家控制的英雄在後期陣亡後的複活時間将會更長，對局勢影響更大；遊戲《英雄聯盟》在20分鐘開始會出現“納什男爵”，成功擊殺“納什男爵”的一方将會得到顯著的加成，是以往往是雙方争奪的重點；微信小遊戲《頭腦王者》的最後一個問題會給玩家“雙倍分數”的獎勵；此外，《哈利波特》裡“魁地奇”比賽中，獲得“金色飛賊”的一方也會獲得數倍于平常的得分；甚至，一些體育賽事也嘗試過将最後一站比賽的得分提高，例如國際田聯鑽石聯賽，印地賽車，世界一級方程式等。
這些設計的目的之一是提高觀衆的驚喜和意外程度：當人們觀看比賽時，他們對誰會獲得最終勝利的信念會随着比賽的進行而改變。我們此前的工作[1]和一系列其他工作[2,3,4]顯示，人們觀看比賽的感覺品質部分源于内容令人驚訝的程度。在這種情況下，理論和實踐的工作都将面臨一個有趣的問題，即如何設計積分方案以最大程度地提高比賽過程的驚訝程度，進而提高節目的娛樂效用并增加其收益。
我們主要關注多輪對抗比賽（例如《頭腦王者》），正如我們之前描述的，一種常見的做法是将玩家最後一輪可以赢得的積分增加一倍或二倍，作為額外獎勵。但是，目前還沒有工作從理論上分析如何設計最後一輪的積分，而這是規則設計者需要考量的重要問題。為了解決這個問題，本文從理論上分析了如何選擇最後一輪的積分以最大化驚喜。
2 模 型
考慮一個持續 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趨向于無窮時，是一個特定函數的解。
3 證明概要
主要挑戰：我們面臨的主要挑戰是，計算每一輪的驚喜值是困難的。甚至，在非對稱的情況下，計算 Alice 初始的勝率都不容易。一個簡單的想法是從後向前推導出每個狀态的勝率，再以此計算出驚喜值。然而，通過這種方法計算最優的獎勵 x 需要 O(n3) 的複雜度。
為了克服這個挑戰，我們需要用到Beta分布的一些性質。首先，我們通過主引理證明隻需要分析最後兩輪的信念值，把問題簡化為最後一輪和倒數第二輪之間的權衡；第二，我們研究了一些重要的特殊情況（對稱、确定、無窮），它們可以進一步簡化最後兩輪的分析；第三，我們不實際計算實際的期望驚喜值，而隻分析其如何随最後一輪積分變化。更多的證明細節請參考論文。
4 總結與展望
我們的工作求解了如何在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.
孔雨晴課題組
孔雨晴課題組主要研究計算機和經濟、社會科學的交叉方向，包含同伴預測，機制設計，資訊設計，認知等級等等，尤其感興趣和日常生活有緊密聯系的研究課題。