Auditing Algorithmic Collusion from Strategy Graphs

あなたは、チェスのハイステークスな対局を観戦していると想像してください。しかし、プレイヤーは人間ではなく、試行錯誤を通じてチェスの遊び方を学んでいる超高速のコンピュータプログラムです。これは、企業がガソリンからアパートの賃貸に至るまで、あらゆるものの価格をAIに決定させている「アルゴリズムによる価格設定」の世界です。時として、これらのプログラムは偶然にも「秘密の手順（シークレット・ハンドシェイク）」を学習してしまうことがあります。つまり、互いに会話をしなくても、全員が高価格を維持し続ければ、全員がより多くの利益を得られるということを理解してしまうのです。これは「アルゴリズムによる協調（アルゴリズム・コリュージョン）」と呼ばれます。これは規制当局にとって悪夢のような事態です。なぜなら、これを見つけ出すのが非常に困難だからです。通常、二人が反競争的な行為を行っていることを証明するには、隅でささやき合っているのを目撃するか、書かれたメモを見つける必要があります。しかし、コンピュータには「ささやき」はなく、「メモ」もまた、企業が極秘のレシピとして扱う数百万行のコードの中に埋もれているのです。

では、日記を読むことも、電話の内容を傍受することもできない場合、どのようにして不正を行う者を見つけ出せばよいのでしょうか？ あなたは、彼らの意思決定の「地図」を見る必要があります。価格設定アルゴリズムを「脳」ではなく、「迷路」と考えてみてください。コンピュータがある特定の状況（例えば「昨日の価格が高かった」など）に直面するたびに、次に何をすべきかというルールを持っています。もし、あらゆる状況から次にコンピュータが選択する行動へと線を引いていけば、巨大で複雑に絡み合った経路の網が出来上がります。公正で競争的なゲームでは、この網は通常、最低価格へと向かう乱雑で直接的なルートになります。しかし、コンピュータが協調している場合、その網は異なる姿を見せます。そこには特定の「チョークポイント（瓶の首のような狭い地点）」や、ルールを破ろうとする者を罰するための長く迂回するループが存在します。この論文は問いかけています。価格も、利益も、あるいはコードさえも知ることなく、この「迷子（迷路）の形」を見るだけで、秘密の共謀を見抜くことができるのだろうか？と。

ニコラス・エッシェンバウムとヤヌシュ・M・メイランという著者たちは、答えは「イエス」であると言います。彼らは、中身を覗き見ることなくこれらのアルゴリズムを監査するための新しい方法を提案しています。秘密のコードや学習データを求める代わりに、規制当局は単にアルゴリズムに対して、「もしあなたがこの特定の状況に置かれたら、あなたはどうしますか？」と尋ねることを提案しています。あらゆる可能なシナリオに対してこれを実行することで、「戦略グラフ」、つまり迷路の地図を作成できるのです。

研究者たちは、協調的なアルゴリズムは、この地図上に非常に特徴的な指紋を残すことを発見しました。アルゴリズムが高価格を維持するために協力しているとき、その意思決定の迷路には強力なボトルネックが発生することを見出したのです。想像してみてください。どこからでも家に帰るために、必ず一つの狭い橋を渡らなければならない街を。もしショートカットを取ろうとしても、その橋を渡る前に交通渋滞（罰則フェーズ）に巻き込まれてしまいます。競争的な市場では、多くの橋や近道が存在します。しかし、協調的な市場では、マップが細工されており、高価格ゾーンに戻る前に、ほとんどすべての経路が特定の「罰則状態」へと集約されるようになっています。

これを証明するために、チームは数千回のシミュレーションを実行しました。彼らは、二つのコンピュータプログラムが価格を設定することを学習する単純な世界を作り出しました。彼らは二つの異なる学習方法をテストしました。一つは、プログラム同士が共に学習する方法（有名な「カルバーノ」方式のようなもの）、もう一つは、個別に学習する方法（分散型Q学習）です。また、個別に訓練された二つのプログラムを強制的に対戦させ、協調関係を崩したシナリオもテストしました。

結果は驚くべきものでした。研究者たちは、迷路の3つの主要な特徴を測定しました。

1. 最大中間性（Maximum Betweenness）: これは、どれほど多くの経路が単一の「チョークポイント」を通過するかを測定します。シミュレーションにおいて、アルゴリズムが協調的であればあるほど、より多くの経路が単一の罰則状態へと強制的に集められました。相関関係は強く、主要なテストにおけるスコアは0.67でした。
2. アトラクター入次数（Attractor In-degree）: これは、「幸せな場所（高価格のループ）」へ直接つながる経路の数をカウントします。協調的な迷路では、そこへ直接つながる経路は非常に少なく、ほとんどの場合は罰則を経由して遠回りしなければなりません。この指標は、-0.67という強い負の相関を示しました（つまり、協調性が高まるにつれて、直接的な経路が減少することを意味します）。
3. 平均経路長（Average Path Length）: これは、ミスをした後に高価格のループに戻るまでに何ステップかかるかを測定します。協調的な迷路は、より長い経路を持っていました（理論モデルでは平均1.96ステップ）。これは、アルゴリズムが許容する前に「罰則フェーズ」を強いるためです。

著者たちは、これが即座に犯罪を証明する魔法の杖ではないことにも注意を払っています。彼らは、これらの「グラフ指標」が、アルゴップが単に諦めてしまう（「グリム・トリガー」戦略）のではなく、罰則の後に協調関係に戻るように学習している場合に最も効果的であることを発見しました。また、現実世界ではアルゴリズムがより複雑になり、ランダムな選択や連続的な更新を行う可能性があるため、マップがより曖昧になる可能性についても認めています。しかし、彼らのシミュレーションは、意思決定プロセスの「形」が堅牢なシグナルであることを示唆しています。

このアプローチの素晴らしさは、必要な情報が極めて少ない点にあります。規制当局は、企業の秘密のコードも、売上データも、利益率も必要としません。彼らに必要なのは、凍結されたポリシー（アルゴリズムが現在従っているルールのセット）に対してクエリを投げ、迷路の線を辿ることだけです。もしマップに、高価格帯に戻るために誰もが通過しなければならない、一つの狭い橋が見えるならば、それはアルゴリズムが協調している可能性があるという大きなレッドフラッグ（警告）となります。それは、城の中に隠された秘密の通路を見つけるようなものです。誰がなぜそれを作ったのかを知る必要はありませんが、その通路の存在自体が、何か疑わしいことが起きていることを物語っているのです。

要するに、この論文は、アルゴリズムの心を読み解くことは常に可能ではないかもしれないが、彼らの「地図」を読み取ることはできると示唆しています。そして、もしその地図が、高価格クラブへの復帰を許可する前に、あなたを罰則のループに閉じ込めるように設計された迷路のような形をしているのであれば、規制当局はより詳細な調査を行うべき時なのです。