メカニズム設計 において、戦略耐性（SP）メカニズム とは、各プレイヤーが弱支配戦略を持つ ゲーム形式 であり、どのプレイヤーも他のプレイヤーを「スパイ」して、他のプレイヤーが何をプレイしようとしているかを知ることで利益を得ることができない。プレイヤーがプライベート情報（例えば、自分のタイプやあるアイテムに対する自分の価値）を持ち、各プレイヤーの戦略空間が可能な情報値（例えば、可能なタイプや値）で構成される場合、真実メカニズム とは、真の情報を開示することが各プレイヤーにとって弱支配戦略となるゲームである。[ 1 ] ： 244 インセンティブ互換性 と区別するために、支配戦略インセンティブ互換（DSIC） とも呼ばれる。[ 1 ] ： 415
SPメカニズムは、個々のプレイヤーによる操作には耐性がある（ただし、連合による操作には耐性がない）。対照的に、グループ戦略耐性メカニズム では、いかなるグループも、全員の利益になるように好みを偽って報告するために共謀することはできない。強力なグループ戦略耐性メカニズムでは、 いかなるグループも、残りのメンバーの利益を損なうことなく、少なくとも1人のメンバーの利益を増やすように好みを偽って報告するために共謀することはできない。[ 2 ]
例 SPメカニズムの典型的な例は以下のとおりです。
SPではない メカニズムの典型的な例は次のとおりです。
ネットワークルーティングにおけるSP SPはネットワークルーティング にも適用できます。ネットワークをグラフとみなし 、 各エッジ（つまりリンク）には、リンクの所有者のみが知っている伝送コストが関連付けられているとします。リンク の所有者は、メッセージを中継することに対して報酬を受け取りたいと考えています。ネットワーク上でメッセージを送信する側としては、最小コストのパスを見つけたいと考えます。大規模なネットワークであっても、これを行うための効率的な方法があります。しかし、1つの問題があります。各リンクのコストが不明であることです。単純なアプローチとしては、各リンクの所有者にコストを尋ね、これらの申告されたコストを使用して最小コストのパスを見つけ、パス上のすべてのリンクに申告されたコストを支払うという方法があります。しかし、この支払い方式はSPではないことが示せます。つまり、一部のリンクの所有者はコストについて嘘をつくことで利益を得ることができます。結果として、実際のコストよりもはるかに多くの金額を支払うことになる可能性があります。ネットワークとプレーヤー（リンクの所有者）に関する特定の仮定の下では、VCGメカニズム の変種がSPであることが示せます。
特性評価 与えられたメカニズムがSPであるかどうかを確認するための簡単な条件があると便利です。このサブセクションでは、必要かつ十分な2つの簡単な条件を示します。
金銭移転を伴うメカニズムがSPである場合、すべてのエージェントについて、以下の2つの条件を満たさなければならない。私 {\displaystyle i} [ 1 ] :
1. 代理店への支払い私 {\displaystyle i} v − 私 {\displaystyle v_{-i}} ではない。 v 私 {\displaystyle v_{i}} P r 私 c e 私 {\displaystyle Price_{i}} x ∈ X {\displaystyle x\in X} v − 私 {\displaystyle v_{-i}} 私 {\displaystyle i} v 私 、 v 私 ′ 、 v − 私 {\displaystyle v_{i},v_{i}',v_{-i}}
O u t c o m e （ v 私 、 v − 私 ） = O u t c o m e （ v 私 ′ 、 v − 私 ） {\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})} それから：
P 1 y m e n t 私 （ v 私 、 v − 私 ） = P 1 y m e n t 私 （ v 私 ′ 、 v − 私 ） {\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})} 証明: もしP 1 y m e n t 私 （ v 私 、 v − 私 ） > P 1 y m e n t 私 （ v 私 ′ 、 v − 私 ） {\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})} v 私 ′ {\displaystyle v_{i}'} v 私 {\displaystyle v_{i}} P 1 y m e n t 私 （ v 私 、 v − 私 ） < P 1 y m e n t 私 （ v 私 ′ 、 v − 私 ） {\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})} v 私 {\displaystyle v_{i}} v 私 ′ {\displaystyle v_{i}'}
その結果として、「値札」関数が存在する。P r 私 c e 私 {\displaystyle Price_{i}} x ∈ X {\displaystyle x\in X} v − 私 {\displaystyle v_{-i}} 私 {\displaystyle i} v 私 、 v − 私 {\displaystyle v_{i},v_{-i}}
O u t c o m e （ v 私 、 v − 私 ） = x {\displaystyle Outcome(v_{i},v_{-i})=x} それから：
P 1 y m e n t 私 （ v 私 、 v − 私 ） = P r 私 c e 私 （ x 、 v − 私 ） {\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})} 2. 選択された結果はエージェントにとって最適である私 {\displaystyle i}
O u t c o m e （ v 私 、 v − 私 ） ∈ 引数 最大 x [ v 私 （ x ） + P r 私 c e 私 （ x 、 v − 私 ） ] {\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]} ここで最大化は、以下の範囲のすべての結果について行われる。O u t c o m e （ ⋅ 、 v − 私 ） {\displaystyle Outcome(\cdot ,v_{-i})}
証明：もし別の結果があった場合x ′ = O u t c o m e （ v 私 ′ 、 v − 私 ） {\displaystyle x'=Outcome(v_{i}',v_{-i})} v 私 （ x ′ ） + P r 私 c e 私 （ x ′ 、 v − 私 ） > v 私 （ x ） + P r 私 c e 私 （ x 、 v − 私 ） {\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})} v 私 {\displaystyle v_{i}} v 私 ′ {\displaystyle v_{i}'}
条件1と条件2は必要条件であるだけでなく十分条件でもある。条件1と条件2を満たすメカニズムはすべてSPである。
証明：エージェントを修正する私 {\displaystyle i} v 私 、 v 私 ′ 、 v − 私 {\displaystyle v_{i},v_{i}',v_{-i}}
x := O u t c o m e （ v 私 、 v − 私 ） {\displaystyle x:=Outcome(v_{i},v_{-i})} x ′ := O u t c o m e （ v 私 ′ 、 v − 私 ） {\displaystyle x':=Outcome(v_{i}',v_{-i})} 性質1によれば、エージェントが正直にプレイする場合の効用は次のようになる。
u 私 （ v 私 ） = v 私 （ x ） + P r 私 c e 私 （ x 、 v − 私 ） {\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})} そして、エージェントが不正行為を行う場合の効用は以下のとおりです。
u 私 （ v 私 ′ ） = v 私 （ x ′ ） + P r 私 c e 私 （ x ′ 、 v − 私 ） {\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})} 特性2による：
u 私 （ v 私 ） ≥ u 私 （ v 私 ′ ） {\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')} したがって、エージェントにとって正直に行動することは支配的な戦略である。
結果関数特性 メカニズムの実際の目標はO u t c o m e {\displaystyle Outcome} 実装可能性 とも呼ばれます）。
単調性という 性質は、戦略耐性にとって必要不可欠である。
単一パラメータ領域における真実性メカニズム 単一パラメータ領域 は、各プレイヤーが私 {\displaystyle i} v 私 {\displaystyle v_{i}} v 私 {\displaystyle v_{i}} 私 {\displaystyle i}
この設定においては、真実性メカニズムを特徴づけるのは容易である。まずはいくつかの定義から始めよう。
すべての負け入札の支払額が0である場合、そのメカニズムは正規化されている と呼ばれます。
プレイヤーが入札額を上げた際に、勝つ確率が（わずかに）増加するような仕組みは、単調であると呼ばれます。
単調なメカニズムの場合、すべてのプレイヤーi と他のプレイヤーの入札のすべての組み合わせに対して、プレイヤーが負けから勝ちに変わる臨界値が存在する。
単一パラメータ領域における正規化されたメカニズムは、以下の2つの条件が満たされる場合に真実である。[ 1 ] ：
割り当て関数は各入札において単調であり、以下の条件を満たす。 落札された入札はすべて、重要な価値を支払うことになる。
ランダム化メカニズムの真実性 真実性の概念をランダム化メカニズムに拡張する方法はいくつかある。それらは、強いものから弱いものへと順に以下の通りである。[ 3 ] ：
普遍的真実性 ：アルゴリズムの各ランダム化において、結果として得られるメカニズムは真実である。言い換えれば、普遍的に真実なメカニズムとは、決定論的な真実なメカニズムのランダム化であり、重みは入力に依存する可能性がある。強い確率的優位性真実性（強いSD真実性） ：エージェントが真実を述べることで得られる確率のベクトルは、虚偽の報告をすることで得られる確率のベクトルに対して、一次確率的優位性を 持つ。つまり、最優先権を得る確率は少なくとも同等であり、かつ、上位2つの優先権のうちの1つを得る確率は少なくとも同等であり、かつ、m個の 上位優先権のうちの1つを得る確率は少なくとも同等である。辞書的真実性（lex-truthfulness） ：エージェントが真実を述べることで得られる確率のベクトルは、虚偽の報告をすることで得られる確率のベクトルに対して辞書的に優位性を 持つ。つまり、最優先権を得る確率が高いか、（最優先権を得る確率は等しく、上位2つの優先権のうち1つを得る確率が高い）か、（最初のm -1個の優先権を得る確率は等しく、上位 m 個の優先権のうち1つを得る確率が高い）か、（すべての確率が等しい）。弱い確率的優位性真実性（弱いSD真実性） ：エージェントが真実を述べることによって得られる確率のベクトルは、彼が虚偽の報告をすることによって得る確率のベクトルによって一次確率的に支配されない。普遍性は強いSDを意味し、Lexは弱いSDを意味し、すべての含意は厳密である。[ 3 ] ：
高い確率で真実を語る すべての定数に対してϵ > 0 {\displaystyle \epsilon >0} 確率で真実であると呼ばれます1 − ϵ {\displaystyle 1-\epsilon } すべてのエージェントとすべての入札ベクトルについて、エージェントが真実でない入札によって利益を得る確率が最大でϵ {\displaystyle \epsilon } [ 1 ] ：
定数ϵ {\displaystyle \epsilon } 高い確率で真実であると呼ばれます。この概念は完全な真実性よりも弱いですが、いくつかのケースでは依然として有用です。たとえば、 コンセンサス推定を 参照してください。
偽名使用防止機能 インターネットオークションの普及に伴い、新たなタイプの詐欺が横行している。それは、偽名入札 、つまり一人の入札者が複数のメールアドレスなど複数の識別情報を用いて入札を行うものだ。
偽名防止とは、 どのプレイヤーにも偽名入札を行うインセンティブがないことを意味します。これは戦略防止よりも強い概念です。特に、ヴィックリー・クラーク・グローブス （VCG）オークションは偽名防止ではありません。[ 4 ]
偽名耐性は、集団戦略耐性とは重要な点で異なる。なぜなら、偽名耐性は、通常は複数の個人の共謀による調整を必要とする特定の行動を、個人単独でシミュレートできると仮定しているからである。
明らかな戦略耐性 明白な戦略耐性（OSP）は、戦略耐性を強化したもので、認知能力が制限されたエージェントに対する戦略耐性の堅牢性を捉えるものです。[ 5 ]
封印入札方式の第二価格オークションは 戦略耐性があるが、入札者が自分の入札が封印されたままであることを信頼しなければならないため、明らかに戦略耐性があるとは言えない。[ 6 ] [ 7 ] 上昇クロックオークションは 明らかに戦略耐性があるが、[ 5 ]
さらに読む Parkes, David C. (2004), On Learnable Mechanism Design, in: Tumer, Kagan and David Wolpert (Eds.): Collectives and the Design of Complex Systems, New York uaO, pp. 107–133. 古典的な社会的選択ルールの漸近的戦略耐性について 投票システムにおける戦略耐性に関するアルカディ・スリンコによる論文。
参考文献 1 2 3 4 5 ヴァジラニ、ビジェイ V.ニサン, ノーム ;ティム・ラフガーデン ;タルドス、エヴァ (2007)。アルゴリズムゲーム理論 (PDF) 。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0 。↑ 「集団戦略耐性と2つの選択肢間の社会的選択」 （PDF） 。 2020年2月12日に オリジナル （PDF） からアーカイブされました。 1 2 Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12). "順序選好を持つメカニズム設計における福祉最大化と真実性" . 第5回理論計算機科学イノベーション会議議事録 . ITCS '14. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 105–120 . arXiv : 1312.1831 . doi : 10.1145/2554797.2554810 . ISBN 978-1-4503-2698-8 . S2CID 2428592 . ↑ 横尾 誠、櫻井 裕、松原 聡 (2004)「組み合わせオークションにおける偽名入札の影響：インターネットオークションにおける新たな不正行為」『 ゲームと経済行動 』 46 : 174–188 . CiteSeerX 10.1.1.18.6796 . doi : 10.1016/S0899-8256(03)00045-9 . 1 2 Li, Shengwu (2017-11-01). "明らかに戦略耐性のあるメカニズム" . American Economic Review . 107 (11): 3257– 3287. doi : 10.1257/aer.20160425 . ISSN 0002-8282 . ↑ Akbarpour, Mohammad; Li, Shengwu (2017). "Credible Mechanism Design" . SSRN Electronic Journal . doi : 10.2139/ssrn.3033208 . ISSN 1556-5068 . SSRN 3033208 . ↑ Komo, Andrew; Kominers, Scott Duke; Roughgarden, Tim (2025-07-02). "Shill-Proof Auctions" . Proceedings of the 26th ACM Conference on Economics and Computation . EC '25. New York, NY, USA: Association for Computing Machinery. p. 784. doi : 10.1145/3736252.3742623 . ISBN 979-8-4007-1943-1 。↑ Ashlagi, Itai; Gonczarowski, Yannai A. (2018-09-01). "安定マッチングメカニズムは明らかに戦略耐性があるわけではない" . Journal of Economic Theory . 177 : 405–425 . doi : 10.1016/j.jet.2018.07.001 . ISSN 0022-0531 .
![{\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0a175fbdf34105f137a0346913d19d2d4098e85)
