論文の概要: Envy-Free Allocation of Indivisible Goods via Noisy Queries

• arxiv url: http://arxiv.org/abs/2602.06361v1
• Date: Fri, 06 Feb 2026 03:44:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.222021
• Title: Envy-Free Allocation of Indivisible Goods via Noisy Queries
• Title（参考訳）: ノイズクェリによる異種商品のうらやましな配置
• Authors: Zihan Li, Yan Hao Ling, Jonathan Scarlett, Warut Suksompong,
• Abstract要約: エージェントのバリュエーションを直接観察できない、かなり分割不可能な商品を割り当てる問題を導入する。 本手法では,要求されるクエリ数の上限値と上限値の上限値を求める。 我々の上限は、非適応的なクエリと計算時間で実行される単純なしきい値に基づくアロケーションアルゴリズムに基づいている。
• 参考スコア（独自算出の注目度）: 66.16311857301167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a problem of fairly allocating indivisible goods (items) in which the agents' valuations cannot be observed directly, but instead can only be accessed via noisy queries. In the two-agent setting with Gaussian noise and bounded valuations, we derive upper and lower bounds on the required number of queries for finding an envy-free allocation in terms of the number of items, $m$, and the negative-envy of the optimal allocation, $Δ$. In particular, when $Δ$ is not too small (namely, $Δ\gg m^{1/4}$), we establish that the optimal number of queries scales as $\frac{\sqrt m }{(Δ/ m)^2} = \frac{m^{2.5}}{Δ^2}$ up to logarithmic factors. Our upper bound is based on non-adaptive queries and a simple thresholding-based allocation algorithm that runs in polynomial time, while our lower bound holds even under adaptive queries and arbitrary computation time.
• Abstract（参考訳）: エージェントのバリュエーションを直接観察することができないが、ノイズの多いクエリによってのみアクセスすることができる。 ガウスノイズと有界値を持つ2つのエージェント設定では、アイテム数、$m$、最適なアロケーションの負のエンビー($Δ$)という点において、ウィッチフリーなアロケーションを見つけるために必要となるクエリ数の上と下限を導出する。 特に$Δ$が小さすぎる場合(すなわち$Δ\gg m^{1/4}$)、クエリの最適数は$\frac{\sqrt m }{(Δ/m)^2} = \frac{m^{2.5}}{Δ^2}$から対数因子までスケールする。 我々の上限は、適応的でないクエリと、多項式時間で実行される単純なしきい値ベースの割当アルゴリズムに基づいており、下限は適応的クエリと任意の計算時間の下でも保持する。

関連論文リスト

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。 提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
  論文  参考訳（メタデータ） (2023-09-21T12:42:52Z)
• On the Optimal Bounds for Noisy Computing [17.56584950469176]
  Wevisit the problem of computing with noisy information considered in Feige et al. 1994。 与えられた要素に対して、目標は、各クエリの結果が確率$p$で反転されたときに、少なくとも1-delta$の確率で所望の関数を正しく回復することである。 本稿では、過去の結果に基づいて各クエリを適応的に設計できる適応型サンプリング設定と、過去の結果に依存しない非適応型サンプリング設定の両方について考察する。
  論文  参考訳（メタデータ） (2023-06-21T00:31:23Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
  我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。 ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
  論文  参考訳（メタデータ） (2022-02-22T01:49:41Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。 線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。 我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
  論文  参考訳（メタデータ） (2020-09-10T16:35:54Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
  本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。 アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。 新規検索戦略として$dyaPM$と$hiePM$が提案されている。
  論文  参考訳（メタデータ） (2020-05-15T22:40:18Z)

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

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