導(dǎo) 讀

本文是 AAMAS 2023入選論文 Sybil-Proof Diffusion Auction in Social Networks 的解讀。該工作由北京大學(xué)前沿計(jì)算研究中心鄧小鐵課題組和上?？萍即髮W(xué)趙登吉課題組共同完成。

文章聚焦于擴(kuò)散拍賣中的女巫攻擊行為，給出了兩個(gè)抗女巫攻擊的擴(kuò)散拍賣機(jī)制并進(jìn)行性能分析。

論文鏈接：https://arxiv.org/abs/2211.01984

01

引 言

在傳統(tǒng)拍賣中，賣家只考慮將物品販賣給一個(gè)確定的買家群體；當(dāng)拍賣發(fā)生在社交網(wǎng)絡(luò)上時(shí)，這個(gè)買家群體就是賣家在社交網(wǎng)絡(luò)上的鄰居集。為了提高拍賣的賣家收益和社會福利，擴(kuò)散拍賣（diffusion auction）允許買家邀請鄰居進(jìn)入拍賣。通過賦予中間買家一定的邀請報(bào)酬，一些擴(kuò)散拍賣機(jī)制（如，Information Diffusion Mechanism [1]）保證了誠實(shí)報(bào)價(jià)并邀請其所有鄰居是所有買家的最優(yōu)策略。然而，這種獎勵(lì)買家邀請鄰居的設(shè)計(jì)讓攻擊者可以通過社交網(wǎng)絡(luò)上低成本的女巫攻擊獲取不正當(dāng)收益——即攻擊者可以通過創(chuàng)造并邀請若干個(gè)虛假身份騙取邀請報(bào)酬?，F(xiàn)有的所有非平凡的擴(kuò)散拍賣機(jī)制均無法解決這一問題。

本文對有向社交網(wǎng)絡(luò)中無共謀的女巫攻擊行為進(jìn)行建模，并提出兩個(gè)抗女巫攻擊的擴(kuò)散拍賣機(jī)制：STM（Sybil Tax Mechanis）和 SCM（Sybil Cluster Mechanism）。進(jìn)一步地，本文比較了兩個(gè)提出的機(jī)制與經(jīng)典擴(kuò)散拍賣機(jī)制、傳統(tǒng)拍賣機(jī)制的性能，發(fā)現(xiàn) STM 和 SCM 在防止女巫攻擊的同時(shí)保持了較高的社會福利和賣家收益；此外，我們還分析了抗女巫攻擊的擴(kuò)散拍賣機(jī)制的效率比，發(fā)現(xiàn)所有抗女巫攻擊的擴(kuò)散拍賣機(jī)制在最壞情況下都有非常低的社會福利和賣家收益。

02

女巫攻擊建模

在有向社交網(wǎng)絡(luò)中，點(diǎn) x 有鄰居 y（點(diǎn) x 有指向點(diǎn) y 的有向邊）表示 x 知道 y 的存在。擴(kuò)散拍賣機(jī)制要求買家匯報(bào)它的報(bào)價(jià)（如圖 (a) 中 x 報(bào)價(jià)8）和他的鄰居集（圖 (a) 中 x 的鄰居集為 {y, z, w} ），買家不必要誠實(shí)匯報(bào)他對物品的私人價(jià)格，也可以選擇瞞報(bào)他的鄰居。在女巫攻擊的情況下，一個(gè)買家 x 可以創(chuàng)造任意多個(gè)假身份?x_{1},?x_{2},... 。一個(gè)假身份 x_{i} 的鄰居集可以包含 x 的鄰居，x 本身以及 x 的其他假身份；在無共謀的情況下，x_{i} 不可以在除 x 和 x 的假身份外其他人的鄰居集中。模型允許社交網(wǎng)絡(luò)中的任何買家發(fā)起女巫攻擊。

因?yàn)榧偕矸葜槐凰膭?chuàng)造者和這一創(chuàng)造者的其他假身份知道，所有從賣家出發(fā)的沿買家匯報(bào)的社交網(wǎng)絡(luò)單向邊的經(jīng)過該假身份的路徑都會經(jīng)過該假身份的創(chuàng)造者。基于以上性質(zhì)，擴(kuò)散拍賣機(jī)制可以根據(jù)買家匯報(bào)的鄰居關(guān)系從圖論角度找出部分“一定不是假身份”的買家，文中稱為圖論非女巫節(jié)點(diǎn)（Graphical non-Sybil agents）。一個(gè)自然的想法是在由圖論非女巫節(jié)點(diǎn)構(gòu)成的社交網(wǎng)絡(luò)中實(shí)行已有的擴(kuò)散拍賣機(jī)制，但這個(gè)想法是不可行的：通過瞞報(bào)鄰居集，買家可以改變圖論非女巫節(jié)點(diǎn)的構(gòu)成，誘導(dǎo)對自己更有利的社交網(wǎng)絡(luò)結(jié)構(gòu)（如下圖，通過瞞報(bào)鄰居 c，買家 a 可以將 c 排除在圖論非女巫節(jié)點(diǎn)的社交網(wǎng)絡(luò)結(jié)構(gòu)之外，從而降低自己買入物品的費(fèi)用）。

03

主要貢獻(xiàn)1 抗女巫攻擊機(jī)制

上一節(jié)說明簡單使用圖論方法來抵抗女巫攻擊是不可行的。本節(jié)介紹本文的主要貢獻(xiàn)：兩個(gè)抗女巫攻擊機(jī)制 STM 和 SCM。機(jī)制設(shè)計(jì)上借鑒了經(jīng)典的擴(kuò)散拍賣機(jī)制 IDM，綜合利用圖論信息和買家報(bào)價(jià)來排除惡意競價(jià)的假身份。

類似 IDM，STM 首先找到匯報(bào)社交網(wǎng)絡(luò)中報(bào)價(jià)最高的買家 x^{*}，再確認(rèn)賣家到 x^{*} 擴(kuò)散拍賣的必經(jīng)節(jié)點(diǎn)；必經(jīng)節(jié)點(diǎn)中任意一個(gè)瞞報(bào)鄰居都可以導(dǎo)致 x^{*}改變，因此稱這些必經(jīng)節(jié)點(diǎn)構(gòu)成的路徑為“支配路徑”。STM 可以看成一個(gè)多次轉(zhuǎn)賣過程：物品將在支配路徑上傳遞，直到下傳物品不能給買家?guī)砀呤找妗Ｖ渎窂缴系馁I家收到物品時(shí)需要支付買入價(jià)格，這一價(jià)格由所有不被它支配的節(jié)點(diǎn)報(bào)價(jià)共同決定。下傳物品時(shí)，買家會收入賣出價(jià)格，這一價(jià)格由買入價(jià)格和由它引入的“圖論非女巫節(jié)點(diǎn)”及后繼共同決定。這一過程中，上家的賣出價(jià)可能小于下家的買入價(jià)，差價(jià)可以看作轉(zhuǎn)賣的稅收成為賣家收入的一部分。（機(jī)制的嚴(yán)格定義請參考原文）

文章證明了 STM 滿足獨(dú)立理性（IR）、賣家收益非負(fù)（non-deficit）以及抗女巫攻擊（Sybil-proof）。在沒有其他“non-Sybil agents”確認(rèn)途徑的情況下，STM 的中間買家收益都是 0；雖然攻擊行為不能為中間買家?guī)硎找妫?STM 中的買家也沒有足夠的激勵(lì)匯報(bào)自己的鄰居。

為了進(jìn)一步驅(qū)動買家誠實(shí)匯報(bào)鄰居集，文章節(jié)提出了第二個(gè)抗女巫攻擊的機(jī)制 ACM；SCM 通過隨機(jī)刪邊將圖論非女巫節(jié)點(diǎn)的出現(xiàn)歸功于部分幸運(yùn)的中間買家，從而提高買家誠實(shí)匯報(bào)鄰居集的意愿（機(jī)制的具體描述請參考原文）。SCM 也滿足獨(dú)立理性、賣家收益非負(fù)以及抗女巫攻擊，同時(shí)，它給中間買家更強(qiáng)激勵(lì)來邀請鄰居。

04

主要貢獻(xiàn)2 性能分析

在提出兩個(gè)抗女巫攻擊的擴(kuò)散拍賣機(jī)制后，文章討論了以下三個(gè)問題：

（1）只在賣家鄰居集中進(jìn)行的傳統(tǒng)拍賣機(jī)制天然是抗女巫攻擊的，相比于傳統(tǒng)拍賣機(jī)制，STM 和 SCM 在賣家收益和社會福利上是否有更好表現(xiàn)？

（2）在所有抗女巫攻擊的擴(kuò)散拍賣機(jī)制中，STM 或 SCM 是否能達(dá)到最優(yōu)的社會福利或賣家收益？

（3）相比于已有的擴(kuò)散拍賣機(jī)制，STM 和 SCM 為了達(dá)到抗女巫攻擊，在社會福利和賣家收益上有多大犧牲？

針對問題（1）和問題（3），文章理論分析了 STM、SCM 和傳統(tǒng)二價(jià)拍賣機(jī)制 NSP，和經(jīng)典擴(kuò)散拍賣機(jī)制 IDM、VCG 在社會福利與賣家收益方面的表現(xiàn)（詳見原文 Theorem 6.1，6.2，6.3）同時(shí)采用模擬實(shí)驗(yàn)定量比較平均情況下，在不同密度的社交網(wǎng)絡(luò)中，以上五個(gè)機(jī)制在社會福利和賣家收益上的表現(xiàn)。

針對問題（2），文章給出了負(fù)面結(jié)論：在最壞的情況下，任何保證賣家收益非負(fù)、抗女巫攻擊、滿足獨(dú)立理性的擴(kuò)散拍賣機(jī)制的社會福利相比于最優(yōu)社會福利都無限趨近于零。在賣家收益上有類似結(jié)論。

參考文獻(xiàn)

[1] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. 2017. Mechanism Design in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence 31, 1 (Feb.
2017). https://ojs.aaai.org/index.php/AAAI/article/vie