論文の概要: Learning and Collusion in Multi-unit Auctions
- arxiv url: http://arxiv.org/abs/2305.17402v2
- Date: Fri, 12 Jan 2024 23:04:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 02:45:02.582460
- Title: Learning and Collusion in Multi-unit Auctions
- Title（参考訳）: 複数単位オークションにおける学習と結束
- Authors: Simina Br\^anzei and Mahsa Derakhshan and Negin Golrezaei and Yanjun
Han
- Abstract要約: 均一な価格で複数ユニットのオークションを繰り返し検討する。
このオークションの特性をオフラインとオンラインの両方で分析する。
ここでは、$(K+1)$-stの価格形式が入札者間の共謀の影響を受けやすいことを示す。
- 参考スコア（独自算出の注目度）: 17.727436775513368
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider repeated multi-unit auctions with uniform pricing, which are
widely used in practice for allocating goods such as carbon licenses. In each
round, $K$ identical units of a good are sold to a group of buyers that have
valuations with diminishing marginal returns. The buyers submit bids for the
units, and then a price $p$ is set per unit so that all the units are sold. We
consider two variants of the auction, where the price is set to the $K$-th
highest bid and $(K+1)$-st highest bid, respectively.
We analyze the properties of this auction in both the offline and online
settings. In the offline setting, we consider the problem that one player $i$
is facing: given access to a data set that contains the bids submitted by
competitors in past auctions, find a bid vector that maximizes player $i$'s
cumulative utility on the data set. We design a polynomial time algorithm for
this problem, by showing it is equivalent to finding a maximum-weight path on a
carefully constructed directed acyclic graph.
In the online setting, the players run learning algorithms to update their
bids as they participate in the auction over time. Based on our offline
algorithm, we design efficient online learning algorithms for bidding. The
algorithms have sublinear regret, under both full information and bandit
feedback structures. We complement our online learning algorithms with regret
lower bounds.
Finally, we analyze the quality of the equilibria in the worst case through
the lens of the core solution concept in the game among the bidders. We show
that the $(K+1)$-st price format is susceptible to collusion among the bidders;
meanwhile, the $K$-th price format does not have this issue.
- Abstract（参考訳）: 我々は,炭素ライセンスなどの商品の割当に広く用いられている,均一価格の複数単位のオークションを繰り返すことを検討する。
各ラウンドにおいて、$k$の同一のユニットは、限界リターンを減少させるバリュエーションを持つバリュエーションを持つグループに販売される。
購入者は各ユニットの入札を提出し、各ユニットごとに$p$が設定され、すべてのユニットが販売される。
我々は、オークションの2つのバリエーションを検討し、価格がそれぞれk$-th highest bidと$(k+1)$-st highest bidに設定される。
我々は、このオークションのプロパティをオフラインとオンラインの両方の設定で分析する。
オフライン環境では、1人のプレイヤーが対面している問題を考える:過去のオークションで競合が提示した入札を含むデータセットへのアクセスを与えられた場合、データセット上のプレイヤー$i$の累積ユーティリティを最大化する入札ベクターを見つける。
この問題に対して多項式時間アルゴリズムを設計し、慎重に構築された有向非巡回グラフ上で最大重み付き経路を求めることに等価であることを示す。
オンライン環境では、プレイヤーは学習アルゴリズムを実行し、オークションに参加するときに入札を更新する。
オフラインアルゴリズムに基づいて、入札のための効率的なオンライン学習アルゴリズムを設計する。
アルゴリズムは、完全な情報とバンディットフィードバック構造の両方の下で、サブリニアな後悔を持っている。
私たちはオンライン学習アルゴリズムを後悔の少ない限界で補完します。
最後に、入札者間のゲームにおけるコアソリューション概念のレンズを通して、最悪の場合における平衡の質を分析する。
我々は、$(K+1)$-stの価格フォーマットが入札者間の共謀の影響を受けやすいことを示し、一方で、$K$-thの価格フォーマットにはこの問題がない。
関連論文リスト
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
本稿では、ROIと予算制約の対象となる価値を最適化するために、オンラインオートバイディングアルゴリズムを設計する問題について検討する。
我々の主な結果は、最高のリプシッツ関数に関して、ほぼ最適の$tilde O(sqrt T)$の後悔を保証する完全な情報フィードバックを持つアルゴリズムである。
論文 参考訳（メタデータ） (2024-04-15T14:31:53Z) - Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳（メタデータ） (2023-10-08T07:04:22Z) - Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
本研究では,単一入札者の視点から,ペイ・アズ・バイド(PAB)オークションにおける入札戦略の問題点を考察する。
提案手法は,競合する入札が事前に知られている場合のオフライン問題を,時間アルゴリズムで解くことができることを示す。
また,PAB平衡のキャラクタリゼーションについても検討した。
論文 参考訳（メタデータ） (2023-07-27T20:49:28Z) - 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) - No-Regret Learning in Partially-Informed Auctions [85.67897346422122]
本研究では,一部の情報を用いたオークションの機械学習定式化について検討する。
各ラウンドでは、未知の分布から新しいアイテムが引き出され、プラットフォームは、そのアイテムに関する不完全な「偽」情報とともに価格を発行する。
アイテムの分布が買い手に知られ、マスクがSimHash関数のマッピングである場合、$mathbbRd$ to $0,1ell$、我々のアルゴリズムは、$tilde MathcalO((Tdell)frac12)$を後悔している。
論文 参考訳（メタデータ） (2022-02-22T01:15:51Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。
対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。
我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
論文 参考訳（メタデータ） (2021-07-05T07:48:52Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。