論文の概要: Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
- arxiv url: http://arxiv.org/abs/2406.03674v3
- Date: Wed, 23 Jul 2025 21:09:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-25 15:10:40.421379
- Title: Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
- Title（参考訳）: 均一価格オークションにおける買い手価値最大化のための安全策の学習
- Authors: Negin Golrezaei, Sourav Sahoo,
- Abstract要約: 価格を最大化する買い手の観点から,単価の複数ユニットオークションを繰り返す際の入札問題について検討する。
本稿では、競合入札に関係なく、RoI制約を満たすものとして、安全な入札戦略の概念を紹介する。
これらの戦略は入札者の評価曲線にのみ依存し, 一般性を損なうことなく, 有限部分集合に焦点を絞ることができることを示す。
- 参考スコア（独自算出の注目度）: 4.089889918897877
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a value-maximizing buyer. The buyer aims to maximize their cumulative value over $T$ rounds while adhering to per-round return-on-investment (RoI) constraints in a strategic (or adversarial) environment. Using an $m$-uniform bidding format, the buyer submits $m$ bid-quantity pairs $(b_i, q_i)$ to demand $q_i$ units at bid $b_i$, with $m \ll M$ in practice, where $M$ denotes the maximum demand of the buyer. We introduce the notion of safe bidding strategies as those that satisfy the RoI constraints irrespective of competing bids. Despite the stringent requirement, we show that these strategies satisfy a mild no-overbidding condition, depend only on the valuation curve of the bidder, and the bidder can focus on a finite subset without loss of generality. Though the subset size is $O(M^m)$, we design a polynomial-time learning algorithm that achieves sublinear regret, both in full-information and bandit settings, relative to the hindsight-optimal safe strategy. We assess the robustness of safe strategies against the hindsight-optimal strategy from a richer class. We define the richness ratio $\alpha \in (0,1]$ as the minimum ratio of the value of the optimal safe strategy to that of the optimal strategy from richer class and construct hard instances showing the tightness of $\alpha$. Our algorithm achieves $\alpha$-approximate sublinear regret against these stronger benchmarks. Simulations on semi-synthetic auction data show that empirical richness ratios significantly outperform the theoretical worst-case bounds. The proposed safe strategies and learning algorithm extend naturally to more nuanced buyer and competitor models.
- Abstract（参考訳）: 価格を最大化する買い手の観点から,単価の複数ユニットオークションを繰り返す際の入札問題について検討する。
買い手は、戦略的(または敵対的な)環境において、ラウンドごとのリターン・オン・投資(RoI)制約に固執しながら、T$ラウンド以上の累積価値を最大化することを目指している。
m$-uniformの入札フォーマットを使用して、バイヤーは$m$の入札通貨対を$(b_i, q_i)$で、入札時に$q_i$の入札単位を$b_i$で、実際に$m \ll M$で、バイヤーの最大需要を表す$M$を提出する。
本稿では、競合入札に関係なく、RoI制約を満たすものとして、安全な入札戦略の概念を紹介する。
厳密な要求にもかかわらず、これらの戦略は入札者の評価曲線のみに依存し、入札者は一般性を損なうことなく有限部分集合に集中することができる。
サブセットサイズは$O(M^m)$であるが,全情報および帯域幅設定の両方において,後方最適安全戦略に対して,サブ線形後悔を実現する多項式時間学習アルゴリズムを設計する。
より富裕層からの後方最適戦略に対する安全な戦略の堅牢性を評価する。
リッチネス比 $\alpha \in (0,1]$ を、よりリッチなクラスからの最適戦略の値と最適安全戦略の値の最小比として定義し、$\alpha$ の強みを示すハードインスタンスを構築する。
我々のアルゴリズムはこれらの強いベンチマークに対して$\alpha$-approximate sublinear regretを達成する。
半合成オークションデータによるシミュレーションでは、経験的富度比が理論的最悪のケース境界よりも著しく優れていることが示された。
提案した安全な戦略と学習アルゴリズムは、よりニュアンスの高い購入者と競合するモデルに自然に拡張される。
関連論文リスト
- Learning to Lead: Incentivizing Strategic Agents in the Dark [50.93875404941184]
一般化プリンシパルエージェントモデルのオンライン学習バージョンについて検討する。
この挑戦的な設定のための最初の証明可能なサンプル効率アルゴリズムを開発した。
我々は、プリンシパルの最適ポリシーを学ぶために、ほぼ最適な $tildeO(sqrtT) $ regret bound を確立する。
論文 参考訳（メタデータ） (2025-06-10T04:25:04Z) - Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
この結果から,悪用可能な相手からOmega(T)$を得ることができながら,少なくともO(1)$損失のリスクを保証できることが分かる。
論文 参考訳（メタデータ） (2025-02-17T11:04:01Z) - Learning to Bid in Non-Stationary Repeated First-Price Auctions [20.933903777434086]
第一価オークションはデジタル広告市場で大きな注目を集めている。
第一価格オークションにおける最適な入札戦略を決定することはより複雑である。
入札順序の正則性を定量化する2つの指標を導入する。
論文 参考訳（メタデータ） (2025-01-23T03:53:27Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳（メタデータ） (2024-02-12T01:33:33Z) - Contextual Dynamic Pricing with Strategic Buyers [93.97401997137564]
戦略的買い手によるコンテキスト動的価格問題について検討する。
売り手は買い手の真の特徴を観察せず、買い手の戦略行動に応じて操作された特徴を観察する。
本稿では,販売者の累積収益を最大化するために,購入者の戦略的行動をオンライン学習に取り入れた戦略的動的価格政策を提案する。
論文 参考訳（メタデータ） (2023-07-08T23:06:42Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Provably Efficient Offline Multi-agent Reinforcement Learning via
Strategy-wise Bonus [48.34563955829649]
本稿では,共同戦略の信頼区間を構築する戦略的な集中原理を提案する。
2人のプレイヤーによるゼロサムマルコフゲームの場合、戦略的なボーナスの凸性を利用して効率的なアルゴリズムを提案する。
すべてのアルゴリズムは、指定済みの戦略クラスである$Pi$を入力として取り、最良の戦略に近い戦略を$Pi$で出力することができる。
論文 参考訳（メタデータ） (2022-06-01T00:18:15Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - Stochastic Strategic Patient Buyers: Revenue maximization using posted
prices [40.698164629357066]
我々は、意思決定を遅らせる能力を持つ買い手と対面する売り手について検討する。
各買い手の型は、価値と忍耐からなり、分布から標本化される。
我々は,販売者の最適な純粋戦略と,販売者の混合戦略に対する買い手の最良の対応戦略の両方を特徴付ける。
論文 参考訳（メタデータ） (2022-02-12T21:11:31Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。
対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。
我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
論文 参考訳（メタデータ） (2021-07-05T07:48:52Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳（メタデータ） (2020-11-10T12:45:02Z) - Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff
in Regret [115.85354306623368]
本研究では,未知の遷移カーネルを持つマルコフ決定過程におけるリスク感応性強化学習について検討する。
確率的に効率的なモデルレスアルゴリズムとして、リスク感性価値反復(RSVI)とリスク感性Q-ラーニング(RSQ)を提案する。
RSVIが $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big) に達したことを証明しています。
論文 参考訳（メタデータ） (2020-06-22T19:28:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。