論文の概要: Pricing Query Complexity of Multiplicative Revenue Approximation

• arxiv url: http://arxiv.org/abs/2602.10483v1
• Date: Wed, 11 Feb 2026 03:42:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-12 21:44:01.434137
• Title: Pricing Query Complexity of Multiplicative Revenue Approximation
• Title（参考訳）: 乗算収益近似の価格クエリ複雑性
• Authors: Wei Tang, Yifan Wang, Mengxiao Zhang,
• Abstract要約: 本研究では、未公開の流通から個人価値を引き出す単一購入者に対する収益の価格クエリについて検討する。 この設定では、売り手は価格を掲示し、二国間購入決定のみを観察することで最適な独占価格を学ばなければならない。
• 参考スコア（独自算出の注目度）: 20.644559918113945
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the pricing query complexity of revenue maximization for a single buyer whose private valuation is drawn from an unknown distribution. In this setting, the seller must learn the optimal monopoly price by posting prices and observing only binary purchase decisions, rather than the realized valuations. Prior work has established tight query complexity bounds for learning a near-optimal price with additive error $\varepsilon$ when the valuation distribution is supported on $[0,1]$. However, our understanding of how to learn a near-optimal price that achieves at least a $(1-\varepsilon)$ fraction of the optimal revenue remains limited. In this paper, we study the pricing query complexity of the single-buyer revenue maximization problem under such multiplicative error guarantees in several settings. Observe that when pricing queries are the only source of information about the buyer's distribution, no algorithm can achieve a non-trivial approximation, since the scale of the distribution cannot be learned from pricing queries alone. Motivated by this fundamental impossibility, we consider two natural and well-motivated models that provide "scale hints": (i) a one-sample hint, in which the algorithm observes a single realized valuation before making pricing queries; and (ii) a value-range hint, in which the valuation support is known to lie within $[1, H]$. For each type of hint, we establish pricing query complexity guarantees that are tight up to polylogarithmic factors for several classes of distributions, including monotone hazard rate (MHR) distributions, regular distributions, and general distributions.
• Abstract（参考訳）: 本研究では、未公開の分布から個人価値を引き出す単一購入者に対して、収益最大化の価格クエリの複雑さについて検討する。 この設定では、売り手は、実際の評価ではなく、価格を投稿し、バイナリ購入決定のみを観察することで、最適な独占価格を学ばなければならない。 事前の作業は、[0,1]$で評価分布がサポートされている場合、加算エラー$\varepsilon$で、ほぼ最適価格を学ぶための厳密なクエリ複雑性境界を確立した。 しかし、最適な収益の少なくとも1-\varepsilon(=1-\varepsilon)を達成できる、最適に近い価格の学習方法に関する私たちの理解は、依然として限られている。 本稿では,このような乗算誤差保証の下で,単一購入者収益の最大化問題における価格クエリの複雑さについて検討する。 価格クエリが購入者の流通に関する情報の唯一の源である場合,価格クエリだけでは分布の規模を学習できないため,アルゴリズムが非自明な近似を達成できないことを確認する。 この基本的な不可能さに動機付けられ、我々は「スケールヒント」を提供する2つの自然なモデルと動機付けされたモデルを考える。 二 単サンプルのヒントで、そのアルゴリズムは、価格クエリを作成する前に、単一の実現された評価を観測する。 (ii) 評価支援が$[1, H]$以内であることが知られている値範囲ヒント。 各種類のヒントに対して, モノトンハザードレート (MHR) 分布, 正規分布, 一般分布など, 複数種類の分布に対して, 多対数的因子に強く依存する価格クエリの複雑性を保証する。

関連論文リスト

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Contextual Learning for Stochastic Optimization [1.0819408603463425]
  最適化によってモチベーションを得て,文脈値分布のサンプルから学習する問題を導入する。 各サンプルは、コンテキスト$x$と、対応する実値分布$D_x$から引き出されたランダム変数からなる。
  論文  参考訳（メタデータ） (2025-05-22T16:01:49Z)
• Online Combinatorial Allocations and Auctions with Few Samples [9.675397292814122]
  本稿では,O(1)競合アルゴリズムの実現可能性について,基礎となる入札者分布から限られた数のサンプルにしかアクセスできないという現実的な制約の下で検討する。 最初の主な貢献は, サブモジュール/XOS評価のためのO(1)競合アルゴリズムを得るのに, 各入札者分布からのサンプルだけで十分であることを示している。
  論文  参考訳（メタデータ） (2024-09-17T11:43:55Z)
• Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models [8.981637739384674]
  意思決定者は、観測可能なコンテキストに基づいてパーソナライズされた価格を投稿する。 それぞれのバリュエーションはコンテキストの未知の潜在関数としてモデル化され、独立性と同一に分散された市場ノイズによって破損する。
  論文  参考訳（メタデータ） (2024-06-24T23:43:56Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
  実験的な分布を2つの課題で推定する問題に取り組む。 まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。 第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
  論文  参考訳（メタデータ） (2023-01-13T18:00:57Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)

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

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