論文の概要: Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
- arxiv url: http://arxiv.org/abs/2007.04568v2
- Date: Wed, 24 Sep 2025 23:52:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-28 17:38:02.835344
- Title: Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
- Title（参考訳）: 対価第一価格オークションにおける最適かつ効率的な入札の学習
- Authors: Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, Tsachy Weissman,
- Abstract要約: 我々は,$widetildeO(sqrtT)$ regretを達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。
Verizon Mediaから得られた3つの実世界の1価オークションデータセットを用いて,本アルゴリズムを検証した。
- 参考スコア（独自算出の注目度）: 27.491349926534685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction, where unlike in second-price auctions, it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? In this paper, we take an online learning angle and address the fundamental problem of learning to bid in repeated first-price auctions, where both the bidder's private valuations and other bidders' bids can be arbitrary. We develop the first minimax optimal online bidding algorithm that achieves an $\widetilde{O}(\sqrt{T})$ regret when competing with the set of all Lipschitz bidding policies, a strong oracle that contains a rich set of bidding strategies. This novel algorithm is built on the insight that the presence of a good expert can be leveraged to improve performance, as well as an original hierarchical expert-chaining structure, both of which could be of independent interest in online learning. Further, by exploiting the product structure that exists in the problem, we modify this algorithm--in its vanilla form statistically optimal but computationally infeasible--to a computationally efficient and space efficient algorithm that also retains the same $\widetilde{O}(\sqrt{T})$ minimax optimal regret guarantee. Additionally, through an impossibility result, we highlight that one is unlikely to compete this favorably with a stronger oracle (than the considered Lipschitz bidding policies). Finally, we test our algorithm on three real-world first-price auction datasets obtained from Verizon Media and demonstrate our algorithm's superior performance compared to several existing bidding algorithms.
- Abstract（参考訳）: 第一価格オークションは、最近オンライン広告業界を席巻し、多くのプラットフォームにおける主要なオークションメカニズムとして第二価格オークションに取って代わった。
このシフトは、入札者にとって重要な課題をもたらしている: 第一価格のオークションにおいて、どのように入札を行うべきか、すなわち、第二価格のオークションとは異なり、個人の価値を真に、他人の入札行動を知るのが困難になるのは、もはや最適ではない。
本稿では,オンライン学習のアングルを取り入れ,入札者の個人評価と他の入札者の入札の両方が任意となるような,第1価格の繰り返しオークションにおける入札の学習の基本的な問題に対処する。
我々は,全てのリプシッツ入札ポリシーの集合と競合するときに,$\widetilde{O}(\sqrt{T})$の後悔を達成する,最初のミニマックス最適オンライン入札アルゴリズムを開発した。
このアルゴリズムは、優れた専門家の存在がパフォーマンス向上に活用できるという洞察と、オンライン学習に独立した関心を持つことのできる、元々の階層的な専門家連鎖構造に基づいて構築されている。
さらに、問題に存在する積構造を利用することにより、このアルゴリズムを、統計的に最適だが計算的に不可能なバニラ形式で、同じ$\widetilde{O}(\sqrt{T})$ minimaxの最適後悔保証を保持する計算効率で空間効率のよいアルゴリズムに修正する。
さらに、不合理な結果を通じて、より強い神託(リプシッツの入札政策を考えれば)と好意的に競合する可能性は低いと強調する。
最後に,Verizon Mediaから取得した3つの実世界の第1価格オークションデータセットを用いてアルゴリズムを検証し,既存の入札アルゴリズムと比較してアルゴリズムの優れた性能を実証した。
関連論文リスト
- BAT: Benchmark for Auto-bidding Task [67.56067222427946]
本稿では,最も普及している2種類のオークション形式を含むオークションベンチマークを提案する。
我々は,新しいデータセットに基づいて,一連の堅牢なベースラインを実装した。
このベンチマークは、研究者や実践者が革新的なオートバイディングアルゴリズムを開発し、洗練するための、ユーザフレンドリで直感的なフレームワークを提供する。
論文 参考訳（メタデータ） (2025-05-13T12:12:34Z) - Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。
我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
論文 参考訳（メタデータ） (2024-11-20T18:06:55Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳（メタデータ） (2024-02-12T01:33:33Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳（メタデータ） (2022-10-19T03:49:05Z) - 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) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳（メタデータ） (2020-11-10T12:45:02Z) - A novel auction system for selecting advertisements in Real-Time bidding [68.8204255655161]
リアルタイム入札(Real-Time Bidding)は、インターネット広告システムで、近年非常に人気を集めている。
本稿では、経済的な側面だけでなく、広告システムの機能にかかわる他の要因も考慮した、新たなアプローチによる代替ベッティングシステムを提案する。
論文 参考訳（メタデータ） (2020-10-22T18:36:41Z) - ProportionNet: Balancing Fairness and Revenue for Auction Design with
Deep Learning [55.76903822619047]
本研究では,強力なインセンティブ保証を備えた収益最大化オークションの設計について検討する。
我々は、高い収益と強力なインセンティブ保証を維持しつつ、公平性の懸念に対処するため、深層学習を用いてオークションを近似する手法を拡張した。
論文 参考訳（メタデータ） (2020-10-13T13:54:21Z) - Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
オンライン学習を反復した初価オークションで研究する。
我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-03-22T03:32:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。