路上的半厭惡型設施選址博弈的機制設計

姜秀秀，姜 永，劉龍城，朱李岑

(1.廈門大學數學科學學院，福建 廈門 361005；2.福建農林大學計算機與信息學院，福建 福州 350002)

算法機制設計，最早起源于Nisan等[1]為解決任務排序和資源分配等優化問題所做的研究. 在這些問題中，輸入的最初信息來源于每個參與者報告的私人信息，而每個參與者可能是自私的，即他們可能會為了獲得更多的利益而謊報私人信息，最終導致輸出的結果與最優結果相差甚遠. 一個機制就是一個可以輸出結果的函數.給定參與者的報告信息，目標是設計一個機制，不僅迫使所有參與者講真話，而且使目標函數最優.

本文討論一種新的設施選址博弈，稱之為半厭惡型設施選址博弈. 一個典型的例子是：政府計劃在一個城市新建一個高鐵站服務于全市居民. 對于即將建立的高鐵站，一部分人因要經常乘坐高鐵出行而希望高鐵站離自己所在居住地越近越好，另一部分人極少乘坐高鐵出門而希望高鐵站離自己所在居住地越遠越好，以免高鐵站給他們的日常生活帶來不利的影響. 所有居民向政府報告他們的居住地址和對高鐵站的偏好(喜歡或討厭)，以便政府確定建立高鐵站的最優位置. 喜歡高鐵站的居民的效用為：城市的直徑減去居住地與高鐵站的距離. 討厭高鐵站的居民的效用為：居住地與高鐵站的距離. 半厭惡的社會福利被定義為所有居民的效用總和. 因此，政府的目標是使半厭惡的社會福利最大化. 與傳統的選址問題不同的是，本文中每個居民的信息都是私人信息，居民可能謊報地址或謊報偏好以達到自身效用最大化. 這種半厭惡的設施選址博弈的目標是設計一個可以根據居民的報告信息來決定設施位置的機制，且該機制具有小性能比的團防策略性.一個機制具有團防策略性是指若對于任意的參與者團體，其中的成員謊報信息，至少有一個成員不會從中獲益.

許多文獻中有著豐富的設施選址博弈研究. 對于一些度量空間已有一些防策略性的機制，例如，當設施在一條路上[2-5]或在一般網絡上[6]. 過去十多年，已有許多研究工作從機制設計角度研究優化問題，主要關于傳統的設施選址博弈，其中每個參與者(居民)希望盡可能靠近設施. 這類問題有兩個優化目標：社會成本和最大成本. 對于社會成本，Procaccia等[7]研究了當所有參與者位于一條路上時的設施選址博弈問題；如果在這條路上只建立一個設施，那么存在一個具有團防策略性的最優機制；如果在這條路上要建立兩個設施，他們給出了一個上界為n-2和下界為1.5的具有防策略性的確定型機制. 對于后一種情況，Lu等[8]給出了一個上界為n/2和下界為1.045的具有防策略性的隨機型機制. 隨后，Lu等[9]還給出了一個具有防策略性的確定型機制，優化上界到(n-1)/2，而且對于一般的度量空間，設計了一個性能比為4的隨機型機制. Cheng等[10]研究了令人討厭的設施選址博弈問題：當參與者位于一條路上時，給出了具有團防策略性的一個性能比為3的確定型機制和兩個性能比分別為5/3和3/2的隨機型機制.

1 預備知識

本文引用文獻[9]的定義和符號.設N={1,2,…,n}為參與者集合且所有參與者在一條路上.不失一般性地，假設路的左端點為0，路的右端點為2，也就是把路看成區間I=[0,2].?x,y∈I的距離為d(x,y)=|x-y|.顯然，?x∈I，d(x,x)=0.

設參與者i報告的位置為xi∈I，則向量X=(x1,x2,…,xn)∈In稱為參與者的位置向量. 設參與者i的偏好為pi，其要么是討厭此設施(記為h)，要么是喜歡此設施(記為l)， 則向量P=(p1,p2,…,pn)(pi∈{h,l})稱為參與者的偏好向量. 用(X,P)來表示所有參與者的信息.

在半厭惡型設施選址博弈中，確定型機制基于給定的位置向量X和偏好向量P輸出設施位置，也可以看作一個函數f:(X,P)→I，而設施位置記為y=f(X,P).如果參與者i討厭該設施，那么參與者i的效用是他/她的居住地與設施的距離，即

u(f(X,P),(xi,pi))=d(y,xi).

如果參與者i喜歡該設施，那么參與者i的效用是圖G的直徑減去他/她的居住地與設施的距離，即

u(f(X,P),(xi,pi))=φ-d(y,xi)，

其中圖G是指通常意義的圖，包括路徑和圈等，其直徑φ即為圖G上任何兩點之間距離的最大值.

隨機型機制可以看成是一個函數f:(X,P)→φI，其中φI是設施在I上的分布. 此時參與者i的效用是基于上述分布的參與者i的期望效用，即如果參與者i討厭該設施，那么

u(f(X,P),(xi,pi))=Ey～f[d(y,xi)]；

如果參與者i偏好該設施，那么

u(f(X,P),(xi,pi))=Ey～f[φ-d(y,xi)].

設X-i=(x1,x2,…,xi-1,xi+1,…,xn)為不含參與者i居住位置xi的其余n-1個參與者的位置向量，P-i=(p1,p2,…,pi-1,pi+1,…,pn)為不含參與者i偏好pi的其余n-1個參與者的偏好向量.參與者集S?N，XS表示S中參與者的位置向量，X-S表示除去S中參與者后剩余參與者的位置向量，PS和P-S表示相對應集合的偏好向量.因此得到3個等價的符號：(X,P)=((xi,X-i),(pi,P-i))=((XS,X-S),(PS,P-S)).

為了書寫方便，記

(xi,X-i,pi,P-i)=((xi,X-i),(pi,P-i))，

(XS,X-S,PS,P-S)=((XS,X-S),(PS,P-S)).

對應于位置向量X和偏好向量P的確定型機制f所獲得的社會福利定義為n個參與者的效用總和，即

若f為隨機型機制，則社會福利為期望效用總和.

對于半厭惡型設施選址博弈問題，本文設計的機制不僅具有防策略性，而且還要使社會福利最大化. 給出一個位置向量X和一個偏好向量P，給定點y∈G的目標函數定義為：

其中，H為討厭此設施的參與者集合，L為喜歡此設施的參與者集合.

本文中稱機制f的性能比為ρ，若對所有的信息向量(X,P)有

OOPT(X,P)≤ρWSW(f,(X,P)).

下面定義防策略性和團防策略性.

定義1一個機制具有防策略性，如果沒有參與者可以從謊報信息(包括只謊報位置或只謊報偏好或同時謊報位置和偏好)中獲益，即對于給定參與者i，信息向量(X,P)=(xi,X-i,pi,P-i)和參與者i謊報其信息為(xi,pi)′，滿足：

u(f((xi,pi),(X-i,P-i)),(xi,pi))≥

u(f((xi,pi)′,(X-i,P-i)),(xi,pi)).

定義2一個機制具有團防策略性，如果對于任意的參與者集合，集合中的成員謊報信息，至少有一個成員不會從中獲益，即給定非空集合S?G，信息向量(X,P)=(XS,X-S,PS,P-S)，S中的參與者謊報其信息為(XS,PS)′，則存在i∈S，滿足：

u(f((XS,PS),(X-S,P-S)),(xi,pi))≥

u(f((XS,PS)′,(X-S,P-S)),(xi,pi)).

給定信息向量(X,P)，xi∈[0,2]，pi∈{h,l}.為了簡單起見，令：

H={i|i為討厭此設施的參與者}，

L={i|i為喜歡此設施的參與者}，

H1={i|xi∈[0,1]且i∈H}，

H2={i|xi∈(1,2]且i∈H}，

L1={i|xi∈[0,1]且i∈L}，

L2={i|xi∈(1,2]且i∈L}，

|H|=h，|L|=l，|H1|=h1，

|H2|=h2，|L1|=l1，|L2|=l2，

n1=h1-l1，n2=h2-l2.

2 確定型機制

在傳統的厭惡型設施選址博弈問題中，當n個參與者位于區間[0,2]時，兩個端點之一必定是最優設施位置；但這個結論不適用于半厭惡的設施選址博弈問題. 例如以下特殊情況：當H=?(空集)，即參與者均喜歡此設施，則易得出設施的最優位置應在參與者位置之間. 特別地，當只有1和2兩個參與者，他們都喜歡此設施，且x1=1/2，x2=2/3，則設施的最優位置應為y∈[1/2,2/3].

下面研究輸出為端點之一的確定型機制.

機制1給定信息向量(X,P)，且?i∈N，xi∈[0,2]，pi∈{h,l}.若n1≥n2，則y=2；否則y=0.

定理1當所有參與者都位于一條路上時，機制1是一個具有團防策略性且性能比為3的確定型機制.

證明首先證明機制1具有團防策略性.

設S?N是部分參與者集合.要證明至少有一個成員不會因謊報而獲益. 不失一般性地，假設n1≥n2，n′1和n′2分別表示S中的參與者謊報其信息后形成的新的相關人數，如果n′1≥n′2，那么S中的參與者謊報其信息后，機制1輸出的位置依然y′=y=2，則對于任意的參與者i∈S，u(y,xi)=u(y′,xi)，也即所有的參與者均未從謊報信息中獲益. 如果n′1

(i) 參與者i的真實居住位置為xi∈[0,1]且偏好為pi=h，僅謊報其居住位置為x′i∈(1,2]，或僅謊報其偏好為p′i=l.由此得到u(y′,xi)=xi≤1≤2-xi≤u(y,xi).

(ii) 參與者i的真實居住位置為xi∈[1,2]且偏好為pi=l，僅謊報其居住位置為x′i∈[0,1)，或僅謊報其偏好為p′i=h.由此得到u(y′,xi)=2-xi≤1≤xi≤u(y,xi).

綜上所述可知，S中的參與者謊報其信息，至少有一個參與者i∈S不會從中獲益，即證明了機制1具有團防策略性.

接下來證明機制1的性能比為3. 這里僅討論n1≥n2的情況(其他情況可類似證明).當n1≥n2時，機制1輸出的設施位置為y=2，因此，社會福利為：

WSW(f,(X,P))=

(1)

設y*為設施的最優位置，即有

OOPT(X,P)=F(X,P)(y*)=

(2)

考慮一個新的信息向量(X,P)′，其中，有h1個位于點1且討厭此設施的參與者，h2個位于點2且討厭此設施的參與者，l1個位于0且喜歡此設施的參與者，l2個位于1且喜歡此設施的參與者，則y*所對應的目標函數值為

F(X,P)′(y*)=h1d(1,y*)+h2d(2,y*)+

l1[2-d(0,y*)]+l2[2-d(1,y*)].

(3)

結論1F(X,P)′(y*)≤3(h1+h2).

事實上，我們知道n1≥n2，即h1-l1≥h2-l2，也即h2+l1≤h1+l2.

若y*∈[0,1]，則

F(X,P)′(y)=h1d(1,y*)+h2[1+d(1,y*)]+

l1[1+d(1,y*)]+l2[2-d(1,y*)]≤

h1d(1,y*)+h1[1+d(1,y*)]+

l2[1+d(1,y*)]+l2[2-d(1,y*)]=

h1[1+2d(1,y*)]+3l2≤3(h1+l2).

若y*∈(1,2]，則

F(X,P)′(y*)=h1d(1,y*)+h2d(2,y*)+

l1d(2,y*)+l2[1+d(2,y*)]≤h1d(1,y*)+

h1d(2,y*)+l2d(2,y*)+l2[1+d(2,y*)]=

h1+l2[1+2d(2,y*)]≤3(h1+l2).

因此，結論1成立.

結論2OOPT(X,P)-WSW(f,(X,P))+h1+l2≤F(X,P)′(y*).

事實上，

OOPT(X,P)-WSW(f,(X,P))+h1+l2=

d(xi,y*)+d(1,y*)+d(xi,y*)-d(1,y*)]+

d(xi,y*)-d(0,y*)-d(xi,y*)+d(0,y*)]+

d(1,y*)]=h1d(1,y*)+h2d(2,y*)+l1[2-

d(0,y*)]+l2[2-d(1,y*)]=F(X,P)′(y*).

綜合不等式(1)、結論1和結論2，可得

機制1的性能比為3是緊的. 考慮下面的特例：有h1=n/2個參與者討厭此設施且位于點1，h2=n/2個參與者討厭此設施且位于點2，且l1=l2=0，由此可得OOPT(X,P)=3/2n.又由機制1可知，輸出的設施位置為y=2，因此社會福利WSW(f,(X,P))=1/2n=1/3OOPT(X,P).

注意，當L=?時，問題即為Cheng等[10]所研究的問題. 因此，由文獻[10]中的定理2，可以得到定理2.

定理2設N={1,2,…,n},n≥2為參與者集合且所有參與者在一條路上，則對于半厭惡設施選址博弈問題，任何只選擇端點之一作為設施位置且具有防策略性的確定性機制的性能比至少為3.

3 隨機型機制

機制2給定信息向量(X,P)，且?i∈N，xi∈[0,2]，pi∈{h,l}.以1/2的概率輸出的設施位置為y=0，以1/2的概率輸出的設施位置為y=2.

定理3當所有參與者都位于一條路上時，機制2是一個具有團防策略性且性能比為2的隨機型機制.

證明給定信息向量(X,P)，且?i∈N，xi∈[0,2]，pi∈{h,l}.首先證明機制2產生的性能比為2. 根據機制2，社會福利為：

WSW(f,(X,P))=

設y*為設施的最優位置，則

(4)

若y*∈[0,1]，則

OOPT(X,P)≤h1+2h2+2l1+2l2≤2n.

若y*∈(1,2]，則

OOPT(X,P)≤2h1+h2+2l1+2l2≤2n.

因此，恒有

OOPT(X,P)≤2n.

綜上所述，有

即機制2的性能比為2.下面再證明該性能比是緊的.

當所有參與者均喜歡此設施且位于1，則OOPT(X,P)=2n.再根據機制2可得

WSW(f,(X,P))=n(1/2×1+1/2×1)=n=

1/2OOPT(X,P).

顯然，無論參與者如何謊報信息，機制2輸出的設施位置分布都不會改變，也即沒有參與者可以從謊報信息中獲益，因此，機制2具有團防策略性.

4 結 論

本文研究位于路上的半厭惡型設施選址博弈問題.設計了一種相對于最優社會福利的具有小性能比的團防策略性機制，具體提出了性能比為3的確定型團防策略性機制和性能比為2的隨機型團防策略性機制. 作為未來的研究方向，可以考慮參與者位于更一般網絡上的部分厭惡的設施選址博弈問題，或是考慮有兩個或更多個設施的部分厭惡的設施選址博弈問題，研究設計具有團防策略性的且有小性能比的確定型和隨機型機制.