近期幾篇有關All-Pay論文總結

• • • • 1.Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions
      • 2.Designing an optimal contest
      • 3.Optimal rewards in contests
      • 4.Asymmetric All-Pay Auctions with Incomplete Information:The Two-Player Case
      • 5.Asymmetric All-Pay Auctions with Two Types
      • 6.All-pay auctions—an experimental study
      • 7.后續

1.Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions

• 目前在線廣告競拍中大多采用重復一價拍賣代替過去的二價拍賣。一價拍賣不可信，因此策略選擇成為關鍵。重復博弈的特點使得學習算法可以成為策略選擇的工具。本文研究基于均值的學習算法在重復一價拍賣中的收斂情況。本文模型簡單，可直接計算證明出均衡，通過模擬實驗的方法比對實驗結果與均衡，從而印證結論。
• 內容涉及：重復博弈、在線學習算法、無悔算法、簡單模型的均衡計算、學習算法在不同條件下（最高估值參賽者個數）是否會收斂到均衡。
• 模型：參賽者集合$N=\{1,2,...,n\},n\ge 2$。單一賣家拍賣單一物品無限輪次。每位競價者都對物品有著固定的估值$v^i$（不隨輪次改變）。假設$v^1\ge v^2\ge ...\ge v^N$。在每一輪$t\ge 1$中，每位競價者產生競價$b_t^i\in \{0,1,...,V\}$。競價最高者得并且支付其競價，其他人不用支付競價，如果出現平局情況，則在候選人中隨機產生一位勝者。每個人的出價范圍是$B^i=\{0,1,...,v^i?1\}$。競價者$i$的期望效用函數為：（$1[b_i=ma{x}_{j\in N}{b}_t^j]$是指當滿足中括號內條件時值為1，否則為0；因為是期望收益，所以最后乘以分數表示平局情況）（一價、贏者支付競價、不同輪次估值相同、不同參賽者估值不同）
  $$u^i(b_t^i,{\mathbf{b}}_{\mathbf{t}}^{?\mathbf{i}})=(v^i?b_t^i)1[b_i=ma{x}_{j\in N}{b}_t^j]\frac{1}{|argma{x}_{j\in N}{b}_t^j|}$$
• 啟發：1.本文是重復博弈且非全支付拍賣，與目前研究的核心差距不小；2.對于重復博弈，均衡可以用學習算法去近似（學習算法也不一定收斂于均衡），那么對于復雜模型的一次博弈，有什么方法計算或者近似均衡？3.我們的模型可不可以設計為重復全支付拍賣？4.一次博弈中均衡的建立過程是否類似于重復博弈不斷學習、利用經驗調整？比如預測2/3。5.重復博弈，是最終輪次更加重要，還是所有輪次的平均更加重要？學習算法可能發散可能收斂，即使收斂結果也不一定收斂于均衡，雖然不是均衡但也代表了博弈的發展趨向，均衡也是用來代表博弈的發展趨向，二者有何區別？

2.Designing an optimal contest

• 非凹CSF可能存在合謀，不利于設計者最大化利益，因此我們考慮凹CSF。本文提出定理，在某種條件下可以為所有的凹CSF找到等價線性CSF來替代，從而簡化了分析計算。在簡化后的線性CSF上可以很容易計算出均衡進而求解最優競賽設計。本文的結論具體精準，只要確定競賽的相關參數，便可以套用公式計算出：參賽者均衡分數、最優CSF參數、設計者的期望收益。
• 模型：設想一個競賽$n$位參賽者共同競爭一個價值為$V$的獎項，并且假設競賽設計者對獎項有$V_0$的估值。參賽者$i$選擇的分數是$x_i\ge 0$，構成分數向量$(x_1,...,x_n)$。參賽者$i$的獲勝概率定義為：
  $$P_i(x_1,...,x_n)=\frac{h(x_i)}{s+{\sum }_{j=1}^{n}h(x_j)}$$
  參賽者$i$選擇分數$x_i$，其獲勝的可能性對應是$h(x_i)$。競賽設計者不將獎項分配給任何一位參賽者的可能性是$s\ge 0$。那么參賽者$i$的期望收益表示為：
  $${\pi }_i(x_1,...,x_n)=P_i(x_1,...,x_n)V?x_i=\frac{Vh(x_i)}{s+h(x_i)+{\sum }_{j=i}{h}_j}?x_i$$
  該模型特點可總結為：1.獎項采取比例分配制。2.選擇分數與權重之間存在映射函數$h()$。3.每位參賽者都需要支付自己所選擇分數的代價（類似All-Pay）。4.所有參賽者對于獎項估值相同。5.設計者也存在獎項估值，因此存在獎項不分配的概率。
• 啟發：1.創新性考慮設計者的估值，其他所有文章中都未曾涉及。但總覺得不太合適，設計者估值存在的意義是可能不會將獎項分配給任何一個人。其實其他模型中的獎項制備代價也可以體現這一點。

3.Optimal rewards in contests

• 本文關注于競賽中最優獎勵的設計，該競賽是不完全信息的，并且設計者安排的獎勵與參賽者付出的努力相關。參賽者已知自己類型與公共的類型分布后，選擇分數以最大化勝利概率，從而產生均衡。設計者由均衡的努力情況反推參賽者分布，結合分布設計最優獎勵。使用該方法分析了total-mult、total-add、highest-mult、highest-add、多獎項競賽等情況。核心結論總結如下圖：
  最有趣的發現在于：有違于常理，在某些情況下，$R^{\prime }(x)<0$，也就是說努力程度越大，獲得的獎勵卻越少。
  
• 本文采取間接的方法來求解最優獎勵。均衡中分數選擇與類型相關，即$\theta (x)$；其反函數$x(\theta )$理解為：根據均衡策略反推其類型；最優獎勵是均衡分數選擇的函數即$R(x)$，但需要結合$\theta (x)$來求解。本文四種情況下都給出了具體的求解公式。
• 模型：考慮一個$n$位參賽者參與且獎項與努力有關地全支付競賽。每位參賽者的類型都獨立同分布于$[\underline{\theta },\bar{\theta }]$，累計分布函數為$F$且為公共已知信息。代價函數為$c({\theta }_i,x_i)$隨著$\theta$而遞減，隨著$x_i$而遞增，且$c(\theta ,0)=0,li{m}_{x\to \infty }c(\theta ,x)=\infty$。
  擁有最高努力的參賽者$i$獲得獎勵$R(x_i)$，其勝利效用為$V(\theta ,R(x_i))$。換句話說，獲勝者獲得的獎勵與其努力程度相關，勝利效用不單單與獎勵相關，還與其類型相關。考慮勝利效用的兩種形式：mult形式：$V(\theta ,R(x_i))=\theta ?R(x_i)$，代表了勝利的金錢效用與類型有關，比如科研競賽；add形式：$V(\theta ,R(x_i))=\theta +R(x_i)$，代表有獨立于金錢效用的一部分勝利效用，比如名望、地位等與金錢無關，比如體育競賽。（代價函數$c({\theta }_i,x_i)$，勝利效用$V(\theta ,R(x_i))$，勝利效用中$\theta$與$R(x_i)$也有兩種關聯方式：乘法與加法，設計者目標函數有兩種。）
• 本文模型設計較為奇怪，類型與代價函數、勝利效用函數的耦合很深，很少見到這樣的模型。

4.Asymmetric All-Pay Auctions with Incomplete Information:The Two-Player Case

• 不完全信息的非對稱全支付拍賣。證明了均衡的存在性與唯一性。（大篇幅的證明過程，無明顯結論，結論與證明過程彼此融合，非常抽象）

5.Asymmetric All-Pay Auctions with Two Types

• 不完全信息的非對稱全支付拍賣。證明了均衡的存在性與唯一性。（大篇幅的證明過程，無明顯結論，結論與證明過程彼此融合，非常抽象）
• 模型：全支付拍賣中有$2$個競價者，勝利估值都是$1$。概率為$p_i\in (0,1)$，競價者$i$屬于強類型，擁有較低的邊際代價$c_i$；概率為$1?p_i$，競價者$i$屬于弱類型，擁有較高的邊際代價$C_i$。我們假設$c_i<C_i<\infty$。概率分布是公共已知的，每位競價者只知道自己的類型而不知道對手的。參賽者的期望收益是$P_i(e)?c_{i}e$或$P_i(e)?C_{i}e$。

6.All-pay auctions—an experimental study

• 這篇文章匯報了關于重復全支付拍賣博弈的一些結論。所使用的拍賣形式盡可能簡單，完全信息、完美響應以及公共估值。我們主要地發現是在這樣的拍賣中，過高出價是非常激烈的，并且在早期階段賣家的收益強依賴于競價者地個數。然而過了幾輪博弈之后，這種依賴性完全消失并且賣家的收益變成獨立于參賽者的個數。這些結果面對與兩個經濟理論的概念，納什均衡與對稱Logit均衡。
• 重復全支付拍賣；模型非常簡單：完全信息、完美響應、公共估值、對稱；觀察Over-biding的現象；實驗結果表明前幾輪設計者收益與參賽者個數相關，之后輪次呈現無關；納什均衡理論與Logit均衡理論都無法很好解釋現象。真人實驗而非模擬實驗。
• 本文模型與經典的All-Pay Contests非常像，本來以為這是一篇使用計算機做模擬實驗的文章呢。

7.后續

• 后續我也找了一些用算法去計算/近似均衡的文章，也都是在All-Pay的模型下，還沒來得及看。所以我的初步設想是，找一篇現在有完整均衡求解推理的文章，然后利用模擬實驗的方法去驗證是否符合均衡；設計一個相對復雜的設定，用模擬實驗的方法去近似均衡。
  
  

總結

以上是生活随笔為你收集整理的近期几篇有关All-Pay论文总结（博弈论+机制设计）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。