論文の概要: Learning in Repeated Multi-Unit Pay-As-Bid Auctions
- arxiv url: http://arxiv.org/abs/2307.15193v1
- Date: Thu, 27 Jul 2023 20:49:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-31 14:23:41.926766
- Title: Learning in Repeated Multi-Unit Pay-As-Bid Auctions
- Title(参考訳): 反復型マルチユニットペイ・アズ・バイドオークションにおける学習
- Authors: Rigel Galgana and Negin Golrezaei
- Abstract要約: 複数単位のペイ・アズ・バイドオークションの入札方法を学ぶことの問題点を考察する。
バイド・バイド・オークションの入札方法を学ぶという問題は、アクション・スペースの性質によって困難である。
時間動的計画法を用いて,オフライン問題に対する最適解が得られることを示す。
- 参考スコア(独自算出の注目度): 6.370905925442655
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by Carbon Emissions Trading Schemes, Treasury Auctions, and
Procurement Auctions, which all involve the auctioning of homogeneous multiple
units, we consider the problem of learning how to bid in repeated multi-unit
pay-as-bid auctions. In each of these auctions, a large number of (identical)
items are to be allocated to the largest submitted bids, where the price of
each of the winning bids is equal to the bid itself. The problem of learning
how to bid in pay-as-bid auctions is challenging due to the combinatorial
nature of the action space. We overcome this challenge by focusing on the
offline setting, where the bidder optimizes their vector of bids while only
having access to the past submitted bids by other bidders. We show that the
optimal solution to the offline problem can be obtained using a polynomial time
dynamic programming (DP) scheme. We leverage the structure of the DP scheme to
design online learning algorithms with polynomial time and space complexity
under full information and bandit feedback settings. We achieve an upper bound
on regret of $O(M\sqrt{T\log |\mathcal{B}|})$ and $O(M\sqrt{|\mathcal{B}|T\log
|\mathcal{B}|})$ respectively, where $M$ is the number of units demanded by the
bidder, $T$ is the total number of auctions, and $|\mathcal{B}|$ is the size of
the discretized bid space. We accompany these results with a regret lower
bound, which match the linear dependency in $M$. Our numerical results suggest
that when all agents behave according to our proposed no regret learning
algorithms, the resulting market dynamics mainly converge to a welfare
maximizing equilibrium where bidders submit uniform bids. Lastly, our
experiments demonstrate that the pay-as-bid auction consistently generates
significantly higher revenue compared to its popular alternative, the uniform
price auction.
- Abstract(参考訳): 炭素排出取引方式, 財務オークション, 調達オークションに動機づけられ, いずれも均質な複数ユニットのオークションが絡み合っており, 複数単位のペイ・アズ・バイ・オークションの入札方法を学ぶことが課題である。
これらのオークションでは、多数の(同一の)アイテムが最も大きな入札に割り当てられ、それぞれの入札の価格は入札そのものに等しい。
対価入札の入札方法を学ぶという問題は、行動空間の組合せの性質のために難しい。
我々は、入札者が過去の入札にのみアクセスしながら入札のベクターを最適化するオフライン設定に焦点を合わせることで、この課題を克服する。
オフライン問題に対する最適解は多項式時間動的計画法(DP)を用いて得られることを示す。
dpスキームの構造を利用して,全情報とバンディットフィードバック設定下で多項式時間と空間複雑性を持つオンライン学習アルゴリズムを設計する。
我々は、それぞれ$O(M\sqrt{T\log |\mathcal{B}|})$と$O(M\sqrt{|\mathcal{B}|T\log |\mathcal{B}|})$の後悔に対する上限の上限を達成する。
これらの結果は、M$の線形依存に一致する、後悔の少ない低い境界で付随する。
以上の結果から,提案した後悔学習アルゴリズムに従わずに全てのエージェントが振る舞うと,結果の市場ダイナミクスは,入札者が一様入札を提出する均衡を最大化するための福祉に収束することが示唆された。
最後に,本研究の結果から,有料化オークションの収益は,人気の選択肢である均一価格オークションに比べ,一貫して有意に高いことがわかった。
関連論文リスト
- Learning and Collusion in Multi-unit Auctions [17.727436775513368]
均一な価格で複数ユニットのオークションを繰り返し検討する。
このオークションの特性をオフラインとオンラインの両方で分析する。
ここでは、$(K+1)$-stの価格形式が入札者間の共謀の影響を受けやすいことを示す。
論文 参考訳(メタデータ) (2023-05-27T08:00:49Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and
Pacing Dynamics [77.67037372500495]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (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) - 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) - 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) - Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
オンライン学習を反復した初価オークションで研究する。
我々は,ほぼ最適の$widetildeO(sqrtT)$ regret boundを達成するための最初の学習アルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-03-22T03:32:09Z) - Online Joint Bid/Daily Budget Optimization of Internet Advertising
Campaigns [115.96295568115251]
複数のチャンネルにまたがるペイ・パー・クリック広告キャンペーンのオンライン共同入札/日次予算最適化の自動化問題について検討する。
どのキャンペーンでも、Gaussian Processesによる入札のクリック数と日々の予算に依存しています。
我々は4つのアルゴリズムを設計し、O(sqrtT)として高い確率で上界した後悔に苦しむことを示す。
我々は,1年以上に1日平均1000ユーロを消費した実世界のアプリケーションにおいて,我々のアルゴリズムの採用結果を提示する。
論文 参考訳(メタデータ) (2020-03-03T11:07:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。