論文の概要: Maximin Share Guarantees via Limited Cost-Sensitive Sharing

• arxiv url: http://arxiv.org/abs/2602.20541v2
• Date: Wed, 25 Feb 2026 16:38:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-26 16:16:21.2896
• Title: Maximin Share Guarantees via Limited Cost-Sensitive Sharing
• Title（参考訳）: 限界コスト感性共有による最大株式保証
• Authors: Hana Salavcova, Martin Černý, Arpita Biswas,
• Abstract要約: 我々は,限定的な共有が許された場合に,分割不可能な商品を割当する問題について検討する。 我々は、商品がコストに敏感に共有されることが許された場合、正確な最大シェア(MMS)割り当てが保証されていることを示す。 また,Sharing Maximin Share (SMMS) の公平性の概念についても紹介する。
• 参考スコア（独自算出の注目度）: 1.75092370599135
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to $k$ agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we demonstrate that allowing controlled sharing can restore fairness guarantees that are otherwise unattainable in certain scenarios. (1) Our first contribution shows that exact maximin share (MMS) allocations are guaranteed to exist whenever goods are allowed to be cost-sensitively shared among at least half of the agents and the number of agents is even; for odd numbers of agents, we obtain a slightly weaker MMS guarantee. (2) We further design a Shared Bag-Filling Algorithm that guarantees a $(1 - C)(k - 1)$-approximate MMS allocation, where $C$ is the maximum cost of sharing a good. Notably, when $(1 - C)(k - 1) \geq 1$, our algorithm recovers an exact MMS allocation. (3) We additionally introduce the Sharing Maximin Share (SMMS) fairness notion, a natural extension of MMS to the $k$-sharing setting. (4) We show that SMMS allocations always exist under identical utilities and for instances with two agents. (5) We construct a counterexample to show the impossibility of the universal existence of an SMMS allocation. (6) Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results. These contributions provide deep theoretical insights for the problem of fair resource allocation when a limited sharing of resources are allowed in multi-agent environments.
• Abstract（参考訳）: 我々は、限定的な共有が許された場合、各商品を最大で400ドルのエージェントに割り当てることができ、共有のコストがかかる場合に、かなり分割不可能な商品を割り当てるという問題を調査する。 古典的な最大値共有(MMS)割り当ては多くのインスタンスに存在しないかもしれないが、制御された共有を許すことで、特定のシナリオでは達成不可能な公平性を保証することができることを実証する。 1) 当社の第一の貢献は、商品が少なくとも半数のエージェントの間で価格に敏感に共有され、エージェントの数が偶数である場合に、正確な最大シェア(MMS)割り当てが保証されることを示し、奇数エージェントについては、やや弱いMMS保証を得る。 2) 1 - C)(k - 1)$-approximate MMSアロケーションを保証する共有バグフィリングアルゴリズムをさらに設計する。 特に、$(1 - C)(k - 1) \geq 1$のとき、我々のアルゴリズムは正確なMMS割り当てを復元する。 (3)Sharing Maximin Share (SMMS) Fairness concept, a natural extension of MMS to the $k$-sharing setting。 (4)SMMS割り当ては同一のユーティリティと2つのエージェントを持つインスタンスに対して常に存在することを示す。 (5) SMMS割り当ての普遍的存在の不確実性を示す反例を構築した。 (6) SMMSと制約付きMMS(CMMS)の接続を確立し, 既存のCMMS結果からSMMSの近似保証を得る。 これらの貢献は、資源の限られた共有がマルチエージェント環境で可能である場合に、公平な資源割り当ての問題に対する深い理論的洞察を提供する。

関連論文リスト

• Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback [42.17945622232755]
  本研究では,モノトーンサブモジュール型ユーティリティを持つエージェント間でアイテムを分割する,emph Submodular Welfare Problem (SWP) について検討する。 我々はこれをEmphmulti-agent bandit framework(textscMA-CMAB)に拡張する。 1-1/e のベンチマークに対して $tildemathcalO(T2/3)$ regret を達成し、最初にそのような保証を行う。
  論文  参考訳（メタデータ） (2026-02-18T05:00:51Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Benchmarking Multi-modal Semantic Segmentation under Sensor Failures: Missing and Noisy Modality Robustness [61.87055159919641]
  マルチモーダルセマンティックセグメンテーション(MMSS)は、モーダル間で補完情報を統合することで、単一モーダルデータの制限に対処する。 顕著な進歩にもかかわらず、マルチモーダルデータ品質の変動と不確実性により、研究と実世界の展開の間に大きなギャップが持続する。 Intire-Missing Modality (EMM)、Random-Missing Modality (RMM)、Noisy Modality (NM)の3つのシナリオでMMSSモデルを評価する頑健性ベンチマークを導入する。
  論文  参考訳（メタデータ） (2025-03-24T08:46:52Z)
• Multi-Agent Reinforcement Learning with Shared Resources for Inventory Management [62.23979094308932]
  私たちの設定では、共有リソース(在庫容量など)の制約は、SKUごとに独立した制御を結合します。 共有資源ゲーム(SRSG)としてこの問題を定式化し,CD-PPO(Context-aware Decentralized PPO)と呼ばれる効率的なアルゴリズムを提案する。 実験により,CD-PPOは標準的なMARLアルゴリズムと比較して学習手順を高速化できることが実証された。
  論文  参考訳（メタデータ） (2022-12-15T09:35:54Z)
• Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise [28.2469613376685]
  原理は、各エージェントが何らかの確率でリソースにマッチするように、ランダムに最大マッチングを選択することを示す。 エージェントは、制限を一定の範囲内で変更することで、マッチする可能性を改善したいと考えています。 本研究では,合成データセットと2つの新しい実世界のデータセットについて実験的に評価した。
  論文  参考訳（メタデータ） (2022-09-12T11:58:19Z)
• DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning [26.286805758673474]
  我々は,MASeのためのテキスト制約付き協調型MARLフレームワークであるDeCOMを開発した。 DeCOMは、各エージェントのポリシーを2つのモジュールに分解し、エージェント間の情報共有により、より良い協力を実現する。 玩具と大規模(500エージェント)環境におけるDeCOMの有効性を,様々なコストで検証した。
  論文  参考訳（メタデータ） (2021-11-10T12:31:30Z)
• Guaranteeing Maximin Shares: Some Agents Left Behind [18.960425204405038]
  最適な近似アルゴリズムが一定数以上のエージェントを満足できないことを示し、MMSの存在と計算を1つのエージェントを除いて議論する。 私たちの結果の重要な意味は、$textMMSlceil3n/2rceil$、すなわち、エージェントが商品を$lceilfrac32nrceil$バンドルに分割することで受け取る値を保証するアロケーションの存在である。
  論文  参考訳（メタデータ） (2021-05-19T20:17:42Z)

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

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