論文の概要: Strategizing against No-Regret Learners in First-Price Auctions
- arxiv url: http://arxiv.org/abs/2402.08637v1
- Date: Tue, 13 Feb 2024 18:03:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 14:17:03.515973
- Title: Strategizing against No-Regret Learners in First-Price Auctions
- Title（参考訳）: プライスオークションにおける非学習者に対する戦略
- Authors: Aviad Rubinstein and Junyao Zhao
- Abstract要約: 本研究は,2人のプレーヤ間の第1価格の繰り返しオークションと一般のベイズゲームについて検討した。
1人のプレイヤーは学習アルゴリズムを使わず、もう1人のプレイヤーは学習者のアルゴリズムを知り、自身のユーティリティを最大限にするために戦略を立てる。
- 参考スコア（独自算出の注目度）: 3.78737122317863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study repeated first-price auctions and general repeated Bayesian games
between two players, where one player, the learner, employs a no-regret
learning algorithm, and the other player, the optimizer, knowing the learner's
algorithm, strategizes to maximize its own utility. For a commonly used class
of no-regret learning algorithms called mean-based algorithms, we show that (i)
in standard (i.e., full-information) first-price auctions, the optimizer cannot
get more than the Stackelberg utility -- a standard benchmark in the
literature, but (ii) in Bayesian first-price auctions, there are instances
where the optimizer can achieve much higher than the Stackelberg utility.
On the other hand, Mansour et al. (2022) showed that a more sophisticated
class of algorithms called no-polytope-swap-regret algorithms are sufficient to
cap the optimizer's utility at the Stackelberg utility in any repeated Bayesian
game (including Bayesian first-price auctions), and they pose the open question
whether no-polytope-swap-regret algorithms are necessary to cap the optimizer's
utility. For general Bayesian games, under a reasonable and necessary
condition, we prove that no-polytope-swap-regret algorithms are indeed
necessary to cap the optimizer's utility and thus answer their open question.
For Bayesian first-price auctions, we give a simple improvement of the standard
algorithm for minimizing the polytope swap regret by exploiting the structure
of Bayesian first-price auctions.
- Abstract（参考訳）: 本研究では,学習者の1人である1人のプレイヤーが学習アルゴリズムを駆使し,もう1人のプレイヤーであるオプティマイザは学習者のアルゴリズムを知ることで,学習者の利便性を最大化するために戦略を練り上げた。
平均ベースアルゴリズムと呼ばれる非回帰学習アルゴリズムの一般的なクラスでは、
(i) 標準(フル情報)の最初の価格オークションでは、オプティマイザはStackelbergユーティリティ(文献の標準ベンチマーク)以上のものを得ることはできないが、
(ii) ベイズ第一価格オークションでは、最適化器がスタックルベルクユーティリティよりもずっと高い価格を実現できる例がある。
一方、Mansour et al. (2022) は「no-polytope-swap-regretアルゴリズム」と呼ばれるより洗練されたアルゴリズムのクラスは、任意のベイズ的ゲーム(ベイズ第一価格オークションを含む)において、最適化者のユーティリティをStackelbergユーティリティに格納するのに十分であることを示した。
一般的なベイズゲームでは、合理的かつ必要条件の下で、オプティマイザの効用を捉えるために、ポリトープ・スワップ・レグレットアルゴリズムが本当に必要でないことを証明する。
ベイズ第一価格オークションに対しては,ベイズ第一価格オークションの構造を利用して,ポリトープスワップ後悔を最小化するための標準アルゴリズムを簡易に改良する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳（メタデータ） (2024-02-12T01:33:33Z) - Strategizing against Learners in Bayesian Games [74.46970859427907]
プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。
一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
論文 参考訳（メタデータ） (2022-05-17T18:10:25Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。
対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。
我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
論文 参考訳（メタデータ） (2021-07-05T07:48:52Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳（メタデータ） (2020-11-10T12:45:02Z) - 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) - Adversarial Online Learning with Changing Action Sets: Efficient
Algorithms with Approximate Regret Bounds [48.312484940846]
睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。
各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。
我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-03-07T02:13:21Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。