路上的半?yún)拹盒驮O(shè)施選址博弈的機(jī)制設(shè)計

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

(1.廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院，福建 廈門 361005；2.福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建 福州 350002)

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

本文討論一種新的設(shè)施選址博弈，稱之為半?yún)拹盒驮O(shè)施選址博弈. 一個典型的例子是：政府計劃在一個城市新建一個高鐵站服務(wù)于全市居民. 對于即將建立的高鐵站，一部分人因要經(jīng)常乘坐高鐵出行而希望高鐵站離自己所在居住地越近越好，另一部分人極少乘坐高鐵出門而希望高鐵站離自己所在居住地越遠(yuǎn)越好，以免高鐵站給他們的日常生活帶來不利的影響. 所有居民向政府報告他們的居住地址和對高鐵站的偏好(喜歡或討厭)，以便政府確定建立高鐵站的最優(yōu)位置. 喜歡高鐵站的居民的效用為：城市的直徑減去居住地與高鐵站的距離. 討厭高鐵站的居民的效用為：居住地與高鐵站的距離. 半?yún)拹旱纳鐣＠欢x為所有居民的效用總和. 因此，政府的目標(biāo)是使半?yún)拹旱纳鐣＠畲蠡? 與傳統(tǒng)的選址問題不同的是，本文中每個居民的信息都是私人信息，居民可能謊報地址或謊報偏好以達(dá)到自身效用最大化. 這種半?yún)拹旱脑O(shè)施選址博弈的目標(biāo)是設(shè)計一個可以根據(jù)居民的報告信息來決定設(shè)施位置的機(jī)制，且該機(jī)制具有小性能比的團(tuán)防策略性.一個機(jī)制具有團(tuán)防策略性是指若對于任意的參與者團(tuán)體，其中的成員謊報信息，至少有一個成員不會從中獲益.

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

如果參與者i偏好該設(shè)施，那么

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

設(shè)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表示相對應(yīng)集合的偏好向量.因此得到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)).

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

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

對于半?yún)拹盒驮O(shè)施選址博弈問題，本文設(shè)計的機(jī)制不僅具有防策略性，而且還要使社會福利最大化. 給出一個位置向量X和一個偏好向量P，給定點y∈G的目標(biāo)函數(shù)定義為：

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

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

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

下面定義防策略性和團(tuán)防策略性.

定義1一個機(jī)制具有防策略性，如果沒有參與者可以從謊報信息(包括只謊報位置或只謊報偏好或同時謊報位置和偏好)中獲益，即對于給定參與者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一個機(jī)制具有團(tuán)防策略性，如果對于任意的參與者集合，集合中的成員謊報信息，至少有一個成員不會從中獲益，即給定非空集合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為討厭此設(shè)施的參與者}，

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

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 確定型機(jī)制

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

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

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

定理1當(dāng)所有參與者都位于一條路上時，機(jī)制1是一個具有團(tuán)防策略性且性能比為3的確定型機(jī)制.

證明首先證明機(jī)制1具有團(tuán)防策略性.

設(shè)S?N是部分參與者集合.要證明至少有一個成員不會因謊報而獲益. 不失一般性地，假設(shè)n1≥n2，n′1和n′2分別表示S中的參與者謊報其信息后形成的新的相關(guān)人數(shù)，如果n′1≥n′2，那么S中的參與者謊報其信息后，機(jī)制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不會從中獲益，即證明了機(jī)制1具有團(tuán)防策略性.

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

WSW(f,(X,P))=

(1)

設(shè)y*為設(shè)施的最優(yōu)位置，即有

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

(2)

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

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

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

(3)

結(jié)論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).

因此，結(jié)論1成立.

結(jié)論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)、結(jié)論1和結(jié)論2，可得

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

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

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

3 隨機(jī)型機(jī)制

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

定理3當(dāng)所有參與者都位于一條路上時，機(jī)制2是一個具有團(tuán)防策略性且性能比為2的隨機(jī)型機(jī)制.

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

WSW(f,(X,P))=

設(shè)y*為設(shè)施的最優(yōu)位置，則

(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.

綜上所述，有

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

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

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

1/2OOPT(X,P).

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

4 結(jié) 論

本文研究位于路上的半?yún)拹盒驮O(shè)施選址博弈問題.設(shè)計了一種相對于最優(yōu)社會福利的具有小性能比的團(tuán)防策略性機(jī)制，具體提出了性能比為3的確定型團(tuán)防策略性機(jī)制和性能比為2的隨機(jī)型團(tuán)防策略性機(jī)制. 作為未來的研究方向，可以考慮參與者位于更一般網(wǎng)絡(luò)上的部分厭惡的設(shè)施選址博弈問題，或是考慮有兩個或更多個設(shè)施的部分厭惡的設(shè)施選址博弈問題，研究設(shè)計具有團(tuán)防策略性的且有小性能比的確定型和隨機(jī)型機(jī)制.