戦略耐性

メカニズム設計において、戦略不可能性 (SP) メカニズムとは、各プレイヤーが弱優位戦略を持つゲーム形式であり、他のプレイヤーが何をプレイしようとしているのかを「スパイ」することで利益を得るプレイヤーはいない。プレイヤーが秘密情報 (たとえば、自分のタイプや何らかのアイテムに対する自分の値) を持ち、各プレイヤーの戦略空間が可能な情報値 (たとえば、可能なタイプや値) で構成されている場合、真実のメカニズムとは、真の情報を明らかにすることが各プレイヤーにとって弱優位戦略となるゲームである。^{[1] : 244} SPメカニズムは、他の種類のインセンティブ適合性と区別するために、優位戦略インセンティブ適合 (DSIC)とも呼ばれる^{[1] : 415}。

SPメカニズムは、個々のプレイヤーによる操作の影響を受けません（ただし、連合による操作は除きます）。対照的に、グループ戦略不可能メカニズムでは、すべてのメンバーがより良い結果を得るような方法で、グループの人々の好みを誤って報告するために共謀することはできません。強力なグループ戦略不可能メカニズムでは、グループの人々の少なくとも1人のメンバーの利益が高まり、残りのメンバーの誰も不利益にならないような方法で、グループの人々の好みを誤って報告するために共謀することはできません。^[2]

SP メカニズムの典型的な例は次のとおりです。

• 2つの選択肢の間での多数決。
• 参加者が準線形効用を持つ場合の第二価格オークション。
• 参加者が準線形効用を持つ場合のVCGメカニズム

SP ではないメカニズムの典型的な例は次のとおりです。

• 3 つ以上の選択肢の間で行われる決定論的かつ非独裁的な選挙。
• ファーストプライスオークション

SP はネットワーク ルーティングにも適用できます。^[要出典]ネットワークをグラフとして考えてみましょう。グラフでは、各エッジ (つまりリンク) には、リンクの所有者だけが知っている送信コストが関連付けられています。リンクの所有者は、メッセージを中継することに対して報酬を受け取りたいと考えています。ネットワーク上のメッセージの送信者として、最小コストのパスを見つけたいと考えます。大規模なネットワークであっても、これを行うための効率的な方法があります。ただし、1 つの問題があります。各リンクのコストが不明であることです。単純なアプローチは、各リンクの所有者にコストを尋ね、これらの宣言されたコストを使用して最小コストのパスを見つけ、パス上のすべてのリンクに宣言されたコストを支払うことです。ただし、この支払い方式は SP ではないことが示されています。つまり、一部のリンクの所有者は、コストについて嘘をつくことで利益を得ることができます。実際のコストよりもはるかに多くの金額を支払うことになるかもしれません。ネットワークとプレーヤー (リンクの所有者) に関する特定の仮定を前提とすると、VCG メカニズムのバリアントが SP であることが示されています。^[要出典]

考えられる結果はいくつかあります。 ${\displaystyle X}$

それぞれの結果に対して異なる評価を持つエージェントが存在します。エージェントの評価は関数として表されます。 ${\displaystyle n}$${\displaystyle i}$

${\displaystyle v_{i}:X\longrightarrow R_{+}}$

これは、各選択肢の価値を金銭的に表したものです。

エージェントは準線形効用関数を持つと仮定します。つまり、結果が であり、さらにエージェントが支払い（正または負）を受け取る場合、エージェントの総効用は次のようになります。 ${\displaystyle x}$${\displaystyle p_{i}}$${\displaystyle i}$

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

すべての価値関数のベクトルは で表されます。 ${\displaystyle v}$

すべてのエージェント について、他のエージェントのすべての価値関数のベクトルは で表されます。つまり です。 ${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle v\equiv (v_{i},v_{-i})}$

メカニズムとは、次の機能のペアです。

• 値ベクトルを入力として受け取り、結果を返す関数（社会的選択関数とも呼ばれます）。${\displaystyle 結果}$${\displaystyle v}$${\displaystyle x\in X}$
• 値ベクトルを入力として受け取り 、各プレイヤーが受け取るべき金額を決定する支払いベクトルを返す関数(負の支払いは、プレイヤーが正の金額を支払う必要があることを意味します)。${\displaystyle 支払い}$${\displaystyle v}$${\displaystyle (p_{1},\dots ,p_{n})}$

すべてのプレイヤーと他のプレイヤーのすべての値ベクトルに対して次の条件が満たされる場合、メカニズムは戦略的証明が不可能であると呼ばれます。 ${\displaystyle i}$${\displaystyle v_{-i}}$

${\displaystyle v_{i}(結果(v_{i},v_{-i}))+支払い_{i}(v_{i},v_{-i})\geq v_{i}(結果(v_{i}',v_{-i}))+支払い_{i}(v_{i}',v_{-i})}$

特定のメカニズムが SP であるかどうかを確認するための簡単な条件があると便利です。このサブセクションでは、必要かつ十分な 2 つの簡単な条件を示します。

金銭移転を伴うメカニズムがSPである場合、すべてのエージェントに対して次の2つの条件を満たす必要があります。^{[1] : 226}${\displaystyle i}$

1.エージェントへの支払いは、選択された結果と他のエージェントの評価の関数であり、エージェント自身の評価の直接的な関数ではありません。正式には、他のエージェントの結果と評価ベクトルを入力として受け取り、任意の に対して、次の条件を満たすエージェントへの支払いを返す価格関数 が存在します。 ${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle v_{i}}$${\displaystyle 価格_{i}}$${\displaystyle x\in X}$${\displaystyle v_{-i}}$${\displaystyle i}$${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle 結果(v_{i},v_{-i})=結果(v_{i}',v_{-i})}$

それから：

${\displaystyle 支払い_{i}(v_{i},v_{-i})=支払い_{i}(v_{i}',v_{-i})}$

証明: の場合、評価を持つエージェントはを報告することを好みます。これは、同じ結果とより大きな支払いを得られるためです。同様に、 の場合、評価を持つエージェントはを報告することを好みます。 ${\displaystyle 支払い_{i}(v_{i},v_{-i})>支払い_{i}(v_{i}',v_{-i})}$${\displaystyle v_{i}'}$${\displaystyle v_{i}}$${\displaystyle 支払い_{i}(v_{i},v_{-i})<支払い_{i}(v_{i}',v_{-i})}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$

結果として、「値札」関数 が存在し、これは他のエージェント の結果と評価ベクトルを入力として受け取り、次の条件を満たすごとにエージェント の支払いを返します。 ${\displaystyle 価格_{i}}$${\displaystyle x\in X}$${\displaystyle v_{-i}}$${\displaystyle i}$${\displaystyle v_{i},v_{-i}}$

${\displaystyle 結果(v_{i},v_{-i})=x}$

それから：

${\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}$

2.選択された結果は、他のエージェントの評価を考慮すると、エージェントにとって最適です。正式には、 ${\displaystyle i}$

${\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}$

ここで、最大化は の範囲内のすべての結果にわたって行われます。 ${\displaystyle Outcome(\cdot ,v_{-i})}$

証明:となる別の結果がある場合、評価を持つエージェントは、より大きな総効用をもたらすため、 を報告することを好みます。${\displaystyle x'=Outcome(v_{i}',v_{-i})}$${\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$

条件 1 と 2 は必要であるだけでなく十分でもあります。条件 1 と 2 を満たすメカニズムはすべて SP です。

証明: エージェントと評価を固定します。以下を示します。 ${\displaystyle i}$${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle x:=Outcome(v_{i},v_{-i})}$- エージェントが誠実に行動した場合の結果。

${\displaystyle x':=Outcome(v_{i}',v_{-i})}$- エージェントが不正行為をした場合の結果。

特性 1 によれば、エージェントが正直にプレイする場合の効用は次のようになります。

${\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}$

エージェントが不正行為をしたときの効用は次のようになります。

${\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}$

プロパティ2により:

${\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}$

したがって、エージェントが誠実に行動することが優勢な戦略となります。

メカニズムの実際の目標はその機能です。支払い機能は、プレイヤーに正直になるように誘導するための単なるツールです。したがって、特定の結果関数が与えられた場合、それが SP メカニズムを使用して実装できるかどうかを知ることは有用です (このプロパティは実装可能性とも呼ばれます)。^[要出典]${\displaystyle Outcome}$

単調性は戦略耐性に必要である。^[要出典]

単一パラメータドメインとは、各プレイヤーが「勝利」に対して特定の正の値を獲得し、「敗北」に対して値 0 を獲得するゲームです。簡単な例としては、プレイヤーがアイテムに割り当てる 値が単一アイテムのオークションがあります。${\displaystyle i}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle i}$

この設定では、真実のメカニズムを特徴付けるのは簡単です。まずはいくつかの定義から始めましょう。

すべての負けた入札が 0 を支払う場合、メカニズムは正規化されていると呼ばれます。

プレイヤーが入札額を上げると、勝つ可能性が（弱く）増加する メカニズムは単調であると呼ばれます。

単調なメカニズムの場合、すべてのプレイヤーiと他のプレイヤーの入札のすべての組み合わせに対して、プレイヤーが負けから勝ちに変わる 臨界値が存在します。

単一パラメータ領域上の正規化メカニズムは、次の2つの条件が満たされる場合に真実である：^{[1] ：229–230}

1. 割り当て関数は各入札において単調であり、次のようになります。
2. 落札するたびに重要な価値が支払われます。

真実性の概念をランダム化メカニズムに拡張する方法は様々ある。最も強力なものから最も弱いものの順に、以下の通りである。^{[3] : 6–8}

• 普遍的な真実性: アルゴリズムの各ランダム化に対して、結果として得られるメカニズムは真実です。言い換えると、普遍的に真実なメカニズムとは、重みが入力に依存する可能性がある、決定論的な真実なメカニズムに対するランダム化です。
• 強い確率的優位の真実性 (強い SD 真実性) : エージェントが正直であることで受け取る確率のベクトルは、誤った報告によって受け取る確率のベクトルに対して1 次確率的優位を持ちます。つまり、最優先事項を取得する確率は少なくとも同じくらい高く、2 つの最優先事項のうちの 1 つを取得する確率は少なくとも同じくらい高く、m 個の最優先事項のうちの 1 つを取得する確率は少なくとも同じくらい高くなります。
• 辞書的真実性 (lex-truthfulness) : エージェントが正直であることで受け取る確率のベクトルは、誤った報告によって受け取る確率のベクトルよりも辞書的優位性を持ちます。つまり、最優先を取得する確率の方が高い、または (最優先を取得する確率は等しく、2 つの最優先のうちの 1 つを取得する確率の方が高い)、または... (最初のm -1 の優先順位を取得する確率は等しく、m 個の最優先のうちの 1 つを取得する確率の方が高い)、または (すべての確率が等しい) です。
• 弱い確率的優位の真実性 (弱い SD 真実性) : エージェントが真実を語ることによって受け取る確率のベクトルは、エージェントが誤報をすることによって受け取る確率のベクトルによって一次確率的に優位にはなりません。

普遍性は強いSDを意味し、Lexは弱いSDを意味し、すべての含意は厳密である。^{[3] : Thm.3.4}

任意の定数 に対して、ランダム化メカニズムが確率 で真実であるとは、任意のエージェントと任意の入札ベクトルに対して、エージェントが不誠実な入札によって利益を得る確率が最大 であり、確率がメカニズムのランダム性を上回る場合を言う。^{[1] : 349}${\displaystyle \epsilon >0}$${\displaystyle 1-\epsilon }$${\displaystyle \epsilon }$

入札者の数が増えたときに定数が0 に近づく場合、そのメカニズムは高い確率で真実であると呼ばれます。この概念は完全な真実性よりも弱いですが、それでも場合によっては有用です。たとえば、コンセンサス推定を参照してください。 ${\displaystyle \epsilon }$

インターネット オークションの増加に伴い一般的になった新しいタイプの詐欺は、偽名入札です。これは、1 人の入札者が複数の電子メール アドレスなどの複数の識別子を使用して入札するものです。

偽名防止性とは、どのプレイヤーにも偽名入札をする動機がないことを意味します。これは戦略防止性よりも強い概念です。特に、ヴィックリー・クラーク・グローブス（VCG）オークションは偽名防止性がありません。^[4]

偽名耐性は、通常は複数の個人の共謀を必要とする特定の行動を、個人が単独でシミュレートできることを前提としているため、グループ戦略耐性とは重要な点で異なります。^{[要出典] [さらなる説明が必要]}

• インセンティブの互換性
• 個人の合理性
• 参加基準- プレイヤーはゲームをプレイすることで負けることはない（つまり、プレイヤーにはゲームのプレイを避ける動機がない）

• Parkes, David C. (2004)、「学習可能なメカニズム設計について」、Tumer, Kagan、David Wolpert (編)、『集団と複雑系の設計』、ニューヨーク出版、pp. 107–133。
• 古典的な社会選択ルールの漸近的戦略証明性について 投票システムにおける戦略証明性に関する Arkadii Slinko による記事。