ロジスティクスにおける資源配分問題に関するゲーム理論的アプローチ
毛利 裕昭，渡辺 隆裕
近年，ゲーム理論は経済学における重要なツールとなったが，ロジスティクスやORにおいてその応用が進んでいるとは言い難い．しかし，SCMをはじめとして1企業だけではない複数企業におけるオペレーション全体の最適化が必要とされる今，費用分担や利益配分などの利害調整メカニズムや，戦略的行動を考慮した市場メカニズムなどが，ソフ
トウエアに実装される必要性が出てきており，ゲーム理論の工学的応用の可敵性は高まってきている．単純なモデルを用いて，いくつかの例を示し，ゲーム理論のロジスティクスに対する多様な接近法を解説する．

キーワード：ゲーム理論，ロジスティクス，費用分担，オークション………lll………l…l川Illlllllll州l…………lllllll…………l川Illllll………l川Illlllll川Il川Il………lllll………lllll州Illl州Illll………l川Illlll川Illlll川Il………l川Illlllll川Ill………l……ll川……州川…

ているのに対し，ORでは，整合的でなくてもいいか

1．はじめにロジスティクスは，生産・流通・販売の一連の流れ

こにある問題を解決する」ことが重視されるからではを最適化することを目標にしているといわれる．生産ないだろうか．筆者はOR学会の様々な研究会でゲーや流通に対する意思決定が，一つの企業で統括されてム理論が活躍できる場を探してきたが，そこでは「現いた時代は確かにそれだけであっただろう．しかし現実の人間行動や利害調整は，大変複雑であり，ゲーム

在は，その流れに関係する企業が複数となり，利害調理論のような単純な理論では表せない」「人間の行動

整や競争・協力などの要素を含んだ「最適化」が求めを理解するにはおもしろいが，技術として適用できるられている．

●

ら「費用が削減できる」「皆が納得する」など「今そ一つの主体の意思決定は最適化であるが，ものではない」といった問題が実務家から提起されて複数の主体が最適化を行ったとき「どうなるのか」

きた．本機関誌7月号の今野会長の論稿［4］からも，「どうあるべきか」は，もはや最適化の問題ではなくそれは感じられる．

その先の問題である．ゲーム理論は，複数主体の意思ゲーム理論の研究者間でもこの課題は意識されてお決定は1主体のそれに比べ，ずっと複雑な問題である

り，2000年に開催された第1回ゲーム理論国際学会と認識し，その相互作用を研究する学問である．この（GAMES2000）では，会長のAumann氏が「次の意味において，資源管理やロジスティクスに対して，ゲーム理論の課題はEngineeringであり，これからそろそろゲーム理論に注目が集まってもおかしくはな

は『現象の描写』から『システムの設計・計画に役立しヽつこと』が重要課題である」と講演している．

しかしながら，ロジスティクス，いやOR全体におそうかといって，展望は悲観的ではない．ロジステ

いてゲーム理論の応用は進んでいるとは言い難い．近ィクスにおいてゲーム理論が必要とされる機運は近年，年，ゲーム理論が経済学における重要なツールとなり，高まっているように思える．一つの要因は，先に述べ市場の理論であるミクロ経済学がゲーム理論中心に大たように近年のロジスティクスが，SCMをはじめときく塗り替わったにもかかわらず，である．この理由

して1企業だけではない複数企業におけるオペレーシ

は理論経済学で「少ない原理から整合的に多くの現象

ョン全体の最適化に向かっているという点である．1

を記述できる」というゲーム理論の整合性が評価され企業では必要なかった費用配分や利益分配などの利害もうり ひろあき早稲田大学商学部〒169−8050新宿区西早稲田1−6−1
わたなべ たかひろ

調整の問題は，複数企業の統合オペレーションの中ではますます重要視される．
二つ目の要因は，このようなロジスティクスの発展

東京都立大学経済学部

を支えているのが，ITやネットワークの発達である〒192−0397 八三l三千市南大沢ト1という事実である．費用分担や利益分配などの利害調

2004年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（9）681

整は，人間が毎回交渉するのではなく，ソフトウエアの中に組み込まれ自動化されなければならない．「何が良い配分か」「良い費用の分け方は何か」がルール化され，プログラムされる必要が出てきているのだ（久保，毛利［3］）．人が顔をつき合わせて費用分担を交渉していた際には，数学的に定義された分配方法を用いて決めることは，計算の手間と参加者の納得度を考慮すれば難しいことかもしれなかった．しかし，プ
ログラムの中にあらかじめ組み込まれ自重力化されるな／コ3

らば少々複雑な計算であっても，それが単なる費用の図1企業の共同配送問題「折半」や「利益に対する比例配分」に比べ，より皆の満足度が高いような分担方法の方が望まれるであろじ配送センタに財を配送しようとしている（図1）．

う．特に，協力ゲームの解の概念は，このような皆がここで，各企業gとセンタとの距離をc∠とし，企業オ

納得できるような「公平性」や「整合性」について考とノとの距離はあとする（あ＝ぁとする）．

え抜かれた解であり，参加者が納得できる可敵性は高ここで単純化のため配送にかかる費用は距離と同じであるとし，dヱノ＜c〜＋cIノが成立するとする．実際はしヽ

要因の三つ目は，ゲーム理論の研究分野として実際

配送トラックに容量制約があり，トラックの台数も考の制度やシステムを設計する際に，机上の理論だけで慮すべき問題であるが，例として複雑になるため，容済ませるのではなく，実験やシミュレーションを組み

量制約は考えず1台のトラックですべての配送が可能

合わせて，より現実的な適用を目指すように考えよう

であるとする．

とする分野が現れてきたことである．このような傾向

各企業オは個別にセンタへ配送を行うと費用は往復

は，資源管理だけではなく，オークションのような他

で2c〜かかる．ここで3企業が共同配送を行えば，1の分野にも当てはまり，「市場設計」や「制度設計工台の配送車を巡回させることで済む．その費用を最小学」などと呼ばれてし−る（松井，渡辺［7，8］）．

化しようとするならば，この間題は巡回セールスマン

このような傾向の中で，具体的にゲーム理論からロ問題（TSP）となる．その最小値をc123とすればジスティクスや資源管理に対して，工学的観点に立っ

c123＝min（cl＋d12＋あ3＋c3，てどのような接近ができるのだろうか．ゲーム理論と一口にいっても，その範囲は広く考え方も様々である．
ゲーム理論には協力ゲームと非協力ゲームがある．非協力ゲームは意思決定主体が基本単位（プレイヤ）であり，プレイヤが合理的に行動した場合に全体が「どc2＋あ3＋d13＋c．，C3＋d13＋d12＋c2）
である．
各企業が全体の曹用を最適化すれば，その節約額〃123は〃123＝2（cl＋c2十c3）−C123

うなるか」を考える記述理論である．これに対し，協となる．しかし，共同配送の費用削減に伴う自社への力ゲームは提携（結託・グループ）を基本単位と考え，メリットが十分大きくなければ，各企業は共同化（＝「どうなるか」を考える記述的な側面だけではなく，全体の最適化）に賛成しないであろう．言い換えると「どうあるべきか」を考える規範理論としての面も持

共同配送時の自社の費用分担によっては「総論賛成，っている．これらの点をふまえ，どちらのアプローチ

各論反対」となりかねない．ここに全体の最適化ではをとるべきか考える必要がある．

ない，ゲーム理論的問題が存在するのである．

次では，単純なモデルを用いて，いくつかの例を示

全体費用を個々の企業に分担させる費用分担ルール

し，ゲーム理論のロジスティクスに対する多様な接近を考えるとき，どのような観点から考えていけばよい法を解説していきたい．

のであろうか．ポイントはいくつかある．
2．1費用分担か，節約額配分か

2．共同配送の費用分担問題

費用分担とは「総費用c123をどのように分担する

3企業の共同配送問題における費用分担問題を考えか」という捉え方であり，節約額配分とは「各企業才る．今，三つの企業（企業1，2，3）が，それぞれ同が分担するはずだった2c∫から，結節約額〃123をどの

682（10）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ように配分するか」という観点から問題を考えること

よりも大きくなっている．これでは企業1は，全体のである．一番単純な均等化（いわゆる「割り勘」）で，費用が削減されても共同配送には賛成しないであろう．

この違いを説明しよう．費用分担を均等化する均等分担では1企業の費用分担額は，c123となる・これにこのように企業の費用負担額は，企業自身の配送費
用2cどよりも小さくなければならない．費用分担ルー
ルがどんなときもこの条件を満たすとき，その専用分

対し，節約額配分における均等化である節約額均等配担ルールは個人合理性を満たすと呼ぶ．個人合理性は，

1 分では，企業才の費用分担額は2ci一丁〃123となる・

費用分担ルールが満たすべき最低の条件であるが，均均等化以外に考えられる単純な分担方法は，企業才自身が配送した場合の費用cォに比例させて費用分担をする比例分担1である．企業才の費用分担額は比例
分担では

C〜

Cl＋c2＋c3

c123となる．

等分担は個人合理性を満たさないことがある．なお，
節約額均等配分と比例分担は，個人合理性を常に満たすことを容易に確かめることができる．

2．3 提携の影響を考えるかどうか
個人合理性は「各企業の費用分担額は各企業で運ぶ

2．2 個人合理性を満たすか

費用よりも小さくなければならない」という考え方でここで，次のような数値例を考えてみよう（図2）．

あるが，「各企業」の部分を「任意の提携（企業の集cl＝20 c2＝22 c3＝45合）」に置き換えても成立することを要請するとき，

d12＝34 品3＝55（ブ13＝35

これを提携合理性と呼ぶ．再び，表1でこれを説明し最短巡回路はセンタを出発して，企業1⇒企業3⇒
企業2の順に回り，センタへ戻るルートであり，このよう．

節約額均等配分において，企業1と企業3の費用分担額の合計は102である．しかし企業1と企業3が，ときの総コストは132である．
表1は，三つの費用分担ルールに対する各企業の費

企業2を除外して2社で共同配送をした場合，2社の合計配送額は20＋35＋45で100となる．したがって，用分担額を示している．
この例では，単純な割り勘である均等分担には問題

節約額均等配分で費用を分担するならば，企業1と3があることが分かる．共同配送時に企業1が支払う雪は自分たちだけで運んだ方がよいと主張するかもしれ

用44は，企業1が自分だけで配送する場合の曹用40ない．すなわち節約額均等配分は提携合理性を満たさないのである．

3．協力ゲームによるアプローチ
このような提携の影響を考慮した分担方法を求めるのであれば，協力ゲームの解によるアプローチが有効である．本間題を協力ゲームと考える場合，先に述べた費用分担の観点から費用ゲームと見るか，節約額配分の観点から節約ゲームと定式化するか二つの方法がある（船木［6］などを参照されたい）．ここでは本間題を節約ゲームとして定式化してみよう．節約ゲームで図2 数値例（3企業の共同配送問題）

は，任意の提携に対して，その節約額を対応させる特性関数を考える．ここで特性関数を￠とすると，特表1費用分担ルールに対する数値例
配分方法

企業1 企業2 企業3

各企業ごとの配送 40

均等分担

44

節約額均等配分 26
比例分担

30．3

44

90

44

44

30

76

33．4

68．3

性関数は以下のようになる．
￠（（才））＝0（ブ＝1，2，3）￠（（オ，ノ））＝2（cど＋cJ）一（cど＋dゴノ＋cJ）＝C〜＋cノーdゎ（g，ノ＝1，2，3∠≠ノ）￠（（1，2，3））＝〃123
ここで節約ゲームの解とは，企業グの曹用削減額である配分∬∠を決定することである．言い換えると，

1結節約額比例配分は比例分担と同じになる．
2004年11月号

企業才の管用分担額は2cゴー∬ヱ・となる．配分の合計は© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（11）683

全体の節約額に一致していなければならないので∬1＋∬2＋∬3＝￠ 1，2，3））＝〃123が要求される．これを全体合理性と呼ぶ．また個人合理性は∬∫＞0，提携合理性は∬ど＋み≦￠（（才，ノ））（ブ，ノ＝1，2，3オ≠ノ）と表現できる2．

図3 2企業の共同配送問題

協力ゲームの基本的な解であるコアは，個人合理性，
全体合理性，提携合理性を満たす配分の集合である．

体か」という意思決定をしていると考えられ，ゲーム先の数値例では，節約額均等配分はコアに属しない．

理論における交渉ゲームとして捉えることができる．

コアはどの提携も納得するような協力ゲームの基本的先の共同配送の節約額配分問題をさらに2企業に簡な解概念であり，費用分担ルールが提携を考えても合単化し（図3），これを解説しよう．共同配送の節約

理的なルールを判定するための基準であると考えるこ

額とができるだろう．

Cl＋c2−d12

しかし，コアは配分の集合を与えるだけで，一つのを企業ダに∬∫だけ配分する（企業ブは2cゴーJ〜の費分担額を決定するわけではない．協力ゲームの解で一用分担をする）とした場合，Jどをどのようにするべ

つの分担額を決定するには，仁やShapley値などのきかという問題である．

このとき可能な配分案は，以下の領域βで表すこ概念がある（船木［6］，武藤［9］，鈴木［5］を参照）．

企業の提携に対する特性関数値は，その提携に関すとができる．

るTSPを解くことによって与えられるので，このよ

β＝（（J．，∬2）lェ1≧0，J2≧0，

うな協力ゲームはTSPゲームと呼ばれる．詳しくは∬1十J2≦cl十c2−d12）

毛利，岡本［10］の解説論文を参照されたい．毛利ら

交渉ゲームは，「交渉によってβに属する（∬1，∬2）を［11］は，さらに企業の配送量と配送車の積載能力と台決定し，もし交渉が決裂したならば，（れ，∬2）＝（0，0）

数を考慮したVRPゲームについて研究を行っている．

となる」と考えるゲームである．配分を決定する要因
は可能な配分案βと決裂点（0，0）である．

4．交渉ゲームによるアプローチ

交渉ゲームにおいては，ナッシュ交渉解が代表的な提携の影響をすべて考えることは良いことばかりと解である．ナッシュ交渉解は，交渉結果が，（1）個人合はいえない．まず，計算の複雑度からすれば，企業数

理性，（2）対称性，（3）パレート最適性，（4）無関係対象か乃の場合，困難なTSPを提携の数2〃−1だけ解かな

らの独立性，（5）一次変換による不変性の5条件を満たければならない．また，実際にすべての提携の影響をすときの配分を示した解である．この場合は，均等配考える必要性があるかどうかも疑問であるし，まずこ分のような提携に関する費用が正確に求められるかどうかも疑問である．毛利ら［11］はこの点を指摘し，1企
業の費用分担額を，（1）その企業自身の配送晋用と，（2）
自分以外の全企業の配送費用に，自分が加わったときに増加する費用，の二つにのみ依存する費用分担ルー

Jl＝∬2＝（cl＋c2−d12）となる．

非常に精緻な分析をして，結果が折半ではあまりありがたくない話ではあるが，あくまでも基本例と考えていただきたい．（1）から（5）までの交渉の結果が「満たルを考察した．
最も簡便なものは，比例分担をはじめとした「企業オの分担額をcブにのみに依存させる」方法である．
この方法では，各企業は提携では行動せず「個人か全すべき」望ましし−性質を，交渉解の満たす公理（または公準）と呼ぶが，この公理を違うものに置き換えれば違った解が得られる．皆が納得できるような公理はどれかを決めて望ましいルールを設計していけばよい．

2ここで提携を企業のすべての部分集合と考え，全体集合

交渉に限らず，先の提携を考えた協力ゲームでも，と1企業も含めれば，全体合理性も個人合理性も提携合理性に含まれる．もちろんそう考えてもよい．ここでは提携を全体集合と1企業の場合を除いた企業の集合と考え，個人合理性と全体合理性を分けて考えた．

このように望ましい性質からゲームの解を特徴づける

684（12）ような研究はなされている．一般的に，均等分担や節約額均等配分における望ましい性質を列挙し，そこか© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ら配分ルールを特徴づける方法を公理的アプローチと方法を企業が実際に交渉して配分する結果を，理論的呼ぶ．公理的アプローチは，望ましい費用の分担はに予測して組み込んだと説明する材料になる．

「どうあるべきか」を考える規範理論である．

5．オークションによる資源配分

これに対し，交渉ゲームを非協力ゲームの交互提案

これまでのアプローチは，全体のオペレーションにゲームと捉えることもできる．このような非協力ゲー
ムによる分析は，ナッシュ交渉解が「どうあるべき

参加する主体がすべて協力的であり，望ましい曹用のか」という規範理論だけではなく，実際に2人が交渉分け方や公平な分担方法を話し合い合意できれば，すを行ったとき「どうなるか」を説明する理論でもある

べての企業はそれに従うという設定であった．

ことを示している．次のような無限期間の交互提案ゲームを考えよう．

しかし，個別の企業の利害が対立する場合は，自社の利益が優先され，全体の公平性や望ましさでの配分（1）第1期に企業1が自分の配分∬1を提案する．企にはなかなか合意できないのが実情であろう．このよ

業2は承諾か拒否のどちらかを選択する．企業2がこうな場合には，組織内においても市場メカニズムを導れに承諾したならば，企業1の配分はJl，企業2の入し，効率的な資源配分を達成するといった考え方も配分は（cl＋c2−d．2）−Jlとなる．拒否したならば次ある．

市場メカニズムとして代表的なものはオークションのステージへ．

（2）第2期に企業2が∬2を提案する．企業1がこれである．特に，ロジスティクスへの利用としては，組に承諾したならば，企業2の配分は裁，企業1の配合せオークションと呼ばれるオークションが提案され，分は（cl＋c2−d．2）−J2となる．拒否したならば次の注目されている．以下でこの例を示そう．

今，図4で示されたような位置関係において，次のステージへ．

（3）（1）に戻り，交渉を繰り返す．奇数期には企業1が，偶数其耶ま，企業2が提案し，相手が承諾するまで，交渉が繰り返される．

ような3ルートの配送が可能なトラックがあるとしよ
つ．

A：J地点20：00発 センタ21：00着

ただし，時間の経過とともに，決着して得る配分の現在佃値は割引かれるとする．企業グの割引率を∂〜（0＜∂∫＜1）とするとき，第f期において交渉が配分（Jl，J2）で決着した場合の企業∠の利得は∂f】1∬iとして評

B：センタ21：30発 〝地点23：00着
C：センタ21：30発 z地点23：00着
これに対し，ある3企業が，次のような配送を望んでいるとする．

価される．無限期間まで決着がつかない場合，双方の企業1：∬地点20：00発 〝地点23：00着

利得は0になると考える．

企業2：∬地点20：00発z地点23：00着

このゲームは無限に続いているため，提案を拒否す

企業3：センタ21：30発 z地点23：00着

れば利得が1期分割り引かれて，相手と自分が入れ替

簡単化のため，積み替えの手間やコストを考えない

わったゲームになる．このアイディアを用いてゲームことにし，一つのトラックは1企業の荷物しか積めなの解である完全均衡点を求めると（詳しくは岡田［2］いとする．企業1はルートAとβのトラックを用いを参照），結果は第1期において，企業1の提案を企れば，希望をかなえることができる．企業2はルート

業2が承諾することとなり，配分は次のようになる．

AとCのトラックを，企業3はルートCのトラック∬1＝古志（cl＋c2−d12）∂2（1−∂1）．l、ご＝1−∂1∂2（cl＋c2−d2）

交渉結果は，割引率∂1，∂2に依存し割引率が大きい（交渉が長引いても価値の減少が少ない）企業ほど，多くの配分を獲得できる（交渉力が強い）ということが分かる．また双方の割引率を同じ∂とし，∂を1に近づけると，この結果は先のナッシュ交渉解に近づく．

このような非協力ゲームによるアプローチは，分担
図4 3ルートの配送路
2004年11月号（13）685© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

題，オークションを使った他のリソースの効率的配分のみ用いれば，希望をかなえることができる．
ここで，「希望するルートの組み合わせ」に対して，支払える対価の最高額（評価額と呼ぶ）を企業1はと利用，契約・交渉・報酬の設計など，多くの可能性が秘められている．

45，企業2は50，企業3は10と考えているとしよう．

経済学で成功したゲーム理論には，これまで工学面

この間題は，三つの財A，B，Cを3企業に割−）当での活躍はあまり見られなかったが，コンピュータやてる組合せオークションと考えることができる．もし，ネットワーク技術の発達により，その契機は訪れたよ

各企業が評価額を正直に申告するならば，財の評価額

うに思える．理論から現象を記述し理解するだけではの合計が最大になるように各企業への財の割り当てをなく，ソフトウエアへの実装，そのシミュレーション

考えればよい．この場合の可能な割り当て方はや実験，フィードバックなどのプロセスを通じて問題

割当1企業1にA，Bを割−）当て，企業3にCを解決を図る「工学的ゲーム理論」と呼ばれるような分野を確立していきたいと筆者らは考えている．

割り当てる（評価額の合計は55）

割当2 企業2にB，Cを割り当てる（評価額の合
参考文献
計は50）

であり，評価額の合計が最大になる割−）当ては割当1［1］T．MatsuiandT．Watanabe，：

SealedBidMultir

Object Auctions with Necessary Bundles andIts

である．

ApplicationtoSpectrumsAuctions

各企業が評価額を正直に申告するならば，問題は組
み合わせ最適化問題（集合パッキング問題）である．

しかし，企業は実際に費用を支払うとなれば，正直

200l，LNAI2132，78−−92，SpringerrVerlag，2001．
［2］岡田章：ゲーム理論，有斐閣，1996．

［3］久保幹雄，毛利裕昭： 配送計画システムMETROに自分の費用を申告せず，できるだけ安く支払おうと（MEta Truck Routing Optimizer）

するであろう．各企業が戦略的に行動した場合，オークションの結果はどのようになるのだろうか，また効，P7VC．qfPRIMA，オペレーションズ・リサーチ，Vol．41，No．8，pp．429−435，1996．
［4］今野浩： OR40年（1） ，オペレーションズリサーチ，

率的資源配分は達成されるのであろうか．

Vol．49，No．7，454−456，2004．

MatsuiandWatanabe［1］は，上記の例にいくつかの仮定をおいた状況におけるオークションを分析した．

［5］鈴木光男：新ゲーム理論，勤草書房，1994．
［6］船木由喜彦：エコノミックゲームセオリーー協力ゲー
ムの応用，サイエンス社，2002．

結果として，このオークションは，戦略的行動のもとでも（すなわちナッシュ均衡において）効率的資源配［7］松井知己，渡辺隆裕： オークションの設計理論とOR分を達成するということが示される．上記の例では，（1）

企業1と企業3の合計の入札額が，企業2が落札しな

2003．

い51まで下がることがナッシュ均衡で，例えば，企［8］松井知己，渡辺隆裕： オークションの設計理論とOR

業1，2，3の入札額が（44，50，7），（43，50，8），（42，50，9）などがナッシュ均衡となる．詳しくは（松井，渡辺［7，8］）を参照されたい．

，オペレーションズリサーチ，Vol．48，No．7，516−521，（2），オペレーションズリサーチ，Vol，48，No．8，574−579，

2003．

［9］武藤滋夫：ゲーム理論入門，日経文庫，2001．
［10］毛利裕昭，岡本吉央： 離散最適化と協力ゲーム（2） ，オペレーションズ・リサーチ，Vol．48，42−49，2003．

6．おわりに［11］毛利裕昭，渡辺隆裕，森雅夫，久保幹雄： 共同配送問

リソースプランニング，ロジスティクスにおいてゲーム理論は，費用分担問題だけではなく，施設配置間

686（14）

題における管用分灯●，♪〟γ犯αJ〆 fゐe（砂 ヲ相加乃5月esβαⅣゐSocオg砂〆ノ（砂α邦，Vol．40，No．4，451−464，1997．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ