論文の概要: Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game

• arxiv url: http://arxiv.org/abs/2506.22089v1
• Date: Fri, 27 Jun 2025 10:21:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-30 21:12:23.169331
• Title: Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game
• Title（参考訳）: Pseudo-Equilibria, or: 暗号の心配をやめて、ただゲームを分析する方法
• Authors: Alexandros Psomas, Athina Terzoglou, Yu Wei, Vassilis Zikas,
• Abstract要約: 本稿では,暗号プロトコルを用いたゲーム解析の問題点を考察する。 疑似ナッシュ平衡という新しい解の概念を提案する。
• 参考スコア（独自算出の注目度）: 48.93355782581436
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the problem of a game theorist analyzing a game that uses cryptographic protocols. Ideally, a theorist abstracts protocols as ideal, implementation-independent primitives, letting conclusions in the "ideal world" carry over to the "real world." This is crucial, since the game theorist cannot--and should not be expected to--handle full cryptographic complexity. In today's landscape, the rise of distributed ledgers makes a shared language between cryptography and game theory increasingly necessary. The security of cryptographic protocols hinges on two types of assumptions: state-of-the-world (e.g., "factoring is hard") and behavioral (e.g., "honest majority"). We observe that for protocols relying on behavioral assumptions (e.g., ledgers), our goal is unattainable in full generality. For state-of-the-world assumptions, we show that standard solution concepts, e.g., ($\epsilon$-)Nash equilibria, are not robust to transfer from the ideal to the real world. We propose a new solution concept: the pseudo-Nash equilibrium. Informally, a profile $s=(s_1,\dots,s_n)$ is a pseudo-Nash equilibrium if, for any player $i$ and deviation $s'_i$ with higher expected utility, $i$'s utility from $s_i$ is (computationally) indistinguishable from that of $s'_i$. Pseudo-Nash is simpler and more accessible to game theorists than prior notions addressing the mismatch between (asymptotic) cryptography and game theory. We prove that Nash equilibria in games with ideal, unbreakable cryptography correspond to pseudo-Nash equilibria when ideal cryptography is instantiated with real protocols (under state-of-the-world assumptions). Our translation is conceptually simpler and more general: it avoids tuning or restricting utility functions in the ideal game to fit quirks of cryptographic implementations. Thus, pseudo-Nash lets us study game-theoretic and cryptographic aspects separately and seamlessly.
• Abstract（参考訳）: 本稿では,暗号プロトコルを用いたゲーム解析の問題点を考察する。 理想的には、理論家はプロトコルを理想的で実装に依存しないプリミティブとして抽象化し、「理想の世界」の結論は「現実の世界」へと続く。 ゲーム理論者は、完全に暗号化された複雑さを扱うことを期待してはならないので、これは非常に重要です。 今日のランドスケープでは、分散台帳の台頭により、暗号とゲーム理論の共通言語がますます必要となる。 暗号プロトコルのセキュリティは、ステート・オブ・ザ・ワールド(例:「リファクタリングは難しい」)と行動(例:「正直な多数派」)の2つの前提に基づいている。 行動的仮定(例えば、台帳)に依存するプロトコルでは、我々のゴールは完全な汎用性では達成不可能である。 現状の仮定に対して、標準的な解の概念、例えば (\epsilon$-)Nash equilibria は理想から実世界への移動が堅牢でないことを示す。 疑似ナッシュ平衡という新しい解の概念を提案する。 informally, a profile $s=(s_1,\dots,s_n)$ is a pseudo-Nash equilibrium if, for any player $i$ and deviation $s'_i$ with higher expected utility, $i$'s utility from $s_i$ is (computationally) indistinguishable with $s'_i$. Pseudo-Nashは、(漸近的な)暗号とゲーム理論のミスマッチに対処する以前の概念よりも、ゲーム理論家にとってシンプルでアクセスしやすくなっている。 理想的、破壊不能な暗号を持つゲームにおけるナッシュ平衡は、理想的暗号が実際のプロトコル(実世界の仮定)でインスタンス化されるときに擬似ナッシュ平衡に対応することを証明している。 私たちの翻訳は概念的にシンプルで、より一般的なもので、暗号実装のクイックに適合する理想的なゲームにおけるユーティリティ関数のチューニングや制限を避けます。 したがって、擬似ナッシュはゲーム理論と暗号の側面を別々にシームレスに研究することができる。

関連論文リスト

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。 また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
  論文  参考訳（メタデータ） (2025-02-24T20:20:06Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。 不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
  論文  参考訳（メタデータ） (2024-06-23T00:27:28Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Safe Equilibrium [1.7132914341329848]
  標準的なゲーム理論解の概念であるナッシュ均衡は、すべてのプレイヤーが合理的に振る舞うことを仮定する。 我々は,特定の確率で合理的に行動する相手をモデル化する,セーフ均衡と呼ばれる新しい解の概念を提案する。 我々は、全ての戦略形式ゲームに安全な平衡が存在することを証明し、その計算がPPADハードであることを証明する。
  論文  参考訳（メタデータ） (2022-01-12T01:45:51Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。 ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
  論文  参考訳（メタデータ） (2021-08-17T07:06:46Z)
• The Electromagnetic Balance Game: A Probabilistic Perspective [3.096615629099617]
  バランスを使って視覚的に同一のコインのセットとは異なる重さの偽造コインを見つけることは、干渉的で刺激的な問題である。 本稿では、特に確率論的観点から、バランスゲームの一部の変種を減弱する。 我々は,プレイヤーがバランスの取れた結果を観察することなく戦略を調整しなければならない,所定の設定に集中する。
  論文  参考訳（メタデータ） (2020-07-21T11:49:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。