- HOME
- シミュレーション適用事例：Algorithmic Collusion
2022年10月 4日 10:00
シミュレーション適用事例
として、シミュレーションで解決できる様々な事例を紹介しています。
NTTデータ数理システムで開発しているシミュレーションシステム S4 Simulation System 上での実装例もご紹介します。
Algorithmic Collusionとは
市場システムの有効性は競争に根ざしています。
顧客を引き付けるために努力することで、企業はより低い価格を請求し、より良い製品とサービスを提供するようになります。
近年では、航空券や電力料金など、ダイナミックプライシングなどにより、モノの価格は一定ではなく、動的に変更されるようになってきました。 また、価格をアルゴリズムによって設定しようとする動きもみられます。
しかし、アルゴリズムによる価格設定の増加は、企業が『合法的』に共謀を行う機会を増やす可能性があります。
このようなアルゴリズムによる共謀は、人工知能（AI）アルゴリズムが、人間の介入、監視、または知識さえもなしに、共謀していない価格設定ルールを採用することを学習したときに発生します。これが Algorithmic Collusion と呼ばれるものです。
シミュレーションによる再現
価格設定AIの学習方法に強化学習を用い、S4 Simulation System によるシミュレーション で Algorithmic Collusion が起こるかどうかを実験しました。
その結果、比較的単純な価格設定アルゴリズムが体系的に協調戦略を実行することを学習することを示しました。
これらの戦略には、裏切りに対する罰が含まれます。
そのような罰は期間が有限であり、逸脱前の価格に徐々に戻ります。
グラフは学習に伴う価格の推移を示したものです。
学習序盤は探索・学習に伴い価格が上下しますが、しばらく経過すると落ち着き、価格競争の結果実現するとされるNash均衡価格よりも高い価格に収束します。
エージェントモデルと学習モデル
環境：市場モデル
すべてのプレイヤーが同時に行動し、過去の歴史に基づいて行動を条件付ける、無限に繰り返される価格設定ゲームである。ロジット需要と一定の限界費用を伴う価格競争のモデルを採用。$n$ 種類の製品と一つの部外品があるとしている（= $n$ 企業の製品がある）。
製品 $i$ の需要
[[q_{i,t} = \frac{\exp(\frac{a_i - p_{i,t}}{\mu})}{\sum_{j=1}^{n}\exp(\frac{a_i - p_{i,t}}{\mu}) + \exp(\frac{a_0}{\mu})}]] $p_{i,t}$ は製品 $i$ の価格、$a_i$ は vertical differentiation（製品の品質の違いなど）、$\mu$ は horizontal differentiation を表す。
利益（報酬）
[[\pi_{i,t} = (p_{i,t} - c_i)q_{i,t}]] ここで $c_i$ は製品（=企業 $i$）の限界費用である。
観測：状態
過去 $k$ 時刻の自プレイヤ・他プレイヤの価格。初期状態は一様ランダムに選択。
行動：離散化した価格
区間 $[p_n - \xi(p_m - p_n), p_m + \xi(p_m - p_n)]$ を $m$ 等分
ただし、$p_m$ は独占価格、$p_n$はナッシュ均衡価格、$\xi$はパラメータ（$\xi > 0$）とする。
アルゴリズム
AI（価格を決定するエージェント）は試行錯誤によって競争価格に対する方策を学習しています。
その際、AI には共謀するように設計または指示されておらず、また互いに通信もせず、AI が動作する環境についての事前知識は持っていません。
但し、競争価格を学習したからと言って、其れだけでは Algorithmic Collusion が起きているとは必ずしも言えません。
メカニズムの考察
そこで、学習した戦略（方策）の一例として、片方のエージェントが価格を下げた場合に、もう片方のエージェントが何かしらの罰（価格を下げる）を与える様子を考察しました。
上図はヒートマップで、色の薄い所が頻度（確率）が高いことを表します。横軸がエージェント0の価格、縦軸がエージェント1の価格を表します。
左上が学習後の価格分布になります。 エージェント0と1では同じような価格を取ることがわかります。
中央の上のグラフは、エージェント1の価格を下げた場合を表しており、その後のそれぞれのエージェントの価格の推移の様子を時計回りに示しています。
右上のグラフでは、学習後に比べて全体的に価格が下がっている（エージェント0が価格を下げた＝罰を与えた）ことがわかります。 その後、右下から左下にかけて、徐々に価格が高価格帯に推移していることがわかります。
最終的には左上の学習後の価格分布に戻ります。
つまり、下げられた側は即時追従して価格引き下げを行い、その後数ターンかけて両エージェントとも高価格帯に戻る様子が観察され、最終的には Supracompetitive pricing に落ち着きます。
まとめ
強化学習とマルチエージェントシミュレーションをもちいて Algorithmic Collusion が起きるかを実験しました。その結果、強化学習価格設定アルゴリズムが体系的に共謀を学習することを示しました。これらの戦略には、裏切りにたいする罰が含まれます。 そのような罰は有限の期間であり、その後、逸脱前の価格に徐々に戻ることを示しました。 アルゴリズムは、事前知識や互いにコミュニケーションをとったり、共謀するように設計されたり指示されたりすることなく、試行錯誤によってこれらの戦略を実行することを学習しました。
参考文献
サンプルプログラム
S4 Simulation SystemのAlgorithmic Collusionのサンプルプログラム (Ver6.2以降) をダウンロードできます。
その他サンプルプログラム一式をダウンロードするにはこちら。
おわりに
シミュレーションについて
他にもシミュレーションで解決できる課題の例をシミュレーション適用事例としてご紹介しています。
そもそもシミュレーションとは？シミュレーションってどうやるの？等の疑問をお持ちの方に向けて、具体例も交えて紹介・解説する【1から分かるシミュレーション読本】を無料公開しています。 よろしければ併せてご覧ください。
S4 Simulation System について
「S4 Simulation System」は、複雑なモデルGUI上で表現しを誰でも簡単にシミュレーションを行なえるソフトウェアです。本記事でも「S4 Simulation System」でのシミュレーション実装例をご紹介しました。
30日間の無償トライアルでシミュレーションモデルをご自身で動かしていただくことも可能です。ご興味をお持ちの方は下記のフォームからお問い合わせください。
また、「S4 Simulation System」のご紹介とハンズオンでのシミュレーション体験を行うオンラインウェビナーを毎月無料で開催しております。ご興味をお持ちの方はぜひご参加ください。
