論文の概要: Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions

• arxiv url: http://arxiv.org/abs/2402.07363v2
• Date: Sun, 7 Jul 2024 06:07:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 02:38:52.692953
• Title: Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions
• Title（参考訳）: 価格オークションにおける入札のための戦略的ロバスト学習アルゴリズム
• Authors: Rachitesh Kumar, Jon Schneider, Balasubramanian Sivan,
• Abstract要約: ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。 本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
• 参考スコア（独自算出の注目度）: 11.988955088595858
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning, which has seen a recent surge in interest due to the transition of display advertising to first-price auctions. In this work, we propose a novel concave formulation for pure-strategy bidding in first-price auctions, and use it to analyze natural Gradient-Ascent-based algorithms for this problem. Importantly, our analysis goes beyond regret, which was the typical focus of past work, and also accounts for the strategic backdrop of online-advertising markets where bidding algorithms are deployed -- we provide the first guarantees of strategic-robustness and incentive-compatibility for Gradient Ascent. Concretely, we show that our algorithms achieve $O(\sqrt{T})$ regret when the highest competing bids are generated adversarially, and show that no online algorithm can do better. We further prove that the regret reduces to $O(\log T)$ when the competition is stationary and stochastic, which drastically improves upon the previous best of $O(\sqrt{T})$. Moving beyond regret, we show that a strategic seller cannot exploit our algorithms to extract more revenue on average than is possible under the optimal mechanism. Finally, we prove that our algorithm is also incentive compatible -- it is a (nearly) dominant strategy for the buyer to report her values truthfully to the algorithm as a whole. Altogether, these guarantees make our algorithms the first to simultaneously achieve both optimal regret and strategic-robustness.
• Abstract（参考訳）: ゲーム理論と機械学習のインターフェースにおいて、繰り返し最初の価格オークションで競うことの学習は根本的な問題であり、ディスプレイ広告が第1価格オークションに移行したことにより、近年関心が高まっている。 本研究では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセントアルゴリズムの解析に利用した。 重要なことは、我々の分析は過去の作業の典型的な焦点であり、入札アルゴリズムが配備されているオンライン広告市場の戦略的背景も考慮している後悔以上のものだ。 具体的には、最も高い競合入札が反対に生成された場合、我々のアルゴリズムが$O(\sqrt{T})$後悔を達成できることを示し、オンラインアルゴリズムが改善できないことを示す。 さらに、この後悔は、競合が定常かつ確率的であるときに$O(\log T)$に減少し、以前の$O(\sqrt{T})$を大幅に改善する。 残念なことに、戦略的な売り手は我々のアルゴリズムを利用して、最適メカニズムの下で可能な以上の収益を平均で取り出すことはできない。 そして最後に、我々のアルゴリズムはインセンティブと互換性があることを証明します -- 買い手にとって、アルゴリズム全体に真に価値を報告するのは(ほぼ)支配的な戦略です。 さらに、これらの保証により、アルゴリズムは最適な後悔と戦略的損耗の両方を同時に達成する最初のものとなる。

関連論文リスト

• Deep Reinforcement Learning for Online Optimal Execution Strategies [49.1574468325115]
  本稿では,動的な金融市場における非マルコフ的最適実行戦略の学習に挑戦する。 我々は,Deep Deterministic Policy Gradient(DDPG)に基づく新しいアクター批判アルゴリズムを提案する。 提案アルゴリズムは最適実行戦略の近似に成功していることを示す。
  論文  参考訳（メタデータ） (2024-10-17T12:38:08Z)
• Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
  オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。 学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
  論文  参考訳（メタデータ） (2023-10-08T07:04:22Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• No-regret Learning in Repeated First-Price Auctions with Budget Constraints [5.834615090865286]
  定常競争下での最適非予測戦略に対して,RLに基づく入札アルゴリズムを提案する。 提案アルゴリズムは,各ラウンドの最後にすべての入札が明らかになった場合,$widetilde O(sqrt T)$-regretを求める。
  論文  参考訳（メタデータ） (2022-05-29T04:32:05Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
  論文  参考訳（メタデータ） (2021-07-05T07:48:52Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  エージェントの報酬がベクトルとして表現される多目的強化学習(RL)について検討する。 エージェントが相手と競合する設定では、その平均戻りベクトルから目標セットまでの距離によってその性能を測定する。 統計的および計算学的に効率的なアルゴリズムを開発し、関連するターゲットセットにアプローチする。
  論文  参考訳（メタデータ） (2021-02-05T14:26:00Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
  我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。 この問題に対する最初のパラメトリック下界を提供する。 本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
  論文  参考訳（メタデータ） (2020-11-10T12:45:02Z)
• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions [40.30925727499806]
  我々は,$widetildeO(sqrtT)$ regretを達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。 Verizon Mediaから得られた3つの実世界の1価オークションデータセットを用いて,本アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2020-07-09T05:40:39Z)

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

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