メインコンテンツまでスキップ

付録I. 戦略モデル拡張(games 0.1)

本付録は,CADLの戦略モデル拡張を規定する。この拡張は,確率モデル拡張 (付録H)の上に成り立ち,model: ブロックにキー players:, profiles:,compliance:,payoffs:,equilibria: を,コマンドにキー owner: を,性質と モードマップにキー profile: を,kind: に値 smg を追加する。これにより,ファイルは, モデルのどのコマンドをどの当事者が選ぶか,各当事者が何を得るかを述べ,契約が求める振る舞いに 名前を付け,その振る舞いが単独の逸脱に対して均衡であるかを問うことができる。問いは,パラメータの 固定値において,またはパラメータの領域の上のマップとして立てる。

コア言語は,これらのキーを必須としない。本拡張を実装していないCADL準拠の処理系は, これらのキーを理由にファイルを拒否してはならない。キーを構文上は受理し,情報レベルの診断を 出すことが望ましい。

拡張の名前は games であり,本付録はバージョン 0.1 を記述する。本拡張は stochastic: 0.1 を 必要とする。ゲームは付録Hのモデルの上で行われるからである。本拡張を用いるファイルは, extensions:(A.2)で両方を宣言しなければならない。 宣言せずに用いた場合に処理系がどう扱うかはI.15で述べる。

sos:
...
extensions:
- stochastic: 0.1
- games: 0.1

本拡張は,規範拡張(付録F)には依存しない。戦略モデルの利得と規範の制裁との 関係は,付録Jが定める。

I.1 動機と範囲​

構成システムは運用と管理の独立性を保つため,構成システムが契約を遵守するのは,遵守が得になるときに 限られる(9.7節)。付録Hのモデルには,選択をする当事者がいない。どの モードモデルもマルコフ連鎖である。合理的検証は,マルチエージェントシステムの均衡の上で性質が 成り立つかを問い [Gutierrez+, AI 2020],確率的なシステムにも 拡張されている [Gutierrez+, KR 2021]。PRISM-gamesは,ターン制の 確率ゲームを検証し [Chen+, FMSD 2013],並行確率ゲームの均衡を計算する [Kwiatkowska+, TACAS 2022]。各プレイヤーがパラメトリックな マルコフ連鎖のパラメータの値を選ぶゲームについては,ナッシュ均衡が計算されている [Mu, QEST 2019]。パラメータリフティングは,パラメトリックな マルコフ決定過程を,2人のプレイヤーの確率ゲームを通して解析する [Quatmann+, ATVA 2016]。それが与えるのは,制御器が達成できることの界で ある。プロファイルが均衡であるかどうかは決定しない。RD-7.2が求めるのはマップ, すなわち,遵守が均衡となるλや他のパラメータの領域である。遷移確率がパラメトリックである 確率ゲームについてそのような領域を計算するツールと方法を探したが(検索語は,parametric stochastic games,Nash equilibrium,parameter synthesis,equilibrium region),見つからなかった。games 0.1では, RD-7.1とRD-7.2のうち,最初の小さな部分に取り組む。

  • ゲームは記述者が書く。 players: はプレイヤーを宣言し,コマンドの owner: はそれを誰が選ぶかを 述べ,payoffs: は各プレイヤーが何を得るかを,H.8の報酬構造から組み立てて述べる。契約や規範からは 何も導出しない。
  • 遵守は名前付きのプロファイルである。 profiles: は,記憶なしで決定的な戦略のプロファイルに 名前を付ける。compliance: は,そのうち,契約が求める振る舞いを表すものを名指す(I.4)。
  • 問いは厳密に定義する。 I.7は,ある付値において,名前付きのプロファイルが設計のナッシュ均衡で あるとは何か,すなわち,どのプレイヤーも単独でそこから逸脱して得をしないとは何か,および 各プレイヤーの逸脱利得を定義する。concept: every_reachable_state は,プレイヤーが自分の 逸脱で到達できるどの状態についても同じことを問う。I.9は均衡マップを定義する。これは パラメータの領域のセルからなり,各セルは,H.9の意味で equilibrium または not_equilibrium と 認証されるか,undecided のまま残る。本付録は,何が正しい答えであるかを定義し,処理系が計算できる 十分条件を与える。アルゴリズムは定めない。

バージョン0.1の範囲。

  • ゲームはターン制である。どの状態でも,選択をするプレイヤーは多くとも1人である(I-5)。 同時手番はなく,コマンドの同期もない。プレイヤーが同時に選ぶ場合,状態が1つのゲームでも均衡には 確率的な選択が必要になり,厳密な値は有理数とは限らなくなる。2人ゼロ和の同時手番確率ゲーム (ShapleyのゲームとEverettのゲーム。同時手番の到達ゲームは後者の特別な場合である)の値は, 無理数の代数的数になりうる[Hansen+, STOC 2011]。PRISM-gamesは, 同時手番確率ゲームについて,社会厚生または社会的公平性の点で最適な部分ゲーム完全ナッシュ均衡と 相関均衡を,非ゼロ和の確率と報酬の目的について計算する。期間が無限の目的については,値を値反復で 近似する[Kwiatkowska+, TACAS 2022]。I.6の利得は期間が無限であり, I.9の主張は厳密に,または健全な誤差限界とともに確立しなければならない。したがって,同時手番の ゲームは,そのような限界を与える方法ができるまで扱わない。
  • ファイルで名前を付ける戦略は,記憶なしで決定的である。すなわち,状態ごとに1つのコマンドを選ぶ。 混合戦略はないので,混合戦略による均衡に名前を付けることも,それを見つけることもできない。 有理数の確率を持つ定常で確率的なプロファイルに名前を付けた場合,単独の逸脱に対する検査は I.7の最適応答問題のままであり,厳密に決定できる。そのようなプロファイルを見つけることはできない。 到達目的を持つ多人数のターン制確率ゲームでは,利得に制約を付けた定常ナッシュ均衡が存在するかの 問題はNP困難であり,平方根和問題がこれに帰着し,定常均衡の利得は無理数になりうる。利得に制約を 付けたナッシュ均衡が存在するかの問題は,純粋戦略に限っても,10人のプレイヤーで決定不能である [Ummels & Wojtczak, LMCS 2011]。このため,バージョン0.1は 名前付きのプロファイルについてだけ問い,確率的なプロファイルの構文を持たない。
  • どのプレイヤーも状態の全体を観測する。部分観測のもとでの均衡は,αが制御するものであるが(RD-7.3), 未解決のままである。状態の全体を観測しない1人のプレイヤーの最適応答は,部分観測マルコフ決定過程で ある。そのような過程に,無限期間の期待総報酬(割引の有無を問わない)が閾値を超える方策が存在するかの 問題は決定不能である[Madani+, AI 2003]。このとき,名前付きの 1つのプロファイルを単独の逸脱に対して検査することさえ,一般には決定できない。有限個の記憶なしの 戦略に帰着させるI.7の議論が成り立たないからである。
  • プレイヤーは,それが代表するアクターの1人の代表であり,1つのアクター集合は多くとも1人のプレイヤーを 持つ(I-3)。1つのアクター集合の2つの要素,たとえば競合する2台のロボットを,2人のプレイヤーに することはできない。
  • 利得は,目標に達するまでに累積する期待報酬の重み付きの和である。対象とするのは,どの1人の プレイヤーもゲームを自分の目標から遠ざけ続けられないプロファイルである(I.6)。割引利得,平均利得,ステップ上限のある利得は定義しない。 有限の期間は,I.12の attempts のように,計数用の変数で書く。
  • 均衡の概念は,名前付きのプロファイルのナッシュ均衡と,到達可能などの状態からも均衡であること (I.7,concept:)であり,それぞれのε緩和を含む。部分ゲーム完全均衡,支配戦略,ゲームのすべての 均衡の集合,および性質がすべての均衡の上で成り立つかどうか(RD-7.1の問いの全体)は定義しない。 到達可能などの状態からも均衡であることが部分ゲーム完全性より弱い理由は,I.7で述べる。
  • 相関均衡としてモデル化する集中的な仲介者と,RD-7.2の集中化の価値は,範囲外である。相関均衡には, プレイヤーに組の選択を推奨する装置が必要であり,付録Hのモデルはそれを持たない。上に挙げた PRISM-gamesの方法は,同時手番のゲームについてこれを計算し,期間が無限の目的については値を近似する。
  • 均衡は設計ごとに問う。モード間の切替はゲームの一部ではない(H.1)。
  • 次のものを予約し,別の意味では用いない。コマンドのキー sync: と変数の owner:,model: の キー mediator: と observations:,equilibria: の項目のキー concept: の値 subgame_perfect と correlated,kind: の値 mdp,およびパラメータの出所 motivation.rho と motivation.kappa である。H.1が予約する名前のうち,本付録は players:,payoffs:,equilibria:,およびコマンドの owner: を定義する。

I.2 構文(H.2へのEBNFの追加)​

文法は付録Aの記法に従う。identifier,actor_ref,number は 付録Aで,state_pred,param_expr,interval はH.2で定義している。

model_block = ... ,
[ "kind:" , ( "dtmc" | "smg" ) ] ,
[ "players:" , { "-" , player_def } ] ,
[ "profiles:" , { identifier , ":" , { "-" , profile_rule } } ] ,
[ "compliance:" , identifier ] ,
[ "payoffs:" , { "-" , payoff_def } ] ,
[ "equilibria:" , { "-" , equilibrium_def } ] ;

player_def = "id:" , identifier ,
"actors:" , { "-" , actor_ref } ;

command_def = ... , [ "owner:" , identifier ] ;

profile_rule = [ "guard:" , state_pred ] , (* string *)
"choose:" , identifier ;

payoff_def = "player:" , identifier ,
"until:" , state_pred , (* string *)
"terms:" , { "-" , payoff_term } ;
payoff_term = "reward:" , identifier ,
[ "weight:" , param_expr ] ; (* string or number *)

property_def = ... , [ "profile:" , identifier ] ;
regime_map_def = ... , [ "profile:" , identifier ] ;

equilibrium_def = "id:" , identifier ,
[ "profile:" , identifier ] ,
[ "regimes:" , { "-" , identifier } ] ,
[ "epsilon:" , number ] ,
[ "over:" , { identifier , ":" , interval } ] ,
[ "resolution:" , number ] ,
[ "concept:" , ( "nash" | "every_reachable_state" ) ] ;

YAMLでの値の書き方。 H.2の規則を適用する。until: と guard: は引用符付きの文字列である (guard: はYAMLの真偽値 true または false でもよい)。weight: は,YAMLの数でも 引用符付きの文字列でもよい(weight: -1,weight: "-2 * lambda")。プロファイルの値は 空の列でもよい(comply: [])。YAML 1.1のローダが真偽値やnullとして読む名前(H.2)は, profiles: または over: のキーである位置では,引用符で囲まなければならない。

既定値。 プロファイルの規則の guard: は "true" である。weight: は 1 である。性質, モードマップ,equilibria: の項目の profile: は,遵守プロファイルである。equilibria: の項目の regimes: は,すべての設計である。epsilon: は 0 である。resolution: は 0.05 である。 concept: は nash である。

I.3 プレイヤーと所有​

kind: smg を持つモデルを戦略モデルという。kind: dtmc を持つか,kind: を持たないモデルは, 付録Hのモデルであり,本付録のキーを用いてはならない(I-2)。

model.players: は,プレイヤーを宣言する。各プレイヤーは,id と,それが代表する宣言済みの アクターのリスト actors: を持つ。1つのアクターを代表するプレイヤーは多くとも1人である(I-3)。 プレイヤーは,そのアクターが集合である場合も,モデルの1人の意思決定者を表す。I.12の "ROBOT[*]" は, 集合の任意の要素を代表する1台のロボットである。アクターへの対応付けは,本付録の意味論には影響しない。 付録Jは,これを用いて,利得を規範の負担者に関係付ける。

コマンドの owner: は,それを選ぶプレイヤーを名指す。owner: を持つコマンドは所有されているといい, 持たないコマンドは所有者がないという。所有者のないコマンドは,どのプレイヤーにも属さない。それは, 付録Hのすべてのコマンドと同じく,偶然または環境のステップである。所有されているコマンドは action: を 持たなければならず,1つのアクションラベルを持つコマンドは,すべて同じ所有者を持つか,すべて 所有者がないかのどちらかである(I-4)。したがって,アクションラベルはその所有者を定める。

設計 D(H.6)を固定する。状態 s において D のもとで有効な(H.5)コマンドの集合を En(s) と書く。 戦略モデルでは,H.10の規則S-9を,I-5で置き換える。S のどの状態でも,En(s) は次のいずれかである。

  • 空である。s はデッドロック状態であり,確率1でその状態にとどまる(H.5)。
  • 所有者のない1つのコマンドである。s は偶然状態である。
  • 同じプレイヤー p が所有する1つ以上のコマンドであり,それらのアクションラベルは互いに異なる。 s は p の状態であり,p がそのうちの1つを選ぶ。

これ以外の場合は許されない。p の状態のうち,有効なコマンドが1つであるものは,選択肢が1つの p の状態である。

I.4 戦略,プロファイル,遵守プロファイル​

設計 D におけるプレイヤー p の戦略とは,p の各状態に,En(s) のコマンドを1つ与える関数である。 本付録では,特に断らない限り,戦略はこの種類のものである。すなわち,記憶なしであり(現在の 状態だけに依存する),決定的である(1つのコマンドを確実に選ぶ)。D におけるプロファイルとは, 各プレイヤーに1つの戦略を与えるものである。プロファイル σ,プレイヤー p,p の戦略 τ について, σ[p↦τ] は,p が τ を用いることを除いて σ と一致するプロファイルである。

model.profiles: は,有限の記述でプロファイルに名前を付ける。名前付きのプロファイルは, 規則の順序付きのリストである。各規則は,アクションラベル(choose:)と状態述語(guard:。 既定値は真)を持つ。規則は,そのガードが s で真であり,かつ En(s) のあるコマンドがその アクションラベルを持つとき,状態 s で適用できるという。プロファイルは,プレイヤーの状態 s で, 次のコマンドを選ぶ。

  • リストの規則のうち,s で適用できる最初の規則のアクションラベルを持つ,En(s) のコマンド。
  • 適用できる規則がなく,En(s) のコマンドが1つであるときは,そのコマンド。

2つ以上のコマンドが有効である状態で,適用できる規則がないとき,ファイルは誤りである(I-6)。 すべてのプレイヤーの規則を1つのリストに書く。規則は,そのアクションラベルを所有するプレイヤーに 関するものである。したがって,名前付きのプロファイルは,どの設計においても,各プレイヤーに1つの 戦略を,到達可能かどうかにかかわらず S のすべての状態の上で定める。

model.compliance: は,遵守プロファイルを名指す。これは,記述者の宣言により,ファイルの契約が プレイヤーに求める振る舞いであるプロファイルである。戦略モデルでは必須である。本付録は,この宣言に, 既定値としての意味だけを与える。プロファイルを名指さない性質,モードマップ,equilibria: の項目は, 遵守プロファイルを参照する。本付録は,遵守プロファイルが何らかの規範を遵守していることを検査しない。 バージョン0.1は,規範とモデルの間の変換を定義しない(H.8)。ファイルが制裁を伴う規範も宣言するときに 処理系が何を検査できるかは,付録JのJ.7節に述べる。

I.5 意味論:誘導されるゲーム​

設計 D と,D が良定義(H.5)となるような,すべてのパラメータへの数の割当て θ を固定する。 f(c, j) と u(c, j) をH.7のとおりとし,コマンド c の更新 j のうち u(c, j)(s) = s′ であるものにわたる f(c, j)[θ] の和を,P(s, c, s′) と書く。ゲーム G(D, θ) は,H.7の状態 S と初期状態 s₀ を持つ。 プレイヤー p の状態では,p が En(s) のコマンド c を選び,次の状態は確率 P(s, c, s′) で s′ である。 偶然状態では,有効なただ1つのコマンドが取られる。デッドロック状態は,その状態にとどまる。

プロファイルのもとでのモデル。 プロファイル σ について,M(D, θ, σ) は,離散時間マルコフ連鎖 (S, s₀, P_σ) である。P_σ(s, s′) は,プレイヤーの状態 s では σ が選ぶコマンド c についての P(s, c, s′),偶然状態では有効なただ1つのコマンドについての P(s, c, s′) であり,デッドロック状態では P_σ(s, s) = 1 である。M(D, θ, σ) はH.7の意味でのモードモデルであり,プレイヤーの状態からの ステップは,選ばれたコマンドを,そのアクションラベルとともに取る。H.7からH.9が M(D, θ) について 定義するものはすべて,M(D, θ, σ) についても同じように定義される。パス,ステップの報酬,性質の値, 解関数,モードマップである。

戦略モデルの性質とモードマップ。 戦略モデルでは,model.properties: または model.regime_maps: の項目は,M(D, θ, σ) において評価する。σ は,その項目の profile: キーが 名指すプロファイルであり,既定値は遵守プロファイルである。その意味,結果,および認証の要求は, H.8とH.9のとおりである。したがって,戦略モデルのモードマップは,1つの固定したプロファイルのもとで モードを比較する。そのプロファイルが均衡であるかは問わない。

一般戦略。 I.7の定義は,ファイルで名前を付けられるものより多くの戦略を量化する。p の 一般戦略とは,s₀ から始まり p の状態 s で終わる,状態とコマンドの有限列のそれぞれに,En(s) の上の 確率分布を与えるものである。I.4の意味での戦略は,s だけに依存し,1つのコマンドに確率1を与える 特別な場合である。各プレイヤーに1つの一般戦略を与えると,θ とともに,状態とコマンドの無限列の上の 確率測度が,標準的な方法で誘導される [Puterman, 1994]。

I.6 利得​

model.payoffs: は,各プレイヤーにちょうど1つの利得を与える(I-7)。利得は,目標 until: φ と, 1つ以上の項を持つ。φ は状態述語であり,性質と同じようにラベルを用いてよい(H.4)。項は, model.rewards: の報酬構造 r(H.8)を名指し,weight: w を持つ。w は,数値リテラルと パラメータの上の param_expr である。重みは負であってよく,均衡マップで開いているパラメータを 含んでよい。報酬の value: は,引き続き負でなく(H.5),そのようなパラメータを含んではならない (I-9)。したがって,利益と費用は,符号が逆の重みを持つ項として書き,インセンティブの項は,その重みに λを持つ(weight: "-2 * lambda")。

パスについて,φ までの r の累積報酬とは,φ が最初に成り立つ位置より前のステップの報酬の和である (H.8)。その位置より後に起こることは数えない。p の利得の目標を φ_p と書く。各プレイヤーに1つの 一般戦略を与えたとき,p の利得は,p の利得の項 k にわたる次の和である。

u_p = Σ_k w_k[θ] · E[ accumulated reward of r_k until φ_p ]

ここで E は,誘導される測度のもとでの期待値である。プロファイル σ については,k 番目の項の期待値は, M(D, θ, σ) における問い合わせ R{"r_k"}=? [ F φ_p ] の値である。この利得を u_p(D, θ, σ) と書く。

プロファイルに対する1人のプレイヤーのゲーム。 I.7の問いでは,他のプレイヤーがプロファイル σ に 従う中で,1人のプレイヤーが逸脱する。プレイヤー p について,コマンドは,次のとき,状態 s で 許されるという。s が p の状態であり,コマンドが En(s) にあるとき。s が他のプレイヤーの状態であり, σ がそのコマンドを選ぶとき。s が偶然状態であり,コマンドがその有効なコマンドであるとき。 Reach_p(D, θ, σ)(Reach_p と書く)は,次のような列 s₀, …, s_n = s が存在する状態 s の集合である。 s₀, …, s_(n−1) のどれでも φ_p が成り立たず,各 s_(i+1) は,s_i で許されるあるコマンド c について, 正の確率 P(s_i, c, s_(i+1)) を持つ。これらは,p の利得がまだ累積している間に p が到達できる状態である。 φ_p が成り立つ状態は,このようにして到達されるとき Reach_p に属し,その先の状態は属さない。

許容できるプロファイル。 この定義には,どの期待値も有限であることが必要であり,また,プレイヤーが, ゲームを自分の目標から遠ざけ続けることによって,利得を無限大や未定義にできてはならない。 プロファイル σ は,p のどの戦略 τ についても,M(D, θ, σ[p↦τ]) における F φ_p の確率が1であるとき, θ において p について許容できるという。すべてのプレイヤーについて許容できるとき,θ において 許容できるという。許容できるかどうかは,どの確率 P(s, c, s′) が正であるかだけに依存し, グラフによる特徴付けを持つ。σ が p について許容できるのは,次のような空でない集合 E が存在しないとき, かつそのときに限る。E は,Reach_p の状態のうち φ_p が成り立たないものからなり,E のどの状態も, デッドロック状態であるか,正の確率を持つ後続状態がすべて E にある許されるコマンドを持つ。 (そのような集合は,目標が成り立たないデッドロックであるか,目標を避ける終端成分である。) 処理系は,これを Reach_p のグラフの上で決定する。Reach_p の状態のうち φ_p が成り立たないものから 始めて,デッドロック状態でなく,正の確率を持つ後続状態がすべて残っているような許されるコマンドを 持たない状態を,そのような状態がある限り取り除く。σ が p について許容できるのは,状態が1つも 残らないとき,かつそのときに限る。

σ が p について許容できるとき,σ に対する p のどの一般戦略のもとでも,Reach_p のどの状態からも, φ_p に確率1で達し,それまでの期待ステップ数は有限である。有限のマルコフ決定過程で状態の集合に 到達する最小の確率は,記憶なしで決定的な方策によって達成されるからである [Baier & Katoen, 2008](第10章)。このとき,p が何をしても,p の利得は 実数である。この言明は Reach_p だけに関するものである。φ_p が成り立った後にだけ到達できる状態は, デッドロック状態であっても,閉路の上にあってもよく,それは害にならない。

I.7からI.9は,設計が良定義(H.5)であり,プロファイルが許容できる付値で,そのプロファイルについて 定義される。θ において許容できないプロファイルは,そこでは均衡に関する判定を持たない。I-8は, 固定値で許容できることを要求する。均衡マップの領域の上で何を要求するかは,I-9とI.9が述べる。 許容できることは,すべてのプロファイルのもとでゲームが終わることを要求するより弱い。問われている プロファイルからの,1人ずつのプレイヤーの逸脱に関するものだからである。

I.7 均衡​

θ において良定義である設計 D と,θ において許容できるプロファイル σ を固定する。

ナッシュ均衡。 σ は,どのプレイヤーも単独で逸脱して得をしないとき,θ における D の ナッシュ均衡である。すなわち,どのプレイヤー p と,p のどの一般戦略 τ についても,p が τ を 用い,他のすべてのプレイヤーが σ のとおりに振る舞うときの p の利得が,u_p(D, θ, σ) 以下である。 この概念は,ファイルで名前を付けたプロファイルからの,単独の逸脱だけに関するものである。

記憶なしで決定的な逸脱で十分である。 他のプレイヤーが σ のとおりに振る舞うとき,残るのは, Reach_p の上で p だけが選択をする有限のマルコフ決定過程である。その報酬は,ステップごとに ρ_p(s, c) = Σ_k w_k[θ] ·(s で c を取ることに対する r_k の報酬)であり,符号は正負どちらでもよく, φ_p まで累積する。[Bertsekas & Tsitsiklis, 1991]の確率的最短経路問題は, 費用を −ρ_p とし,φ_p の状態を終点とした,この問題である。その2つの仮定は,固有な定常方策 (どの状態からも確率1で終点に達する方策)が存在すること,および,固有でないどの定常方策も, ある状態から無限大の費用を持つことである。費用の符号は正負どちらでもよい。これらの仮定のもとで, 最適費用はベルマン方程式のただ1つの解であり,定常で決定的な方策によって達成される。ここでは, σ が p について許容できるので,どの定常方策も固有である。したがって,第1の仮定は成り立ち, 第2の仮定は空虚に成り立つ。履歴に依存する方策や確率的に選ぶ方策も,それより多くを達成しない。 そのようなどの方策と初期状態についても,ステップと現在の状態だけに依存し,どのステップでも状態と コマンドのどの組の確率も同じである,確率的に選ぶ方策が存在し ([Puterman, 1994],5.5節),したがって期待総報酬も同じである。 そして,ある状態で確率的に選んでも,ベルマン方程式におけるコマンドにわたる最大値を超えない。 したがって,最適応答値

BR_p(D, θ, σ) = max over the strategies τ of p of u_p(D, θ, σ[p↦τ])

は,I.4の意味での有限個の戦略にわたる最大値であるが,p のすべての一般戦略にわたる上限に等しい。 そして,σ が θ における D のナッシュ均衡であるのは,どのプレイヤー p についても BR_p(D, θ, σ) = u_p(D, θ, σ) であるとき,かつそのときに限る。このように,「σ はナッシュ均衡である」 という主張は,プロファイルそのものは記憶なしで決定的であるが,すべての一般戦略による逸脱を対象とする。 プレイヤー自身が確率的に選んだり記憶を用いたりする均衡については,何も述べない。

逸脱利得。 p の逸脱利得は,次のとおりである。

gain_p(D, θ, σ) = BR_p(D, θ, σ) − u_p(D, θ, σ)

σ における p 自身の戦略が候補に含まれるため,これが負になることはない。 u_p(D, θ, σ[p↦τ]) = BR_p(D, θ, σ) である p の戦略 τ を,σ に対する p の最適応答という。

ε均衡。 数 ε ≥ 0 について,σ は,どのプレイヤー p についても gain_p(D, θ, σ) ≤ ε であるとき, θ における D のε均衡である。ナッシュ均衡は0均衡である。ε は,各プレイヤーの利得と, その利得自身の単位で比べる。本付録は,異なるプレイヤーの単位を互いに関係付けない。

付値における決定。 θ において σ を検査することは,プレイヤーごとに1つの最適応答問題からなる。 マルコフ連鎖 M(D, θ, σ) で u_p を評価し,Reach_p の上の p のマルコフ決定過程を解いて BR_p を求める。 パラメータが有理数であるとき,どちらも,有理数の上の連立1次方程式と方策反復によって厳密に解ける。

状態からの値。 Reach_p の状態 s について,s₀ の代わりに s から始めたゲームでの,σ のもとでの p の利得を V_p(s),p の最適応答値を V*_p(s) と書く。s で φ_p が成り立つとき,どちらも0である。 Reach_p の状態 s のうち φ_p が成り立たないものと,s で許されるコマンド c について,次のように書く。

Q_p(s, c) = ρ_p(s, c) + Σ_s′ P(s, c, s′) · V_p(s′)
Q*_p(s, c) = ρ_p(s, c) + Σ_s′ P(s, c, s′) · V*_p(s′)

Q_p(s, c) は,s で1回だけ c を取り,その後は σ に従うときの p の利得である。V*_p は, V*_p(s) = 許されるコマンド c にわたる Q*_p(s, c) の最大値,のただ1つの解であり, BR_p = V*_p(s₀) である。

到達可能などの状態からも均衡。 σ は,どのプレイヤー p と Reach_p のどの状態 s についても V*_p(s) = V_p(s) であるとき,θ において到達可能などの状態からも均衡であるという。すなわち, どのプレイヤーも,Reach_p のどこから逸脱を始めても,単独の逸脱で得をしない。数 ε ≥ 0 について, どのプレイヤー p と Reach_p のどの状態 s についても V*_p(s) − V_p(s) ≤ ε であるとき,σ は 到達可能などの状態からもε均衡であるという。p の状態逸脱利得

sgain_p(D, θ, σ) = Reach_p の状態 s についての V*_p(s) − V_p(s) の最大値

は,これらの差の最大値である。s₀ は Reach_p に属するので,これは gain_p 以上である。したがって, 到達可能などの状態からも均衡であれば,ナッシュ均衡である。逆は成り立たない。p 自身が逸脱したときに だけ到達する状態で p が得をし得る場合にも,σ はナッシュ均衡であり得る。equilibria: の項目に concept: every_reachable_state を書くと,この概念を問う(I.8,I.9)。既定の概念 nash の結果は, 途中でこれを確立したとき,それを from_every_state として報告する。

部分ゲーム完全性より弱いこと。 プロファイルが部分ゲーム完全であるとは,以前に誰が逸脱したかに かかわらず,どの状態から始めたゲームでも均衡であることである。到達可能などの状態からも均衡である ことは,2つの点でこれより少なく求める。第1に,Reach_p は,他のプレイヤーが σ に従う間に p が自分の 逸脱で到達する状態だけを含む。別のプレイヤー q が逸脱したときにだけ到達する状態は Reach_q に属し, そこでは q の逸脱利得だけを調べる。その状態は Reach_p には属さない。第2に,Reach_p の状態が別の プレイヤー q のものであるとき,σ が q に選ぶコマンドは固定されており,その状態が Reach_q にも 属するのでなければ,q 自身の利害に照らして調べることはない。したがって,プレイヤーが実行しない 脅しは検出されない。例(このファイルはリファレンス実装のテストのデータである)。A は out(A の 利得は1,B の利得は3)か enter を選ぶ。enter の後で,B は fight(両者とも −1)か share (両者とも2)を選ぶ。プロファイル (out; fight) は,到達可能などの状態からも均衡である。enter の後の 状態は Reach_A に属し,A は参入しても得をしない。この状態は Reach_B には属さない。プロファイルの もとでは A が参入しないからである。このプロファイルは部分ゲーム完全ではない。enter の後の状態で, B は分け合うことで3だけ得をする。部分ゲーム完全性を問い合わせとして提供しないのは,別のプレイヤーの 逸脱でしか到達しない状態からは,プレイヤーの利得が一般には定義されないからである。許容性(I.6)は プレイヤー自身の逸脱にかかわるものであり,そのような状態からは,別のプレイヤーがゲームを目標から 遠ざけ続けられることがある。定義するには,まず,どのプロファイルがどの状態から許容できなければ ならないかを定める必要がある。

1ステップ検査。 Reach_p のどの状態 s についても V*_p(s) = V_p(s) であるのは,Reach_p にある p の状態 s のうち φ_p が成り立たないものと,En(s) のコマンド c のすべてについて Q_p(s, c) ≤ V_p(s) で あるとき,かつそのときに限る。不等式が成り立てば,V_p はベルマン方程式を満たし,その解はただ1つである。 ある s で成り立たなければ,s で1回 c を取ることで,s から得をする。したがって,この検査は, 「p は Reach_p のどの状態からも得をしない」ことの必要十分条件であり,gain_p = 0 の十分条件であるが, 必要条件ではない。

報告する最適応答。 p の最適応答のうち,標準の最適応答とは,次の戦略である。Reach_p にある p の状態 s のうち φ_p が成り立たないものでは,σ が選ぶコマンド c について Q*_p(s, c) = V*_p(s) で あればそれを選び,そうでなければ,model.commands: の順で,Q*_p(s, c) = V*_p(s) である En(s) の 最初のコマンド c を選ぶ。他のどの状態でも,σ が選ぶものを選ぶ。これは最適応答であり,ファイルによって 定まり,σ のコマンドが最適でないところでだけ σ と異なる。

I.8 固定値での均衡検査​

model.equilibria: は,均衡問い合わせを列挙する。over: のない項目は均衡検査である。 これは,regimes: に挙げた各設計(既定値はすべての設計)について,profile: が名指すプロファイル (既定値は遵守プロファイル)が,すべてのパラメータの固定値(H.3)において,その設計のε均衡であるかを 問う。ε は epsilon: で与える(既定値は0)。transitions: のないファイルでは,設計は base だけで ある(H.6)。このとき,regimes: は省略するか,[base] とする。

結果は,設計ごとに,次のものからなる。

  • 各プレイヤー p について,利得 u_p,最適応答値 BR_p,逸脱利得。
  • status。どの逸脱利得も ε 以下であるとき equilibrium,そうでないとき not_equilibrium である。
  • not_equilibrium の場合は,逸脱利得が ε を超えるプレイヤーの空でない集合 deviators と, そのそれぞれについての標準の最適応答(I.7)。最適応答は,σ[p↦τ] のもとで φ_p が成り立つ前に 初期状態から到達可能であり,かつそれがプロファイルと異なるコマンドを選ぶ状態のリストとして, S の順(変数は宣言の順,値はその定義域の順)に,それぞれに選ばれたアクションラベルを添えて示す。
  • from_every_state。プロファイルが到達可能などの状態からも均衡である(I.7)ことを処理系が確立した とき true,そうでないことを確立したとき false,その問いを調べていないときは,なしまたは null である。これは,status が equilibrium であり,ε = 0 であるときにだけ報告する。

概念 every_reachable_state。 concept: every_reachable_state のとき,検査は,プロファイルが 到達可能などの状態からもε均衡であるか(I.7)を問う。結果は上と同じであり,次の点だけが異なる。 status は,どの状態逸脱利得も ε 以下であるとき equilibrium である。deviators は,状態逸脱利得が ε を超えるプレイヤーである。どのプレイヤーも状態逸脱利得を持ち,逸脱者であるときは状態 s も持つ。 s は,Reach_p の状態のうち,S の順で最初の,V*_p(s) − V_p(s) が状態逸脱利得に等しい状態である。 逸脱者の標準の最適応答は,s₀ の代わりに s から σ[p↦τ] のもとで φ_p が成り立つ前に到達可能な状態の 上で示す。標準の最適応答は,Reach_p のどの状態でも最適なコマンドを選ぶので,Reach_p のどの状態からも 最適であり,s からのその利得は,V_p(s) を状態逸脱利得だけ上回る。from_every_state の意味は 変わらない。

I-8により,プロファイルは固定値で許容できる。他の値で検査を評価する処理系(I.13)は,まず,そこで 設計が良定義であり,プロファイルが許容できることを確立し,そうでなければ誤りを報告する。

結果を報告する処理系は,それを厳密な算術で,または健全な誤差限界を持つ数値計算で計算するか, 結果を近似であると明示しなければならない。誤差限界によって決まらない status は inconclusive である (H.8と同じ)。

I.9 均衡マップ​

model.equilibria: の項目のうち over: を持つものは,均衡マップ問い合わせである。そのキーは 次のとおりである。

  • over: は,開いているパラメータを与える。H.9と同じく,少なくとも1つ,多くとも4つであり, それぞれに宣言範囲の中の閉区間 [lo, hi],lo < hi を与える。領域 B は,これらの区間がなす 直方体である。over: のパラメータには,model.regimes: のどのモードも値を割り当ててはならず, また,そのパラメータは報酬の value: に現れてはならない。確率と重みには現れてよい。 制度パラメータも他のパラメータと同じように開くことができる。λの上のマップは,lambda に束縛した パラメータを開いて求める。
  • profile:,regimes:,epsilon:,concept: は,I.8のとおりである。
  • resolution: は,0 < r < 1 である数 r であり,設計ごとに,B の体積のうち未決定のまま 残ってよい割合である。

設計 D と付値 v ∈ B について,θ(v) は,開いているパラメータでは v と一致し,それ以外では D の固定値を 持つ(H.7)。問い合わせのプロファイルについて,θ(v) における D での p の利得,最適応答値,逸脱利得を, U_p(v),BR_p(v),gain_p(v) と書き,状態逸脱利得と Reach_p の状態 s からの値(I.7)を sgain_p(v), V_p(s, v),V*_p(s, v) と書く。これらは,θ(v) において D が良定義であり,プロファイルが 許容できるところで定義される。

問い合わせの内容。 挙げた各設計について,B のどの付値でプロファイルがε均衡であるかを問う。 セルとは,B に含まれる閉じた直方体である(H.9)。

  • プロファイルは,すべての v ∈ C において,θ(v) で D が良定義であってプロファイルが許容でき, どのプレイヤー p についても gain_p(v) ≤ ε であるとき,セル C の上で均衡である。
  • プレイヤー p は,すべての v ∈ C において,θ(v) で D が良定義であってプロファイルが許容でき, gain_p(v) > ε であるとき,セル C の上で逸脱者である。

concept: every_reachable_state では,どちらの定義でも gain_p を sgain_p に置き換える。すなわち, C のすべての v で,どのプレイヤーについても sgain_p(v) ≤ ε であるとき,プロファイルは C の上で 均衡であり,C のすべての v で sgain_p(v) > ε であるとき,p は C の上で逸脱者である。このとき, 逸脱者が得をする状態は付値によって異なることがある。また,確率がある付値では0で別の付値では正で あることがあるので,Reach_p 自体がセルの中で変わることがある。

結果。 答えは,挙げた設計ごとに1つの均衡マップからなる。均衡マップは,B を覆い,内部が互いに 交わらない有限個のセルの集合であり,各セルは status を持つ。これに,未決定の割合(undecided の セルの体積を B の体積で割ったもの)と,それが resolution: 以下であるかどうかを添える。

status主張ともに報告するもの
equilibriumプロファイルは,セルの上で均衡であるfrom_every_state(後述)
not_equilibriumdeviators のどのプレイヤーも,セルの上で逸脱者であるdeviators(プレイヤーの空でない集合)
undecidedなしreason

deviators は,セルのすべての付値で得をするプレイヤーだけを含む。処理系は,それを確立したプレイヤーを すべて挙げることが望ましい。逸脱者が入れ替わる面をまたぐセルでは,どの付値でも誰かが得をするが, セル全体で得をする1人のプレイヤーはいない。そのようなセルは,細分によって部分が分かれるまで undecided のままである。処理系は,not_equilibrium のセルについては,方法がそれを与えるとき (後述の条件Nは与える),各逸脱者について,セルのすべての付値で ε を超えて得をする戦略も報告することが 望ましく,決定したどのセルについても,確立した逸脱利得の上下界を報告することが望ましい。 concept: every_reachable_state では,戦略を,それが得をする状態 s(後述の条件N_sにより,セルの すべての付値で Reach_p に属する)と,その逸脱利得の下界とともに報告する(deviation_states)。 from_every_state は,equilibrium のセルについて,プロファイルがセルのすべての付値で 到達可能などの状態からも均衡である(I.7)ことを処理系が確立したとき true であり,そうでなければ, なしまたは null である。セルについては,このフィールドは ε に依存しない。それは逸脱利得が0で あることについての言明であり,ε均衡の主張より強いので,ε > 0 のときにも true であってよい。

undecided のセルは,reason を持つことが望ましい。not_well_defined(設計がセルの上で良定義である ことを,処理系が確立していない),not_admissible(プロファイルがセルの上で許容できることを確立して いないか,許容できない付値を見つけた),bounds(上下界がセルを決定しないか,予算を使い切った)の いずれかである。

プロファイルがε均衡である付値と,そうでない付値の両方を含むセルは,どちらの status も持てない。 I.12のλ*のように,2種類の付値が接するところでは,分割をどれほど細かくしても,そのようなセルが 残る。resolution: が0より大きいのはこのためである。

処理系は,複数のセルの和集合が直方体であり,主張がそのどの部分でも成り立つとき,その和集合を 1つのセルとして報告してよい。すなわち,status が同じであること。not_equilibrium では, deviators は,どの部分の逸脱者の集合の空でない部分集合でもあり,逸脱は,その逸脱者についてどの部分でも 同じ戦略が報告されているときにだけ報告すること。from_every_state: true は,どの部分もそれを持つ ときにだけ報告すること。gain_bounds は,それらを包む範囲とすること。

同じ領域の上の複数の設計のマップは,「どのモードで,どこで,プロファイルが均衡であるか」に答える。 2つの設計のセルは一致しなくてよい。処理系は,マップを共通の細分の上で報告してよい。

認証付き。 equilibrium と not_equilibrium は,セルのすべての付値についての主張であり, H.9の認証の要求が適用される。処理系は,セル全体について健全な方法により,厳密な算術または健全な 誤差限界を持つ数値計算で確立した場合を除いて,これらの主張をしてはならない。標本点での評価は, それだけではそのような方法ではない。resolution: に算入するのは,認証付きのセルだけである。 要求された分解能に達することができない処理系も,マップを報告し,達しなかったことを述べる。処理系は, 方法の名前を示すことが望ましい。標本点での推定は,H.9と同じく,分けて報告してよい。推定がセルの status を変えることはない。

領域の上での良定義性と許容性。 これらの主張は,セルの上でI.7が定義されていることを前提とする。 処理系は,セルのすべての付値において,設計が良定義(H.5)であり,プロファイルが許容できる(I.6)ことを 確立した場合を除いて,セルについて equilibrium または not_equilibrium を主張してはならない。

許容性については,直方体の頂点を検査するだけでは足りない。確率は,直方体の内部で正であり,頂点で 0であることがある。したがって,頂点でグラフが最も小さく,内部で最も大きい。確率がすべて, 開いているパラメータについて多重アフィンである設計(rest の値を含めて,どの確率にも, 開いているパラメータが1より高いべきで現れない)では,次が成り立つ。直方体 B の面とは,開いている パラメータのいくつか(0個でもよい)をその区間の端に固定し,残りのそれぞれを,その両端の間の開区間の上で 動かして得られる集合である。開いているパラメータが n 個のとき,B は 3ⁿ 個の面を持ち,B のどの付値も, そのちょうど1つに属する。設計が B の頂点で良定義であれば,確率は,ある面のどの付値でも,その面の 頂点での値の正の係数による結合である。したがって,確率が面の1つの付値で0であるのは,面全体で0である ときに限る。ゆえに,ゲームのグラフは,1つの面のすべての付値で同じであり,許容性はグラフだけに 依存するので,次が成り立つ。

確率が開いているパラメータについて多重アフィンであり,B の頂点で良定義である設計では, プロファイルが B のすべての付値で許容できるのは,B の 3ⁿ 個の面のそれぞれの中心(開いている どのパラメータも,その区間の下端,中点,上端のいずれかにある付値)で許容できるとき, かつそのときに限る。

I-9は,この検査を要求する。そのような設計では,面の中心での失敗は,その面のどの付値でも プロファイルが許容できないことを意味する。したがって,退化した端に接する領域,たとえば lo で 成功確率が0である再試行ループを持つ領域は,ファイルの誤りであり,記述者は区間を縮める。そのような 設計でこの検査が成功すれば,プロファイルはどのセルの上でも許容でき,許容性については,セルごとに 確立すべきことは残らない。ただし,上下界を与える方法は,なおセルの上で失敗することがある。たとえば, そのような面に接するセルの上での緩和である。そのセルは,理由 bounds で undecided である。 したがって,未決定のセルの理由 not_admissible は,多重アフィンでない設計でだけ生じる。多重アフィンでない確率を持つ設計では,処理系は, たとえば後述の緩和によって,セルごとに許容性を確立するか,理由 not_admissible を付けてセルを undecided のままにする。

上下界によるセルの決定。 プレイヤー p とセル C について,R_C(p) を,次のような状態の集合とする。 s₀ を含み,φ_p が成り立たない状態 s を含むならば,p について s で許される(I.6)あるコマンド c に ついて,C のある付値で P(s, c, s′) が正である状態 s′ をすべて含む。R_C(p) は,C のどの付値における Reach_p も含む。ある方法が,各プレイヤー p について,C のすべての付値 v で成り立つ次の数を与えるとする。

  • l_p ≤ U_p(v) ≤ u_p。プロファイルのもとでの利得の上下界である。
  • b_p ≥ BR_p(v)。最適応答値の上界である。また,R_C(p) の各状態 s について,s が Reach_p の状態で あるような C のどの v についても b_p(s) ≥ V*_p(s, v) を満たす数 b_p(s)。
  • p の1つ以上の戦略 τ について,d_p(τ) ≤ U_p(τ, v)。p が τ を用いるプロファイルのもとでの p の利得の下界である。また,R_C(p) の状態 s から始めたゲームでのその利得の下界 d_p(τ, s)。 これは,s が Reach_p の状態であるような C のどの v についても成り立つ。
  • R_C(p) の各状態 s について,数 l_p(s) と u_p(s)。これらは,C のどの v と,θ(v) における Reach_p の どの状態 s についても,l_p(s) ≤ V_p(s, v) ≤ u_p(s) を満たす(s で φ_p が成り立つときは,どちらも0)。 および,R_C(p) にある p の状態 s のうち φ_p が成り立たないものと,En(s) の各コマンド c について, 数 q_p(s, c)。これは,s が θ(v) における Reach_p の状態であるような C のどの v についても, q_p(s, c) ≥ Q_p(s, c, v) を満たす。s に到達できない付値では,V_p(s, v) は存在するとは限らず, 何も要求しない。そのような数は,C の上でのステップ利得 ρ_p(s, c) の上界と,後続状態の 上界 u_p(s′) から得られる。すなわち,q_p(s, c) は,コマンドが C の上で取り得るどの分布 μ に ついても,ρ_p(s, c) + Σ_s′ μ(s′) · u_p(s′) 以上である。

このとき,次が成り立つ。

  • N. p のある戦略 τ について d_p(τ) − u_p > ε であるとき,p は C の上で逸脱者である。
  • E1. b_p − l_p ≤ ε であるとき,C の上で gain_p(v) ≤ ε である。
  • E2. R_C(p) にある p の状態 s のうち φ_p が成り立たないものと,En(s) のコマンド c のうち プロファイルが選ぶもの以外のすべてについて q_p(s, c) ≤ l_p(s) であるとき,C のどの付値でも, Reach_p のどの状態 s についても V*_p(s, v) = V_p(s, v) であり,特に C の上で gain_p(v) = 0 である (I.7の1ステップ検査。逸脱するコマンドの上界を,同じ状態でのプロファイルの下界と比べる)。
  • どのプレイヤーもE1またはE2を満たすとき,プロファイルは C の上で均衡である。どのプレイヤーも E2を満たすとき,プロファイルは,C のすべての付値で,到達可能などの状態からも均衡である (from_every_state: true)。

concept: every_reachable_state では,E2はそのまま使え,E1はどの状態でも求め,Nには状態を名指す 条件を加える。R⁺_C(p) を,次のような状態の集合とする。s₀ を含み,φ_p が成り立たない状態 s を含む ならば,p について s で許されるあるコマンド c について,C のすべての付値で P(s, c, s′) が正である 状態 s′ をすべて含む。許されるコマンドは付値に依存しないので,それを加えた道に沿った帰納法により, R⁺_C(p) のどの状態も,C のすべての付値で Reach_p に属する。開いているパラメータについて多重アフィンで ある確率は,C のすべての頂点で正であれば C の上で正である。C の付値でのその値は,頂点での値の凸結合 だからである。それ以外の確率は,C の上での厳密な区間による囲みの下端が正であれば,C の上で正である。 C の頂点で0である確率は,C の他の付値で正であっても数えない。

  • E1*. R_C(p) の状態 s のうち φ_p が成り立たないものすべてについて b_p(s) − l_p(s) ≤ ε である とき,C の上で sgain_p(v) ≤ ε である。どの v でも,Reach_p のどの状態 s も R_C(p) に属し, V*_p(s, v) − V_p(s, v) は b_p(s) − l_p(s) 以下である。
  • N_s. R⁺_C(p) の状態 s で φ_p が成り立たないものと,p の戦略 τ があって,d_p(τ, s) − u_p(s) > ε であるとき,p は C の上で逸脱者である。どの v でも,s は Reach_p に属し,s からの τ の利得は V_p(s, v) を ε より多く上回るので,sgain_p(v) > ε である。Nは s = s₀ の場合である。
  • どのプレイヤーもE1*またはE2を満たすとき,プロファイルは C の上で均衡である。NまたはN_sを満たす プレイヤーは,C の上で逸脱者である。ε = 0 のとき,この概念の均衡のセルは,すべての付値で 到達可能などの状態からも均衡である(from_every_state: true)。

R⁺_C(p) がなければ,N_sは健全でない。セルの中心で到達可能な状態が,そこへ至る確率が0になる頂点では 到達できないことがあり,そこではプロファイルが到達可能などの状態からも均衡であることがある。

これらの条件は十分条件であり,必要条件ではない。E1は,H.9の条件と同じく,ある関数の界を別の関数の 界と比べる。しかも,ここでは2つの関数が接する。どこでも BR_p(v) ≥ U_p(v) であり,p が得をしない ところでは等号が成り立つ。したがって,ε = 0 では,E1が成り立つのは,U_p がセルの上で定数であり, かつ両方の界が厳密であるときに限られる。開いているパラメータが,プロファイルのもとで0である項の 重みにだけ現れるとき,たとえばI.12のλの場合は,これに当たる。開いているパラメータがプロファイルの もとでの利得を変えると,もはやこれに当たらない。E2にはこの欠点がない。E2は,1ステップの逸脱の利得を, 同じ状態でのプロファイルの利得と比べる。逸脱が真に損をする付値では,この2つは異なる。E2は, 問われていること以上を確立する。そのため,p 自身の逸脱だけが到達する状態で p が得をし得るような ナッシュ均衡のセルでは,E2は成り立たない。境界に接するセルは,3つの条件のどれによっても undecided のままである。

パラメータリフティングによる上下界(参考)。 H.14の緩和は,プロファイルに対する1人のプレイヤーの ゲームに拡張できる。セルの上で,各状態が,他の状態とは独立に,その許されるコマンドのそれぞれについて 分布を1つ選ぶ。調べているプレイヤーの状態は,それに加えてコマンドも選び,他のプレイヤーの状態は, プロファイルが選ぶコマンドを取る。コマンドの確率が開いているパラメータについて多重アフィンであるとき, 選べる分布はセルの頂点での分布であり,セルのどの付値での分布も,それらの混合である。多重アフィンで ないときは,頂点では足りない。H.14に述べるように,各確率をセルの上の区間で囲み,状態は,それらの区間の 中の分布の集合の頂点を選ぶ。ステップの利得 ρ_p(s, c) は,セルの上での最小値と最大値で囲む(重みが 開いているパラメータについて多重アフィンであるときは頂点での値,そうでないときは区間演算による)。 緩和した過程で到達可能な状態は,集合 R_C(p) をなす。緩和した過程のどの方策も確率1で φ_p に達するとき, プロファイルは,セルの上で p について許容できる。上側のステップ利得を用いた過程の最大値が数 b_p であり, プレイヤーのコマンドを τ またはプロファイルで固定し,下側と上側のステップ利得を用いた最小値と最大値が, 数 d_p(τ),l_p,u_p である。R_C(p) の各状態を初期状態とすれば,l_p(s) と u_p(s) が得られる。 条件Nの戦略 τ は,たとえば,セルの中心における p の標準の最適応答(I.7)を,そこでそれのもとで到達 可能な状態に制限したものとして選べる。この選び方が,領域のどれだけが not_equilibrium になるかを 左右する。N_sには,中心での Reach_p 全体の上の同じ戦略を使い,d_p(τ, s) を s からの緩和した過程の 最小値とし,報告する戦略を,緩和した過程がそれのもとで s から到達する状態に制限したものとできる。 他の健全な方法も認められる。たとえば,有理関数 U_p と BR_p の上の厳密な推論や,次に述べるセルの 端点による認証である。後者は,逸脱利得があるパラメータについて凸または単調であることを証明する。 次に述べる条件PD+とPD−は,1ステップの優位を通して逸脱利得を直接に抑える。

1ステップの優位による条件。 R_C(p) にある p の状態 s のうち φ_p が成り立たないもの,En(s) の コマンド c,および s が Reach_p の状態であるような C の付値 v について,優位を次で定める。

A_p(s, c, v) = Q_p(s, c, v) − V_p(s, v)

これは,s で c を1回取り,その後はプロファイルに従うときの得である。プロファイルが選ぶコマンドでは 0である。p の戦略 τ と,θ(v) における Reach_p の状態 s について,p が τ を用い,他のプレイヤーが プロファイルに従うとき,s から始めたゲームでの p の利得を U_p(τ, s, v) と書く。性能差の恒等式は 次を述べる。

U_p(τ, s, v) − V_p(s, v) = E[ Σ_t A_p(s_t, c_t, v) ]

ここで,期待値は σ[p↦τ] のもとで s から φ_p までの道についてとり,s_t はステップ t の状態,c_t は そこで取るコマンドである。他のプレイヤーの状態でのステップと,τ がプロファイルのコマンドを選ぶ 状態でのステップは,0を加える。証明. s_t と c_t が与えられたとき,ρ_p(s_t, c_t) + V_p(s_(t+1), v) の期待値は Q_p(s_t, c_t, v) である。したがって,優位の和の期待値は,p の累積利得から V_p(s, v) を 引き,φ_p が初めて成り立つ状態での V_p の値を加えたものであり,その値は0である。道のどの状態も Reach_p に属し,プロファイルが許容できるので(I.6),ステップ数の期待値は有限である。∎ V*_p(s, v) − V_p(s, v) は,p の戦略 τ にわたるこれらの期待値の最大値である(I.7)。

ある方法が,そのような各 s と,プロファイルが選ぶもの以外の各コマンド c について,s が Reach_p の 状態であるような C のどの v でも a⁻_p(s, c) ≤ A_p(s, c, v) ≤ a⁺_p(s, c) を満たす数を与えるとする。 プロファイルのコマンドと他のプレイヤーの状態では,どちらも0とする。g⁺_p(s) を,p のすべての戦略と, s が Reach_p の状態であるような C のすべての v にわたる,s からの道に沿った a⁺_p の和の期待値の上界と する。g⁻_p(τ, s) を,それらの v にわたる,s からの τ の道に沿った a⁻_p の和の期待値の下界とする。 このとき,次が成り立つ。

  • PD+. g⁺_p(s₀) ≤ ε であるとき,C の上で gain_p(v) ≤ ε である。concept: every_reachable_state では,R_C(p) の状態 s のうち φ_p が成り立たないものすべてについて g⁺_p(s) ≤ ε であるとき,C の上で sgain_p(v) ≤ ε である。それらの状態すべてについて g⁺_p(s) ≤ 0 であるとき,E2のもとでと同じく, C のどの付値でも,Reach_p のどの状態 s についても V*_p(s, v) = V_p(s, v) である。
  • PD−. p のある戦略 τ について g⁻_p(τ, s₀) > ε であるとき,p は C の上で逸脱者である。 concept: every_reachable_state では,R⁺_C(p) の状態 s で φ_p が成り立たないものについて g⁻_p(τ, s) > ε であるときも,そうである。

PD+はE1またはE1*の代わりに,また from_every_state についてはE2の代わりに使える。PD−はNまたは N_sの代わりに使える。これらの条件も十分条件であり,必要条件ではない。E1やNと異なり,ある戦略の もとでの利得の界を,別の戦略のもとでの利得の界と比べないので,セルの上での U_p の変動が2回入る ことはない。プロファイルのコマンドを σ(s) とすると,V_p(s, v) = Q_p(s, σ(s), v) である。両方の分布の 和は1なので,どの数 m についても次が成り立つ。ρ_p と P は v での値である。

A_p(s, c, v) = ρ_p(s, c) − ρ_p(s, σ(s))
+ Σ_s′ (P(s, c, s′) − P(s, σ(s), s′)) · (V_p(s′, v) − m)

2つのステップ利得の差と,2つの確率の差のそれぞれは,開いているパラメータの単一の関数であり, そのまま C の上で抑える(多重アフィンであれば頂点での値で,そうでなければ厳密な区間による囲みで)。 V_p(s′, v) は l_p(s′) と u_p(s′) で抑え,積は区間演算で抑える。v で差が0でない後続状態 s′ は, s で両方のコマンドが許されるので,v における Reach_p に属する。上の緩和では,g⁺_p(s) は, ステップ報酬を a⁺_p とした s からの最大値であり,g⁻_p(τ, s) は,p のコマンドを τ で固定し, ステップ報酬を a⁻_p とした s からの最小値である。これらが界になる理由は,b_p と d_p(τ) の場合と同じである。

ベルマン方程式による優位の界(参考)。 V_p(s′, v) を l_p(s′) と u_p(s′) で抑えると,値の v への依存が失われる。確率の差も v に依存するので,両者の関係も失われる。後続状態の値が v に依存するときは,後続状態の値を, v でのプロファイルのベルマン方程式で置き換えることができる。s′ で φ_p が成り立つときは V_p(s′, v) = 0 であり,そうでないときは次が成り立つ。ρ_p と P は v での値である。

V_p(s′, v) = ρ_p(s′, σ(s′)) + Σ_s″ P(s′, σ(s′), s″) · V_p(s″, v)

上の A_p(s, c, v) の式で m = 0 とし,この置き換えを何回か繰り返すと,C のどの v でも次が成り立つ。

A_p(s, c, v) = K(v) + Σ_x Q_x(v) · V_p(x, v)

K と Q_x は開いているパラメータの多項式である(置き換えた状態を通るステップ利得と確率の積の和)。 係数 Q_x(v) が0でない状態 x には,v において,s から c または σ(s) とその後のプロファイルによって正の確率で到達する ので,s が v における Reach_p に属するとき,x もそれに属する。数 m_x を用いて,次が成り立つ。

A_p(s, c, v) ∈ range(K + Σ_x m_x · Q_x) + Σ_x range(Q_x) · [l_p(x) − m_x, u_p(x) − m_x]

各 range は C の上での値の範囲であり,積と和は区間演算でとる。値がセルの上で厳密に分かっている状態 (l_p(x) = u_p(x))は区間を加えない。非巡回のゲームでは,l_p(x) < u_p(x) の状態がなくなるまで置き換えを 繰り返すことができ,そのとき界は C の上での多項式 A_p(s, c, ·) の値の範囲になる。この界は,上の界とも 下の結合した界とも併用でき,そのたびに小さいほうの上界と大きいほうの下界を用いる。

優位の結合した界(参考)。 上の界は,後続状態ごとに別々に,V_p(s′, v) を l_p(s′) と u_p(s′) の 間にあるとする。優位が2つの異なる後続状態の値の差であり,それらの値が v とともに変わるとき,それらの 界の差は,C の上での優位の値の範囲よりはるかに広くなりうる。設計のどのコマンドの確率も開いている パラメータについて多重アフィンであるときは,2つの道を同時に進めることで優位を抑えられる。C の付値 v に ついて,C の頂点 e に関する v の多重線形の重みを w_e(v) と書く。これらは負でなく,和は1であり,開いて いるパラメータについて多重アフィンであるどの関数 f についても f(v) = Σ_e w_e(v) · f(e) が成り立つ。 s から始まる2つの道を考える。一方は s で c を取り,他方は σ(s) を取り,どちらもその後はプロファイルに 従う。各ステップで,確率 w_e(v) で頂点 e を1つ引き,現在の状態の組 (x, y) を,周辺分布が e での2つの コマンドの分布であるような同時分布で動かす。そのような同時分布は,(x, y) と e の固定した関数として どれを選んでもよい。ただし,x = y のときは2つの状態を等しく保たなければならず,φ_p が成り立つ道は その状態にとどまる。このとき,それぞれの道は,単独では v でのマルコフ連鎖である。過去が与えられた とき,次の状態の分布は Σ_e w_e(v) · P(x, ·, e) = P(x, ·, v) だからである。各ステップでの各道の ステップ利得の期待値も v での値である。どちらの道もステップ数の期待値が有限で φ_p に達するので, 2つの道の累積利得の差の期待値は Q_p(s, c, v) − Q_p(s, σ(s), v) = A_p(s, c, v) である。等しい状態の 組と,どちらの状態でも φ_p が成り立つ組は,それ以降0を加える。

頂点を無作為に引くことは,次の状態の組についての過程の無作為化した方策である。異なる2つの状態の組 (x, y) で, 両方では φ_p が成り立たないものでは,頂点 e を1つ選び,ステップ報酬を ρ_p(x, e) − ρ_p(y, e) と し,組を e での同時分布で動かす。開いているパラメータについて多重アフィンでないステップ利得は,求める 界の向きに応じて,C の上でのその界で置き換える。それぞれの道は,単独では上の緩和した過程のある方策に 従う。そこで確かめたとおりにプロファイルがセルの上で許容できるとき,緩和した過程はどの方策のもとでも 確率1で φ_p に達するので,状態の組についての過程のどの方策も確率1で終わる。したがって,最初のステップ(s での c と σ(s))からのこの過程の最大値は上界 a⁺_p(s, c) であり,最小値は下界 a⁻_p(s, c) である。これらは C のどの付値でも成り立つ。上の界と合わせて,小さいほうの上界と大きいほうの下界を用いてよい。結合した 界は,同時分布が,できるところでは2つの道を同じ状態に保ち,そうでないところでは対応する更新を 一緒に取らせるときに,狭くなりやすい。e での確率が同じ2つのコマンド,たとえばI.12の2つ目の例で 監視がある場合とない場合のロボットの試行では,2つの道は対応する更新を一緒に取る。各ステップがなお 頂点を選ぶので,この界は厳密ではない。

確率が多重アフィンでないときは,H.14の分布の集合の頂点は,すべてのコマンドに共通の重みによる混合では ないので,この議論はそのままでは当てはまらない。持ち上げたセルの上では当てはまる。開いているパラメータ x について多重アフィンでない確率のそれぞれを,数 a,b と定数項のない多項式 R により a + b · R(x) と書く。 R は,a と b だけが異なる確率が同じ R を持つように正規化しておく(たとえば最初の係数を1とする)。そのような R のそれぞれに新しい座標 y_R を設け,その区間 [α_R, β_R] を,C の上での R の厳密な囲み(たとえばH.14の 緩和が用いるもの)とする。R(x) を y_R で置き換えると,どの確率も (x, y) の多重アフィンな多項式 L になり, L(x, R(x)) = P(x) を満たす。あるコマンドの持ち上げた多項式の和が恒等的に1にならないときは,y を含む もののうち1つを,1から他のものを引いたもので置き換える。確率の和は1なので,置き換えたものも (x, R(x)) ではその確率に等しい。C と区間 [α_R, β_R] の直積を,持ち上げたセル B とする。C の v について, 点 u(v) = (v, R(v)) は B に属するので,B の頂点 e に関する多重線形の重み w_e(u(v)) は負でなく,和は1で あり,どのコマンドにも共通である。持ち上げたどの多項式も L(u(v)) = Σ_e w_e(u(v)) · L(e) を満たす。 したがって,v でのコマンドの分布は Σ_e w_e(u(v)) · D_e である。ここで D_e は e でのそのコマンドの 持ち上げた多項式の値を並べたものであり,2つの道で重みは同じである。x について多重アフィンなステップ 利得は (x, y) についても多重アフィンであり,同じ重みによる混合である。頂点 e をあるコマンドに用いるのは, D_e が上の緩和した過程の分布であるとき,すなわち,その各成分が,緩和がその確率に C の上で与える区間に 属するときだけである(成分の和は作り方から1である)。この確認のもとでは,それぞれの道は,単独では やはり緩和した過程の分布の混合に従い,状態の組についての過程のどの方策も確率1で終わる。C の頂点を B の 頂点に,w_e(v) を w_e(u(v)) に置き換えて,上の議論が成り立つ。y と x の関係を捨てるので,界は広くなる。 一方で,同じ確率を持つ2つのコマンドは同じ座標を持ち,B のどの頂点でも同じ値を取るので,2つの道は やはり対応する更新を一緒に取る。ある界が必要とする頂点で確認が成り立たないときは,その界を用いない。 これは常に健全である。確率が多重アフィンである設計では,B は C である。

セルの端点による認証。 開いているパラメータが1つだけで,それが重みを通してだけゲームに入るとき, セルは2回の厳密な評価で決定できる。処理系は,均衡マップのセル [a, b] をその端点から決定してよい。 ただし,条件Aが成り立たない限り,そうしてはならない。

  • A. 問い合わせの開いているパラメータがちょうど1つ ℓ であり,ℓ が設計のコマンドのどの prob: にも どの報酬の value: にも現れず,どのプレイヤーのどの weight: にも,付録J が定めるどの重みにも,文面上で数えて1以下のべきでしか現れない(積では因子のべきを足し,打ち消しは 考えない。lambda * lambda - lambda * lambda のべきは2である)。

Aのもとで,p の k 番目の項の重みは,他のパラメータの固定値において,数 a_k と c_k を用いて a_k + c_k·ℓ である。プレイヤー p と Reach_p の状態 s について,次のように定める。

  • p のどの項 k についても c_k ≤ 0 であり,c_k ≠ 0 であるどの項についても,s から始めたゲームで プロファイルのもとで φ_p まで累積する r_k の期待値が0であるとき,s から p について**B−**が成り立つ。
  • c_k ≥ 0 として同じことが成り立つとき,s から p について**B+**が成り立つ。

これらの値で ℓ の係数が0である項,および重みに ℓ が現れない項は,何も課さない。ほかの項を持たない プレイヤーは,両方を満たす。付録Jでは,sanction_of: の項は c_k = −m ≤ 0 を持ち,プロファイルが その規範の制裁を受けないとき,s₀ からB−を満たす。J.7の条件 (ii) はこのことを述べる。

命題。 Aを仮定し,他のパラメータの値を固定する。

  1. D が良定義であるか,プロファイルが許容できるか,Reach_p,およびどの累積報酬の期待値も, ℓ に依存しない。
  2. それらが成り立つところで,どのプレイヤー p と Reach_p のどの状態 s についても, V*_p(s) − V_p(s) は ℓ の凸で区分線形な関数であり,gain_p と sgain_p も同様である。
  3. s から p についてB−が成り立てば,V*_p(s) − V_p(s) は ℓ について非増加であり,p の固定した どの戦略の s からの逸脱利得も同様である。B+が成り立てば,どちらも非減少である。

証明。 Aにより,確率は ℓ に依存せず,したがってゲームのグラフも依存しない。良定義性と許容性は 確率だけに(H.5,I.6),Reach_p はグラフだけに,累積報酬の期待値は確率と報酬の値だけに依存する。 p の戦略 τ について,σ[p↦τ] のもとで s から始めたゲームでの p の利得は Σ_k (a_k + c_k·ℓ) · E_τ,s[r_k] = A_s(τ) + ℓ·B_s(τ) である。ここで E_τ,s[r_k] は φ_p まで累積する r_k の期待値であり,A_s(τ) と B_s(τ) は ℓ に依存しない。V*_p(s) は,有限個のそのようなアフィン関数の 最大値(s から始めたゲームについてのI.7)なので,凸で区分線形である。V_p(s) = A_s(σ) + ℓ·B_s(σ) は アフィンなので,差は凸で区分線形である。gain_p は s = s₀ の場合であり,sgain_p は,ℓ に依存しない Reach_p の有限個の状態についての最大値なので,やはり凸で区分線形である。B−のもとでは,報酬の値は 負でないので(H.5),どの E_τ,s[r_k] も0以上であり,どの τ についても B_s(τ) ≤ 0 である。また, c_k ≠ 0 であるどの項もプロファイルのもとでの期待値が0なので,B_s(σ) = 0 である。すると,どの τ の s からの逸脱利得 (A_s(τ) − A_s(σ)) + ℓ·B_s(τ) も非増加であり,τ についてのその最大値も非増加である。 B+のもとでは B_s(τ) ≥ 0 であり,同じ議論で非減少な関数が得られる。∎

セル [a, b] とプロファイル σ について,方法は次のとおりである。

  • σ が a と b で(問い合わせの概念の)ε均衡であることを厳密に確立したとき(I.8),セルは equilibrium である。命題の0により,設計はセル全体で良定義であり,σ は許容できる。命題の1により, 両端で ε 以下である凸関数は,その間でも ε 以下である。各プレイヤーについて,逸脱利得の上下界 [0, max(g(a), g(b))] が成り立つ。g は gain_p である。
  • concept: nash では,s₀ から p についてB−が成り立ち gain_p(b) > ε であるとき,または s₀ からB+が 成り立ち gain_p(a) > ε であるとき,p はセルの上で逸脱者である。命題の2により,判定に用いた端での 逸脱利得はセルの上での下界である。その端での標準の最適応答は,セル全体で ε を超えて得をする逸脱で あり,逸脱利得の上下界は,B−のもとで [g(b), g(a)],B+のもとで [g(a), g(b)] である。
  • concept: every_reachable_state では,Reach_p のある状態 s について,s からB−が成り立ち b で V*_p(s) − V_p(s) > ε であるとき,または s からB+が成り立ち a でその差が ε を超えるとき,p はセルの 上で逸脱者である。命題の0により,s はセル全体で Reach_p に属する。判定に用いた端での標準の最適応答を, それのもとで s から到達可能な状態に制限したものは,命題の2により,セル全体で s から ε を超えて得を する。
  • これ以外の status は導かない。条件Bがなければ,両端で逸脱利得が ε を超えても,p はセルの上で 逸脱者にならない。逸脱利得 |1 − 2ℓ| は凸であり,ℓ = 0 と ℓ = 1 で1/4を超えるが,ℓ = 1/2 で0である。 この方法が from_every_state: true を主張するのは,ε = 0 で concept: every_reachable_state の 均衡のセルについてだけである。

これは,H.9の意味での標本点での評価ではない。命題が凸性と単調性を証明しており,方法は,Aのもとで, 逸脱者についてはBのもとでだけ健全である。この方法を上の条件と併せて用いる処理系は,上の条件が undecided のまま残したセルにこの方法を適用し,端点が確立した逸脱者を not_equilibrium のセルに 加えてよい。上の条件で決まったセルは,その主張を保つ。Aがなければ,上のことはどれも成り立たない。 ℓ が確率に現れるとき,利得は ℓ の有理関数であり,端点が均衡であるセルの中で,逸脱利得が増えてから また減ることがある。開いているパラメータが2つ以上のとき,命題は,他を固定してパラメータごとに 成り立つが,直方体については何も述べない。J-14 は, 付録Jが定める重みについてこの方法を参照する。

I.10 静的意味論​

本拡張を実装する処理系は,games: 0.1 を宣言しているファイルにおいて,H.10の規則を,ここに述べる 変更を加えて適用し,さらに次の検査をしなければならない。

  • I-1. games: 0.1 を宣言するファイルは,stochastic: 0.1 も宣言しなければならない。 そうでない場合,処理系は誤りを報告し,本拡張のキーを解釈しない。
  • I-2. kind: は,あれば dtmc または smg でなければならない(これはS-1の最後の文を 置き換える)。kind: smg を持つモデルは,少なくとも1人のプレイヤーを持つ players:, profiles:,compliance:,payoffs: を持たなければならない。kind: が dtmc であるか, kind: を持たないモデルは,players:,profiles:,compliance:,payoffs:,equilibria:, コマンドの owner:,性質またはモードマップの profile: を持ってはならない。それは付録Hの モデルであり,S-9が適用される。
  • I-3. プレイヤーの id は,識別子でなければならず,A.11のキーワード,IN,rest であっては ならず,プレイヤーの間で一意でなければならない。性質の部分言語のキーワード F,U,P,R は 認める。プレイヤーの id は,どの式にも現れないからである。actors: は,少なくとも1つのアクター参照を 列挙しなければならず,それぞれは宣言済みのアクターを名指さなければならない。2人のプレイヤーが 同じアクター名を持つ参照を挙げてはならず,1人のプレイヤーがそれを2回挙げてもならない。
  • I-4. owner: は,宣言済みのプレイヤーを名指さなければならない。所有されているコマンドは action: を持たなければならない。1つのアクションラベルを持つコマンドは,すべて同じ所有者を 持つか,すべて所有者がないかのどちらかでなければならない。
  • I-5. (戦略モデルではS-9を置き換える。)どの設計についても,S のどの状態(到達可能か どうかにかかわらない)についても,その設計に存在し,ガードが真であるコマンドは,多くとも1つで あるか,すべて同じプレイヤーが所有し,アクションラベルが互いに異なるコマンドでなければならない。 これは,S を列挙して決定する。
  • I-6. プロファイルの名前は,識別子でなければならず,S-2が除外するキーワードであっては ならず,プロファイルの間で一意でなければならない。規則の choose: は,所有されているコマンドの アクションラベルでなければならず,guard: は,変数と列挙リテラルの上のブール型の state_pred (S-6)でなければならず,ラベルを含んではならない。どの設計についても,2つ以上のコマンドが有効で ある S のどの状態でも,各プロファイルのある規則が適用できなければならない(I.4)。compliance: は, プロファイルを名指さなければならない。どの設計のどの状態でも最初に適用できる規則にならない規則に ついて,処理系は警告することが望ましい。(profiles: はYAMLのマッピングである。ファイルを YAMLのローダで読む処理系は,同じ名前の2つのプロファイルを検出できない。ローダがその一方だけを 残すからである。H.4のラベルについても同様である。)
  • I-7. model.payoffs: は,各プレイヤーにちょうど1つの項目を持たなければならず,player: は 宣言済みのプレイヤーを名指さなければならない。until: は,ブール型の state_pred でなければ ならず,性質と同じようにラベルを用いてよい(S-6)。terms: は,少なくとも1つの項を持たなければ ならない。reward: は,宣言済みの報酬構造を,1つの利得につき多くとも1回名指さなければならない。 weight: は,数であるか,識別子が宣言済みのパラメータである param_expr でなければならない。 利得の目標が初期状態で成り立つとき,処理系は警告することが望ましい。このとき,利得はどの プロファイルのもとでも0である。項のキー sanction_of: と reward_of: は, 付録Jが定義する。grounding: 0.1 を宣言しないファイルでは, そのどちらかを持つ項は誤りである。それを宣言するファイルでは,付録Jを実装していない処理系は, そのような項を持つ利得も,その利得を必要とする問い合わせも,評価してはならない。処理系は, その項を名指す診断とともに,問い合わせを評価しなかったと報告する。equilibria: のどの項目も, すべてのプレイヤーの利得を必要とするので,このときは評価しない。性質とモードマップは利得を 必要としないので評価し,I-8とI-9は利得の目標だけを必要とする。そのような項を,既定値の重みを 持つ項として読むことは決してない。
  • I-8. どの設計も,その固定値において良定義でなければならず(S-11),ファイルのどのプロファイルも, どの設計でも,固定値において許容できなければならない(I.6)。これは,ゲームのどのプレイも終わることを 要求するより弱い。
  • I-9. equilibria: の項目の id は,S-2が認める識別子でなければならず,性質とモードマップの 名前空間で一意でなければならない。profile: は,プロファイルを名指さなければならない。 regimes: は,ファイルの設計を,少なくとも1つ,それぞれ1回だけ名指さなければならない。 epsilon: は,負でない有限の数でなければならない。concept: は nash または every_reachable_state でなければならない。over: と resolution: は,S-14が モードマップについて述べる条件を満たさなければならない(over: は1つから4つの宣言済みの パラメータを持ち,それぞれ宣言範囲の中で lo < hi であり,どのモードも値を割り当てていない。 0 < r < 1)。resolution: は,over: なしに現れてはならない。モードマップ(S-10)と異なり, over: を持つ項目は,transitions: のないファイルでも許され,そこでは設計 base に関する。 equilibria: の項目の over: にあるパラメータは,報酬の項目の value: に現れてはならない。 処理系は,挙げたどの設計についても,設計が領域の頂点(S-14と同じ)とどの面の中心でも良定義である ことと,プロファイルが領域のどの面の中心でも許容できること(I.9。開いているどのパラメータも,その区間の 下端,中点,上端のいずれかにある 3ⁿ 個の付値)を検査しなければならない。これらの付値の1つでの 失敗は,ファイルの誤りである(多重アフィンである設計では,このとき,プロファイルはその面の全体で 許容できない。I.9)。確率が開いているパラメータについて多重アフィンである設計では, これらの検査が,領域全体で両方の性質を決定する(S-14,I.9)。それ以外の設計では,決定しない。 その場合,処理系は,セルごとに両方を確立するか,セルを undecided のままにする。両方を確立して いないセルを認証してはならない。
  • I-10. 性質またはモードマップの profile: は,プロファイルを名指さなければならない。 S-12からS-14は,モードモデルの位置に M(D, θ, σ) を置いて,戦略モデルにそのまま適用する。
  • I-11. 処理系は,I.1で予約したキーまたは値について情報レベルの診断を出すことが望ましく, それに意味を与えてはならない(games: 0.1 を宣言するファイルでは,これがS-15の一覧を 置き換える)。予約された値(kind: mdp,motivation. で始まる出所,concept: の subgame_perfect と correlated)には,I-2,S-3またはI-9の誤りに加えて,この診断を出す。

規則S-2からS-8とS-10からS-14は,戦略モデルに,書かれているとおりに適用する。重みは,確率でも 報酬の値でもない。その符号や範囲を制限する規則はない。

I.11 PRISM-gamesへのエクスポート(参考)​

PRISM-gamesは,PRISMモデリング言語の拡張で,ターン制の確率的な多人数ゲームを読む。モデルの種類は smg であり,各プレイヤーは,player … endplayer の構成で宣言する。この構成は,そのプレイヤーが 制御するアクションラベル(角括弧で囲む)とモジュールを列挙する。利用できる遷移がすべて1人の プレイヤーに属する状態は,そのプレイヤーが制御する。アクションとモジュールは,そのような遷移を複数持つ 状態がない限り,どのプレイヤーにも割り当てなくてよい。遷移が複数のプレイヤーに所有される状態は 誤りである [Kwiatkowska+, CAV 2020]。これらは,I-4とI-5の条件である。 PRISM-gamesが期待総報酬を計算するのは,停止ゲーム,すなわち,すべての戦略のもとで報酬0の終端状態に 確率1で達するゲームに限られる。これは,I.6の許容性より強い。Storm(stormpy 2.0.0)は, エクスポートした smg のファイルを構文解析するが,すべてのコマンドがプレイヤーに所有されていない限り, モデルを構築しない。エクスポートは,PRISM-gamesを対象とする。

H.11は,書かれているとおりには戦略モデルに適用されない。戦略モデルの設計はマルコフ連鎖でないので, 処理系は,それを dtmc のファイルとしてエクスポートしてはならない。バージョン0.1は,プロファイルの マルコフ連鎖 M(D, θ, σ) のエクスポートも定義しない。処理系は,戦略モデルの設計を,H.11のモデルファイルに 次の2つの変更を加えたものとして,エクスポートしてよい。

  1. 最初の行を,dtmc の代わりに smg とする。
  2. その後に,各プレイヤーについて,宣言の順に,そのプレイヤーが所有する設計のコマンドの アクションラベルを,最初に宣言された順に列挙する構成を1つ書く。設計のコマンドを1つも所有しない プレイヤーでは,この列挙は空である。
smg

player R_
[careful], [careless]
endplayer

設計のコマンドを1つも所有しないプレイヤーは,空の列挙で,player D に続けて endplayer と書く。 所有者のあるコマンドを持たない設計では,そのようなプレイヤーを書かないと player の構成を1つも 持たない smg のファイルになり,PRISM-games 3.2.4はこれを受け付けない。また,書かれていない プレイヤーは,提携に含められない。設計のすべてのコマンドを,プロファイルが何を 選ぶかにかかわらず書く。所有者のないコマンドとデッドロックのコマンドは,どのプレイヤーにも 割り当てない。プレイヤーの名前は,キーワードに等しいとき,H.11の規則によって改名する(R は キーワードであるので,player R_ となる)。戦略モデルでは,H.11のキーワードの一覧に, PRISM-gamesのマニュアルがPRISM言語に加えるキーワード player,endplayer,smg,csg,tptg を 加え,エクスポートするモデルのどの名前も,この一覧によって改名する。 名前がモデルの他の識別子に等しいプレイヤーをPRISM-gamesが受け付けるかどうかは,本付録では定めない。 エクスポートする処理系は,そのような名前を報告することが望ましい。PRISM-games 3.2.4は,他の識別子が 変数,ラベル,アクションラベル,パラメータ,報酬構造,モジュール main のとき,そのような プレイヤーを受け付ける(I.14)。均衡マップでだけ開いている パラメータは,その固定値で書く(I.13)。

バージョン0.1は,戦略モデルの性質ファイルを定義しない。利得は,符号が正負どちらでもよい重みを 持つ期待報酬の和であり,I.7の問いは,固定したプロファイルに対する最適応答である。PRISM-gamesの 性質言語が述べるのは,<<p1>> R{"r"}max=? [ F "success" ] のように,ある提携が他のプレイヤーに 対して保証できること [Chen+, FMSD 2013]と,PRISM-gamesが自ら選ぶ 均衡である。どちらも本付録の問いとは異なる。変換は後のバージョンに委ねる。上の構文は,PRISM-gamesの マニュアル(2026年11月閲覧)と照合し,この形式でエクスポートしたファイルを,PRISM-games 3.2.4で 実行した(I.14)。PRISM-games 3.2.4は,負の報酬を持つ報酬構造を受け付けず,ゲームについては 厳密な計算の機能を持たない。したがって,重みの符号が正負両方である利得は,エクスポートしたファイルの 1つの報酬構造にはならず,PRISM-gamesが計算する値は浮動小数点数である。

I.12 例​

1つ目の例は,H.12の例に,1つの選択を加えたものである。2つ目の例は, 本節の終わりにあり,ディスパッチャの選択を加える。ロボットは, 各試行の前に,取扱手順に従うかどうかを決める。careful(丁寧)な試行は,ロボットに1の労力を 要し,H.12の確率 s で成功する。careless(手抜き)な試行は,労力を要さず,確率 s/2 で成功する。 ディスパッチャは,配達された荷物に10の料金を支払う。手抜きの試行には制裁が科され,ロボットは 2·λ を失う。2は強度が最大であるときの制裁の大きさであり,λは契約のインセンティブ強度である。 変数 settled と偶然のコマンド settle を1つずつ加えて,タスクを締める。これにより,料金が ステップの報酬になる。

sos:
name: "RobotDeliveryGame"
type: Acknowledged
extensions:
- stochastic: 0.1
- games: 0.1

actors:
- { id: DISPATCHER, role: "Assigns and replans routes" }
- { id: "ROBOT[1..N]", role: "Delivers parcels" }

contracts:
- id: DELIVERY
parties: [DISPATCHER, "ROBOT[*]"]
information: { alpha: 0.9 }
authority: { decision_holder: DISPATCHER, beta: 0.9 }
incentives: { lambda: 0.1 }

transitions:
- { from: CENTRALIZED, to: DISTRIBUTED, condition: "loss_rate > 0.3" }
- { from: DISTRIBUTED, to: CENTRALIZED, condition: "loss_rate <= 0.2" }

model:
kind: smg
parameters:
- { id: p_fail, range: [0, 0.5], value: 0.05 }
- { id: p_loss, range: [0, 0.5], value: 0.1 }
- { id: alpha, from: "DELIVERY.alpha" }
- { id: beta, from: "DELIVERY.beta" }
- { id: lambda, from: "DELIVERY.lambda" } # 0.1, range [0, 1]
- { id: q_local, range: [0, 1], value: 0.6 }
variables:
- { id: task, type: "{Pending, Delivered}", init: Pending }
- { id: attempts, type: "[0..3]", init: 0 }
- { id: settled, type: bool, init: false }
labels:
delivered: "task == Delivered"
players:
- { id: R, actors: ["ROBOT[*]"] }
- { id: D, actors: [DISPATCHER] }
commands:
- action: careful
owner: R
guard: "task == Pending AND attempts < 3"
updates:
- prob: "beta * alpha * (1 - p_fail) * (1 - p_loss) + (1 - beta) * q_local"
set: { task: Delivered, attempts: "attempts + 1" }
- prob: rest
set: { attempts: "attempts + 1" }
- action: careless
owner: R
guard: "task == Pending AND attempts < 3"
updates:
- prob: "0.5 * (beta * alpha * (1 - p_fail) * (1 - p_loss) + (1 - beta) * q_local)"
set: { task: Delivered, attempts: "attempts + 1" }
- prob: rest
set: { attempts: "attempts + 1" }
- action: settle
guard: "(task == Delivered OR attempts == 3) AND NOT settled"
updates:
- set: { settled: true }
regimes:
CENTRALIZED: { parameters: { beta: 0.9 } }
DISTRIBUTED: { parameters: { beta: 0.1 } }
rewards:
- { id: fee, items: [ { action: settle, guard: "task == Delivered", value: 1 } ] }
- { id: effort, items: [ { action: careful, value: 1 } ] }
- { id: shortcuts, items: [ { action: careless, value: 1 } ] }
profiles:
comply:
- { choose: careful }
shortcut_first:
- { guard: "attempts == 0", choose: careless }
- { choose: careful }
compliance: comply
payoffs:
- player: R
until: "settled"
terms:
- { reward: fee, weight: 10 }
- { reward: effort, weight: -1 }
- { reward: shortcuts, weight: "-2 * lambda" }
- player: D
until: "settled"
terms:
- { reward: fee, weight: 5 }
properties:
- { id: P_DELIVERY, expr: "P>=0.95 [ F<=3 delivered ]" }
- { id: P_DELIVERY_SHORTCUT, profile: shortcut_first, expr: "P=? [ F<=3 delivered ]" }
equilibria:
- { id: comply_nash }
- { id: shortcut_nash, profile: shortcut_first }
- { id: comply_by_lambda, over: { lambda: [0, 1] }, resolution: 0.05 }
- id: comply_by_lambda_and_failure
regimes: [CENTRALIZED, DISTRIBUTED]
over: { lambda: [0, 0.4], p_fail: [0, 0.5] }
resolution: 0.05

ゲーム。 モデルは16個の状態を持ち,そのうち11個が到達可能である。 task == Pending AND attempts < 3 である状態では,R の2つのコマンドが有効である。これらが R の 状態である(I-5)。task == Delivered OR attempts == 3 であり,まだ締められていない状態では, 所有者のないコマンド settle が有効である。これらは偶然状態である。締められた状態は デッドロック状態である。プレイヤー D はコマンドを所有せず,選択肢を持たない。D は,料金の受け手を 置くために宣言している。R が何をしても,どのパスも4ステップ以内に settled に達するので, どのプロファイルも,すべての付値で許容でき,2つのマップの領域の上で,すべての確率は [0, 1] に 収まる。プロファイル comply は,R のどの状態でも careful を選ぶ。プロファイル shortcut_first は, 最初の規則により,最初の試行の前に careless を選び,その後は careful を選ぶ。

comply のもとでは,モデルはH.12のモデルにステップを1つ加えたものであるので,P_DELIVERY は H.12の値を持つ。CENTRALIZED では 0.984848(satisfied),DISTRIBUTED では 0.943796(violated)で ある。shortcut_first のもとでは,P_DELIVERY_SHORTCUT は 1 − (1 − s/2)(1 − s)² であり, 0.961808 と 0.898534 である。本節の計算値は,小数第6位に丸めている。

閉形式。 料金を g = 10,労力の費用を c = 1,制裁の大きさを m = 2 と書き,丁寧な試行が成功する 確率を s と書く(H.12により,固定値では s_C = 0.75255,s_D = 0.61695)。試行が k 回残っている 状態からの,comply のもとでの R の利得を V_k とする。

V_0 = 0, V_k = s·g − c + (1 − s)·V_(k−1)
V_1 = s·g − c, V_2 = (s·g − c)(2 − s), V_3 = (s·g − c)(1 + (1 − s) + (1 − s)²)

V_3 が,comply のもとでの R の利得である。comply は手抜きの試行をしないので,ここにλは現れない。 試行が k 回残っているときに1回だけ手抜きをし,その後 comply に従うと,利得は −m·λ + (s/2)·g + (1 − s/2)·V_(k−1) である。これが V_k 以下であるのは,次のとき,かつそのときに 限る。

λ ≥ T_k, where T_k = ( c − (s/2)·(g − V_(k−1)) ) / m

手抜きは,労力 c を節約する一方で,確率 s/2 で,いま配達することと続けることとの差を失う。 次のようにおく。

λ* = max(0, T_1, T_2, T_3)
T_1 = ( c − (s/2)·g ) / m
T_2 = ( c − (s/2)·(g − (s·g − c)) ) / m
T_3 = ( c − (s/2)·( g·(1 − s)² + c·(2 − s) ) ) / m

(T_3 では,g − V_2 = g·(1 − s)² + c·(2 − s) を用いた。)

0 ≤ s < 1 のとき,comply が θ において設計のナッシュ均衡であるのは,λ ≥ λ* であるとき, かつそのときに限る。 comply のもとでは,試行が確率 1 − s > 0 で失敗するので,R の3つの状態の それぞれに,正の確率で到達する。したがって,R が得をしないのは,I.7の1ステップ検査がその3つの状態で 成り立つとき,すなわち k = 1, 2, 3 について λ ≥ T_k であるとき,かつそのときに限る。D は選択肢を 持たず,得をしない。条件 s < 1 は,「かつそのときに限る」のために必要である。s = 1 では,後の状態には R が逸脱したときにだけ到達する。

s·g ≥ c のとき,すなわち s ≥ 0.1 のとき,V_0 ≤ V_1 ≤ V_2 であり,したがって T_1 ≤ T_2 ≤ T_3 で あるので,λ* = max(0, T_3) である。手抜きをする動機は,失敗をまだ取り返せる最初の試行の前に最も強い。 固定値と,以下の2つのマップの領域(そこでは s ≥ 0.4245)では,この場合に当たる。小さい s では 当たらない。s = 0.07695(DISTRIBUTED で q_local = 0 のとき)では,T_1 = 0.307625 が3つのうちで 最も大きい。

同じ計算により,0 ≤ s < 1 のとき,shortcut_first がナッシュ均衡であるのは, max(0, T_1, T_2) ≤ λ ≤ T_3 であるとき,かつそのときに限る。 R は,最初の試行の前には手抜きを好み, その後は丁寧な試行を好まなければならない。

どちらの設計でも,固定値では T_1 と T_2 は負であり(T_2 は −0.153684 と −0.245044),T_3 は正である。 そこでは,どの λ ≥ 0 についても,最初より後の手抜きの試行は損であり,λ < λ* では shortcut_first が 最適応答であり,shortcut_first がナッシュ均衡であるのは λ ≤ λ* であるとき,かつそのときに限り, λ = λ* では両方のプロファイルが均衡であって,次が成り立つ。

gain_R = max(0, m·(λ* − λ)) = max(0, 2·(λ* − λ))

検査。 固定値,λ = 0.1 では,次のとおりである。

CENTRALIZEDDISTRIBUTED
s0.752550.61695
λ* = T_3480347064349/3200000000000 = 0.150108193194567781/3200000000000 = 0.060373
comply のもとでの fee,effort,shortcuts の期待値0.984848,1.308682,00.943796,1.529777,0
comply のもとでの u_R6831840915651/800000000000 = 8.5398016326547012219/800000000000 = 7.908184
shortcut_first のもとでの fee,effort,shortcuts の期待値0.961808,0.778066,10.898534,0.956414,1
shortcut_first のもとでの u_R8.840018 − 2·λ = 8.6400188.028930 − 2·λ = 7.828930
comply / shortcut_first のもとでの u_D4.924241 / 4.8090424.718981 / 4.492672
comply_nash:BR_R,gain_R8.640018,160347064349/1600000000000 = 0.1002177.908184,0
comply_nash:statusnot_equilibrium,deviators は R,標準の最適応答は attempts == 0 の状態での carelessequilibrium,from_every_state: true
shortcut_nash:gain_R,status0,equilibrium,from_every_state: true126805432219/1600000000000 = 0.079253,not_equilibrium,deviators は R

宣言値 λ = 0.1 では,遵守は,分散モードでは均衡であり,集中モードでは均衡でない。D の逸脱利得は, どの検査でも0である。R が手抜きをすると,D は損をする。料金が支払われる頻度が下がるからである。

λの上のマップ。 comply_by_lambda は,両方の設計で,λを [0, 1] の上で開く。セル [a, b] が 均衡のセルであるのは a ≥ λ* であるとき,かつそのときに限り,R がその上で逸脱者であるのは b < λ* であるとき,かつそのときに限る。λ* を内部に含むセルは undecided である。I.9の条件E1と Nは,他のすべてのセルを,厳密な界によって決定する。U_R はλについて定数であり,セルの上で最大の 最適応答値は λ = a でのものであり,shortcut_first の利得は λ = b で最小である。最大の未決定セルを, 分解能0.05に達するまで二分し,主張が同じセルを結合する(I.9)処理系は,次を報告する。

設計not_equilibrium(deviators は R)undecided(reason: bounds)equilibrium未決定の割合
CENTRALIZED[0, 1/8][1/8, 5/32][5/32, 1]1/32
DISTRIBUTED[0, 1/32][1/32, 1/16][1/16, 1]1/32

0.060373 ≤ λ < 0.150108 では,遵守は DISTRIBUTED でだけ均衡であり,0.150108 以上では両方で 均衡である。

λと故障確率の上のマップ。 comply_by_lambda_and_failure は,p_fail も開く。他のパラメータを 固定すると,s_C = 0.729·(1 − p_fail) + 0.06,s_D = 0.081·(1 − p_fail) + 0.54 であり,各設計で, comply が均衡であるのは,λ ≥ λ*(s) であるところ,かつそこに限る。T_3 は,現れる s の範囲で s と ともに増加する。したがって,遵守が均衡でない領域は,p_fail が大きくなるにつれて下がる曲線の下にある。 実装の確認のための λ* の値を示す。

p_fails_Cλ*(CENTRALIZED)s_Dλ*(DISTRIBUTED)
00.7890.1733130.6210.062908
0.050.752550.1501080.616950.060373
0.10.71610.1258570.61290.057859
0.20.64320.0771180.60480.052897
0.30.57030.0329070.59670.048028
0.40.497400.58860.043261
0.50.424500.58050.038604

CENTRALIZED では,s = 1/2,すなわち p_fail = 289/729 = 0.396433 で T_3 = 0 である。 ディスパッチャがそれほど頻繁に故障するとき,試行の失敗はロボットにとって非常に高くつくので, ロボットは制裁がなくても丁寧に試行する。p_fail = 0.2 までは集中モードの方が強いインセンティブを 必要とし,p_fail = 0.3 では分散モードの方が必要とする。このマップでは U_R が p_fail とともに 変わるので,E1は equilibrium のセルを1つも決定しない(I.9)。逸脱利得が0である D に ついては,どのセルでもE2が成り立つ。R については,曲線から離れたセルを主にPD+とPD−が決定する。 CENTRALIZEDを分解能0.05まで二分する場合(I.14),セルを結合する前の equilibrium のセル91個の すべてで,E1とE2は成り立たず,PD+が V*_R = V_R を確立する。not_equilibrium のセル68個のうち 66個ではPD−が,残りの2個ではNが,R を逸脱者として確立する。

2つ目の例:選択をするプレイヤーが2人の場合​

1つ目の例では,選択をするのはロボットだけであるので,各プレイヤーの検査は,1人のプレイヤーの最適化で ある。2つ目の例では,ディスパッチャも選択をする。ディスパッチャは,最初の試行の前に,費用 κ を払って ロボットを monitor(監視)するか,trust(信頼)するかを決める。手抜きの試行に制裁が科されるのは, ディスパッチャが監視しているときだけである。ファイルは,1つ目の例のファイルに次の変更を加えたもので ある(コマンド careful と careless の更新はそのままである)。

model:
kind: smg
parameters:
# ... as above, and:
- { id: kappa, range: [0, 1], value: 0.05 } # cost of monitoring
variables:
- { id: watch, type: "{Open, On, Off}", init: Open }
# ... task, attempts, settled as above
commands:
- action: monitor
owner: D
guard: "watch == Open AND task == Pending AND attempts == 0"
updates:
- set: { watch: "On" }
- action: trust
owner: D
guard: "watch == Open AND task == Pending AND attempts == 0"
updates:
- set: { watch: "Off" }
- action: careful
owner: R
guard: "watch != Open AND task == Pending AND attempts < 3"
# updates as above
- action: careless
owner: R
guard: "watch != Open AND task == Pending AND attempts < 3"
# updates as above
- action: settle
guard: "watch != Open AND (task == Delivered OR attempts == 3) AND NOT settled"
updates:
- set: { settled: true }
rewards:
- { id: fee, items: [ { action: settle, guard: "task == Delivered", value: 1 } ] }
- { id: effort, items: [ { action: careful, value: 1 } ] }
- { id: shortcuts, items: [ { action: careless, guard: "watch == On", value: 1 } ] }
- { id: monitoring, items: [ { action: monitor, value: 1 } ] }
profiles:
comply:
- { choose: monitor }
- { choose: careful }
comply_if_watched:
- { choose: monitor }
- { guard: "watch == Off AND attempts == 0", choose: careless }
- { choose: careful }
compliance: comply
payoffs:
- player: R
until: "settled"
terms:
- { reward: fee, weight: 10 }
- { reward: effort, weight: -1 }
- { reward: shortcuts, weight: "-2 * lambda" }
- player: D
until: "settled"
terms:
- { reward: fee, weight: 5 }
- { reward: monitoring, weight: "-kappa" }
equilibria:
- { id: comply_nash }
- { id: watched_nash, profile: comply_if_watched }
- id: watched_map
profile: comply_if_watched
regimes: [CENTRALIZED]
over: { lambda: [0, 0.4], kappa: [0, 0.4] }
resolution: 0.25

モデルは48個の状態を持つ。初期状態は D の状態である。 watch != Open AND task == Pending AND attempts < 3 である状態は R の状態である。ガードは,到達不能な 状態でもI-5が成り立つように書いてある。どのパスも5ステップ以内に settled に達するので,どの プロファイルも,すべての付値で許容できる。どちらのプロファイルでも,実際にたどるパスの上では,D は 監視し,R は丁寧に試行するので,両者は同じ利得を与える。u_R は前と同じく V_3 であり, u_D = 5·(1 − (1 − s)³) − κ である。両者が異なるのは,D が監視しなかった場合に R が何をするかである。 comply のもとでは,R はそれでも丁寧に試行する。comply_if_watched のもとでは,R は最初の試行の前に 手抜きをする。

R。 D が監視している間,どちらのプロファイルに対する R のゲームも1つ目の例であるので,固定値では, 1つ目の例の λ* について gain_R = max(0, 2·(λ* − λ)) である。watch == Off である状態は Reach_R に 属さず,そこでプロファイルが何を選ぶかは,R にとっては関係しない。

D。 comply に対しては,信頼することは κ を節約し,他には何も変えない。したがって gain_D = κ で あり,どの κ > 0 についても,λ が何であっても,D は逸脱者であって,comply はナッシュ均衡でない。 comply_if_watched に対しては,信頼することは κ を節約するが,R に手抜きをさせ,配達の確率を 1 − (1 − s)³ から 1 − (1 − s/2)(1 − s)² に下げる。

κ* = 5 · (s/2) · (1 − s)²

とおくと,D は信頼することで 5·(s/2)(1 − s)² − κ を失い,gain_D = max(0, κ − κ*) である。

comply_if_watched が,他のパラメータの固定値において,設計のナッシュ均衡であるのは,λ ≥ λ* かつ κ ≤ κ* であるとき,かつそのときに限る。 実際にたどる振る舞いは comply のものである。しかし,それが 均衡になるのは,監視されていないときのロボットの振る舞いと組み合わせたときだけである。監視されなければ ロボットが手抜きをするので,監視に費用をかける意味がある。

CENTRALIZEDDISTRIBUTED
λ*0.1501080.060373
κ*368638137651/3200000000000 = 0.115199724187274219/3200000000000 = 0.226309
両方のプロファイルのもとでの u_R,u_D(λ = 0.1,κ = 0.05)8.539801,7798786117651/1600000000000 = 4.8742417.908184,7470368854219/1600000000000 = 4.668981
D が信頼したときの u_D(comply に対して / comply_if_watched に対して)4.924241 / 4.8090424.718981 / 4.492672
comply_nash:gain_R,gain_D0.100217,1/200,1/20
comply_nash:statusnot_equilibrium,deviators は R と Dnot_equilibrium,deviators は D
watched_nash:gain_R,gain_D0.100217,00,0
watched_nash:statusnot_equilibrium,deviators は Requilibrium

comply_nash では,D の標準の最適応答は,初期状態での trust である。DISTRIBUTED の watched_nash では, 1ステップ検査が両方のプレイヤーについて成り立つので,結果は from_every_state: true を持つ。

マップ。 watched_map は,CENTRALIZED で λ と κ を開く。R は λ < 0.150108 であるところで逸脱者で あり,D は κ > 0.115199 であるところで逸脱者である。領域を 4 × 4 個のセルに一様に分割すると(二分によるセルではない), I.9の条件は次を与える。列は λ の区間,行は κ の区間である。

κ \ λ[0, 0.1][0.1, 0.2][0.2, 0.3][0.3, 0.4]
[0.3, 0.4]not_equilibrium,R と Dnot_equilibrium,Dnot_equilibrium,Dnot_equilibrium,D
[0.2, 0.3]not_equilibrium,R と Dnot_equilibrium,Dnot_equilibrium,Dnot_equilibrium,D
[0.1, 0.2]not_equilibrium,Rundecidedundecidedundecided
[0, 0.1]not_equilibrium,Rundecidedequilibriumequilibrium

二分では,λ ∈ [0, 0.4] × κ ∈ [0.2, 0.4] を deviators: [D] の1つのセルとして決定する。粗いセルは, 挙げる逸脱者が少ないことがある。

16個のセルのうち4個が,理由 bounds で undecided である。未決定の割合は 1/4 であり,これは 問い合わせの resolution: である。逸脱者はNが決定する。R については,監視されている間に最初の試行の 前に手抜きをする戦略を用い,その利得は λ の上端で最小である。D については trust を用い,κ の下端での プロファイルの利得と比べる。2列目の上の2行のセルでは,D は逸脱者であり,R は逸脱者として確立されない。 λ* がその列の中にあるからである。deviators は,確立されたものを挙げる。2つの equilibrium の セルでは,E2が両方のプレイヤーについて成り立つ(D については,trust の利得 4.809042 が,κ = 0.1 での プロファイルの利得の下界 4.824241 以下である)。したがって,これらのセルは from_every_state: true を持つ。E1は,プロファイルのもとでの利得が定数である R については成り立ち, プロファイルのもとでの利得が κ とともに下がる D については成り立たない。

I.13 中間表現(IR)への追加と結果​

H.13のフィールド stochastic_model を,戦略モデルのために拡張する。 kind は "smg" である。各コマンドは,action の後にフィールド owner(プレイヤーの id または null)を持つ。各性質は regimes の後に,各モードマップも regimes の後に,既定値を補った フィールド profile を持つ。各パラメータは,open の後にフィールド open_in_equilibria を持つ。 これは,equilibria: のある項目がそのパラメータを over: に挙げているとき,真である。open フィールドは,H.13の意味(あるモードマップで開いている)のままであり,H.11がパラメータをどう書くかを 決めるのは open だけである。均衡マップでだけ開いているパラメータは,その固定値でエクスポートする。 regime_maps の後に,次の5つのフィールドをこの順で追加する。

{
"stochastic_model": {
"kind": "smg",
// ... the fields of H.13
"players": [ { "id": "R", "actors": ["ROBOT[*]"] }, { "id": "D", "actors": ["DISPATCHER"] } ],
"profiles": [
{ "id": "comply", "rules": [ { "guard": "true", "choose": "careful" } ] },
{ "id": "shortcut_first", "rules": [ { "guard": "attempts == 0", "choose": "careless" },
{ "guard": "true", "choose": "careful" } ] }
],
"compliance": "comply",
"payoffs": [
{ "player": "R", "until": "settled",
"terms": [ { "reward": "fee", "weight": "10" }, { "reward": "effort", "weight": "-1" },
{ "reward": "shortcuts", "weight": "-2 * lambda" } ] }
// ... D
],
"equilibria": [
{ "id": "comply_nash", "profile": "comply", "regimes": ["CENTRALIZED", "DISTRIBUTED"],
"epsilon": 0, "over": null, "resolution": null, "concept": "nash" },
{ "id": "comply_by_lambda", "profile": "comply", "regimes": ["CENTRALIZED", "DISTRIBUTED"],
"epsilon": 0, "over": { "lambda": [0, 1] }, "resolution": 0.05,
"concept": "nash" }
// ... shortcut_nash, comply_by_lambda_and_failure
]
}
}

ガード,目標,重みは,H.13の式と同じく,テキストのまま保持する。I.2の既定値を補う。profiles は, ファイルの順のリストである。付録Hのモデルでは,5つのフィールドはなく,owner,profile, open_in_equilibria も書かない。したがって,本拡張を用いないファイルのIRは変わらない。解析の結果は IRに含めない。

結果(参考。ただし,JSONを出力する処理系は,この形を用いることが望ましい)。 厳密な数は文字列で ある。整数,または既約分数 "n/d" とする。均衡検査の結果は,次のとおりである(一部を省略している)。

{ "id": "comply_nash", "profile": "comply", "epsilon": "0",
"designs": [
{ "design": "CENTRALIZED",
"parameters": { "p_fail": "1/20", "lambda": "1/10" /* ... every parameter */ },
"status": "not_equilibrium", // equilibrium | not_equilibrium | inconclusive | not_evaluated
"deviators": ["R"], // [] unless not_equilibrium
"from_every_state": null, // true | false | null
"players": [
{ "player": "R",
"payoff": "6831840915651/800000000000",
"best_response_value": "13824028895651/1600000000000",
"gain": "160347064349/1600000000000",
"best_response": [ { "state": { "task": "Pending", "attempts": 0, "settled": false },
"action": "careless" } ] },
{ "player": "D", "payoff": "7878786117651/1600000000000",
"best_response_value": "7878786117651/1600000000000", "gain": "0", "best_response": [] }
] }
// ... DISTRIBUTED
] }

均衡マップ問い合わせの結果は,次のとおりである。

{ "id": "comply_by_lambda", "profile": "comply", "epsilon": "0",
"over": { "lambda": ["0", "1"] }, "resolution": "1/20",
"designs": [
{ "design": "CENTRALIZED", "method": "...",
"parameters": { "p_fail": "1/20" /* ... every parameter that is not open */ },
"cells": [
{ "box": { "lambda": ["0", "1/8"] }, "status": "not_equilibrium", "deviators": ["R"] },
{ "box": { "lambda": ["1/8", "5/32"] }, "status": "undecided", "reason": "bounds" },
{ "box": { "lambda": ["5/32", "1"] }, "status": "equilibrium", "from_every_state": true }
],
"undecided_fraction": "1/32", "resolution_reached": true }
// ... DISTRIBUTED
] }

付録Jを実装していない処理系が,sanction_of: または reward_of: の項を持つ利得のために問い合わせを 評価しないとき(I-7),検査でもマップでも,各設計の結果は { "design": "...", "status": "not_evaluated", "reason": "..." } であり,他のフィールドを持たない。 reason は,その項を名指す。マップの結果は,設計ごとに,検査の結果と同じ形のフィールド parameters を 持ち,開いていないパラメータの固定値を示す。

players は宣言の順であり,cells は,パラメータを over: の順に並べたときの,下側の頂点の 辞書式順である。best_response は,I.7の標準の 最適応答であり,すべての変数の値を宣言の順に示す。ε を超える逸脱利得を持たないプレイヤーでは, 空である。セルは,method(セルを決定した方法。たとえば "end points (I.9)"),deviations (各逸脱者について,best_response の形の戦略),deviation_states(concept: every_reachable_state のとき,各逸脱者について,条件N_sまたは端点の状態 s を { "state": …, "gain_lower": … } として示し, deviations の戦略は s から得をするものである),gain_bounds(各プレイヤーについて,gain_p の下界と 上界の組)も持ってよい。

concept: every_reachable_state の問い合わせの結果は,epsilon の後に "concept": "every_reachable_state" を持つ。既定の概念の結果は,このフィールドを省いてよい。この概念の 検査では,どのプレイヤーも,gain の後に state_gain(厳密な数)と state(逸脱者についてはI.8の 状態 s,そうでなければ null)を持ち,その best_response は s からのものである。

処理系の動作。 検査とマップをコマンドとして提供する処理系は,終了ステータスによって, 3つの結末を区別しなければならない。

終了ステータス意味
0要求されたどの結果も計算した。答えが何であるかは問わない(equilibrium でも not_equilibrium でも,分解能の範囲内で undecided のセルがいくつあってもよい)
1ある結果が inconclusive または not_evaluated であるか,あるマップがその resolution: に達しなかった
2何も主張できない。ファイルの静的な誤り,コマンドの使い方の誤り,または,コマンドが評価を求められた値において,設計が良定義でないか,プロファイルが許容できない

コマンドが,利用者に,パラメータに固定値以外の値を与えることを許すとき(cadl model-check の --set のように),その値は宣言範囲の中になければならず,評価する問い合わせが over: に挙げている パラメータに値を与えることは,使い方の誤りである(終了ステータス2)。処理系は,評価の前に,評価する問い合わせのどの設計とプロファイルについても,用いる値で,設計が 良定義であり,プロファイルが許容できることを(マップについてはI-9の検査を)検査しなければならない。

コマンドが,利用者に,評価を1つの設計に限ることを許すとき(--regime のように),regimes: が その設計を挙げていない問い合わせは,「この問い合わせはこの設計に関しない」と報告する。これは誤りでは ない(終了ステータス0)。コマンドは,マップを,領域の各開いているパラメータを N 個の区間に分ける 一様な分割から始めることと,セルを結合せず(I.9),解析したとおりに報告することを提供してよい。 cadl game-check では,--partition N と --no-merge である。

I.14 リファレンス実装の状況​

リファレンス実装は,cadl 0.3.23から,games 0.1を次のように実装する。0.3.22までは,cadl check は 拡張の名前 games を未知のものとして報告し,戦略モデルをS-1とS-9の誤りとして報告していた(H.14を参照)。

  • cadl check は,規則I-1からI-11を適用し(「望ましい」は警告とする),I-9の頂点と面の中心での 検査も行い,戦略モデルをI.13のIRへ変換する。プレイヤーの id は F,U,P,R であってよい (I-3)。同じ名前の2つのプロファイルは,ファイルをYAMLのローダで読むため,検出できない(I-6)。 本付録のキーの宣言されていない使用には,情報レベルの診断を1つ出す(I.15)。
  • cadl game-check は,I.8の均衡検査を厳密な有理数算術で評価し(明示的な列挙と方策反復), --certify を付けると,認証付きモードマップのソルバ (H.14)の上で,I.9の緩和によって I.9の均衡マップを計算する。オプションは,--equilibrium ID(繰り返してよい),--regime,--set, --certify,--max-depth,--max-cells,--partition N,--no-merge,--format text|json である。--certify がなければ,マップは計算しなかったものとして列挙する。--certify なしに --equilibrium でマップを名指すことは,使い方の誤りである。結果と終了ステータスはI.13のとおりである。 算術が厳密であるので,inconclusive は生じない。条件Nには,セルの中心での標準の最適応答(I.9)を 用い,E1とE2がともに成り立たないプレイヤーについてだけNを試す。--no-merge を付けない限り, 主張が同じセルを結合する(I.9)。cadl 0.3.24からは,条件Aが成り立つとき,N,E1,E2 (および後述のPD+とPD−)で決まらなかったセルを,どの戦略モデルでも端点(I.9)から決定する。マップは,Aが成り立つかどうか, s₀ から逸脱利得が非増加(B−)または非減少(B+)であるプレイヤー,端点を使わない場合はその理由を 報告し,そのようなセルは method: "end points (I.9)" を持つ。概念 every_reachable_state は,検査と マップ(E2,E1*,N,N_s,端点)について実装している。N_sでは,R⁺_C(p) をセルごとに計算し,τ を セルの中心での Reach_p 上の標準の最適応答とし,s を条件を満たす S の最初の状態とする。 cadl 0.3.27からは,PD+とPD−(I.9)も用いる。E1(every_reachable_state ではE1*)と E2がともに成り立たないプレイヤーについて,I.9に述べるとおりにセルの上で優位を抑える。ステップ利得の 差と確率のそれぞれの差は厳密に(頂点で,多重アフィンでないときは区間による囲みで)抑え,後続状態の 値は l_p と u_p で抑え,m はこれらの界の凸包の中点とする。PD+はNより前に試し,g⁺_p(s) を緩和した 過程の最大値とする。PD−はNが成り立たないときに試し,τ をセルの中心での標準の最適応答とする。N_sに ついては,N_sの戦略と状態を用いる。equilibrium のセルが from_every_state: true を持つのは, どのプレイヤーについても,E2か,φ_p が成り立たない R_C(p) のすべての状態で g⁺_p(s) ≤ 0 となるPD+の どちらかが成り立つときである。プレイヤーごとに異なる条件でもよい。concept: every_reachable_state で ε = 0 のときは,常に持つ。games_eval.USE_ADVANTAGES = False とすると,0.3.26のマップを得る。 cadl 0.3.28からは,優位の結合した界(I.9)も用いる。対象は,確率がすべて開いている パラメータについて多重アフィンである設計で,E1,E2,PD+,N,PD−がどれも成り立たないプレイヤーである。 セルの中心でのプレイヤーの逸脱利得(every_reachable_state では Reach_p の状態からの逸脱利得の 最大値)が ε 以下であるときは,正である優位の上界のそれぞれを,それと結合した上界の小さい ほうで置き換えて,PD+を再び試す。そうでないときは,τ のコマンドの下界を同じように置き換えて,PD− (およびN_s)を再び試す。結合した界はセルの中心でも成り立つので,試さないほうの条件は成り立ちえない。 緩和した過程での c の後続状態 x と,それと異なる σ(s) の後続状態 y のどの組でも,x または y がセルの 上で l_p = u_p を満たす(その値が付値によらない)ときは,結合した界は狭くならないと見込まれるので, 計算しない。条件を再び試すのは,ある界が狭くなったときだけである。各ステップの同時分布は,組 (s′, s′) に min(P₁(s′), P₂(s′)) を置き,残りを2つのコマンドの更新の順に 対応させる(北西隅の規則)。状態の組についての過程の値は,最初のステップから到達可能な組が非巡回のグラフをなす ときは後ろ向きの帰納で,そうでないときは方策反復で計算し,1つのセルの優位の間で共有する。頂点での 分布はセルごとに1回だけ計算する。games_eval.USE_COUPLING = False とすると,0.3.27のマップを得る。 cadl 0.3.29からは,多重アフィンでない確率を持つ設計でも,I.9の持ち上げたセルの上で結合した 界を用いる。確率 a + b · R の持ち上げでは,R の最初の係数(指数の順で最初のもの)を1に正規化する。 これにより,a と b だけが異なる確率は座標を共有する。持ち上げた多項式の和が恒等的に1にならない コマンドでは,座標を含む最後のものを,1から他のものを引いたもので置き換える。座標の区間は,緩和が 用いる区間演算による囲みと,セルの上での R のベルンシュタイン係数による囲みとの共通部分である (x = lo + (hi − lo) · t と置くと,多項式は [0, 1]ⁿ 上のベルンシュタイン基底関数の結合になる。基底関数は 負でなく,和は1なので,多項式の値は最小の係数と最大の係数の間にある)。係数はパラメータごとに計算し, 係数が N 個で次数が d_k のとき O(N · Σ_k d_k) 回の演算で済む。N が4 096を超えるときは,区間演算による 囲みだけを用いる。持ち上げたセルとその頂点は,セルで結合した界を初めて計算するときに求める。持ち 上げたセルの座標(開いているパラメータと持ち上げた関数)は10個までとし,それより多くの持ち上げた関数を 要する設計では結合した界を用いない。多重アフィンな設計は,持ち上げた関数を要しない。 頂点は,そこでの分布が初めて必要になったときに緩和の区間と照合し,照合に失敗した頂点を要する界は 用いない。games_eval.USE_LIFTING = False とすると0.3.28のマップを, games_eval.LIFT_BERNSTEIN = False とすると区間演算による囲みだけを用いた持ち上げを得る。 cadl 0.3.31からは,開いているパラメータについて多重アフィンでない多項式(確率,ステップ利得,それらの差, 持ち上げた関数)を,セルの上での値の範囲で抑える。範囲は有理数で厳密に計算する。両端それぞれについて, セルの中の箱を調べる。まず,多項式が箱の上で単調なパラメータ(偏導関数の囲みの符号が変わらないもの) ごとに,箱をその端の面に縮める。縮めた箱の頂点での値が内側の界を与え,区間演算とベルンシュタイン係数の 共通部分が箱の上の外側の界を与える。外側の界が最大の箱を二分し,2つの界が一致するか,二分が 16回に達するまで続ける。二分する点は,偏導関数がそのパラメータだけについてアフィンであるときはその零点とする。 細かくするのは囲みだけであり,セルは分けない。緩和(確率の区間,セルの上で設計が良定義であることの 確認,セル全体で正である確率),ステップ利得,優位の界,持ち上げた座標の区間がこの範囲を用いる。 確率 a + b · R には,a に,R の範囲の b 倍を加えたものを与える。これにより,持ち上げたセルの頂点は 緩和の区間の中にとどまる。ただし,持ち上げた多項式を1から他のものを引いたもので置き換えたときは この限りでなく,そのような頂点は0.3.29と同じく用いない。範囲は,探索が打ち切られない限り厳密である。 単項式ごとの区間演算では,4 · p · (1 − p) は p = 1/2 の近くで1を超え, (1 − p)² = 1 − 2p + p² は p = 0 の近くで1を超える。これはセルをどれだけ小さくしても変わらず,そのような セルは0.3.30までは not_well_defined であった。その後,結合した界の前に,I.9のベルマン方程式で優位を 抑えて,PD+とPD−を再び試す。l_p と u_p が異なる後続状態の値を,現れる順に方程式で置き換える。 置き換えは16回までとし,多項式の単項式が64個以下で,各パラメータについての次数が6以下である間だけ 行う。残る範囲は二分を4回まで行って調べ,条件が必要とする端だけを求める。対象は,正の上界(PD+)と,τ の コマンドの下界(PD−)だけである。games_eval.TIGHT_RANGES = False とすると,ベルマン方程式による 展開の中も含めて0.3.30の区間演算による囲みを,games_eval.UNROLL_ADVANTAGES = False とすると ベルマン方程式による展開を用いないマップを,両方とすると0.3.30のマップを得る。
  • cadl model-export は,I.11のファイル(smg と player の構成。H.11の改名と,I.11が戦略モデルの ために加えるキーワードの改名を伴い,2人のプレイヤーが衝突しないことを検査する)を書き出す。 0.3.26までは,設計のコマンドを1つも所有しないプレイヤーを書かなかった。
  • sanction_of: または reward_of: の項を持つ利得は,J.7の重みを持ち,J-14(I.9の端点)は --certify で用いる (J.11)。I.13の not_evaluated は, 付録Jを持たない処理系のために残る。
  • I.12のどの数値も,cadl game-check が再現する。利得,最適応答値,逸脱利得は,表示される分数として, λ* と κ* は逸脱利得を通して,λ* の表は --set によって,status,逸脱者,from_every_state も 再現する。1つ目の例のマップは,comply_by_lambda では結合後に設計ごとに3個のセル(解析したセルは11個, 両方の設計で約0.4秒),comply_by_lambda_and_failure では結合後に46個と13個のセル(解析したセルは 125個と87個,約1秒)である(CENTRALIZED では,equilibrium が0.8125,not_equilibrium が 0.137695,未決定が51/1024)。0.3.30までと同じく優位のベルマン方程式による展開を使わなければ,結合後に 105個と13個のセル(解析したセルは567個と115個,約1.5秒。CENTRALIZED では0.811768,0.138672, 203/4096)である。0.3.26までと同じくPD+とPD−を使わなければ,結合後に257個と17個の セル(解析したセルは3 849個と271個,約6.3秒。CENTRALIZED では0.808838,0.141235,409/8192)である。watched_map では,二分は結合後に5個の セル(解析したセルは17個)を与え,--partition 4 --no-merge はI.12の表を与える。時間は, ノートパソコンでの実時間である。
  • 実装者による検証。cadl とコードを共有せず,記憶なしで決定的なすべての戦略を列挙するオラクルを 用いた。対象は,無作為に生成した2 500個のパラメトリックなゲームであり,プレイヤーは2人または3人, 閉路,パラメータを含む符号付きの重み,確率の中のパラメータ(多重アフィンでないものも含む), 確率0または1に接する領域,ε ∈ 1 を含む。決定したどのセル(equilibrium が1 933個, not_equilibrium が2 504個)も,頂点,面の中心,中心,および無作為な有理点で評価した。点評価は 69 195回であり,誤った主張はなかった。固定値での検査は,2 500個のモデルのすべてでオラクルと 一致した。コードに故意に入れた5つの健全性の誤りは,それぞれ検出された。プロファイルのもとでの利得と 最適応答値を,プロファイルに対する1人のプレイヤーのゲームをMDPとして書き,Storm(stormpy 2.0.0, 厳密)と比べた。90個の値が,有理数としてすべて一致した。
  • 独立したレビューは,生成した860個のモデルをコマンドライン(cadl check,cadl game-check --certify) で実行した。決定したセルの厳密な点評価は76 921回であり,誤った主張はなかった。244個の最適応答値を Stormと比べ,すべて一致した。cadl 0.3.22に対する退行はなかった。
  • grounding のない端点,概念 every_reachable_state,3人と4人のプレイヤーのゲームの,実装者による 検証。上のオラクルを,Reach_p のどの状態からの逸脱利得と,報告された状態とその逸脱の検査で拡張して 用いた。無作為に生成した2 350個のゲームであり,プレイヤーが2人のものが1 109個,3人のものが1 009個, 4人のものが232個,開いているパラメータが3つのマップが472個である。750個は every_reachable_state だけを問い,850個は2つの概念の一方を無作為に選んだ。461個の not_equilibrium のセルは,s₀ 以外の 状態から確立した(N_s)。端点は590個のマップで使え,領域全体,その半分,4分の1,無作為な部分区間でも 直接試した(equilibrium が2 629個,not_equilibrium が1 222個の主張)。決定したセルの厳密な点評価は 74 531回であり,誤った主張はなかった。固定値での検査は,どのモデルでもオラクルと一致した。故意に 入れた5つの誤り(確率についての部分を除いた条件A,重みのアフィン性を除いた条件A,どのプレイヤーにも Bを仮定すること,到達可能性の保証 R⁺_C(p) を除いたN_s,every_reachable_state に nash の条件を 用いること)は,それぞれファジングで検出され,さらに,テストスイートの固定したファイルで,誤った 主張として決定的に検出される。そのファイルは,J.11のこぶのファイルから grounding を除いたもの, 逸脱利得 |1 − 2ℓ| を持つもの,プレイヤー自身の逸脱だけが確率 p で到達する状態を持つものである。 このバージョンの独立したレビューの2つのファイルもテストスイートに加えた。一方では,6つ目の故意の誤り (条件Bを s₀ から検査し,どの状態にも当てはめること)が,到達可能などの状態からも均衡である ところで逸脱者を主張する。他方では,R⁺_C(p) のないN_sが,p = 0 を含むセルを決定する。そのセルは 未決定のままでなければならない。 0.3.23の独立したレビューの生成器を,新しいコードに対して再び実行した。コマンドラインで,付録Jのレビューの10個の生成設定(600個のモデル)とマップのレビューの ドライバ(160個のモデル)を用い,決定したセルの厳密な点評価は15 467回であり,誤った主張はなかった。同梱の例と レビューのファイルでの cadl game-check の主張は,0.3.23と同じである。
  • 開いているパラメータが3つのマップ。同梱の例でパラメータをもう1つ開いて測定した(1つ目の例では λ ∈ [0, 0.4],p_fail ∈ [0, 0.5],p_loss ∈ [0, 0.5],2つ目の例では CENTRALIZED でプロファイル comply_if_watched について λ,κ ∈ [0, 0.4] と p_fail ∈ [0, 0.5])。予算は既定値(--max-cells 20000) であり,時間はノートパソコンでのプロセッサ時間である。0.3.26までと同じくPD+とPD−を使わない場合, 1つ目の例では,DISTRIBUTED は,解析したセル3 891個で分解能0.1に達し(結合後139個。領域の0.838が equilibrium,0.062が not_equilibrium),15 853個で0.05に達する(結合後526個)。CENTRALIZED は, 解析したセル39 999個で予算を使い切り,未決定は0.269である(結合後1 059個。0.700が equilibrium, 0.030が not_equilibrium)。両方の設計で50秒(分解能0.1)と82秒(0.05)かかる。2つ目の例も予算を 使い切り,39 999個のセルの後で未決定は0.260である(77秒)。境界に接するセルは3つの方向のどれでも 小さくなければならず,NとE1は2つの異なる関数の界を比べるので,利得が強く依存するパラメータの方向に 幅の広いセルでは,界が離れる。CENTRALIZED では,λ = 0 の近くのセルは,p_fail と p_loss の幅が1/32 でも,中心で R が約0.23だけ得をするのに未決定のまま残る。PD+とPD−を使うと(0.3.26の次の バージョンから),CENTRALIZED は,解析したセル7 987個で分解能0.1に達し(結合後921個。0.849が equilibrium,0.051が not_equilibrium),27 031個で0.05に達する(結合後3 037個。0.889と0.062)。 DISTRIBUTED は463個(結合後39個)と2 271個(結合後154個)である。両方の設計で18秒(分解能0.1)と 64秒(0.05)かかる。concept: every_reachable_state は,PD+とPD−の有無にかかわらず,nash と同じ セルを与える。0.3.27までは,2つ目の例は予算を使い切り,39 999個のセルの後で未決定は0.200であった(結合後290個。 0.410が equilibrium,0.390が not_equilibrium。92秒)。この例では,初期状態での配車係にとっての trust の優位は,監視される場合とされない場合の2つの異なる後続状態の値の差である。PD+はこれを2つの 状態の l_p と u_p で抑えるが,これらはE1の界と同じく p_fail とともに離れる。p_fail の幅が1/8のセルでは, D の逸脱利得の上界は,頂点での逸脱利得の最大値を約0.1から0.4上回る。I.9の結合した界を使うと(cadl 0.3.28 から),2つ目の例は,解析したセル13 853個で分解能0.1に達する(結合後208個。0.459が equilibrium,0.441が not_equilibrium)。そのうち3 049個のセルでは,結合した界が D を決定する (PD+で1 910個,PD−で1 139個)。λ ∈ [0, 0.1],κ ∈ [0.1, 0.2],p_fail ∈ [0, 1/8] のセルでは,trust の優位の界は,l_p と u_p によるものが [−0.150, 0.203],結合した緩和によるものが [−0.080, 0.122] であり, セルの上の格子の125点での厳密な優位は [−0.059, 0.112] に収まる。同じ計算機で続けて測ると,マップは 結合した界を使って52秒,使わずに(0.3.27と同じく)127秒かかった。1つ目の例のマップは変わらない (どちらの分解能でもセルは同じであり,時間は0.1で約2%,0.05で約9%増える)。そこでの R の優位は,値が 付値によらない状態と,付値による状態とを比べるものだからである。I.12のマップも変わらない。0.3.27の ために試したカップリングによる緩和は,2つの道を等しい状態でだけ合わせ,他の条件が決めなかったすべての セルで用いたもので,39 999個のセルの後で未決定は0.129であり,約4倍の時間がかかった。2つの道の更新を そろえる同時分布と,上に述べた,結合した界を計算する場所の制限によって,この差が生じた。結合した緩和でも 各ステップが頂点を選ぶので,優位の符号が変わるセルは小さくなければならない。0.3.28までは,多重 アフィンでない確率には用いなかった。持ち上げの測定は下に述べる。上のファジングでは,プレイヤーが3人または4人で,多くは開いている パラメータが3つのゲームが,1個あたり約0.9秒であった(実時間。検査,予算24個のセルのマップ, オラクルを含む)。
  • PD+とPD−の,実装者による検証(cadl 0.3.27)。上のオラクルを用いた。tests/games_fuzz.py の無作為なゲーム5 200個であり,最初の検証と同じ種類のものが2 600個,every_reachable_state を問う ものが800個,プレイヤーが3人または4人のもの(その3分の2は開いているパラメータが3つ)が900個, grounding のない端点のゲームが700個,grounding のあるものが200個である。equilibrium のセルが 3 486個,not_equilibrium のセルが4 693個,厳密な点評価は167 069回であり,誤った主張はなかった。 固定値での検査は,どのモデルでもオラクルと一致した。独立したレビューのドライバをコマンドラインで 実行した。マップのレビューのドライバ(860個のモデル,点評価16 042回),付録Jのレビューの10個の 生成設定(600個のモデル,点評価5 868回),0.3.24のレビューの8個の設定(560個のモデル,点評価 7 149回)であり,誤った主張はなかった。新しい条件に故意に入れた3つの誤り(後続状態の項を除くこと, 優位の下界と上界を入れ替えること,利得と確率の差をセルの中心だけで取ること)は,それぞれファジングと テストスイートで検出される。以前の故意の誤りは,PD+とPD−を使わずに実行し,引き続き検出される。
  • 結合した界の,実装者による検証(cadl 0.3.28)。上のオラクルを用いた。PD+とPD−のときと 同じ種類の tests/games_fuzz.py の無作為なゲーム5 200個で,equilibrium のセルが3 455個, not_equilibrium のセルが4 913個,厳密な点評価は170 529回であり,誤った主張はなかった。プレイヤーが 結合した界によるPD+またはPD−で決定されたのは1 188回である。多重アフィンなゲームでは,領域全体と 無作為な2つの部分の箱の上の結合した界をすべて,オラクルが標本点で計算する優位と直接に比べた。比較は 251 933回であり,界の外に出たものはなかった。以前の独立したレビューのドライバは手元になかったので, コマンドラインを通すドライバ(4種類の生成したゲーム860個に cadl game-check --certify --format json を実行し,決定したセルをオラクルで確かめる)を用い,厳密な点評価25 530回で誤った主張はなかった。 結合した界に故意に入れた3つの誤り(最大値と最小値を入れ替えること,最初のステップのステップ利得の差を 除くこと,最初のステップより後のステップ利得を除くこと)は,それぞれ,ファジングでのマップの主張, 直接の比較,tests/test_games_coupling.py の2つ目の例のセルで検出される。
  • 多重アフィンでない確率(cadl 0.3.29)。上の3パラメータのマップで,成功確率の因子の1つを 置き換えたものを,既定の予算で測った。2つ目の例では,1 − p_fail の代わりに (1 − p_fail)² と 1 − 4 · p_fail · (1 − p_fail) を用いたもの(λ,κ,p_fail は上と同じ)と, 1 − p_fail · q_local · (1 − q_local) を用いて λ ∈ [0, 0.4], p_fail ∈ [0, 0.5],q_local ∈ [0, 1] の上で マップを求めたもの(κ = 0.05)である。1つ目の例では,(1 − p_fail)² を用いたもの(three_10, CENTRALIZED)である。持ち上げを用いないと(0.3.28と同じ),2つ目の例の3つのマップはどれも予算を 使い切り,39 999個のセルの後で未決定はそれぞれ0.673,0.891,0.180である。区間演算による囲みだけで 持ち上げると,39 999個のセルの後で0.225,0.594,0.105である。持ち上げた座標にベルンシュタイン係数による 囲みを用いると,最初の2つは39 999個のセルの後で0.174と0.431であり,3つ目は32 083個のセルで分解能0.1に 達する(未決定は0.100)。1台のラップトップで,持ち上げの有無の2つを同時に実行して測ると(実時間),2つ目の 例のマップは,(1 − p_fail)² で161秒と237秒,4 · p_fail · (1 − p_fail) で148秒と237秒, p_fail · q_local · (1 − q_local) で142秒と146秒(セルは39 999個に対して32 083個)であった。持ち上げると, 組は2³個の頂点に代えて最大2⁴ = 16個の持ち上げた頂点から選ぶので,1つのセルの計算が重くなる。 1つ目の例のマップは,持ち上げの有無で変わらない(39 999個のセルの後で未決定は0.231。どちらも122秒)。 多重アフィンな場合に,結合した界の有無で変わらなかったのと同じである。2つ目の例に 残る未決定のセルの多くは,緩和そのものから生じる。4 · p_fail · (1 − p_fail) のような確率を単項式ごとの 区間演算で囲むと幅が広く,p_fail = 1/2 の近くでは1を超えるので,そのセルでは設計が良定義であることを 示せない。N,E1,E2 と界 l_p,u_p は,この囲みを用いる。
  • 持ち上げの,実装者による検証(cadl 0.3.29)。上のオラクルと,tests/games_fuzz.py の生成 オプション --mode nonaffine を用いた。このオプションは,確率 p²,1 − p², 4p(1 − p),pq(1 − q),q², p²q,(1 − p)²,1/2 + pq(1 − q)/2 を用い,コマンドが複数ある状態の半分では,最初のコマンドの確率を 別の後続状態とともに用いる。最終のコードで,ゲーム3 800個を調べた(--mode nonaffine のものが2 700個で, そのうち600個は every_reachable_state を問う。既定の種類のものが800個,プレイヤーが3人または4人で 両方の概念を問うものが300個)。そのうち3 090個は多重アフィンでない確率を持つ。equilibrium のセルが 2 247個,not_equilibrium のセルが2 792個,厳密な点評価は90 372回であり,誤った主張はなかった。 固定値での検査は,どのモデルでもオラクルと一致した。多重アフィンでないゲームのプレイヤーが,結合した 界によるPD+またはPD−で決定されたのは1 504回である。領域全体と無作為な2つの部分の箱の上の結合した 界をすべて,オラクルが標本点で計算する優位と比べた。比較は213 153回で,そのうち147 959回は多重 アフィンでないゲームのものであり,界の外に出たものはなかった。これらのゲームでは,頂点が緩和との 照合に失敗したことはなかった。これらのゲームでは,コマンドごとの持ち上げた関数は1つまでである。独立した レビューは,1つのコマンドに持ち上げた関数が複数あるもの(持ち上げた多項式の1つが,1から他のものを 引いたものになる),確率の中の λ,6次までの次数を加えた。これらは --mode nonaffine でも生成するように した。そのようなゲーム1 600個と,レビューの生成器によるゲーム200個では,equilibrium のセルが836個, not_equilibrium のセルが1 030個,厳密な点評価は29 326回,多重アフィンでないゲームでの直接の比較は 40 048回であり,誤った主張も界の外に出たものもなかった。持ち上げた多項式を置き換えたコマンドは685個, 頂点が照合に失敗してその界を用いなかったのは115回である。ベルンシュタイン係数による囲みを用いない 以前の実行(ゲーム4 400個, 点評価99 569回,多重アフィンでないゲームでの比較166 698回)と,コマンドラインを通すドライバ (--mode nonaffine のゲーム300個,点評価7 638回)でも,誤った主張はなかった。持ち上げに故意に入れた 3つの誤りは,それぞれ直接の比較で検出される。多重アフィンでない確率を持ち上げずにセルの頂点で評価 すること,持ち上げた座標の区間を中心での値に縮めること,囲みの下半分に縮めることである。後の2つは, ファジングでのマップの誤った主張と,(1 − p_fail)² を用いた2つ目の例のセルでの誤った界も生む (tests/test_games_coupling.py)。最初のものは, ゲーム4 500個でマップの誤った主張を生まず,その例でも 誤った界を生まなかった。その例の確率は p_fail について単調で凸だからである。
  • 厳密な値の範囲とベルマン方程式による展開(cadl 0.3.31)。まず未決定のセルを分類した。同梱の例のマップ, 2つ目の例の3パラメータのマップとその (1 − p_fail)² のもの,tests/games_fuzz.py のゲーム45個のマップを 一様に分割し(パラメータが1つなら32区間,2つなら各12区間,3つなら各5区間),未決定の各セルの頂点,面の中心, 中心と無作為な4点で厳密な主張を求めた。主張が変わるセル(領域を単位として2.96)は,どの十分条件でも決定 できない。残り(6.72)のうち4.87は区間演算による囲みのために not_well_defined であり,残りの大部分は, 後続状態の値を l_p と u_p の間にあるとする優位の界から生じていた。これらのマップでは,持ち上げたセルの頂点が緩和との 照合に失敗したことはなく,持ち上げた座標を10個より多く要する設計もなかった。上の変更により,主張が変わらない 未決定の部分は0.67に減った。これはすべて持ち上げた関数を持つ4個のファジングのゲームにあり(そのうち2個で 0.62),結合した界が広すぎるためである。主張が変わるセルは2.90になった。一様な分割の計算時間は約2倍になった (全体で10秒に対して19秒)。二分と既定の予算で(プロセッサ時間。変更の前後のマップを1台で同時に実行した), 1つ目の例の comply_by_lambda_and_failure は,解析したセル567個に対して125個で分解能に達する。上の3パラメータの マップは,1つ目の例で7 987個と463個に対して363個と291個(32秒に対して6秒),2つ目の例で13 853個に対して 4 059個(84秒に対して31秒)で分解能0.1に達する。多重アフィンでない確率では,2つ目の例は,(1 − p_fail)² で 5 311個(61秒)で達する。以前は39 999個の後で0.174が未決定であった(291秒)。1 − 4 · p_fail · (1 − p_fail) では 11 103個(111秒)で達する(以前は39 999個の後で0.431,284秒)。1 − p_fail · q_local · (1 − q_local) では 349個(6秒)で達する(以前は32 083個,199秒)。1つ目の例は (1 − p_fail)² で2 551個(33秒)で達する (以前は39 999個の後で0.231が未決定,152秒)。分類に用いた56個のマップでは(テストとファジングのマップは予算200個のセル), 未決定の割合の平均は0.112から0.049に減った。決定したセルの主張が変わったことはない。変更の前後のマップの決定したセルは, 重なるところではいつも同じ状態であった(上のマップとファジングのゲーム80個で,重なる組が465個)。変更の後に だけ決定したセル145個の中心では,cadl の均衡の検査はセルの主張を与え,下に述べる方法でPRISM-games 3.2.4と 一致した(判定509回,状態の値42 128個で,違いはなかった)。
  • 厳密な値の範囲とベルマン方程式による展開の,実装者による検証(cadl 0.3.31)。上のオラクルを用いた。オラクルは, l_p と u_p による優位の界とベルマン方程式による展開の界も,標本点での優位と直接に比べる。ゲーム1 800個 (既定の種類と --mode nonaffine が700個ずつで,それぞれ300個は every_reachable_state を問う。プレイヤーが 3人または4人で両方の概念を問うものが200個,--mode endpoints が200個。多重アフィンでない確率を持つものは 1 133個)で,equilibrium のセルが1 297個,not_equilibrium のセルが1 690個,厳密な点評価が59 875回,直接の 比較が583 214回(多重アフィンでないゲームで417 596回)であり,誤った主張も界の外に出たものもなかった。 ベルマン方程式による展開を用いたPD+またはPD−でプレイヤーが決定されたのは2 361回であり,not_well_defined のセルはなかった。故意に入れた2つの誤りは,それぞれ直接の比較とマップの誤った主張で検出される。多項式の 値の範囲をセルの頂点での値からとることと,展開の後に残る値をその界の中点で厳密であるとみなすことである。 端点と,N,E1,E2,N_s に故意に入れた誤りは,区間演算による囲みで実行する。これにより,セルはそれらが 関わる条件に達する。
  • cadl 0.3.27からは,I.11のエクスポートを,PRISM-gamesプロジェクトが配布するバイナリ (prismmodelchecker.org/games。macOS arm64用とLinux x86-64用)のPRISM-games 3.2.4で実行する。 エクスポートしたモデルファイルをそのまま渡し,その後に,プレイヤーのアクションラベルで同期し, 1人を除くどのプレイヤーにもプロファイルのコマンドだけを取らせるモジュールと,プレイヤーごとの 報酬構造を加える。PRISM-gamesは負の報酬を受け付けず,ゲームについては厳密な計算の機能を持たない。 そのため,V_p は,どのプレイヤーもプロファイルに従うときの <<p>> R{"r"}max=? [ F φ_p ] によって, エクスポートした報酬構造から項ごとに計算する。V*_p は,報酬構造 ρ_p(s, c) + h(s) − Σ_s′ P(s, c, s′) · h(s′) から計算する。h(s) を,s から φ_p までのステップ数の 期待値の最大値の倍数とすれば,この報酬は負にならない。加えた項はどの道に沿っても打ち消し合うので, s からの最大値は V*_p(s) + h(s) である。値は値反復(-e 1e-12)で得たものであり,相対許容誤差 10⁻⁶ で比べる。同梱の3つの例と tests/games_fuzz.py の200個のゲーム(プレイヤーは2人から4人, 両方の概念,端点のゲームを含む)について,設計とプロファイルの212個の組で,状態の数,2 240個の 利得と最適応答値,Reach_p の7 813個の状態での V_p と V*_p − V_p,212個の status と逸脱者 (そのうち118個では逸脱利得が ε に等しく,そこでは cadl の厳密な逸脱利得も ε である),69個の from_every_state の値が,cadl game-check と一致した。先に実行した別の200個のゲームでも 一致した。エクスポートの誤りを1つ見つけて直した(I.11)。設計のコマンドを1つも所有しないプレイヤーを 書かなかったので,所有者のあるコマンドを持たない設計からは,プレイヤーのない smg のファイルが生じ, PRISM-gamesはこれを受け付けなかった。名前が変数,ラベル,アクションラベル,パラメータ,報酬構造, モジュール main に等しいプレイヤーは受け付けられる。tests/test_games_prism_games.py は, PRISM-gamesがインストールされていれば比較を実行する。CIは,1つのPythonのバージョンについて Linux用の配布物をインストールする(テストは12個。ノートパソコン上のエミュレートしたLinux x86-64の コンテナで約7分)。

I.15 後方互換性​

本拡張を用いないCADL v0.3のファイルは引き続き有効であり,同じように読まれる。stochastic: 0.1 を 宣言し,games: 0.1 を宣言しないファイルは,付録Hによってそのまま読む。H.1が予約する名前は そのファイルでは予約されたままであり,S-1,S-9,S-15が適用される。

games: 0.1 を宣言せずに kind: smg または本付録のキーを用いるファイルは,本付録に適合しない。 本拡張を実装する処理系は,そのようなファイルの model: ブロックを付録Hによって読み,それらのキーを 宣言されていない拡張として,情報レベルの診断で報告することが望ましい。stochastic: 0.1 なしに games: 0.1 を宣言する ファイルには,I-1の誤りを出す。

付録Hを実装し,本付録を実装していない処理系は,戦略モデルをマルコフ連鎖として読むことができない。 games: 0.1 を宣言し,kind: が dtmc でないモデルを持つファイルをそのような処理系がどう扱うかは, H.10(S-1)とH.15が述べる。処理系は,1つの情報レベルの診断を出して モデルを読み飛ばし,それをマルコフ連鎖として評価してはならない。そのブロックには,S-2からS-15の 検査をせず,IRへ変換せず,エクスポートしない。どちらの拡張も実装していない処理系は, model: を理由にファイルを拒否してはならない。ファイルごとに1つの情報レベルの診断を出すことが 望ましい。