## 第10章:サプライチェーン管理 I:2エージェント新聞売り子問題

章の概要

サプライチェーン管理問題全般に共通して生じる問題として、資源を必要とするマネージャー(「エージェント」)が、上位のマネージャーにその資源を要求しなければならない、という状況がある。実務上、これらの「現場」マネージャーは自分が実際にどれだけ必要になるか正確には分からないため、不足した場合の大きな下振れコストを避けようとして、多めに要求する傾向がある。「中央」マネージャーは現場マネージャーに必要なものを持たせたいと考えているが、彼らが過大に要求しがちなインセンティブを持つことも認識している。そこで中央マネージャーは、現場マネージャーに本当に必要な分だけを与えようとして、これらの要求を削減する傾向がある。

この両方のマネージャーは、それぞれ自分自身の「newsvendor問題」を抱えており、これは第3章で最初に見たものである。しかし今回は、互いに駆け引きをする2人の「newsvendor」が存在し、それぞれが相手がどう行動するかについての近似を作る必要がある。この問題はビジネス全般に見られるにもかかわらず、研究文献ではこれまであまり注目されてこなかったようである。

この問題を扱うには、マルチエージェント問題のモデル化に足を踏み入れる必要がある。これまで適用してきた標準的なモデリングフレームワークを用いるが、今回はこれらのモデルの版を各意思決定エージェントごとに作成するという点が新しい。しかし、より豊富な相互作用が導入される点を除けば、この普遍的なモデリングフレームワークを各エージェントに適用する方法自体は変わらない。

ナラティブ

Amazonの現場マネージャーが、シカゴから貨物を運び出すためのトレーラーを毎週手配しなければならない状況を想像してほしい。この現場マネージャーは、その週にどれだけのトレーラーが必要になるかを見積もるための情報にアクセスできるが、実際の数値はそれより多くも少なくもなり得る。そこで現場マネージャーは中央マネージャーにトレーラーを要求し、中央マネージャーは自分自身の判断でどれだけのトレーラーを提供するかを決め、最終的に提供されるトレーラー数についての決定を下す。

この2人のマネージャーは同じ会社で働いているが、現場マネージャーは、トレーラーが不足した場合に短期レンタルをしなければならないため、不足することをはるかに強く懸念している。一方、中央マネージャーは現場マネージャーに不足してほしくないと考えているが、同時に、そのトレーラーの費用を負担しなければならないため、現場マネージャーに過剰なトレーラーを持たせたくもない。

このプロセスは以下のように展開すると仮定する:

ステップ1: 現場マネージャーは、必要となるトレーラー数についての初期見積もりを観測する。この情報は現場マネージャーだけが知る私的情報である。

ステップ2: 次に現場マネージャーは中央マネージャーにトレーラーを要求するが、その際、不足の確率を減らすために要求を水増しするのが通例である。

ステップ3: 続いて中央マネージャーは、現場マネージャーに与えるトレーラーの数を決定するが、現場が必要以上の数を要求するというパターンに気づいているため、通常はその要求を削減する。

ステップ4: 現場マネージャーは中央マネージャーから認められたトレーラー数を受け取り、その後、実際に必要なトレーラー数を観測する。

ステップ5: 現場マネージャーと中央マネージャーは、それぞれ超過分(未使用のトレーラー)と不足分(カバーされなかった需要)についての自身のコストを用いて、自らの成績を算出する。

この問題における緊張関係は、まず第一に、必要なトレーラー数の初期見積もりが単なる見積もりに過ぎないことに起因する(これは平均的には正しい、すなわち不偏であると仮定してよい)。問題は、現場マネージャーが不足した場合に大きなコストを被るため、彼の戦略が自らの必要量を過大評価することになる点である(第3章のnewsvendor問題を思い出してほしい)。一方、中央マネージャーは恐らく過剰と不足に対してバランスの取れたコストを持っており、多すぎても少なすぎても発注したくないと考えている。

この問題を複雑にしているのは、現場マネージャーに与えられる初期見積もりである。完璧ではないものの、それはある日の需要が高いか低いかを示す貴重な情報を含んでいる。つまり、中央マネージャーは、現場マネージャーの要求が上方に偏っていることを認識しつつも、その要求に注意を払わなければならない。これを踏まえ、中央マネージャーは現場マネージャーの要求を出発点として使う傾向があるが、最終的な割り当てに対してはそれを減らすことになる。当然ながら、現場マネージャーも中央マネージャーがそうすることを知っており、それに応じて調整を行う。

問題の枠組み

3つの枠組み設定の質問への回答は以下の通りである:

指標: 各エージェントは、それぞれ独自の指標を持っており、不足と超過の期待コストを最小化することを目指す。
決定: 現場エージェントは中央エージェントにどれだけ要求するかを決定する。中央エージェントは、現場エージェントの要求のうちどれだけを満たすかを決定する。
不確実性: 核心となる不確実性は、現場における資源の実際の需要である。さらに、現場エージェントは中央エージェントが自分の要求にどう応答するかという不確実性に対処しなければならず、中央エージェントは、現場エージェントがどれだけ要求してくるかという、私的情報を反映した不確実性に対処しなければならない。

基本モデル

両プレイヤーで情報が同じではないため、両エージェントについてこの問題をモデル化する。モデル全体を通じて、現場マネージャーを$q$、中央マネージャーを$q’$として参照する。

状態変数

現場マネージャーが利用できる初期情報は、必要となるトレーラー数の見積もりであり、これを$R^{est}_{tq}$、すなわち必要なトレーラー数の初期見積もりとして表す。この初期見積もりには偏りがある可能性があるため、$\delta^{est}_{tq}$、すなわち$R^{est}_{tq}$と真の需要との差の初期見積もりを用いて、この偏りの推定値を導入する。また、中央マネージャーが現場マネージャーの要求をどの程度削減するかも推定する必要があり、これを$\delta_{tq}$、すなわち中央マネージャーが現場マネージャーの要求をどの程度削減するかの推定値として表す。同様に、中央マネージャーは、現場マネージャーが行う要求と、現場マネージャーが最終的に必要とする量との差を学習していくが、これを$\delta_{tq’}$、すなわち現場マネージャーが要求する量と現場が最終的に必要とする量との差の推定値として表す。

各エージェントの状態変数は、決定を下す前に持っている情報である。現場マネージャーについて、状態変数は

\[S_{tq} = (R^{est}_{tq}, \delta^{est}_{tq}, \delta_{tq}).\]

中央マネージャーの状態変数は

\[S_{tq'} = (x_{tqq'}, \delta_{tq'}).\]

ここで$x_{tqq’}$は現場エージェント$q$が中央エージェント$q’$に対して行う要求である(次に導入する)。

決定変数

各エージェントの決定は、$x_{tqq’}$(エージェント$q$がエージェント$q’$に要求するトレーラーの数)と、$x_{tq’q}$(エージェント$q’$がエージェント$q$に与えるトレーラーの数、すなわち現場で実行される数)によって与えられる。

外生情報

現場マネージャーにとっての外生情報は、必要なトレーラー数の初期見積もりだと考えることができる(ただしこれは状態変数に含めている): $R^{est}_{tq}$、すなわち必要なトレーラー数の初期見積もりである。この見積もりは現場エージェント$q$だけが知っている。

決定$x_{tqq’}$を下した後、2種類の情報を受け取る。それは、中央マネージャーが認めてくれる量と、実際に必要となる需要である: $x_{tq’q}$、すなわち現場マネージャーの要求に応じて中央マネージャーが下す決定と、$\Rhat_{t+1}$、すなわち現場マネージャー$q$が最終的に必要とするトレーラーの実数(この情報は中央マネージャーにも利用可能である)。

エージェント$q$にとっての外生情報は、すなわち

\[W_{t+1,q} = (x_{tq'q},\Rhat_{t+1}).\]

念のため補足すると、この情報は時刻$t+1$においてインデックス付けされているものの、中央マネージャーによって認められた要求$x_{tq’q}$は、時刻$t$までに利用可能な情報に依存するため、$t$でインデックス付けされている。初期見積もり$R^{est}_{tq}$は新しい情報であるが、決定が下される前に到着するため、現場エージェントの状態変数の中で捕捉される。

中央マネージャーは、外生情報として到着する初期要求$x_{tqq’}$を受け取るが、これは彼女が決定を下す前に受け取られるため、中央マネージャーの状態変数を通じて入ってくる。中央マネージャーにとっての唯一の外生情報は、その後の決定に影響を与える信念の更新に用いられ得る最終需要である。すなわち

\[W_{t+1,q'} = (\Rhat_{t+1}).\]

遷移関数

現場マネージャーには3つの状態変数がある: $R^{est}_{tq}$、見積もり$R^{est}_{tq}$と実際の値$\Rhat_{t+1}$との間の偏り$\delta^{est}_{tq}$、そして現場が要求を行う際に中央マネージャーによって導入される偏り$\delta_{tq}$である。最初の状態変数$R^{est}_{tq}$は外生情報として直接到着する。偏り$\delta^{est}_{tq}$と$\delta_{t,q}$は次式を用いて更新される

\[\delta^{est}_{t+1,q} = (1-\alpha) \delta^{est}_{tq} + \alpha (\Rhat_{t+1} - R^{est}_{tq}), \qquad \delta_{t+1,q} = (1-\alpha) \delta_{tq} + \alpha (x_{tqq'} - x_{tq'q}),\]

ここで$0 < \alpha < 1$は平滑化係数である。

中央マネージャーの遷移関数も同様である。ここでも、現場マネージャーの決定$x_{tqq’}$は外生的に状態変数に到着する。そして、中央マネージャーが現場マネージャーの要求について推定する偏りを、次式を用いて更新する

\[\delta_{t+1,q'} = (1-\alpha) \delta_{t,q'} + \alpha (x_{tqq'} - \Rhat_{t+1}).\]

目的関数

まず$c^o_q$、すなわち現場マネージャーが超過した各トレーラーについて負担する単位コスト(現場がトレーラー1台あたり1日に支払う費用、超過コストとも呼ばれる)、$c^u_q$、すなわち能力不足を補うためにレンタルしなければならないトレーラー1台につき現場マネージャーが負担する単位コスト(不足コストとも呼ばれる)、そして$c^o_{q’}, c^u_{q’}$、すなわち中央マネージャーにとっての超過および不足のコストを定義する。

各エージェントのコストは次式で与えられる

\[C_{tq}(S_{tq},x_{tq'q}) = c^o_q \max\{x_{tq'q}-\Rhat_{t+1},0\} + c^u_{q} \max\{\Rhat_{t+1} - x_{tq'q},0\},\] \[C_{tq'}(S_{tq'},x_{tq'q}) = c^o_{q'} \max\{x_{tq'q}-\Rhat_{t+1},0\} + c^u_{q'} \max\{\Rhat_{t+1} - x_{tq'q},0\}.\]

現場と中央マネージャーの両方の成績は、中央マネージャーが現場に与えるトレーラーの数$x_{tq’q}$に依存する。しかし、この決定は現場マネージャーが下す決定に依存している。

現場マネージャーの決定は、方策$X_{tq}(S_t\vert \theta_q)$を用いて下される。ここで$\theta_q$は次式を解くために使われる1つ以上の調整可能なパラメータである

\[\begin{align} \min_{\theta_q}\E \left\{\sum_{t=0}^T C_{tq}(S_{tq},X_{tq}(S_t\vert \theta_q))\vert S_0\right\}. \label{eq:fieldobjective} \end{align}\]

同様に、中央マネージャーの決定は、方策$X_{tq’}(S_t\vert \theta_{q’})$を用いて下される。ここで$\theta_{q’}$は次式を解く1つ以上の調整可能なパラメータである

\[\begin{align} \min_{\theta_{q'}}\E \left\{\sum_{t=0}^T C_{t{q'}}(S_{tq'},X_{tq'}(S_t\vert \theta_{q'}))\vert S_0\right\}. \label{eq:centralobjective} \end{align}\]

$\eqref{eq:fieldobjective}$と$\eqref{eq:centralobjective}$における最適化問題は、両方の方策を同時にシミュレーションしなければならないため、同時に解く必要がある。もちろん、現場マネージャーの$\theta_q$を調整している間、中央マネージャーの$\theta_{q’}$を一定に保つこともできるが、最終的に我々が求めているのは安定した局所最小値である。

不確実性のモデル化

この問題はデータ駆動型であり、データが到着するたびにそれに反応することを意味する。関与するエージェントに応じて、3種類の情報がある:

必要な資源の初期見積もり$R^{est}_t$。
現場マネージャーによって行われ、中央マネージャーに到着する要求$x_{tqq’}$。この決定には現場マネージャーが導入したロジックが関わっており、それには無作為化が含まれることもある。これは中央マネージャーにとっての情報として届く。
中央マネージャーによって下され、現場マネージャーに与えられるトレーラー数を決定する決定$x_{tq’q}$。これは現場マネージャーにとっての情報として届く。
実際に必要とされるトレーラー数の最終的な実現値$\Rhat_{t+1}$であり、(この基本モデルにおいては)両エージェントに明らかにされる。

このプロセスをシミュレーションしたい場合、$R^{est}_t$と$\Rhat_t$の生成をモデル化するだけでよい。より正確に言えば、$R^{est}_t$をある分布から、そして誤差$\Rhat_t - R^{est}_t$を別の分布から生成する必要がある。

方策の設計

この2エージェントnewsvendor問題については、各エージェントについて方策を開発する必要がある。まず現場マネージャーの方策から始める。

現場マネージャー

現場マネージャーは見積もり$R^{est}_t$から出発するが、次の3つの要因を考慮しなければならない:

1) 見積もり$R^{est}_t$には偏り$\delta^{est}$がある可能性がある(見積もり$R^{est}_{tq}$の出所について確信を持つことはできない)。この偏りは次式で与えられる

\[\delta^{est}_{tq}= \E \Rhat_{t+1} - R^{est}_{tq}.\]

したがって、もし$\delta^{est}_{tq} > 0$であれば、これは$R^{est}_t$が上方に偏っていることを意味する。

2) 実際に必要となるトレーラーの真の数$\Rhat_{t+1}$は、偏りを考慮に入れたとしてもなお確率的である。現場マネージャーは、トレーラーが多すぎる場合よりも少なすぎる場合の方が高いコストを被るため、不足に見舞われた場合の高いコストを反映させるために上方への偏りを導入したいと考えるだろう。

3) 中央管理者は多すぎることと少なすぎることの両方に対してバランスの取れた姿勢を持っており、現場管理者にバイアスがあることを知っている。その結果、中央管理者は通常、現場管理者からの要求$x_{tqq’}$を用いる際に調整を行うが、それはちょうど現場管理者が推定値$R^{est}$と実際の値$\Rhat_t$の間の起こりうるバイアスを調整するのと同様である。現場管理者は中央管理者がこの調整を行うことを知っているため、それを推定し、対抗しようとしなければならない。現場管理者は自身の要求$x_{tqq’}$を知っており、その後中央管理者が何を提供するかを見るので、時間$t$におけるバイアスの観測は次式で与えられる。

\[\delta_{tq} = x_{tq'q} - x_{tqq'}.\]

我々は、$R^{est}_t$と$\Rhat_t$の差、$x_{tqq’}$と$x_{tq’q}$の差、そして$x_{tqq’}$と$\Rhat_t$の差についての推定値を用いる必要がある。現場管理者に対する方策として、次式を提案する。

\[\begin{align} X_{tqq'}(S_t\vert \theta_q) = R^{est}_t - \delta^{est}_{t-1,q} - \delta_{t-1,q} + \theta_q. \label{eq:fieldpolicy} \end{align}\]

この方策は、初期推定値$R^{est}_t$から始まり、$\delta^{est}_{t-1,q}$を用いてこの初期推定値のバイアスを補正し、次に中央管理者からのバイアス$\delta_{t-1,q}$を補正し、最後に現場管理者にとっての過剰と過小のコストの違いを捉えるシフトを導入する。パラメータ$\theta_q$は調整する必要がある。

埋め込まれた最適化問題(すなわち$\argmax_x$や$\argmin_x$)が存在しないため、これは典型的なパラメータ化された方策関数近似(PFA)である。

中央管理者

中央管理者に対する我々の方策は次式で与えられる。

\[X_{tq'q}(S_t\vert \theta_{q'}) = x_{tqq'} - \delta_{t-1,q'} + \theta_{q'}.\]

ここでは、現場管理者が行った要求から出発し、現場管理者の要求と最終的に必要とされたものとの差の最良の推定値$\delta_{tq’}$を差し引き、その後中央管理者にとって調整可能なパラメータである$\theta_{q’}$を加える。ここで$\theta_{q’}$は負の値を取り得る。

方策探索

これで我々は2つのパラメータ化された方策を持つことになった。現場方策の調整は$\eqref{eq:fieldobjective}$の目的関数を用いて行われ、中央方策の調整は$\eqref{eq:centralobjective}$の目的関数を用いて行われる。ここでの巧妙な点は、両方の方策が相互に結びついているため、両方の目的関数を並行してシミュレートする必要があることである。そして両方のシミュレーションが実行されている間、各エージェントの目的関数を追跡し続ける。

各エージェントのパラメータの最適化に対する正しいアプローチは、両エージェントの振る舞いを同時にシミュレートしつつ、それぞれのエージェントに対して独立であるかのように探索アルゴリズムを実行することである。例えば現場エージェントの性能は、現場エージェントが他の形態の外生情報に影響を受けるのとまったく同様に、中央エージェントの振る舞いによって影響を受けることになる。

このシミュレーションは、各エージェントの決定がもう一方のエージェントの振る舞いをどのように変化させ得るかを探る機会を提供する。この点については演習問題でさらに追求する。

何を学んだか

現場エージェントが中央エージェントに資源を要求しなければならない、「二エージェント新聞売り子問題」と呼ぶ基本的なマルチエージェント問題を導入した。両エージェントは協力して働くことになっているが、それぞれが過剰(資源を多く持ちすぎること)と過小(資源が不足し、満たされない需要が生じること)に対する独自のコストを持つ。
現場エージェントに固有の情報と、中央エージェントに固有の情報をモデル化した。
この問題は、現場エージェントが決定を下すのを助けるために、中央エージェントの振る舞いを推定し予測するという次元を導入している。
各時点において、現場エージェントは推定値$R^{est}_{tq}$と中央エージェントが要求を調整してきた履歴を踏まえて、注文したいものについての最良の推定値を持つ。不確実性と、不足することのコストが過剰を持つことのコストよりも高いことを考えると、良い方策は必要と予想されるものに不確実性に対するバッファーを加えて注文することであると期待するのが自然であり、そのためこの形式の方策を提案することから始めた。
この問題は、現場エージェントによって行われる調整に対して中央エージェントがどのように応答するかについての信念を組み込むための基盤を築いている。なぜなら、彼女が最終的には過剰または過小を目にすると仮定しているからである。
この問題は非常に単純に見えるが、より複雑な多くのマルチエージェント資源配分問題の基盤を築くものである。

演習問題

復習問題

エージェント$q$には知られているがエージェント$q'$には知られていないものは何か?同様に、エージェント$q'$には知られているがエージェント$q$には知られていないものは何か?
両エージェントに利用可能となる情報が1つある。それは何か?
現場エージェントに利用可能となる外生情報は何か?中央エージェントに利用可能となる外生情報は何か?
我々のシステムには3つの不確実性の源がある。それらは何か?

問題解決演習

現場管理者と中央管理者両方の動的モデルを書き出しなさい。一方の管理者の決定がもう一方にとっての外生情報となることを忘れないように。
現場エージェントが単に注文量をますます増やしていったらどうなるか?このような不安定性を最小化するために、モデルにどのような仕組みを導入できるか?
現場エージェントの決定$x_{tqq'}$が中央エージェントの振る舞いにどのように影響し得るかについて推定値を作成しなさい。次に、この効果を捉える方策を設計し、現場エージェントによって行われる決定が自身の決定の効果を予測するようにしなさい。
別のエージェントの方策についての信念を作成するために使用できる情報は1つだけある。その情報とは何か?
ここで、現場エージェントが中央エージェントから得た資源を、時間ごとにランダムに変化する価格$p_{tq}$で販売できると仮定する。これは、価格$p_{tq}$が低すぎる場合、現場エージェントが資源の一部または全部を後の期間まで保持できることを意味する。この章のモデルを拡張して、このはるかに豊かな設定を扱えるようにしなさい。新しい決定変数(需要のうちどれだけを満たすか)を導入する必要がある。決定を行うための方策関数近似を提案しなさい。

プログラミング演習

これらの演習では、tinyurl.com/sdagithubのPythonモジュールTwoNewsvendorを使用する。

現場管理者と中央管理者のバイアスについてグリッドサーチを実行しなさい。現場管理者については範囲$[0,10]$(1刻み)、中央管理者については範囲$[-11,0]$(1刻み)で探索しなさい。ゲームを$N = 30$時間ステップ実行し、シミュレーションを1,000サンプルで繰り返す(そして平均を取る)。30時間ステップにわたって報酬を加算しているが、1,000サンプルにわたっては平均を取っていることに注意すること。以下について3つのヒートマップをプロットしなさい。
1. 2つのバイアスの組み合わせそれぞれについての現場管理者の総報酬。
2. 2つのバイアスの組み合わせそれぞれについての中央管理者の総報酬。
3. 2つのバイアスの組み合わせそれぞれについての会社全体の総報酬(現場管理者と中央管理者を合わせたもの)。3つの視点それぞれからの最適な組み合わせの違いについて議論しなさい。各プレイヤーは自身の報酬を最大化したいと考えている。
ここでは、区間推定学習方策を用いて各バイアスを学習することにする([第4章](/sdam/ja/chapter-4/)における方策の議論を参照)。$\theta^{IE}_q$を現場管理者のIE方策のパラメータとし、$\theta^{IE}_{q'}$を中央管理者のIE方策のパラメータとする。最良のバイアスを探索する代わりに、バイアスを見つけるための方策を導くための最良のパラメータを探索することにする。
1. 各学習パラメータを範囲$(0, 1, 2, 3, 4, 5)$で変化させながらPythonモジュールを実行しなさい。これは合計36回のシミュレーション(計画期間$N = 20$、1,000サンプルパス)を意味する。演習問題10で行ったのと同じ3つのヒートマップをプロットしなさい。
2. (a)のヒートマップの振る舞いを、演習問題10のヒートマップと比較しなさい。方策を書き出し、それがどのように振る舞うべきかを考えることで、現場エージェントと中央エージェントの振る舞いを説明しようとしなさい。
3. バイアスに対する直接探索が最も高い全体報酬を与えることを確認しなさい。問題のパラメータが時間とともに変化しうるより現実的な設定において、各アプローチの長所と短所は何か?
(この演習にはPythonモジュールへの若干の修正が必要である。)ここで、中央管理者も需要についての外部情報を何らか持っている二エージェント新聞売り子問題を考える。彼が持っているのは、需要についてはるかにノイズの大きい推定値である(例えば、需要が常に20から40の間にある我々のスプレッドシートデータについて、ノイズが現場管理者と通信する情報源からのノイズの3倍大きいとする)。中央管理者からのバイアスを、彼が得た推定値に加える量として再定義しなさい。彼が選択するバイアスが区間$[-11, 0]$の中から選ばれるという学習アプローチを試しなさい。プログラムを実行し、結果を以前の学習過程と比較しなさい。以前と同様に、ゲームを$N = 30$時間ステップ実行し、シミュレーションを1,000サンプルで繰り返す(そして平均を取る)。$N = 30$時間ステップ後、中央エージェントは現場から来る情報と、自身のその他の外部情報源から来る情報のどちらにより重みを置いているか?それはなぜか?
現場管理者が学習アプローチを用い、中央管理者が懲罰戦略を用いる場合を考える。中央管理者は、現場が需要を下回って提供することに対してより大きなペナルティを受けることを知っているため、前回の現場のバイアス(時間$t-1$について)を計算し、それが正であれば、次のラウンドでは、現場の要求に対して大きさが2倍で符号が逆のバイアスを適用することにする。この実験を実行し、30時間ステップ後の現場のバイアスがどうなるかを見なさい。この方策を以前の方策と比較して、中央管理者はこの戦略を採用すべきか?