チップ発射ゲーム

チップ発射ゲームは、 1983 年頃に発明され、それ以来構造組合せ論の研究の重要な部分となっているグラフ上の1 人用ゲームです。

各頂点には、状態変数によって示される「チップ」の数があります。発火するたびに、頂点が選択され、そのチップの 1 つが各隣接頂点 (エッジを共有する頂点) に転送されます。各頂点のチップの数は負にはなりません。発火が不可能になると、ゲームは終了します。

有限グラフ Gが連結かつループなしであり、頂点V = {1, 2, . . . , n } であるとします。deg( v ) は頂点の次数、e( v,w ) は頂点vとw の間の辺の数とします。ゲームの構成または状態は、各頂点に、その頂点にあるチップの数を表す非負の整数s ( v ) を割り当てることによって定義されます。移動は、次数と同じ数以上のチップを持つ頂点w を選択することから始まります: s ( w ) ≥ deg( w )。頂点wが発火し、 w から各入射辺に沿ってチップを 1 つずつ隣接頂点に移動し、次のように定義される新しい構成が生成されます。${\displaystyle s'}$

${\displaystyle s'(w)=s(w)-\deg(w)}$

そしてv ≠ w の場合、

${\displaystyle s'(v)=s(v)+e(v,w)。}$

それ以上の発砲が不可能な状態が安定状態です。初期設定から開始して、ゲームは次の結果で進行します（接続されたグラフ上）。

• チップの数がエッジの数より少ない場合、ゲームは常に有限となり、安定した状態になります。
• 各頂点のチップがその次数より少ない場合、ゲームは有限です。

• チップの数が少なくともエッジの数である場合、適切に選択された初期構成では、ゲームは安定状態に到達することなく無限になる可能性があります。
• チップの数が辺の数から頂点の数を引いた数の 2 倍を超える場合、ゲームは常に無限になります。

有限チップ発射ゲームの場合、発射イベントの可能な順序は反マトロイドによって記述できます。反マトロイドの一般的な特性から、各頂点の発射回数と最終的な安定状態は、発射イベントの順序に依存しないことがわかります。^[1]

ドルゲームとして知られるチップ発射ゲームでは、チップをドル、頂点をお金の借り手と貸し手として解釈します。文献ではドルゲームの 2 つのバリエーションが有名です。

このドルゲームでは、負の整数値（負債を表す）が有限グラフGのいくつかの頂点に割り当てられます。すべての頂点を正にできる状態が存在する場合、ゲームは勝てると呼ばれます。 ^[2]リーマン・ロッホの定理のグラフ理論的類似物を使用して、ゲームが勝てるかどうかを特徴付けることができます。^{[2] [3]}

砂山モデルに密接に関連するチップ発射の変形形式（ドルゲームとしても知られる）では、単一の特別な頂点qが銀行として指定され、負債を負の整数値s ( q ) < 0 を取ることが許可されます。他の頂点が発射できる場合、銀行は発射できず、チップを収集することしかできません。最終的に、q は他の頂点が発射できないほど多くのチップを蓄積します。このような状態でのみ、頂点q は隣接する頂点にチップを発射して「経済を活性化」できます。

このゲームにおいて安定（つまりqのみが発火可能）かつ再帰的な状態の集合は、と砂山群（ヤコビ群または臨界群とも呼ばれる）の直積に同型なアーベル群の構造を与えることができる。後者の順序はグラフのツリー番号である。 ^{[4] [5]}${\displaystyle \mathbb {Z} }$

• アーベル砂山モデル
• チップ焼成の数学
• リーマン・ロッホの定理

• A. Björner、L. Lovász: 有向グラフ上のチップ発射ゲーム。代数的組合せ論ジャーナル、1992 年 12 月、第 1 巻、第 4 号、pp 305–328 doi :10.1023/A:1022467132614

• MIT コース 18.312: 代数的組合せ論
• Weisz Ágoston: コロングロヴジュ ジャーテク。 Szakdolgozat、ELTE TTK Bsc、2014 ^{[永久リンク切れ‍ ]}
• エゲルヴァリ研究グループにおけるチップ焼成調査
• チップ発射で作られたゲーム (2010) 2017-07-11 にWayback Machineでアーカイブされました
• ドルゲーム -ベイカーとノリンのドルゲームのバリエーションに関するNumberphileビデオ。
• https://thedollargame.io/ - Baker と Norine のドルゲームのバリエーションに基づいたゲーム。