論文の概要: Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics

• arxiv url: http://arxiv.org/abs/2101.11946v1
• Date: Thu, 28 Jan 2021 11:53:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-01-31 18:11:39.554039
• Title: Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics
• Title（参考訳）: 組合せオークションにおける平衡学習--擬次力学による近似ベイズナッシュ平衡計算
• Authors: Stefan Heidekr\"uger, Paul Sutterer, Nils Kohring, Maximilian Fichtl, and Martin Bichler
• Abstract要約: 汎用的でスケーラブルなマルチエージェント平衡学習法を提案する。 様々なオークションでBNEを近似する高速で頑健な収束を観察する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Applications of combinatorial auctions (CA) as market mechanisms are prevalent in practice, yet their Bayesian Nash equilibria (BNE) remain poorly understood. Analytical solutions are known only for a few cases where the problem can be reformulated as a tractable partial differential equation (PDE). In the general case, finding BNE is known to be computationally hard. Previous work on numerical computation of BNE in auctions has relied either on solving such PDEs explicitly, calculating pointwise best-responses in strategy space, or iteratively solving restricted subgames. In this study, we present a generic yet scalable alternative multi-agent equilibrium learning method that represents strategies as neural networks and applies policy iteration based on gradient dynamics in self-play. Most auctions are ex-post nondifferentiable, so gradients may be unavailable or misleading, and we rely on suitable pseudogradient estimates instead. Although it is well-known that gradient dynamics cannot guarantee convergence to NE in general, we observe fast and robust convergence to approximate BNE in a wide variety of auctions and present a sufficient condition for convergence
• Abstract（参考訳）: 市場メカニズムとしての組合せオークション(CA)の適用は実際には普及していますが、ベイズナッシュ平衡(BNE)は理解が不十分です。 解析解は、問題が可搬偏微分方程式 (pde) として再定式化できるいくつかのケースでのみ知られている。 一般の場合、BNEの発見は計算が難しいことが知られている。 オークションにおけるBNEの数値計算に関するこれまでの研究は、これらのPDEを明示的に解いたり、戦略空間におけるポイントワイズ最適応答を計算したり、制限されたサブゲームを反復的に解いたりしていた。 本研究では,戦略をニューラルネットワークとして表現し,自己遊びにおける勾配ダイナミクスに基づく政策イテレーションを適用する,汎用的かつスケーラブルなマルチエージェント均衡学習手法を提案する。 ほとんどのオークションは元ポスト微分不可能であるため、勾配は使用できないか誤解を招く可能性がある。 勾配力学は一般に NE への収束を保証できないことはよく知られているが、多種多様なオークションにおいて近似 BNE への高速で堅牢な収束を観察し、収束のための十分条件を示す。

関連論文リスト

• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games [0.0]
  我々は,2プレイヤーゼロサムゲームの混合ナッシュ平衡と,純戦略の連続的なセットと,ペイオフ関数への一次アクセスとの問題を考察する。 この問題は例えば、分散ロバスト学習のようなゲームにインスパイアされた機械学習アプリケーションで発生する。 本稿では,この問題に対する局所収束性を保証する粒子法の導入と解析を行う。
  論文  参考訳（メタデータ） (2022-11-02T17:03:40Z)
• On NeuroSymbolic Solutions for PDEs [12.968529838140036]
  物理情報ニューラルネットワーク(PINN)は,PDEを数値的に解く代替手法として広く普及している。 本研究ではPDEの解を近似するためのNeuroSymbolicアプローチについて検討する。 ニューロシンボリック近似は、ニューロシンボリック近似とシンボリック近似に比較して、一貫して1-2次であることを示す。
  論文  参考訳（メタデータ） (2022-07-11T16:04:20Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  偏微分方程式(PDE)の数値解は困難であり、これまでの1世紀にわたる研究に繋がった。 近年、ニューラルネットワークと数値のハイブリッド・ソルバの構築が推進されており、これは現代のエンドツーエンドの学習システムへのトレンドを後押ししている。 この研究では、すべてのコンポーネントがニューラルメッセージパッシングに基づいて、これらの特性を満たす解決器を構築します。 本稿では, 有限差分, 有限体積, WENOスキームなどの古典的手法を表現的に含んでいることを示す。
  論文  参考訳（メタデータ） (2022-02-07T17:47:46Z)
• Semi-Implicit Neural Solver for Time-dependent Partial Differential Equations [4.246966726709308]
  本稿では,PDEの任意のクラスに対して,データ駆動方式で最適な反復スキームを学習するためのニューラルソルバを提案する。 従来の反復解法に類似したニューラルソルバの正当性と収束性に関する理論的保証を提供する。
  論文  参考訳（メタデータ） (2021-09-03T12:03:10Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。 ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。 本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
  論文  参考訳（メタデータ） (2021-05-11T03:38:16Z)
• Adversarial Robustness Guarantees for Gaussian Processes [22.403365399119107]
  ガウス過程(GP)は、モデルの不確実性の原理的計算を可能にし、安全性に重要なアプリケーションに魅力的です。 境界付き摂動に対するモデル決定の不変性として定義されるGPの対向的堅牢性を分析するためのフレームワークを提案する。 我々は境界を洗練し、任意の$epsilon > 0$に対して、我々のアルゴリズムが有限個の反復で実際の値に$epsilon$-closeの値に収束することを保証していることを示す分岐とバウンドのスキームを開発する。
  論文  参考訳（メタデータ） (2021-04-07T15:14:56Z)
• Bayesian neural networks for weak solution of PDEs with uncertainty quantification [3.4773470589069473]
  ラベルなしでPDEを解くために、新しい物理制約ニューラルネットワーク(NN)アプローチが提案されている。 我々は,PDEの離散化残差に基づくNNの損失関数を,効率的で畳み込み演算子に基づくベクトル化実装により記述する。 本研究では, 定常拡散, 線形弾性, 非線形弾性に応用し, 提案フレームワークの性能と性能を示す。
  論文  参考訳（メタデータ） (2021-01-13T04:57:51Z)

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

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