論文の概要: 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のダイナミクスはより早く収束し、より高い収益を達成する。

関連論文リスト

• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• 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)
• 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)
• 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)

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

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