FIT2010（第 9 回情報科学技術フォーラム）RA-007

架空名義操作不可能な施設配置メカニズムの特徴付け
Characterization of False-name-proof Facility Location Mechanisms
東藤 大樹∗

岩崎 敦 ∗

横尾 真 ∗Taiki Todo

Atsushi Iwasaki

Makoto Yokoo

1 序論
1.1 研究の背景
施設の配置場所を適切に決定する問題は施設配置問題 (facility location problem) と呼ばれ，伝統的にはオペレーションズリサーチや経済学において広く研究が行われてきた [4]．配置の適切さ，即ち社会的にどれだけ望ましいかの評価基準は様々であるが，例えば配置場所と各エージェントの所在地の距離の総和（社会的コスト）
や，配置場所から最も遠いエージェントの距離（最大コスト）等が考えられる．施設配置問題の最もシンプルなモデルである実軸（直線）上の施設配置問題においては様々な配置メカニズム（ルール／アルゴリズム）が提案されており，社会的コストを最小化する中央値 (median)メカニズムや最大コストを最小化する中点 (center) メカ
ニズムなどがよく知られている．
また，各エージェントが利己的に行動するような環境での施設配置問題では，エージェントが自分の所在地を偽って申告する誘因を持たない配置メカニズムの設計が重要である．中央値メカニズムはこの性質を満たすが，中点メカニズムにおいてはエージェントが所在地を偽る誘因を持つことが知られている [7]．エージェントが自分の所在地を偽る誘因を持たない，という性質は戦略的操作不可能性 (strategy-proofness) と呼ばれ，社会的コス
トや最大コストの最小化と共にメカニズムが満たすべき
重要な性質であると認識されている [5]．
一方で，電子投票システムを用いた選挙のように，インターネットを介してこのような施設配置を実現する
場合には，一人のエージェントが複数のアカウントを用いるなどして複数のエージェントであるかのように振舞う不正行為が可能となる．戦略的操作不可能性を満たす中央値メカニズムにおいても，一人のエージェント
が十分多くのアカウントを用いて全てのアカウントで自分の所在地を申告することで，自分の所在地に配置場所を変更させることができる．例えば図 1 で表される
3 エージェントの施設配置をインターネットを介して行う場合，それぞれのエージェントが正直に自分の所在地
x1 , x2 , x3 を申告した場合の中央値は x2 である (a) が，
所在地 x3 を持つエージェントが新たに 2 つのアカウン

トを用いて (x3 , x3′ , x3′′ ) = (x3 , x3 , x3 ) という 3 つの所在地を申告した場合 (b) ，中央値が x3 となり，配置
場所がこのエージェントの真の所在地に変化する．
ネットワークの普及は大規模な施設配置メカニズムを容易に実現するインフラを安価に提供する．その一方で，匿名性を利用したこのような不正行為の急速な拡大を引き起こす可能性も指摘されている [13]．このため，
不正行為の影響を受けない（不正に対して頑健な）メカ
ニズムを議論することは重要な課題として認知されている．特に電子商取引／オークションの研究分野においては，不正に対して頑健なオークションメカニズムが既にいくつか提案されてきた [13]．しかしながら，施設配置問題においてはこのような不正行為の影響を扱った従来研究は存在せず，不正に対して頑健な配置メカニズムについての議論はほとんどなされていなかった．

1.2 本研究による成果
本研究ではまず，一次元（直線）上にただ一つの施設を配置する施設配置問題において，エージェントが複数の名義を用いる誘因を持たない性質（架空名義操作不可能性／ false-name-proofness）を定式化し，この性質を満たす配置メカニズムの特徴付けを与える．これは，文献 [5] による成果の拡張である．また，この特徴付けを応用し，架空名義操作不可能な配置メカニズムが達成可能な近似率を解明する．具体的には社会的コスト及び最大コストの二つの評価基準に関して，
架空名義操作不可能な配置メカニズムが達成可能な近似率の下界値を解明し，その下界値を達成するメカニズムの存在を示す．更に，従来議論されてきた人口単
調性 (population monotonicity)，結託的戦略的操作不可
能性 (group-strategyproofness)，及び匿名操作不可能性(anonymity-proofness) について，架空名義操作不可能性との関係を明確にする．具体的には，人口単調性，匿名

図1

中央値メカニズムと架空名義操作によるコストの減少の例∗ 九州大学大学院 システム情報科学府

39（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）操作不可能性，架空名義操作不可能性の 3 つの性質が等価となることを明らかにする．また，架空名義操作不可
能な配置メカニズムは常に結託的戦略的操作不可能性を満たすことを示す．

1.3 関連研究
施設配置問題は文献 [4, 9] 等で詳細に説明されている．文献 [5] は，配置メカニズムが戦略的操作不可能性を満たすための必要十分条件を示している．文献 [7] は施設配置問題に対する計算機科学分野からの近年の成果であり，戦略的操作不可能な配置メカニズムの達成する
近似率についての考察を行っている．
適切なメカニズムの設計に関する研究はメカニズムデ
ザインと呼ばれ，経済学分野で研究されてきた [8]．中でもオークション理論 [13] やマッチング理論 [11] は特に注目を集めている．近年では計算機科学分野でもメカ
ニズムデザインの重要性が認知されてきており，アルゴ
リズム的ゲーム理論 (algorithmic game theory) [6] や計算論的社会選択理論 (computational social choice) [1] 等の新たな研究領域が形成されつつある．
エージェントが複数の名義を用いる不正行為は架空名
義操作 (false-name manipulations) と呼ばれ，従来組合
せオークションの分野で広く議論されてきた [12, 10]．
適切な社会的決定のためには架空名義操作は排除されるべきであるが，インターネットのような匿名性の高い環境においてアカウントの真の名義情報を特定することは困難である．このため，架空名義操作不可能性を満たす
メカニズムを設計する，というメカニズムデザインを用いたアプローチが重要であると考えられている．

2 準備

ないことを意味し，エージェント i, j が申告を入れ替えてそれぞれ xj , xi を申告しても，メカニズムの出力は変化しない．この仮定より，一般性を失うことなく
x1 ≤ . . . ≤ xn であるとする．パレート効率性は，いずれかのエージェントのコストを増加させることなしには，他のエージェントのコストを減少できないことを意味する．施設配置問題においては，任意の申告の組 x に対して配置場所 z が領域 [x1 , xn ] 内に定まることが，配置メカニズムがパレート効率的であるための必要十分条件となる．また，本論文で扱う配置メカニズムは決定的(deterministic) であるとする．即ち，ある申告の組 x に対して配置場所は一意に定まる．更に，配置メカニズムは任意のエージェント数に対して配置場所を決定する．
定義 2 (配置メカニズム). 配置メカニズム f は，任意のエージェント数 n ∈ N に対し，エージェントによる申告の組 x = (x1 , . . . , xn ) ∈ Rn を入力として配置 z ∈ R を出力する関数 f n の集合として次のように定義される：

f = {f n |n ∈ N, f n : Rn → R}
各エージェントが利己的である，即ち自分のコストを最小化するように振舞う場合，エージェント i によって申告される所在地が i の真の所在地 xi である保証はな
い．しかし本論文では，次に説明する戦略的操作不可能
性 (strategy-proofness) を満たす配置メカニズムを対象とするため，エージェント i によって申告される所在地
を真の所在地と区別することなく xi で表すことにする．
定義 3 (戦略的操作不可能性). 配置メカニズム f が戦略的操作不可能性を満たすとは，∀n ∈ N, ∀i ∈ N , ∀x−i ,∀xi , ∀x′i に対してcost(xi , f n (xi , x−i )) ≤ cost(xi , f n (x′i , x−i ))2.1 基本的なモデル
本章では，本論文で扱う施設配置問題のモデルと，施設配置問題における既存研究による成果を概説する．
本論文では簡単化のため，実軸 R 上でただ一つの施設の配置場所を決定する施設配置問題を扱うことにする．n 人のエージェントが参加する施設配置問題を考え，この n エージェントからなる集合を N で表す．各
エージェント i ∈ N は実軸上に真の所在地 xi ∈ R を持
つ．また，施設の配置場所が z のとき，自分の所在地と配置場所との距離が i のコストとなる．
定義 1 (エージェントのコスト). 施設が z ∈ R に配置された場合の，真の所在地 xi を持つエージェント i のコ
スト cost(xi , z) は cost(xi , z) = |xi − z| である．
施設の配置場所は，配置メカニズムと呼ばれるルール
によって決定される．配置メカニズムは各エージェントの申告する所在地の組 x = (x1 , . . . , xi , . . . , xn ) を入力とし，施設の配置場所を決定する関数として定式化できる．本論文で扱う配置メカニズムは匿名性 (anonymity)
及びパレート効率性 (Pareto-efficiency) を満たすと仮定する．匿名性は，エージェントの名前が結果に影響し(1)が成立することである．
ここで，x−i は i 以外のエージェントによる申告の組を表しており，f n (xi , x−i ) と書いた場合には，エージェント i によって xi が，i 以外のエージェントによってが x−i がそれぞれ申告された場合の施設配置を表す．
定義 3 は，戦略的操作不可能な配置メカニズムにおいては，全てのエージェントにとって自分の真の所在地を申告することが（弱）支配戦略となることを意味している．
戦略的操作不可能なメカニズムの代表的な例として，
第 1 章で挙げた中央値メカニズムがある．ここで，与えられた引数の組に対してその中央値を返す関数 medを定義する．この記法を用いると，中央値メカニズム f
は f (x) = med(x) と記述できる．また，申告された所
在地のうち最も左に位置するものを配置場所に選ぶ最左値 (leftmost) メカニズムや，最も右のものを選ぶ最右
値 (rightmost) メカニズム等も戦略的操作不可能な配置
メカニズムとしてよく知られている．
戦略的操作不可能性を満たす配置メカニズムに関して
は，文献 [5] による次の定理がよく知られている．

40（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）定理 1 (Moulin, 1980). 配置メカニズム f が戦略的操作
不可能性，パレート効率性，匿名性を満たすための必要十分条件は，f が次のように表されることである：
n∀n ∈ N, ∃(α1n , . . . , αn−1
) ∈ Rn−1 , ∀x = (x1 , . . . , xn ),n
f n (x) = med(x1 , . . . , xn , α1n , . . . , αn−1).

(2)

定理 1 は，式 (2) のパラメータによって戦略的操作不可能なメカニズムを特徴付けるものである．実際，中央値メカニズムはパラメータが{−∞ if l is oddn∀l ∈ {1, . . . , n}, αl =∞if l is evenと定められたものと解釈でき，最左値（最右値）メカニ
ズムは全てのパラメータが −∞(∞) と定められたものであると解釈できる．

2.2 メカニズムの評価基準
メカニズムの評価基準，即ちメカニズムの性能を判断する指標は，メカニズム設計者の目的によって様々に定義できる．本論文では社会的コスト (social cost) 及び最大コスト (maximum cost) の最悪時の近似率 (worst-caseapproximation ratio) を評価基準として導入する．
まず，申告の組 x に対する配置メカニズム f の社会的コスト及び最大コストを定義する．
定義 4 (配置メカニズムのコスト). 申告の組 x に対する
配置メカニズム f の社会的コスト SCf (x) 及び最大コ
スト MCf (x) はそれぞれ以下で与えられる：SCf (x) =∑cost(xi , f n (x)),

i

MCf (x) = max cost(xi , f n (x))
i

即ち，社会的コストは参加エージェント全体のコストの総和を表しており，社会的コストを最小化すること（ミニサム型配置 [4] とも呼ばれる）は社会全体の効率を高めることに繋がる．一方で最大コストはコスト最大のエージェントのコストを表しており，最大コストを最小化すること（ミニマックス型配置 [4] とも呼ばれる）は，ある意味で公平な施設配置に繋がる．
次に，これらのコストに関して，そのコストの下で最適な施設配置に対するコストの近似率 (approximation
ratio) を定義する．
定義 5 (近似率). 申告の組 x に対する配置メカニズム fの社会的コストの近似率 ARSC
f (x) 及び最大コストの近似率 ARMCf (x) はそれぞれ以下で与えられる：SC (x)∑ f
ARSC,
f (x) =
minz i cost(xi , z)
MCf (x)
ARMC
f (x) =
minz maxi cost(xi , z)

これらを評価基準に用いて，配置メカニズムの最悪時の近似率を定義する．
定義 6 (最悪時の近似率). 配置メカニズム f の社会的コストの最悪時の近似率 WCARSC
f 及び最大コストの最悪時の近似率 WCARMC
はそれぞれ以下で与えられる：f
SC
WCARSCf = max ARf (x),x

WCARMC= max ARMC
f
f (x)
x

2.3 架空名義操作不可能性
次に，配置メカニズムの架空名義操作不可能性 (falsename-proofness) について議論する．まず，エージェン
ト i が使用する名義の集合を ϕi とし，i が名義の集合
ϕi を用いて申告する所在地の組を x′ϕi で表すとする．
このとき，配置メカニズムの架空名義操作不可能性は以
下のように定義される．
定義 7 (架空名義操作不可能性). 配置メカニズム f が架空名義操作不可能性を満たすとは，∀n ∈ N, ∀i ∈ N ,∀x−i , ∀xi , ∀ϕi ∀x′ϕi に対してcost(xi , f n (xi , x−i )) ≤ cost(xi , f n−1+|ϕi | (x′ϕi , x−i ))(3)が成立することである．
即ち，架空名義操作不可能な配置メカニズムにおいては，全てのエージェントにとって，複数の名義で参加できるにも関わらず，ただ一つの名義のみを用いて自分の真の所在地を申告することが（弱）支配戦略となる．
第 1 章で述べたように，中央値メカニズムは架空名義
操作不可能性を満たさない．一方，最左値メカニズムや最右値メカニズムは架空名義操作不可能性を満たす．

3 架空名義操作不可能性の特徴付け
本章では，架空名義操作不可能な配置メカニズムを特徴付ける．具体的には，以下の定理を示すことで，配置メカニズムが架空名義操作不可能性を満たすための必要十分条件を与える．
定理 2. 施設配置メカニズム f が架空名義操作不可能性，パレート効率性，及び匿名性を満たすための必要十分条件は，f が次のように表されることである：∃α ∈ R, ∀n ∈ N, ∀x = (x1 , . . . , xn ),f n (x) = med(x1 , . . . , xn , α, . . . , α)
| {z }(4)n−1

この定理を，以下の二つの補題に分けて示す．
補題 1. 配置メカニズム f が式 (4) を満たすとき，f は
架空名義操作不可能性，パレート効率性，及び匿名性を満たす．

41（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）

数学的帰納法を用いて示す．まず基底段階である

図2

n = 2 のとき，パラメータは一つのみなので，明らかに
n 以下の任意のエージェント数に関して同一のパラメー
タ α を持つ．
次に，n = k(≥ 2) の場合に k 以下の任意のエージェ
ント数に関して同一のパラメータ α を持つと仮定し，
n = k + 1 の場合の k 個のパラメータも全て α に等しいことを示す．即ち，定理 1 で与えられるパラメータにコストの減少しない架空名義操作

関して証明. 明らかに，配置メカニズム f が式 (4) を満たすな
らば同時に式 (2) を満たす．よって定理 1 より，f はパレート効率性及び匿名性を満たす．あとは，f が式 (4)を満たすとき，f が架空名義操作不可能性を満たすことを示せば十分である．
式 (4) を満たす配置メカニズム f のパラメータ α に対して，エージェントの真の所在地の組 x = (x1 , . . . , xn )が x1 ≤ α ≤ xn である場合，いずれのエージェントも架空名義操作を行わない場合の出力 f n (x) は f n (x) = α
である．このとき，自分の真の所在地を申告せず，他のエージェントの申告も含めた全ての申告が α から見て同じ方向に存在するような架空名義操作（図 2）を行った場合にのみ出力は変化する．しかしながら，式 (4) より，この操作によって f の出力が自分の真の所在地に近づくことはなく，コストは減少しない．よって架空名義
操作不可能性を満たす．
次に，α < x1 である場合，いずれのエージェントも架空名義操作を行わない場合の出力 f n (x) は f n (x) = x1
である．このとき，式 (4) より，あるエージェント i が（少なくとも一つの）架空名義 i′ を追加して xi′ < x1
なる点 xi′ を申告した場合にのみ，出力は変化する．このときメカニズムの出力は f n+1 (x, xi′ ) = max{α, xi′ }となる．今，α < x1 及び xi′ < x1 が成立しているので，任意のエージェント i に関してコストは増加する．
よって架空名義操作不可能性を満たす．同様の議論が
xn < α の場合にも成立する．
補題 2. 配置メカニズム f が架空名義操作不可能性，パレート効率性，及び匿名性を満たすとき，f は式 (4) を満たす．
証明. 架空名義操作不可能性は戦略的操作不可能性を包含する性質であるため，定理 1 より，配置メカニズム
f が架空名義操作不可能性，パレート効率性，及び匿名性を満たすとき，f はエージェント数 n(≥ 2) に対して
nn − 1 個のパラメータ α1n , . . . , αn−1を持ち，式 (2) で与えられる中央値を出力する．あとは，任意の n(≥ 2) に対して定義されるこれらのパラメータkα1k = . . . = αk−1
= α1k−1 = . . . = α1k−2 = . . . = α12 = α(5)が成立していると仮定し，n = k + 1 において

α1k+1 = . . . = αkk+1 = α(6)が成立することを示す．
まず，α < α1k+1 の場合を考える．このとき，k 人のエージェントによる申告の組 x がα ≤ x1 ≤ . . . ≤ xk < α1k+1を満たす状況において，エージェント k が架空名義 k ′を用いて xk′ = xk を申告すると，メカニズムの出力はf k (x) = med(α, . . . , α, x1 , . . . , xk ) = x1
| {z }
k−1

から

f k+1 (x, xk′ ) = med(x1 , . . . , xk , xk , α1k+1 , . . . , αkk+1 ) = xkに変化する．この操作によってエージェント k のコストは xk − x1 から 0 に減少しており，架空名義操作不可
能性を満たすという前提に矛盾する．不等号を逆にする
ことで，αkk+1 < α の場合にも同様の議論が成立する．
次に，ある j ∈ {1, . . . , k − 1} が存在して
k+1
k+1
αjk+1 ≤ α < αj+1
または αjk+1 < α ≤ αj+1
k+1が成立している場合を考える．今，αjk+1 ≤ α < αj+1とすると，k 人のエージェントによる申告の組 x がk+1
α < x1 ≤ . . . ≤ xk < αj+1

なる申告の組 x = (x1 , . . . , xk ) を考えることができる．
このとき，k − j 番目に小さい値を持つエージェントを
l とおくと，l が架空名義 l′ を追加して xl′ = xl を申告することで，メカニズムの出力はf k (x) = med(α, . . . , α, x1 , . . . , xk ) = x1
| {z }
k−1

から

f k+1 (x, xl ) =n. . . , α1n , . . . , αn−1
, α1n+1 , . . . , αnn+1 , . . .

med(α1k+1 , . . . , αjk+1 , x1 , . . . , xl , xl ,
|
{z
}
k

k+1
xl+1 , . . . , xk , αj+1
, . . . , αkk+1 )が全て等しいことを示せばよい．

= xl

42
（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）証明. 定理 2 より，任意の架空名義操作不可能な配置メ
カニズム f はパラメータとしてある点 α を持つことが示されている．このとき，f の持つパラメータ α(̸= ∞)に対して次のような申告の組 x = (x1 , . . . , xn ) を考えることができる：

α < x1 < x2 = . . . = xn
図3

架空名義操作不可能な配置メカニズムに変化する．よって l のコストが減少し，架空名義操作
不可能性を満たすという前提に矛盾する．αjk+1 ≤ α <k+1
αj+1の場合にも同様の議論が成立する．

定理 2 の与える特徴付けは，以下のように解釈できる．今，パレート効率性と匿名性を満たす配置メカニズ
ムを考えるとする．このとき，配置メカニズム f がある
パラメータ α ∈ R を持ち，

パラメータ α = ∞ の場合にも，不等号を逆にすれば以下の議論は同様に成立する．
定 理 2 よ り ，x に 対 す る メ カ ニ ズ ム f の 出 力 は
f n (x) = x1 となり，このときの社会的コスト SCf は

SCf (x) = (n − 1) · |x2 − x1 |となる．一方，この x に対して社会的コストを最小化す
る配置 z は z = x2 であり，このときの社会的コストは|x2 − x1 |• 全てのエージェントによる申告が α から見て同じ方向にある場合，申告された所在地の内 α に最も近い値を配置場所として出力（図 3 (a) または (b)）• さもなければ α を配置場所として出力（図 3 (c)）

である．よって，x に対する社会的コストの近似率がと表現可能である場合，またその場合に限り，f は架空
名義操作不可能性を満たす．明らかに，α = −∞ である最左値メカニズムと α = ∞ である最右値メカニズム
はこの形式で表現可能であるため，架空名義操作不可能性を満たす．一方，中央値メカニズムはこの形式では表現できないため，架空名義操作不可能性を満たさない．
このように，我々の与えた特徴付けによって，メカニズ
ムの架空名義操作不可能性の容易な検証が可能となる．

となる．任意の架空名義操作不可能な配置メカニズムに対して上記の議論は成立するので，社会的コストの最悪時の近似率の下界値は n − 1 となる．

4 近似率解析
本章では，架空名義操作不可能な配置メカニズムの社
会的コスト及び最大コストを議論する．具体的には，最悪時の近似率を評価基準とし，架空名義操作不可能な
配置メカニズムが達成可能な最悪時の近似率の下界値(lower bound) を解明するとともに，実際にその下界値を達成する配置メカニズムが存在することを示す．表 1に本章で得られた結果をまとめている．

4.1 社会的コスト
本節では架空名義操作不可能な配置メカニズムが達成可能な社会的コストの最悪時の近似率を議論する．まず
定理 3 で架空名義操作不可能な配置メカニズムが達成可能な社会的コストの最悪時の近似率の下界値を示した
後，定理 4 でその下界値を達成する配置メカニズムの存在を示す．
定理 3. 架空名義操作不可能な配置メカニズムが達成可
能な社会的コストの最悪時の近似率の下界値は n − 1 である．

(n−1)·|x2 −x1 |ARSC
f (x) =
|x2 −x1 |= n−1

定理 4. 最左値メカニズムの社会的コストの最悪時の近似率は n − 1 である．
証明. 最左値メカニズムは，パラメータ α = −∞ で定義される架空名義操作不可能な配置メカニズムである．
任意の申告の組 x に対し，最左値メカニズムの社会的コストの近似率 ARSC
LM (x) は∑i̸=1 |xi − x1 |ARSC
LM (x) = ∑i̸=⌈n/2⌉ |xi − x⌈n/2⌉ |(7)∑である．ここで，式 (7) の分母 i̸=⌈n/2⌉ |xi − x⌈n/2⌉ |は入力 x に対する中央値メカニズムの社会的コストを表す．中央値メカニズムは社会的コストの最悪時の近似率が 1 である [7] ，中央値メカニズムの社会的コストを近似率の分母に用いることができる．
式 (7) の右辺について∑∑∑i̸=1 |xi − x1 |i̸=⌈n/2⌉ |xi − x⌈n/2⌉ |≤∑i̸=1 |xn − x1 |

i=1,n |xi − x⌈n/2⌉ |(n − 1)(xn − x1 )=xn − x1=n−1であり，x1 < x2 = . . . = xn なる申告の組 x に対して等号が成立する．よって，WCARSC
LM = n − 1 となる．

43
（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）表 1 架空名義操作不可能な配置メカニズムが達成可能な社会的コスト及び最大コストの最悪時の近似率を示す．

SP および FNP はそれぞれ戦略的操作不可能性と架空名義操作不可能性を表している．架空名義操作不可能性に関して，いずれのコストにおいてもタイトな近似率が得られていることが分かる．

社会的コスト
最大コスト

近似率

SP

FNP

上界値
下界値

1 （中央値メカニズム）1n − 1（定理 4）n − 1（定理 3）

上界値

2 （最左値メカニズム）2（定理 6 (文献 [7]) ）下界値

2 (文献 [7])2（定理 5）4.2 最大コスト
社会的コストを議論した第 4.1 節に対し，本節では，
架空名義操作不可能な配置メカニズムが達成可能な最大コストの最悪時の近似率を議論する．まず定理 5 で架空名義操作不可能な配置メカニズムが達成可能な最大コストの最悪時の近似率の下界値を示した後，実際にその下界値を達成するメカニズムが存在することを示す．
定理 5. 架空名義操作不可能な配置メカニズムが達成可
能な最大コストの最悪時の近似率の下界値は 2 である．
証明. 文献 [7] によって，戦略的操作不可能な配置メカ
ニズムが達成可能な最大コストの最悪時の近似率の下界
値が 2 となることが示されている．架空名義操作不可
能性は戦略的操作不可能性よりも厳しい条件であるため，その下界値は小さくなることはない．よって，架空
名義操作不可能な配置メカニズムが達成可能な最大コストの最悪時の近似率の下界値は 2 となる．
更に文献 [7] において，最左値メカニズムの最大コス
トの最悪時の近似率が 2 であることも示されている．
定理 6 (Procaccia and Tennenholtz, 2009). 最左値メカニ
ズムの最大コストの最悪時の近似率は 2 である．
既に述べた通り，最左値メカニズムはは架空名義操作不可能な配置メカニズムである．よって，定理 5 で示された下界値がタイトなものであることが分かる．

5 他の概念との関係
社会選択理論やメカニズムデザインの分野では，戦略的操作不可能性や架空名義操作不可能性以外にも，メカニズムが満たすべき様々な性質が提案されている．それらの性質の関係を明確にすることは，可能な限り多くの性質を満たすメカニズムを設計する上で重要である．
本論文で扱う架空名義操作不可能性は，エージェントの操作によって参加する名義数が変化する環境を考慮している．このような参加エージェント（名義）数が一定
でない環境を考慮した他の研究事例として，人口単調性と匿名操作不可能性という性質が知られている．また，結託的戦略的操作不可能性は，戦略的操作不可能性を拡張した概念として広く議論されてきた性質である．

本章では，施設配置問題におけるこれらの性質と架空
名義操作不可能性との関係を解明する．具体的には，パレート効率性と匿名性を満たす施設配置問題において，
人口単調性，匿名操作不可能性，架空名義操作不可能性の 3 つの性質が等価となることを示した．また，架空
名義操作不可能な配置メカニズムは結託的戦略的操作
不可能性を満たすが，逆は必ずしも成立しないことを示した．

5.1 人口単調性との関係
人口単調性は社会選択における整合性 (consistency)と呼ばれる性質に関する概念である [2]．
定義 8 (人口単調性). 配置メカニズム f が人口単調性を満たすとは，∀n ∈ N, ∀x = (x1 , . . . , xn ), ∀j ∈ N に対して，以下の 2 式のいずれかが成立することである：

cost(xi , f n (x)) ≤ cost(xi , f n−1 (x−j )) ∀i ̸= j, (8)cost(xi , f n (x)) ≥ cost(xi , f n−1 (x−j )) ∀i ̸= j

(9)

即ち，人口単調性を満たす配置メカニズムにおいては，あるエージェント j が参加することによって，元々存在していた他のエージェントのコストは，全員増加す
るか，あるいは全員減少するかのいずれかとなる．
本節では人口単調性と架空名義操作不可能性との関係について，次の定理を示す．
定理 7. 匿名かつパレート効率的な施設配置問題において，メカニズムの架空名義操作不可能性と人口単調性とは等価である．
証明. 文献 [2] において，配置メカニズムが人口単調性を満たすための必要十分条件が与えられている．その条
件は式 (4) と一致しており，人口単調性と架空名義操作不可能性が等価であることが分かる．
配置メカニズムにおける架空名義操作不可能性と人口単調性との等価性は，直感的には以下のように解釈できる．今，パレート効率的な配置メカニズムのみを考慮しているため，新規エージェント j の参加によって誰かのコストが真に減少するならば，他の誰かのコストは真に増加する．即ち，人口単調性が定義 8 の式 (8) の意味で成立することはない．よって，パレート効率的な配置メカニズムにおいては，人口単調性は式 (9) による定義の44（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）みで必要十分となる．ここで式 (9) は，新規エージェン
トの追加によって，元々存在していたエージェントのコ
ストが真には減少しないことを意味しており，架空名義
操作不可能性と同じ条件を示すものとなる．

5.2 結託的戦略的操作不可能性との関係
結託的戦略的操作不可能性は，エージェントの結託（グループ）による操作に対しての頑健性として提案された性質であり，経済学分野で広く議論されている [5]．
定義 9 (結託的戦略的操作不可能性). 配置メカニズム fが結託的戦略的操作不可能性を満たすとは，∀n ∈ N,
∀S ⊆ N , ∀x−S , ∀xS , ∀x′S に対して，次式を満たすエー
ジェント i ∈ S が少なくとも一人存在することである：

cost(xi , f n (xS , x−S )) ≤ cost(xi , f n (x′S , x−S )) (10)ここで，xS は結託 S に属するエージェントの真の所
在地の組を表しており，x′S は結託 S による操作（申告の変更）を意味する．即ち，結託的戦略的操作不可能な
配置メカニズムにおいては，エージェントの集合 N 内のどのような結託 S による操作 x′S に対しても，S 内に少なくとも一人，コストが真に減少することのないエー
ジェントが存在する．施設配置問題においては，メカニ
ズム外部での金銭による補償 (side-payment) が不可能であるため，コストが真に減少しないエージェントは結託に参加する誘因を持たないと考えられる．
施設配置問題における戦略的操作不可能性と結託的戦
略的操作不可能性との関係については，文献 [5] にてその等価性が示されている．
定理 8 (Moulin, 1980). 匿名かつパレート効率的な施設配置問題において，メカニズムの戦略的操作不可能性と結託的戦略的操作不可能性とは等価である．
本節では，結託的戦略的操作不可能性と架空名義操作
不可能性との関係について，次の定理を示す．
定理 9. 匿名かつパレート効率的な施設配置問題において，架空名義操作不可能なメカニズムは結託的戦略的操
作不可能性を満たすが，逆は必ずしも成り立たない．
証明. 定理 8 より，匿名かつパレート効率的な施設配置問題において結託的戦略的操作不可能性を議論する場
合，戦略的操作不可能性を議論すれば十分である．架空
名義操作不可能性の定義より，メカニズムが架空名義操作不可能性を満たす場合，同時に戦略的操作不可能性を満たす．一方，中央値メカニズムは戦略的操作不可能ではあるが，第 1 章で述べたように架空名義操作不可能性を満たさない．

5.3 匿名操作不可能性との関係
匿名操作不可能性 (anonymity-proofness) は架空名義
操作不可能性を更に拡張した概念である．匿名操作不可能性を定義する前に，まず参加制約 (participation) と呼ばれる概念を説明する．

定義 10 (参加制約). 配置メカニズム f が参加制約を満たすとは，∀n ∈ N, ∀i ∈ N , ∀x−i , ∀xi に対して次式が成立することである：

cost(xi , f n (xi , x−i )) ≤ cost(xi , f n−1 (x−i ))(11)

匿名操作不可能性は，架空名義操作不可能性と参加制
約を合わせた性質として，投票制度を扱った文献 [3] において次のように定式化された．
定義 11 (匿名操作不可能性). 施設配置メカニズム f が
匿名操作不可能であるとは，f が架空名義操作不可能性と参加制約を同時に満たすことである．
即ち，匿名操作不可能なメカニズムにおいては，全てのエージェントにとって，架空名義操作のみならず，メ
カニズムに参加しないことも戦略として選べる状況においても，ただ一つの名義のみを用いて自分の真の所在地を申告することが（弱）支配戦略となる．
本節では，匿名操作不可能性と架空名義操作不可能性との関係について，以下の定理を示す．
定理 10. 匿名かつパレート効率的な施設配置問題において，メカニズムの架空名義操作不可能性と匿名操作不可能性とは等価である．
証明. 匿名操作不可能性の定義より，配置メカニズム f
が匿名操作不可能であれば f が架空名義操作不可能性を満たすことは明らかである．定理を証明するためには，f が架空名義操作不可能性を満たすとき，f が同時に参加制約を満たすことを示せば十分である．
今，f が架空名義操作不可能性を満たすと仮定すると，定理 2 より，あるパラメータ α が存在し，エージェ
ント数 n と申告の組 x = (x1 , . . . , xn ) に対して f は
式 (4) で与えられる配置を出力する．このとき左右の対称性から，パラメータ α に関して α ≤ x⌊n/2⌋+1 を仮定しても一般性を失わない．
まず α ≤ x1 の場合，メカニズムの出力は

f n (x) = med(α, . . . , α, x1 , . . . , xn ) = x1
| {z }n−1

である．このとき，エージェント 1 が参加しないことによってメカニズムの出力は

f n−1 (x−1 ) = med(α, . . . , α, x2 , . . . , xn ) = x2
| {z }n−2と変化するが，エージェント 1 のコストは |x1 − x1 | ≤|x1 − x2 | と非減少であり，エージェント 1 に関しては参加制約を満たす．他のエージェント i(̸= 1) についても，
i が参加しないことによって得られる出力 f n−1 (x−i ) は
f n−1 (x−i ) = x1 となり，i が参加している場合の出力と同じである．よって，参加しないことでコストが真に減少するエージェントは存在せず，参加制約を満たす．

45（第1分冊）

FIT2010（第 9 回情報科学技術フォーラム）次に x1 < α ≤ x2 である場合，メカニズムの出力は

f n (x) = med(x1 , α, . . . , α, x2 , . . . , xn ) = α| {z }n−1

である．このとき，エージェント 1 が参加しないことによってメカニズムの出力は

f n−1 (x−1 ) = med(α, . . . , α, x2 , . . . , xn ) = x2
| {z }n−2と変化するが，エージェント 1 のコストは |x1 − α| ≤|x1 − x2 | と非減少であり，エージェント 1 に関しては参加制約を満たす．他のエージェントに関しても，α < x1の場合と同様に参加制約を満たす．
最後に，ある j (2 ≤ j ≤ ⌊n/2⌋) が存在し，xj < α ≤xj+1 である場合を考える．このときの出力は

f n (x) = med(. . . , xj , α, . . . , α, xj+1 , . . .) = α| {z }n−1

であり，一人のエージェントの不参加によって出力が変化する例は存在しない．よって参加制約を満たす．
以上より，f が架空名義操作不可能ならば，同時に参加制約を満たす．よって架空名義操作不可能性と匿名操
作不可能性は等価となる．

6 結論
本論文では，一次元上にただ一つの施設を配置する施設配置問題における架空名義操作不可能性を定式化し，
架空名義操作不可能な配置メカニズムの特徴付けを与えた．また，特徴付けを応用し，架空名義操作不可能な配置メカニズムが達成可能な近似率を解明した．更に架空名義操作不可能性と，類似の 3 つの性質との関係を解明した．これらの成果は，施設配置問題における架空名義
操作に関する初めての理論的な考察であり，グラフや平面としてモデル化される一般の施設配置問題を議論する
際の基盤となる．特に第 3 章で与えた特徴付けは，架空
名義操作不可能な配置メカニズムの設計にも応用可能であり，匿名性を利用した不正行為に対する頑健性が求められるネットワーク上での意思決定理論の研究の進展に貢献すると考えられる．
以下に今後の課題を述べる．本論文で与えた特徴付け
は，メカニズムに対して厳しい条件を提示しており，更に第 4 章で示した最悪時の近似率は，社会的コストと最大コストのいずれにおいても，パレート効率性を仮定する範囲で最悪の値である．これらの結果は，決定性配置
メカニズムにおける架空名義操作不可能性の達成の困難さを示している．この問題に対する一つの解決方法は，非決定性（確率的）配置メカニズムの導入である．例
えば文献 [7] において，最大コストの最悪時の近似率が3/2 となる戦略的操作不可能な非決定性配置メカニズムが提案されており，戦略的操作不可能な決定性配置メカ

ニズムが達成可能な最悪時の近似率 2 を更新している．
架空名義操作不可能な配置メカニズムに関しても，非決定性メカニズムを導入することで，達成可能な近似率を改善できると考えている．

謝辞
本研究の遂行にあたり，日本学術振興会科学研究費補助金特別研究員奨励費の助成を受けました．ここに深く感謝致します．また，有益なコメントを下さった情報処
理学会アルゴリズム研究会の 2 名の査読者にも感謝致
します．

参考文献
[1] Yann Chevaleyre, Ulle Endriss, Jérôme Lang, andNicolas Maudet. A short introduction to computational social choice. In the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp. 51–69, 2007.
[2] Stephen Ching and William Thomson. Populationmonotonic solutions in public good economies withsingle- peaked preferences. RCER Working Papers
362, 1993.
[3] Vincent Conitzer. Anonymity-proof voting rules. In
the Fourth International Workshop on Internet andNetwork Economics (WINE), pp. 295–306, 2008.
[4] 栗田治. 施設配置モデル―配置問題と社会の公平さ― . オペレーションズ・リサーチ, 42(12):782–784,
1997.
[5] Harvé Moulin. On strategy-proofness and single
peakedness. Public Choice, 35(4):437–455, 1980.
[6] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory.
Cambridge University Press, 2007.
[7] Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. In
the Tenth ACM Conference on Electronic Commerce(EC), pp. 177–186, 2009.
[8] 坂井豊貴, 藤中裕二, 若山琢磨. メカニズムデザイ
ン―資源配分制度の設計とインセンティブ . ミネル
ヴァ書房, 2008.
[9] James Schummer and Rakesh V. Vohra. Mechanism
design without money. In [6], chapter 10. 2007.
[10] 東藤大樹, 岩崎敦, 横尾真, 櫻井祐子. 架空名義操
作不可能な組合せオークションの割当規則の特性.
電 子情 報 通信 学会 論 文誌, J92-D(11):1890–1901,
2009.
[11] 安田洋祐. 学校選択制のデザイン―ゲーム理論アプ
ローチ. NTT 出版, 2010.
[12] 横尾真, 櫻井祐子, 松原繁夫. 架空名義入札に頑健な組合せオークションプロトコル. 情報処理学会論文誌, 43(6):1814–1824, 2002.
[13] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. The effect of false-name bids in combinatorial
auctions: New fraud in internet auctions. Games andEconomic Behavior, 46(1):174–188, 2004.

46（第1分冊）