本文是 AAMAS 2023入選論文 Altruism, Collectivism and Egalitarianism: On a Variety of Prosocial Behaviors in Binary Networked Public Goods Games 的解讀。該工作由北京大學(xué)前沿計(jì)算研究中心鄧小鐵教授課題組與蘇州科技大學(xué)程郁琨教授、杭州秘猿科技有限公司 Xie Jan 合作完成。

文章聚焦于網(wǎng)絡(luò)公共品博弈當(dāng)中參與者的三種“親社會(huì)性”：利他主義、集體主義以及平等主義；對(duì)三種類型的親社會(huì)性分別進(jìn)行數(shù)學(xué)建模，并理論分析在不同類型“親社會(huì)性”環(huán)境下尋找純策略納什均衡的計(jì)算復(fù)雜度。更進(jìn)一步，文章還研究了“親社會(huì)性網(wǎng)絡(luò)調(diào)整”問題。

01

引 言

在我們現(xiàn)今的生活中，人們面臨著諸如是否佩戴口罩，是否接種疫苗等選擇問題。這些行為不僅能起到保護(hù)自己的作用，同時(shí)還可以防止他人被傳染疾病。為了分析人群在該類問題上的行為決策，研究者們通常將這類問題建模成一個(gè)網(wǎng)絡(luò)二元公共品博弈問題（Binary Networked Public Good，BNPG）。同時(shí)，因?yàn)樵诂F(xiàn)實(shí)生活中，每位參與者的決策行為只會(huì)對(duì)他自己以及社會(huì)關(guān)系較為親近的人有直接影響，因此本文主要關(guān)注的是網(wǎng)絡(luò)上的二元公共品投資問題。這里所提及的網(wǎng)絡(luò)可以很好地刻畫參與者之間的社會(huì)關(guān)系，其中網(wǎng)絡(luò)頂點(diǎn)代表參與者，邊代表參與者之間對(duì)彼此產(chǎn)生的影響。由于公共品的投資需要付出成本，而參與者可以從自身和周圍鄰居處獲得效用，因此參與者的“自私性”會(huì)促使“搭便車”等策略行為的出現(xiàn)。如何解決這一問題從而使得社會(huì)總福利得到提升，是學(xué)術(shù)界和業(yè)界在網(wǎng)絡(luò)上的二元公共品博弈中主要關(guān)注的問題。

02

問題建模

[Yu, et al, 2020] 首次對(duì)網(wǎng)絡(luò)二元公共品投資博弈進(jìn)行建模。假設(shè)網(wǎng)絡(luò)公共品博弈中有 n 個(gè)參與者，其網(wǎng)絡(luò)關(guān)系可以由無向圖 G=(V, E) 表示，其中 V=1, 2, ..., n 中的每個(gè)頂點(diǎn)代表一位參與者，邊代表參與者在社會(huì)中的相互關(guān)系。在單輪博弈中，每位參與者只需要做出投資或不投資公共品的二元決策。如果我們記參與者們的決策組合為 x= , 用? 表示此時(shí)參與者 i 的鄰居中投資了公共品的人數(shù)，則參與者的效用為：

其中? 為參與者 i 的收益函數(shù)，該函數(shù)關(guān)于投資數(shù)量單調(diào)增加； 是該參與者的投資成本。

在本篇論文中，我們重點(diǎn)關(guān)注二元網(wǎng)絡(luò)公共品博弈問題的純策略納什均衡；同時(shí)為了衡量社會(huì)中公共品投資對(duì)整個(gè)社會(huì)的貢獻(xiàn)，我們還關(guān)注公共品投資策略帶來的的社會(huì)總福利，即所有參與者的效用之和：

03

親社會(huì)性建模

在現(xiàn)實(shí)中，人們對(duì)公共品的投資決策不僅受到個(gè)人利益的影響，同時(shí)還會(huì)去考慮自己的投資行為對(duì)身邊他人利益的影響，即受到人的“社會(huì)屬性”的影響。論文 [Yu, et al, 2021] 曾將“利他性”（Altruism）概念引入網(wǎng)絡(luò)二元公共品博弈問題中，而我們?cè)诒酒撐闹懈娴乜紤]了參與者的親社會(huì)屬性，分別對(duì)參與者的利他主義，集體主義和平等主義進(jìn)行建模，并分別定義收益函數(shù)：

利他主義：

集體主義：

平等主義：

在上述三類效用中，利他主義是將鄰居的部分收益加到自己的效用函數(shù)中，而自己的收益仍然占比較高。相比于利他主義，在集體主義的建模中，個(gè)人將自己的利益和他人的利益同等對(duì)待，利用相同的權(quán)重來代表著參與者的集體傾向。而在平等主義建模中，我們參考了經(jīng)典的最大最小平等概念，讓每個(gè)人關(guān)注弱勢(shì)鄰居，即其鄰居中效用最少的人。

04

主要貢獻(xiàn)1

純策略均衡的計(jì)算復(fù)雜度

我們首先討論了在樹、團(tuán)以及一般網(wǎng)絡(luò)圖上的網(wǎng)絡(luò)二元公共品博弈中純策略納什均衡的存在性問題，給出了在不同網(wǎng)絡(luò)結(jié)構(gòu)下判斷純策略納什均衡存在性的計(jì)算復(fù)雜性。詳細(xì)結(jié)果如下圖所示：

05

主要貢獻(xiàn)2

親社會(huì)性網(wǎng)絡(luò)調(diào)整方案及計(jì)算復(fù)雜度

更進(jìn)一步的，本文還討論了公共品投資的治理問題，即政策制定者如何通過鼓勵(lì)、宣傳、培養(yǎng)親社會(huì)性等措施，來引導(dǎo)人們投資公共品，獲得可使社會(huì)福利最大化等既定目標(biāo)的納什均衡。為此，本文第二部分研究了“親社會(huì)性網(wǎng)絡(luò)調(diào)整”（Prosociality Network Modification，PNM）問題，即設(shè)計(jì)出一種網(wǎng)絡(luò)調(diào)整方案，在有計(jì)劃地改變一些個(gè)體的親社會(huì)性強(qiáng)弱后，使得整個(gè)網(wǎng)絡(luò)中的個(gè)體自發(fā)地趨向更好的納什均衡。本工作在利他主義、集體主義、平等主義三種親社會(huì)性下分別證明了 PNM 問題的計(jì)算復(fù)雜性結(jié)果（Table 2）。

參考文獻(xiàn)

[Yu, et al, 2020] Sixie Yu, Kai Zhou, P. Jeffrey Brantingham, and Yevgeniy Vorobeychik. 2020.

Computing Equilibria in Binary Networked Public Goods Games. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020. AAAI Press, 2310–2317. https://ojs.aaai.org/index.php/AAAI/article/view/5609

[Yu, et al, 2021] Sixie Yu, David Kempe, and Yevgeniy Vorobeychik. 2021. Altruism Design in Networked Public Goods Games. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, Zhi-Hua Zhou (Ed.). ijcai.org, 493–499. https://doi.org/10.24963/ijcai.2021/6