論文の概要: From No-Regret to Strategically Robust Learning in Repeated Auctions
- arxiv url: http://arxiv.org/abs/2601.03853v1
- Date: Wed, 07 Jan 2026 12:09:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-09 02:15:23.497449
- Title: From No-Regret to Strategically Robust Learning in Repeated Auctions
- Title（参考訳）: 繰り返しオークションにおける非回帰から戦略的ロバスト学習へ
- Authors: Junyao Zhao,
- Abstract要約: 任意の非回帰学習アルゴリズムが、量子的表現に関して勾配フィードバックを入力した場合、戦略的に堅牢であることを示す。
特に、乗法重み更新(MWU)アルゴリズムは、最適の後悔保証と最もよく知られた戦略的堅牢性保証を同時に達成する。
- 参考スコア（独自算出の注目度）: 0.5076419064097732
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Bayesian single-item auctions, a monotone bidding strategy--one that prescribes a higher bid for a higher value type--can be equivalently represented as a partition of the quantile space into consecutive intervals corresponding to increasing bids. Kumar et al. (2024) prove that agile online gradient descent (OGD), when used to update a monotone bidding strategy through its quantile representation, is strategically robust in repeated first-price auctions: when all bidders employ agile OGD in this way, the auctioneer's average revenue per round is at most the revenue of Myerson's optimal auction, regardless of how she adjusts the reserve price over time. In this work, we show that this strategic robustness guarantee is not unique to agile OGD or to the first-price auction: any no-regret learning algorithm, when fed gradient feedback with respect to the quantile representation, is strategically robust, even if the auction format changes every round, provided the format satisfies allocation monotonicity and voluntary participation. In particular, the multiplicative weights update (MWU) algorithm simultaneously achieves the optimal regret guarantee and the best-known strategic robustness guarantee. At a technical level, our results are established via a simple relation that bridges Myerson's auction theory and standard no-regret learning theory. This showcases the potential of translating standard regret guarantees into strategic robustness guarantees for specific games, without explicitly minimizing any form of swap regret.
- Abstract（参考訳）: ベイズ単体オークション(Bayesian single-item auctions)では、より高い値の型に対するより高い入札を規定するモノトーン入札戦略が、上昇する入札に対応する連続区間への量子空間の分割として等価に表される。
Kumar氏(2024年)は、アジャイルオンライン勾配降下(OGD)が、その量的表現を通じて単調な入札戦略を更新するのに使用される場合、すべての入札者がアジャイルOGDをこの方法で採用する場合、その1ラウンド当たりの平均収入は、どのように予約価格を調整するかに関わらず、Myersonの最適オークションの収入のほとんどである、という戦略的な第一価格オークションにおいて、戦略的に堅牢であることを証明している。
本研究は,この戦略的堅牢性保証がアジャイルのOGDや最初の価格オークションに特有のものではないことを示す。任意の非回帰学習アルゴリズムは,量子的表現に関して勾配フィードバックを供給した場合,オークション形式が各ラウンドに変化しても,その形式が一律性や自発的参加性を満たすことを条件として,戦略的に堅牢である。
特に、乗法重み更新(MWU)アルゴリズムは、最適の後悔保証と最もよく知られた戦略的堅牢性保証を同時に達成する。
技術的レベルでは、Myersonのオークション理論と標準ノンレグレット学習理論を橋渡しする単純な関係によって、この結果が確立される。
これは、標準的な後悔の保証を、スワップ後悔の形式を明示的に最小化することなく、特定のゲームに対する戦略的堅牢性を保証するものに翻訳する可能性を示している。
関連論文リスト
- Is Online Linear Optimization Sufficient for Strategic Robustness? [54.49053278073321]
no-swap-regretアルゴリズムは望ましい特性の両方を達成するが、統計的および計算効率の面では最適ではない。
オンライン勾配上昇は、O(sqrtTK)$ 後悔と戦略的堅牢性を達成する唯一のアルゴリズムである。
我々は,任意のOLOアルゴリズムを戦略的にロバストなノンレグレット入札アルゴリズムに変換する,単純なブラックボックス削減を構築する。
論文 参考訳（メタデータ） (2026-02-12T18:41:55Z) - Learning to Bid in Non-Stationary Repeated First-Price Auctions [27.743710782882136]
第一価オークションはデジタル広告市場で大きな注目を集めている。
第一価格オークションにおける最適な入札戦略を決定することはより複雑である。
対戦者の最多入札の順序のクラスに対する動的後悔の最小最大最適評価法を提案する。
論文 参考訳（メタデータ） (2025-01-23T03:53:27Z) - Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions [6.309531239485479]
価格を最大化する買い手の観点から,単価の複数ユニットオークションを繰り返す際の入札問題について検討する。
本稿では、競合入札に関係なく、RoI制約を満たすものとして、安全な入札戦略の概念を紹介する。
これらの戦略は入札者の評価曲線にのみ依存し, 一般性を損なうことなく, 有限部分集合に焦点を絞ることができることを示す。
論文 参考訳（メタデータ） (2024-06-06T01:29:47Z) - Statistically Truthful Auctions via Acceptance Rule [23.38395470540186]
買い手が真のバリュエーションの入札にインセンティブを与えられることを保証するため、戦略の保護は不可欠だ。
本稿では, オークション機構に対する統計的戦略耐性の定式化を提案する。
当社の手法は、実質的な収益損失を犠牲にして、真理性 ― ゼロレグレット ― を強制することの間の、実践的な中間地点を表現している。
論文 参考訳（メタデータ） (2024-05-20T13:39:58Z) - Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
性能インセンティブとロバストネスの2つの目的を同時に満たすバンディットアルゴリズムのクラスを導入する。
そこで本研究では,第2価格オークションのアイデアをアルゴリズムと組み合わせることで,プリンシパルが腕の性能特性に関する情報を持たないような設定が可能であることを示す。
論文 参考訳（メタデータ） (2023-12-13T06:54:49Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
競売人の収益を最大化しつつ、競売人の過去の後悔を最小限にする競売メカニズムは、経済学において重要であるが複雑な問題である。
ニューラルネットワークによる最適なオークションメカニズムの学習を通じて、注目すべき進歩が達成されている。
論文 参考訳（メタデータ） (2022-10-11T16:13:25Z) - Dynamic Budget Throttling in Repeated Second-Price Auctions [11.823210231891517]
スロットリングは人気のある選択であり、広告主の総支出を管理するために、オークションのサブセットだけを選択することで、広告主の総支出を管理する。
本稿では,2次価格の繰り返しオークションにおいて,単一の広告主の動的予算絞りプロセスの理論的パノラマを提供する。
本研究は, 競売におけるスロットリングの理論的研究のギャップを埋めるものであり, この一般的な予算平滑化戦略の能力を明らかにするものである。
論文 参考訳（メタデータ） (2022-07-11T08:12:02Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳（メタデータ） (2020-11-10T12:45:02Z) - Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳（メタデータ） (2020-06-22T16:06:25Z) - Certifying Strategyproof Auction Networks [53.37051312298459]
我々は、任意の数のアイテムと参加者でオークションを表現できるRegretNetアーキテクチャに焦点を当てる。
本稿では,ニューラルネットワーク検証文献から得られた手法を用いて,特定の評価プロファイルの下で戦略の安全性を明示的に検証する方法を提案する。
論文 参考訳（メタデータ） (2020-06-15T20:22:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。