Contest Design with Threshold Objectives 論文閱讀筆記

• • • 一、基本信息
    • 二、文章摘要
    • 三、核心模型
    • • 3.1 Rank-Order Allocation Contests
      • 3.2 General Contests
      • 3.3 Objective Functions
    • 四、分析過程
    • 五、本文總結(jié)

一、基本信息

• 題目：帶有門限目標(biāo)函數(shù)的競(jìng)賽設(shè)計(jì)
• 作者：Edith Elkind、Abheek Ghosh、Paul W. Goldberg

二、文章摘要

• 以下內(nèi)容取自原文摘要部分：
• 我們研究的是一種競(jìng)賽，該種競(jìng)賽的目標(biāo)函數(shù)是在已經(jīng)廣泛研究的目標(biāo)函數(shù)——最大化輸出的基礎(chǔ)上拓展的，并且當(dāng)參賽者的輸出水平非常低或者非常高時(shí)設(shè)計(jì)者的邊際效用為0。我們考慮兩種變體，換言之兩種目標(biāo)函數(shù)：二進(jìn)制門限值（超過門限值對(duì)設(shè)計(jì)者產(chǎn)生1的效用，反之產(chǎn)生0的效用）、線性門限值（在兩個(gè)門限值之間產(chǎn)生效用與輸出成線性關(guān)系，其他情況下為常數(shù)）。對(duì)于這兩種目標(biāo)函數(shù)，我們分別研究兩種競(jìng)賽：rank-order allocation contest（獎(jiǎng)項(xiàng)分配只基于參賽者的排名）以及general contest（使用參賽者輸出的數(shù)字值去分配獎(jiǎng)項(xiàng)）。我們分析研究最優(yōu)化競(jìng)賽的性質(zhì)，并且指出一些有效計(jì)算均衡的技巧。我們也證明了在一定情況下，對(duì)于線性門限值目標(biāo)函數(shù)，某種ranl-order allocation contest可以接近于最優(yōu)ranl-order allocation contest。
• 我的總結(jié)：本文的核心貢獻(xiàn)在于，針對(duì)競(jìng)賽設(shè)計(jì)者提出了兩種不同的目標(biāo)函數(shù)，并且將兩種目標(biāo)函數(shù)分別在Rank-Order Allocation Contest和General Contest的設(shè)置下研究其最優(yōu)競(jìng)賽性質(zhì)。

三、核心模型

• 基礎(chǔ)設(shè)定：共有$n$位參賽者。$v=(v_1,v_2,...,v_n)$是參賽者的能力組合，$v_i$獨(dú)立產(chǎn)生于分布$F$，并且該分布的概率密度函數(shù)（PDF）記為$f$。參賽者同時(shí)產(chǎn)生輸出$b=(b_1,b_2,...,b_n)$。接下來模型的細(xì)節(jié)將會(huì)分兩類敘述。

3.1 Rank-Order Allocation Contests

• 競(jìng)賽有$n$個(gè)價(jià)值遞減的獎(jiǎng)項(xiàng)$w=(w_1,w_2,...,w_n),1\ge w_1\ge w_2...\ge w_n\ge 0$（對(duì)于unit-sum模型來說，額外要求${\sum }_j{w}_j\le 1$）。參賽者根據(jù)其輸出的排名順序獲得相應(yīng)獎(jiǎng)項(xiàng)。擁有最高輸出的參賽者獲得$w_1$，擁有第二高輸出的參賽者獲得$w_2$，以此類推。
• 具體來說，參賽者犧牲代價(jià)cost，結(jié)合自身type產(chǎn)生output參與排名。即output=cost*type。因此效用函數(shù)可以表示如下。其中$P_{ij}$表示參賽者$i$獲得第$j$個(gè)獎(jiǎng)項(xiàng)的概率。為了簡化形式，式子兩邊同乘$v_i$得到下式。
  $$\begin{gathered} u(v_i,b)=\sum _{j\in [n]}{w}_j{P}_{ij}?\frac{b_i}{v_i} \\ u(v_i,b)=v_i\sum _{j\in [n]}{w}_j{P}_{ij}?b_i \\ {P}_{ij}=\frac{\bar{1}\{b_i=b_{ij}\}}{|\{k|b_k=b_{ij}\}|} \end{gathered}$$
• 我們令$p_j(v)$表示值$v$在分布$F$下獨(dú)立取樣是第$j$高的概率，形式化表述如下。（解釋一下，$F(v)$表示獨(dú)立取樣值小于等于$v$的概率，那么值$v$是第$j$個(gè)大，就有$j?1$個(gè)大于$v$，其余小于$v$，由此而得）$n$個(gè)獨(dú)立同分布抽樣獲得第$j$高的統(tǒng)計(jì)結(jié)果的概率密度函數(shù)如下。
  $$\begin{gathered} p_j(v)=\left(\genfrac{}{}{0ex}{}{n?1}{j?1}\right)F(v{)}^{n?j}(1?F(v){)}^{j?1} \\ {f}_{n,j}(v)=\frac{n!}{(j?1)!(n?j)!}F(v{)}^{n?j}(1?F(v){)}^{j?1}f(v) \end{gathered}$$
• 定理1表明：在上述環(huán)境設(shè)定下，唯一的貝葉斯納什均衡由下式定義。（決策在于，輸入類型，輸出最優(yōu)的輸出值（output）。也就是說結(jié)合自身類型，選定最優(yōu)代價(jià)，產(chǎn)生最優(yōu)輸出值。）
  $$\beta (v)=\sum _{j\in [n]}{w}_j{\int }_0^{v}t{p}_j^{\prime }(t)dt$$
• 何為簡單競(jìng)賽（Simple Contest）？如果存在一個(gè)$j$，使得排名前$j$個(gè)參賽者每人被分配一個(gè)相等的正值獎(jiǎng)項(xiàng)，其余參與者獲得$0$獎(jiǎng)勵(lì)。

3.2 General Contests

• $x_i(v)$表示在接受能力組合$v$后，參賽者$i$獲得的期望獎(jiǎng)項(xiàng)價(jià)值。無論是unit-range/unit sum，都要求$0\le x_i(v)\le 1$，另外對(duì)于unit-sum還要求${\sum }_i{x}_i(v)\le 1$。因此相比之下，unit-range更加簡單，因?yàn)槠淇梢元?dú)立優(yōu)化每位參賽者的決策。
• 分配規(guī)則$x(v)=(x_1(v),...,x_n(v))$，假設(shè)分配規(guī)則是對(duì)稱的，也就是說相同輸出不同參與者對(duì)應(yīng)的期望收益是相等的。期望分配函數(shù)設(shè)計(jì)為$\xi (v)=E[x_i(v)|v_i=v]$。貝葉斯納什均衡下的輸出函數(shù)為：
  $$\beta (v)=v\xi (v)?{\int }_o^v\xi (t)dt$$
• 定理2：任何非減的期望分配函數(shù)$\xi$滿足下式，是可以被某些滿足unit-sum約束的分配函數(shù)$x$所實(shí)現(xiàn)的。
  $${\int }_V^1\xi (v)f(v)dv\le \frac{1?F(V{)}^n}{n}$$

3.3 Objective Functions

• 接下來形式化定義兩種目標(biāo)函數(shù)，分別是二進(jìn)制門限目標(biāo)函數(shù)（binary threshold）以及線性門限目標(biāo)函數(shù)（linear threshold）

• Binary Threshold Objective
  二進(jìn)制門限目標(biāo)函數(shù)的意思是，如果輸出值大于$B$那么其對(duì)于競(jìng)賽設(shè)計(jì)者產(chǎn)生的效用為1，如果輸出值小于$B$那么其對(duì)于競(jìng)賽設(shè)計(jì)者產(chǎn)生的效用為0。
  

• Linear Threshold Objective
  線性門限值目標(biāo)函數(shù)的含義是，在$B_L$與$B_H$之間的輸出值與所產(chǎn)生的效應(yīng)之間存在著線性關(guān)系。
  

四、分析過程

• 細(xì)節(jié)較多…

五、本文總結(jié)

• （future work）本文中，我們關(guān)注于兩個(gè)自然且實(shí)用的競(jìng)賽設(shè)計(jì)者的目標(biāo)函數(shù)，并且我們?yōu)檫@兩種目標(biāo)函數(shù)都設(shè)計(jì)了最優(yōu)競(jìng)賽。一個(gè)有趣的開放問題是，一個(gè)沒有既定輸出的競(jìng)賽，或者說一個(gè)rank-order allocation contest，可以多大程度上接近于general contest的最優(yōu)程度。另外一個(gè)該工作的拓展是研究其他實(shí)際的競(jìng)賽設(shè)計(jì)者的目標(biāo)函數(shù)，單調(diào)轉(zhuǎn)換形式與本文研究的門限轉(zhuǎn)化形式不同。結(jié)合本文對(duì)于設(shè)計(jì)者目標(biāo)函數(shù)的研究以及非線性效用、代價(jià)函數(shù)也是一個(gè)有趣的研究方向。

總結(jié)

以上是生活随笔為你收集整理的Contest Design with Threshold Objectives（博弈论+机制设计） 论文阅读笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。