論文の概要: Improving the Bounds on Approximating Weighted Maximin Share for Chores
- arxiv url: http://arxiv.org/abs/2610.15520v1
- Date: Sun, 11 Oct 2026 10:37:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-15 21:06:15.221643
- Title: Improving the Bounds on Approximating Weighted Maximin Share for Chores
- Title（参考訳）: 選別における重み付き最大シェアの近似に関するバウンドの改善
- Abstract要約: 任意の正重みを持つエージェントと、付加的な非負のコスト関数を持つエージェント間での分別不能な雑用を割り当てる問題について検討する。
エージェント数、雑用数、入力の総バイナリエンコーディング長に時間的に4.12$-WMMSを割り当てる。
- 参考スコア（独自算出の注目度）: 5.727449438047249
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$-WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$-WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$. Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$.
- Abstract（参考訳）: 任意の正重みを持つエージェントと、付加的な非負のコスト関数を持つエージェント間での分別不能な雑用を割り当てる問題について検討する。
割当が$α$-weighted-maximin-share (WMMS) であるとは、各エージェントが引き起こしたコストが彼女の重み付きmaximinの最大値のα$倍である場合である。
すべてのインスタンスが4.124234528$-WMMSのアロケーションを許可していると確認します。
さらに、全ての重みとコストが2進数で表される場合、エージェント数、コレ数、入力の総バイナリ符号化長の時間多項式の割り当てを4.12424$-WMMSで計算するアルゴリズムを与える。
これらの上限を補完し、最適WMMS近似係数が$e$に収束する厳密な正の、同じ順序のコストのインスタンス群を構築する。
この結果により、Li et al ~\cite{LWX26} が確立した$[2,12]$を$[e,4.12424]$に実質的に制限した。
関連論文リスト
- Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
我々は,各ラウンドにおいてエージェントが$k$アームのスレートを選択し,それらの$d$次元報酬ベクトルを半帯域フィードバック下で観察する多目的バンディット問題を考える。
この目的を、選択されたアームのサブセットによって誘導される支配的な超体積を通して定式化し、最高のサイズに対して$$$-approximate hypervolume regretを定義する。
ギャップのない後悔境界を持つ$tildeO(dsqrtnkT)$を、ギャップとともにすべてのインスタンスに保持する。
論文 参考訳（メタデータ） (2026-07-28T21:10:39Z) - Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
このモデルは、$M$armと$K$playで構成されている。
各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。
複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
論文 参考訳（メタデータ） (2025-12-25T11:19:09Z) - Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。
善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。
我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
論文 参考訳（メタデータ） (2025-05-28T09:48:16Z) - Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文 参考訳（メタデータ） (2024-11-13T05:59:04Z) - Stochastic Multi-round Submodular Optimization with Budget [7.902059578326225]
我々は、アイテムの部分集合上で定義された単調部分モジュラー目的関数の和を、複数のラウンドで適応的に最大化することを目指している。
目的関数はイベントの実現にも依存しており、全てのラウンドで選択できるアイテムの総数は、限られた予算で制限されている。
論文 参考訳（メタデータ） (2024-04-21T18:24:43Z) - Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである
本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。
マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
論文 参考訳（メタデータ） (2024-02-11T01:51:15Z) - Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。
我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。
マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
論文 参考訳（メタデータ） (2020-07-02T10:48:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。