181

数理解析研究所講究録
第1148巻 2000年 181-186

正則グラフ上の単純投票に対する平均合意時間
福岡教育大学 教育中田 寿夫(Toshio NAKATA)

概要

頂点の正則グラフについて、 確率的分散合意形成問題を考える。 そのときの単純投票についての平均合意時間は \Omega(n^{2}) かつ O(n^{3}) であり、 特に n ‐完全グラフであれば (\log 2+o(1))n^{2} であることを古典的な破産の問題
nを応用、 拡張して証明した。

1

はじめに
分散合意形成問題に対して、 有限無向グラフの上での局所的な投票による決定は有効な手段であり、 Peleg らによって色々と議論されている ([4] はそのサーベイである)。 局所多数決とは簡単に言うと次の通りである : 「グラフについて各頂点に0,1を配置し、 各頂点の “近傍” の頂点が参加する多数決で (引き分けのときの処理も含めて)その頂点の値が 0 に忌るか1になるかをある方法を用いて決定する」。 それを各頂点ごとに同期的/非同期的に行い、 全体の状態 (大域状態) を変化させる。 それを繰り返して、 各頂点の値がすべて 0 ( 0 状態という) またはすべて1(1状態という) にまとめることを目標とする。 全体の意見が合意されたというのは大域状態が 0 状態または1状態になることを言う。

方、 上記の局所多数決は決定的な多数決であれば有限集合上での決定的な力学系となり、 最終的には周期的になることが容易に分かり、 得られた周期から、 何らかの意味で” 合意” を決定づけるのは困難であると思われる。

そこで、 Hassin&Peleg [2] や中田、 今林、 山下 [3] によって確率的な多数決についての考察が行われた。 それによると、 適当な条件をみたすときには、 確率的局所多数決を有限回繰り返せば、 確率1で合意されることがわかっている。

[2] では、 大域状態を変化させる際に、 すべての頂点で同時に確率的な多数決を行なう同期的なものを扱っている。 —方、 [3] では、 (細かな設定の説明は省略するが)k‐投票についての考察が行われている。 すなわち、 k‐投票とは全体の頂点の中から k 個の頂点をランダムに選びだし、 そこで k 個同時に局所的な確率的多数決を行い、または1の意見を確率的に更新させる。 当然、k=n0のときには、 [2] で扱った同期的投票となるので、 自然な拡張ということになる。

[3] では、 有向で重みのついたグラフについて、\bulletどのような条件の下で、 確率的局所多数決を繰り返せば最終的に合意される (狭義の周期になったりしない)確率が1となるか ?
\bullet

そのとき、0状態 (resp. 1状態) のどちらに合意されるか初期状態に依存した確率で計算されるが、 その確率の具体的な形はどうなっているか ?という問いに応えるものであった。 これについいて、 最終的に 0 状態、 1状態におちこむ確率が初期状態だけで判断できたわけであるが、 合意されるまでの時間 (合意時間 (または吸収時間)) の方はあまり手がつけられておらず、 平均合意時間を与える問題は、 Hassin, Peleg [2] がグラフ上のランダムウォークの手法を使って、 殊な場合の多数決の方法で (ここで扱うものとは少し異なった多数決の方法で) 平均合意時間は可逆マルコフ連鎖で扱える範囲では、 O(M\log n) であることを示した1。ただし、 M は最大平均出会い時間 (meeting time) とよばれるものである。 最大平均出会い時間自身の評価は、 Tetali, Winkler [5] により (これまた) 特殊な場合に限り、 o(n^{3}\log n)であることが知られているが、 一般的には詳しく調べられているわけではない。 また、 平均合意時間の評価可能なものをグラフの性質ではなく、 そこから導入されるマルコフ連鎖の条件を用いて議論するのも少し不満が残る。
そこで、 この小文では、 上記の未解決問題の—部を解決すべく特別な場合すなわち、 正則グラフ (重みのない無向グラフ) での1‐投票 (単純投票という) を繰り返し行ったときの合意時間の平均値をギャンブラーの破産の問題[1] を応用、 拡張してその評価を行う。 さらに、 完全グラフの場合は平均合意時間を明示的に求める。

1上記の結果のみは [2] に書いているが` 証明等は full paper に書くということなのでしばらく待つ必要がある (Peleg に問いあわせたところ、 1999年10月現在は執筆中だそうである)。

1822問題設定
G=(V, E) を n 個の頂点で各頂点の次数が r である単純 r ‐正則グラフとし、G 上での単純投票を考える。問題設定は以下のとおりである : 各頂点に \{0,1\} の値を決め (局所状態) 、それらで大域状態 \xi=(\xi(v))_{t\in V}.\in f^{o,1}\}^{V}= 三が決まる。 そこで、 単純投票とは以下のような手続きであり、 それをすべての頂点が合意するまで繰り返す。

個の頂点の中から、 頂点 v\in V を1つだけランダムにとりだし (一様分布に従う)\bulletn\bullet

その頂点について局所的な確率的多数決を行う。 すなわち、 選ばれた頂点 v について、 自分自身を含んだ近傍 \Gamma(v)=\{w\in V : (w.v)\in E\}\cup\{v\} の要素の数は r+1 であるが、 その中の 0 の頂点の数力∼ 個とす

ると、s/(r+1) の確率でその頂点は 0 に更新され、1-s/(r+1) の確率で1に更新される。

ここで、 [3, Theorem 2] により、 確率1で有限回で合意されることがわかっている。 [3] では上記の単純投票から決まるマルコフ連鎖を導入してその解析を行った。 その三値確率過程であるマルコフ連鎖を \{X_{t} : t\in N\} とする。 ただし、N は非負整数であり、このマルコフ連鎖は初期分布が P_{\xi}\{X_{0}=\xi\}=1 である確率空間 (_{-}^{-N}-, \mathcal{F}, p_{\xi})の上のものを考える。

問題としては、 \xi\in 三 \backslash \{0,1\} という状態から出発するとして、 合意時間を\tau=\inf\{t\in N : X_{t}\in\{0,1\}\} とおいたときに E_{\xi}[\tau] を求めよ (評価せよ) というものである。 ただし、 E_{\xi} [] は上記の確率空間での (初期状態が \xi であるときの) 期待値である。 これは、 一般的に [3, Theorem 7] の形の差分方程式を解けば明示的に求まるわけであるが、 2^{n}-2 元の連立—次方程式を解く必要があり、 その計算量は O(h^{3}) ただし h=2^{n}-2 であり、 困難を極めている。 次のセクションでは扱うグラフを正則グラフに限定して、 グラフのある意味での” 対称性” から推移行列を簡素化することにより、 解 (平均合意時間) の評価を行う。

3‘正則グラフでの平均合意時間の評価\xi\in 三について\sim\sigma(\xi)=|\{v\in V : \xi(v)=1\}| とする。 \xi, \eta\in 三について、 \xi\sim\eta を \sigma(\xi)=\sigma(\eta) と定義すると、は三の上の同値関係になり、 商空間を三/∼ =\{_{-0,,n}^{-\ldots\underline{=}}-\}\simeq\{0, \cdots, n\} とする。
—方、 [3, Theorem 6] により、 正則グラフの性質を利用するとE_{\xi}[\sigma(x_{t})]=\sigma(\xi)(1)

t\in Nがなりたっている。 それにより、 正則グラフ上での単純投票はその共役類を新たな” 状態” とみたてた” 単純ランダムウォーク” として捉えることを考えたい。 すなわち、 単純投票であるので、 1回の単純投票により、 意見が変化する数は高々 1つであるので、 島上の要素は乙‐1 、 亀、 \Xi_{i+1} のいずれかに推移して、 (1) により 「島上の要素が亀+1にうつる確率」 と \lceil_{\cup i}- 上の要素が亀‐1にうつる確率」 は等しいことがわかる (ただし、 i=1, \cdots, n-1とする)。 すなわち、 以下のことがいえる。
補題31 正則グラフ上の単純投票について以下がなりたつ :P_{\xi}\{\sigma(X_{t+1})=\cdot\sigma(X_{t})+1\}=P_{\xi}\{\sigma(x_{t+1})=\sigma (x_{t})-1\}
さらに、t\in N(2)

i\in\{1, \cdots, n-1\} とし、 ある t\in N について、 X_{t}=\xi_{1}\in 三とすると、\xi'\in^{- }\sum_{-j+1}p(\xi 1, \xi^{;})=\sum_{\xi"\in-}p(\xi- _{i-}11, \xi")(3)

ただし、p(\eta_{1}, \eta_{2})=^{p_{\xi\{x_{t}}}+1=\xi_{2}|X_{t}=\xi 1\},\eta_{1}, \eta_{2}\in\Xi,t\in Nとするマルコフ連鎖の (定常な (すなわち時間に依存しない)) 推移確率をあらわす。
しかし、 上記のように単純に1の個数でマルコフ連鎖としての状態空間を決定することはできない2。なぜならば島上の要素要素の選びかたによって ( i 個の1の配置の方法によって) 、 自分自身以外に推移する確率が異なる。
すなわち、 自分自身の” 状態” に留まる (足踏みする) 確率が異なる。
2個数で全て分類できるのは次のセクションの完全グラフの場合に限られる。

183例3.1 5‐サイクルグラフ (5頂点からなるループで2‐正則グラフとなる) について、 \xi=(0,0,0,1,1), \eta=(0,1,0,1,0) とすると、 \xi, \eta\in--2- である。 すなわち、 \sigma(\xi)=\sigma(\eta)=2 である。 ここで、 直接計算すると、\sum_{\xi'\in_{-}^{-_{1} -}p(\xi.\xi\prime)=\frac{2}{15} \sum_{\xi'\in_{-}^{- _{2} p(\xi, \xi')=\frac{1 }{15} \sum_{\xi'\in_{- }^{-}s p(\xi, \xi^{;})=\frac{2}{15}.\cdot\eta'\in_{-}^{- }\sum_{1}p(\eta, \eta')=\frac{4}{15} \sum_{\eta\in- }-2p(\eta, \eta')=\frac{7}{15} \sum_{\eta\in_{- }^{-}3}p(\eta, \eta')=\frac{4}{15},,.となり、 1の数が同じでも配置のしかたで推移する確率が異なる。

\xi\eta

図1: 5頂点の2正則グラフの推移の様子

そこで、 足踏みの確率の最大値、 最小値を評価し、 それにより全体の合意時間を評価するのが、 平均合意時間の評価の鍵になる。

補題32r‐正則グラフの単純投票について、 個数の変化が無い確率が最も低い状態、 最も高い状態は以下のように評価される :ただし、- =-\wedge-- \backslash \{0,1\} 。

\frac{1}{r+1}\leq p(\eta, \eta)\leq 1-\frac{2r}{n(r+1)} , for \eta\in- =-\wedge-- \backslash \{o, 1\} .

(4)[証明のアウトライン] 単純投票により各眞点を選ぶ確率は 1/n であり、 各頂点の近傍に含まれる頂点の個数は r‐正則グラフなのでr+1 個ある。

状態 \eta において自分自身に留まる確率は\frac{1}{n}\cdot\frac{1}{r+1}\sum_{v\in V}|\{w\in\Gamma(v) : \eta(v)=\eta(w)\} |(5)である。 このとき、 |\{w\in\Gamma(v) : \eta(v)=\eta(w)\}|\geq 1 であるのは明らかであり、 式 (5) の最大値は、 1つの頂点を除いて全て同色になるときである。 すなわち、\frac{1}{n}\cdot\frac{1}{r+1}\sum_{v\in V}1\leq p(\eta, \eta)\leq\frac{1}{n} \cdot\frac{1}{r+1}\{(n-r-1)(r+1)+r+1\}2 \eta\in- -\wedge,.

これを計算すると (4) をえる。 I

また、 一様な足踏みをするときのランダムウォークについての平均合意時間については以下のことが言える。

184

補題33状態空間が \{0, \cdots, n\} であり、 固定された 0\leq c<1 について、 推移確率 q(i, j), i,j\in\{0. \cdot\cdot, , n\} が次のように与えられた図2のようなランダムウォ

クを考える ( \{0, n\} は吸収壁である) :q( \ell, \ell-1)=\frac{1-c}{2} q( \ell, \ell+1)=\frac{1-c}{2}q(\ell, \ell)=c ,q(o, o)=1-,,q(n, n)=1\ell=1, \cdots, n-1,,

このとき、 \ell からスタートしたときの吸収壁 \{0, n\} への平均合意時間勿 =\mathcal{Z}\ell(C) は以下のように与えられる。

\cup\perp

1‐11n‐l1+1u

図2: 吸収壁ランダムウォ一ク

z \ell=\frac{1}{1-c}\ell(n-\ell) ,\ell=0, \cdot\prime\cdot, n .

(6)

注意3.1 c=0 のときは普通のギャンブラーの破産の問題であり [1]_{、} 自然な拡張となっている。 補題33はギャンブルに—様な引き分けをつけたときの破産するまでの平均時間を計算していることになる。

[証明のアウトライン] このランダムウォ—クについて \ell からスタートしたときの \{0, n\} への平均合意時間 Z\ell はZ \ell=\frac{1-c}{2}Zp-1+\frac{1-c}{2}Z_{\ell}+1+cz_{\ell}+1,z_{0}=z_{n}=0をみたす唯— の解である。 (6) は上記の非斉次差分方程式をみたすので証明が終わる。 1式 (6) より、 任意の \ell について、 Z\ell(C) は 0\leq c<1 による単調増加関数である。 この補題33を用いて次のことが言える。

定理31 頂点をもつ ‐正則グラフでの \sigma(\xi)=\ell\in\{1, \cdots, n-1\} から出発したときの単純投票による平均合意
時間 (平均吸収時間) に対して以下のような評価がえられる :rn(1+ \frac{1}{r})l(n-\ell)\leq E_{\xi}[\tau]\leq\frac{n\ell(r+1)(n-\ell)}{2r}(7)特に平均合意時間は \Omega_{\lrcorner}(n^{2}) かつ O(n^{3}) である。

[証明のアウトライン]\sigma(\xi_{1})=\ell をみたす状態 \xi_{1} を考える。

r‐正則グラフでの単純投票のときには、 補題31より、 次のステップで1の個数が P+1 になる確率と \ell+1 になる確率は等しい。 それゆえ、 足踏みをする時間を考慮しなければ普通の破産の問題と等しくなる。 —方、 足踏みの確率が—様に のときには、 各状態について足踏みから脱出する時間は、 c の幾何分布に従い、 補題33より、 平均合意時間は (6) で与えられ、 に関する単調関数であった。 そのことにより、 平均合意時間は各状態を足踏みする確率の評価に帰着されることになる。 さらに、足踏みの確率の最大、 最小は補題32により与えられている。 よって、 \sigma(\xi)=\ell で与えられた状態 \xi から出発しccたときの平均合意時間は以下のようになる :\frac{1}{1-1/(r+1)}\ell(n-l)\leq E_{\xi}[\tau]\leq\frac{n(r+1)}{2r}\ell(n- \ell)
よって (7) をえる。

I

185

4

完全グラフでの平均合意時間
このセクションでは完全グラフでの平均合意時間を考える。 完全グラフのときには、 例31のような事は起きずに、 配置によらず1の個数のみで推移確率が決定される。 これにより、 これまで \xi から出発したのときの確率、期待値を P_{\xi}, E_{\xi} と書いていたが、 \sigma(\xi)=\ell をみたすときには、 それぞれ p_{p} , E_{\ell} と記す。
このとき、 合意時間をあらわす差分方程式が解かれ平均合意時間を明示的に求める。

命題41完全グラフ I\zeta_{n} の単純投票に対するマルコフ連鎖は、 その上の推移確率は次のようになる。

p(l, \ell)=a_{p}^{2}+b_{p}^{2}p(o, o)=1
ただし、,p(^{\ell,\ell}-1)=a_{\ell}b\ell ,,p(n, n)=1p(\ell, \ell+1)=a_{\ell}b_{\ell} ,\ell=1, \cdots, n-1,

ap=\ell/n, b\ell=(n-\ell)/n[証明のアウトライン]\ell 個の1とn-\ell個の 0 が配置されていて、 単純投票より、n頂点から1つ選ばれる。

(i) (\ellarrow\ell) 惚個の中から選ばれそれが変化しない。 (i- 1) 」 または「n -\ell 個の中から選ばれそれが変化しない。
(i‐2) J(ii) (Parrow l-1)

r\ell 個の中から選ばれそれが 0 に変化する。」(iii) (larrow\ell+1)r_{n-\ell} 個の中から選ばれそれが1に変化する。」(i) の確率を計算すると、 (i‐1) は (\ell/n)^{2} で (i‐2) は ((n-\ell)/n)^{2} であり、 これらは排反事象の確率であるので、p(\ell, \ell)=a_{\ell}^{2}+b_{\ell}^{2} をえる。 他のものも同様な方法で得ることができる。 I
すなわち、 状態の遷移の様子は以図2のようになるが、 補題33と異なるところは、 足踏みする確率が状態によって異なることである。 命題41を用いて以下を得る。
補題41 P=0, \cdots, n に対して.

Xpを \sigma(\xi)=\ell をみたす \xi からはじめて、0 に吸収される確率. yp を \sigma(\xi)=\ell をみたす .\xi からはじめて、 \{0,1\} に吸収される平均合意時間とすると、 以下の差分方程式が成りたち、 それぞれ解は—意的に存在する。
(\ell=1, \cdots, n-1) ,x_{0}=1, x_{n}=0(8)y_{p+1}-2y \ell+y\ell_{-}1+\frac{n^{2} {\ell(n-\ell)}=0 (\ell=1, \cdots, n-1) ,y_{0}=0, y_{n}=0(9)

Xp+1-2xp+X\ell_{-}1=0(8) は容易に解けて、 解は Xp=(n-\ell)/n, \ell=0,と求まる [3]。しかし、 一般の条件の下での非斉次型の差分方程式を解くのは困難であったが、 条件を強くして (9) ときに限定したことにより、 以下のように解くことがで\cdots, nきる。

定理41n‐完全グラフ上での単純投票の合意時間は、 \sigma(\xi)=\ell から出発したときに、 ( \ell 個 (または n-\ell 個) の意見が混ざっていた場合) 、

E_{n-p}[\tau]=E_{\el }[\mathcal{T}]=n\sum_{i=1}\el n\sum_{ik=}-i\frac{1}{k}である。 オーダとしては以下のとおり :for \ell=0, \cdots, \lfloor n/2\rfloor(10)\max\{E_{\xi}[\tau] : \sigma(\xi)=\ell, \ell=0, \cdots, n\}=(\log 2+o(1))n^{2}[証明のアウトライン] まず、 対称性の条件より、 対称性より 防 =y_{n-i}, i=0, \cdots, であることに注意する。
a\ell=y\ell+1-yp とおき、 (9) の差分方程式を考えると
ap-a \ell_{-1}+\frac{n^{2}}{p(n-\ell)}=0 である。 これより —般式は次の形で書\circ
a_{n-l}ける-a_{0}=- \sum_{k=1}^{n-1}\frac{n^{2} {k(n-k)} さらに. (9) の境界条件より a_{0}=y_{1}-y0=y_{1} , a_{n-1}=y_{n}-yn-1=-y_{n-1}nであるので、a_{n-1}-a_{0}=-2y_{1} であり、y_{1}= \frac{n^{2} {2}\sum_{k=1}^{n}\frac{1}{k(n-k)}-1=n(\frac{1}{1}+\cdots+ \frac{1}{n-1})=nH_{n-1}186となる。 一般的に、

a_{n-\ell\ell}-a-1=-_{L_{k},k=\ell}\overline{(n-k)}
であり 、a_{n-}p-a\ell_{-}1=(y_{n-\ell+}1-y_{n-\ell})-(y\ell-y_{P}-1)=2y\ell_{-}1- 2y\ell であることより.

y_{\el }-y_{l}-1= \frac{7l^{2} {2}\sum_{k=^{p} ^{\el }\frac{1}{k(n-k)}nであることがわかる。 よって、 y_{0}=0 であることを用いて

y_{l}=\frac{n^{2} {2}\sum_{j=1}^{p}n.\sum_{\kap a=j}\frac{1}{k(n-k)}-j= \frac{n}{2}\sum_{j=1}^{\el}n-\sum_{=kj}^{j}(\frac{1}{k}+\frac{1}{n-k})= 7l\sum_{j=1}^{\el}\sum\frac{1}{k}n-k=jJとなり、 (10) を得る。 簡単のためにnは偶数として、m=n/2 とする。

このとき、 y_{m} が最大となるのがわかる

ので、 積分を用いて評価すると(/1 \backslash 1

Qr .

/2m-1

1 \backslash 1

4m^{2} \{\log(\frac{2m}{m+1}+\frac{1}{m})\}<y_{m}<4m^{2}\{ \log(\frac{2m-1}{m+1}+\frac{1}{m})\}-2mとなり y_{m}=(4\log 2+o(1))m^{2} であるので y_{n/2}=(\log 2+o(1))n^{2} がわかる。 15

おわりに

ここでは、 正則グラフ、 完全グラフでの1‐投票 (単純投票という) を繰り返し行ったときの合意時間の平均値をギャンブラーの破産の問題 [1] を応用して明示的に求めた。 もし、 1投票で確率的多数決を行わず、 個の頂点から1つとり出して、 (確率1で)n 個の頂点の中で多い方の意見に自分の意見と採用することとすれば、 合意するま
nでの時間の問題は、 完全グラフのカバータイム問題とほぼ等しく、 平均合意時間は O(n\log n) となることが知られている (証明はそう難しくない)。
今後の課題としては、. 正則グラフとは限らず、 一般のグラフや重みつき有向グラフの場合。
. k‐投票のときの議論。

. 合意時間の平均値だけでなく、 分布について。

やその組み併せを考えてそれらを解析することが考えられるが、 今のところは目覚しい結果には至っていない。

参考文献[1] W. Feller, “An Introduction to Probability Theory and its Applications Vol. I (3rd ed.), ” New York:John Wiley&Sons, 1950.

[2] Y. Hassin and D. Peleg; Distributed Probabilistic Polling and Applications to Proportionate Agreement,
ICALP99, Lecture Notes in Computer Science, vol. 1644, 402‐411.

[3] T. Nakata, H. Imahayashi and M. Yamashita; Repetitive Probabilistic Local Majority Polling for theAgreement Problem on Weighted Directed Graphs, To appear Networks.

[4] D. Peleg; Local Majority Voting, Small Coalitions and Controlling Monopolies in Graphs: A Review,Technical Report (1996)

http: //www . wisdom. weizmann. ac . il/Papers/trs/cs96-12/abStract . html.

[5] P. Tetali and P.Winkler; Simultaneous reversible markov chains, Combinatorics Paul Erdós is Eighty(Vol. 1), 1993, pp.433‐451.