論文の概要: Learning in Repeated Multi-Unit Pay-As-Bid Auctions

• arxiv url: http://arxiv.org/abs/2307.15193v2
• Date: Mon, 15 Jul 2024 19:58:56 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-18 00:10:39.543174
• Title: Learning in Repeated Multi-Unit Pay-As-Bid Auctions
• Title（参考訳）: 反復型マルチユニットペイ・アズ・バイドオークションにおける学習
• Authors: Rigel Galgana, Negin Golrezaei,
• Abstract要約: 複数単位のペイ・アズ・バイドオークションの入札方法を学ぶことの問題点を考察する。 バイド・バイド・オークションの入札方法を学ぶという問題は、アクション・スペースの性質によって困難である。 時間動的計画法を用いて,オフライン問題に対する最適解が得られることを示す。
• 参考スコア（独自算出の注目度）: 3.6294895527930504
• 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$の線形依存に一致する、後悔の少ない低い境界で付随する。 以上の結果から,提案した後悔学習アルゴリズムに従わずに全てのエージェントが振る舞うと,結果の市場ダイナミクスは,入札者が一様入札を提出する均衡を最大化するための福祉に収束することが示唆された。 最後に、我々の実験により、ペイ・アズ・バイドのオークションは、人気の高い代替品である均一価格のオークションと比較して、一貫して収益が著しく高いことを実証した。

関連論文リスト

• Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
  競売業者がプライベートコストで戦略的売り手からサービスを取得しようとする競売について検討する。 我々の目標は、取得したサービスの品質と販売者の総コストとの差を最大化する計算効率の良いオークションを設計することである。
  論文  参考訳（メタデータ） (2024-11-20T18:06:55Z)
• Randomized Truthful Auctions with Learning Agents [10.39657928150242]
  本研究では, エージェントが未学習の学習を用いて, 繰り返しオークションに参加する環境について検討する。 競売者が非回帰入札アルゴリズムを用いて第2価格の競売に参加する場合、勝者が真に競売に収束しないことが示される。 我々は,第2代競売の収益と競売との収益を比べて,エムオークションのコンセプトを定義した。
  論文  参考訳（メタデータ） (2024-11-14T15:28:40Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
  本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。 我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
  論文  参考訳（メタデータ） (2024-04-15T14:31:53Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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 [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)
• 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)

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

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