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

• arxiv url: http://arxiv.org/abs/2307.15193v3
• Date: Sat, 09 Nov 2024 19:30:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:04:55.802511
• Title: Learning in Repeated Multi-Unit Pay-As-Bid Auctions
• Title（参考訳）: 反復型マルチユニットペイ・アズ・バイドオークションにおける学習
• Authors: Rigel Galgana, Negin Golrezaei,
• Abstract要約: 本研究では,単一入札者の視点から,ペイ・アズ・バイド(PAB)オークションにおける入札戦略の問題点を考察する。 提案手法は,競合する入札が事前に知られている場合のオフライン問題を,時間アルゴリズムで解くことができることを示す。 また,PAB平衡のキャラクタリゼーションについても検討した。
• 参考スコア（独自算出の注目度）: 3.6294895527930504
• License:
• Abstract: Motivated by Carbon Emissions Trading Schemes, Treasury Auctions, Procurement Auctions, and Wholesale Electricity Markets, 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. In this work, we study the problem of optimizing bidding strategies from the perspective of a single bidder. Effective bidding in pay-as-bid (PAB) auctions is complex due to the combinatorial nature of the action space. We show that a utility decoupling trick enables a polynomial time algorithm to solve the offline problem where competing bids are known in advance. Leveraging this structure, we design efficient algorithms for the online problem under both full information and bandit feedback settings that achieve an upper bound on regret of $O(M \sqrt{T \log T})$ and $O(M T^{\frac{2}{3}} \sqrt{\log T})$ respectively, where $M$ is the number of units demanded by the bidder and $T$ is the total number of auctions. We accompany these results with a regret lower bound of $\Omega(M\sqrt{T})$ for the full information setting and $\Omega (M^{2/3}T^{2/3})$ for the bandit setting. We also present additional findings on the characterization of PAB equilibria. While the Nash equilibria of PAB auctions possess nice properties such as winning bid uniformity and high welfare \& revenue, they are not guaranteed under no regret learning dynamics. Nevertheless, our simulations suggest these properties hold anyways, regardless of Nash equilibrium existence. Compared to its uniform price counterpart, the PAB dynamics converge faster and achieve higher revenue, making PAB appealing whenever revenue holds significant social value.
• Abstract（参考訳）: 均一な複数ユニットのオークションを含む、炭素排出取引方式、大蔵競売、調達競売、およびWholeale Electricity Marketsによって動機付けられ、我々は、繰り返し行われる複数ユニットのペイ・アズ・バイドオークションにおける入札の仕方を学ぶことの課題を考える。 これらのオークションでは、多数の(同一の)アイテムが最も大きな入札に割り当てられ、それぞれの入札の価格は入札そのものに等しい。 本研究では,単一入札者の視点から,入札戦略を最適化する問題を考察する。 ペイ・アズ・バイド(PAB)オークションの効果的な入札は、アクション空間の組合せの性質のために複雑である。 ユーティリティデカップリング手法により、多項式時間アルゴリズムは、競合入札が事前に知られているオフライン問題を解くことができることを示す。 この構造を利用すると、オンライン問題に対する効率の良いアルゴリズムをフル情報と帯域幅のフィードバック設定の両方で設計し、それぞれ$O(M \sqrt{T \log T})$と$O(M T^{\frac{2}{3}} \sqrt{\log T})$の残高の上限を達成し、$M$は入札者が要求するユニット数であり、$T$はオークションの総数である。 これらの結果に付随して、全情報設定に対して$\Omega(M\sqrt{T})$と、バンディット設定に対して$\Omega (M^{2/3}T^{2/3})$という残念な低い境界がある。 また,PAB平衡のキャラクタリゼーションについても検討した。 PABオークションのナッシュ均衡は、入札の均一性や高い福祉と収入などの優れた性質を持っているが、これらは後悔の学習動力学では保証されていない。 しかしながら、我々のシミュレーションは、これらの性質はナッシュ平衡の存在にかかわらず、いずれにせよ成り立つことを示唆している。 均一な価格と比較すると、PABのダイナミクスはより早く収束し、より高い収益を達成する。

関連論文リスト

• 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)

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

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