路上的半厌恶型设施选址博弈的机制设计

姜秀秀，姜 永，刘龙城，朱李岑

(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的随机型团防策略性机制. 作为未来的研究方向，可以考虑参与者位于更一般网络上的部分厌恶的设施选址博弈问题，或是考虑有两个或更多个设施的部分厌恶的设施选址博弈问题，研究设计具有团防策略性的且有小性能比的确定型和随机型机制.