日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-8

制御可能な不確実性を含む Stochastic Matching の確率的挙動の最適化
050007541.

日本電信電話株式会社*引間友也

HIKIMA Yuya

日本電信電話株式会社

赤木 康紀

AKAGI Yasunori

日本電信電話株式会社

金 秀明

KIM Hideaki

日本電信電話株式会社

幸島 匡宏

KOHJIMA Masahiro

日本電信電話株式会社

倉島 健

KURASHIMA Takeshi

日本電信電話株式会社

戸田 浩之

TODA Hiroyuki

はじめに各ノード𝑢 ∈ 𝑈 に不確実性を含むグラフにおいて最適なマッチングを(i) ついて，𝑥 を決定

𝑢1

応用をもつため，数多くなされてきた．これらの研究で決定:

各(u,v)の重み: 𝑣1
𝑤𝑢𝑣 + 𝑥𝑢

𝑣2

𝑣1

発見する研究は，広告の割当 [1] や腎臓交換 [2] などのは，グラフに含まれる不確実性に関するパラメータは(ii) マッチングを決定

𝑢𝑢2𝑢3

𝒙𝒖𝟏 𝒙𝒖𝟐 𝒙𝒖𝟑

1 − 𝑝𝑢 (𝑥𝑢 )の確率で 𝑢 は除去．

𝑢1𝑣2𝑢2

決定𝑢3

除去された
ノード所与のものとして与えられることが多い．例えば，広告割当では，web 閲覧者に該当するノードは所与の確

図 1: マッチングのプロセス率分布から次々と生じるものとして扱われる．しかしながら，多くの応用では不確実性のパラメータは制御

但し， δ(ξ) はノード ξ に隣接するノード集合を指す．

可能である．本研究では，この設定のもと，得られる

また，au ∈ {0, 1} は au = 0 のとき参加者 u が市場にマッチングの重みの期待値を最大化する新しい最適化

不参加，au = 1 のとき参加者 u が市場に参加したこと問題を定式化し，その近似解法を与える．提案する最を表す変数である．決定変数 zuv ∈ {0, 1} は zuv = 1 の適化問題と解法は，クラウドソーシングや交通サービとき，(u, v) をマッチングすることを表す．

スにおける価格最適化など，複数の重要な応用をもつ．

2.

上記のような状況設定は，クラウドソーシングなど
において，各ワーカの賃金（xu ）を決定したうえで，そ最適化問題の定式化

本研究では，次のような状況を考える (図 1)．参加者の集合を U ，資源の集合を V とし，それらをノードとしてもつ重み付き二部グラフ G = (U, V, E) を考えの賃金を承諾したワーカ ({u ∈ U | au = 1}) に対してタスク (v) を割り当てる場合などが当てはまる．
このとき，本研究で取り組む最適化問題は以下である．

る．ここで，(u, v) ∈ E であるとき，u と v はマッチン(P)グ可能である．また，wuv を枝 (u, v) の重みであると

maxx∈R|U |

Ea∼D(x) [ max f (x, z)]z∈Z(a)

する．これらの設定の下，サービス提供者は各参加者

但し，f (x, z) と Z(a) は，それぞれ (Psub ) の目的関に対して xu を設定する．それに対して，各参加者 u は数値と実行可能領域である．D(x) は {0, 1}|U | 上の確率 pu (xu ) で市場にそのまま参加し，1 − pu (xu ) の確率で市場から去る．グラフ G′ = (U ′ , V, E ′ ) を，去った確率分布であり，その確率質量関数は} Pr(a | x) ={∏au(1−au )である．この最pu (xu ) (1 − pu (xu ))参加者に該当するノードを取り除いた二部グラフであ

適化問題は，最終的に得られるマッチングの重みの期るとする．このとき，サービス提供者は以下の最適化待値を x について最大化するものである．

問題を解くことで，マッチング M ⊂ E ′ を決定し，各(u, v) ∈ M について利益 wuv + xu を得る．
(Psub )

maxzs.t.

∑(u,v)∈E∑v∈δ(u)(wuv + xu ) · zuv

zuv ≤ au ,∀u ∈ Uzuv ≤ 1,∀v ∈ V∑u∈δ(v)zuv ∈ {0, 1},∀(u, v) ∈ Eu∈U(P) は応用上重要であるものの，以下の理由で効率的に解くことが難しい．

(i) 確率により生起する承諾結果 a の場合の数が 2n 個あり，目的関数値や勾配を正確に計算するには 2n 個の重み付き二部グラフマッチングを解く必要がある．

(ii) 応用上，関数 pu (x) として非凸な関数を用いることが多く，その場合目的関数も非凸になってしまう．

3.

関数 pu に対する仮定

このとき，以下の定理 2 が成り立つ．

仮定 1. pu (x) は x に関して全単射かつ単調減少であ

仮定 1 が成り立つとする. (PA′ ) の最適解を∑∗z とし，各 u ∈ U について x∗u := p−1u (v∈δ(u) zuv )すなわち， −p′u (x)/pu (x) が x に関して単調非減少で定理 2 より，(PA′ ) を解けば (PA) の解が求まる．

ある．さらに，pu (x) = 0 or limx→∞ pu (x) = 0 となる
上記の仮定は，機械学習でよく用いられる確率分布

ここで，新たな添字 s と t を導入する. 各 u ∈ U に∑ついて，zsu := v∈δ(u) zuv とし，各 v ∈ V について，∑zvt := u∈δ(v) zuv とする．さらに，スラック変数 zst をである正規分布や指数分布の相補累積分布関数を含む導入し，n := min{|U |, |V |} とする．このとき，(PA′ )ような緩い仮定である．

は以下のように書ける．

本研究では以下の仮定を関数 pu に対しておく．

定理 2∗∗∗
る．また，Monotone hazard rate function [3] である． とする．このとき，(x , z ) は (PA) の最適解である．

x が存在する.

4.

提案手法

(FP)

minz

以下の最適化問題の最適値を fˆ(x) とする．
∑maxzs.t.

∑(u,v)∈Ev∈δ(u)∑u∈δ(v)s.t.

(xu + wuv ) · zuv

zuv ≤ pu (xu ),zuv ≤ 1,0 ≤ zuv ≤ 1,

ここで，(P) の目的関数 Ea∼D [maxz∈Z(a) f (x, z)] を
ˆf (x) に置き換えると以下の最適化問題となる．

s.t.

∑v∈δ(u)u∈δ(v)zuv = 0,∀u ∈ Uzuv − zvt = 0,∀v ∈ Vv∈δ(u)∀u ∈ U0 ≤ zvt ≤ 1,∀v ∈ V0 ≤ zuv ≤ 1,∀(u, v) ∈ E0 ≤ zst ≤ n

これは U ∪ V ∪ {s, t} をノードとしてもつ最小費用流問題であり，仮定 1 の下では最小凸費用流問題となる．

(xu + wuv ) · zuv

よって既存解法 [4, 5] を用いて解くことができる．

zuv ≤ pu (xu ),5.

(u,v)∈E∑zvt + zst = nv∈V∑zsu ∈ Su ,1/3 · fˆ(x) ≤ Ea∼D [maxz∈Z(a) f (x, z)] ≤ fˆ(x)x,z∑u∈δ(v)定理 1 任意の x について，以下が成り立つ．

maxzsu + zst = n,∑∀v ∈ Vwuv · zuv(u,v)∈Ezsu −∀u ∈ U

このとき，以下の定理が成り立つ．

(PA)u∈U∑∑−p−1u (zsu ) · zsu −u∈U∀(u, v) ∈ E∑∑zuv ≤ 1,0 ≤ zuv ≤ 1,∀u ∈ U

おわりに

本研究では，不確実性のパラメータを制御すること∀v ∈ Vができる設定のもと，得られるマッチングの重みの期∀(u, v) ∈ E

待値を最大化する新しい最適化問題を定式化した上で，

x ∈ R|U |その 13 -近似解法を与えた．定理の証明や数値実験の結(PA) の最適解は定理 1 より (P) の 13 -近似解となる．但果等については，当日の発表において説明を行う．

し，(PA) には制約に非凸関数 pu (xu ) が含まれており，参考文献

内点法などを用いて直接解くことはできない．
そこで，(PA) を仮定 1 の下で最小凸費用流問題に帰着することを考える．以下の最適化問題を与える．
(PA′ ) maxzs.t.

∑p−1uu∈U∑( ∑v∈δ(u)zuv) ∑v∈δ(u)zuv +∑wuv zuv(u,v)∈Ezuv ∈ Su , ∀u ∈ Uv∈δ(u)∑zuv ≤ 1, ∀v ∈ Vu∈δ(v)0 ≤ zuv ≤ 1,∀(u, v) ∈ E

但し，Su は pu の値域である．この最適化問題は (PA)∑の決定変数 x を，xu := p−1u (v∈δ(u) zuv ) の等式によって消去したものである．

[1] Aranyak Mehta. Online matching and ad allocation. Theoretical Computer Science, Vol. 8, No. 4, p. 265–368, 2012.
[2] Ning Chen, Nicole Immorlica, Anna R Karlin, Mohammad
Mahdian, and Atri Rudra. Approximating matches madein heaven. In ICALP, pp. 266–278, 2009.
[3] Richard E Barlow, Albert W Marshall, and Frank Proschan.
Properties of probability distributions with monotone hazard rate. The Annals of Mathematical Statistics, Vol. 34,No. 2, pp. 375–389, 1963.
[4] Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network Flows: Theory, Algorithms, and Applications.
Prentice-Hall, 1993.
[5] László A Végh. A strongly polynomial algorithm for a classof minimum-cost flow problems with separable convex objectives. SIAM Journal on Computing, Vol. 45, No. 5, pp.
1729–1761, 2016.