論文の概要: (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna

• arxiv url: http://arxiv.org/abs/2202.02672v1
• Date: Sun, 6 Feb 2022 01:29:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-10 09:39:14.340221
• Title: (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
• Title（参考訳）: (ほとんど)不可分な混合マンナの自在, 比例的, 効率的配置
• Authors: Vasilis Livanos, Ruta Mehta, Aniket Murhekar
• Abstract要約: エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。 公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
• 参考スコア（独自算出の注目度）: 10.933894827834825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX$_0$), and proportional up to the maximin good or any bad (PropMX and PropMX$_0$). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item $j$, every agent has either a non-positive value for $j$, or values $j$ at the same $v_j>0$. We obtain polynomial-time algorithms for the following: (i) Separable instances: PropMX$_0$ allocation. (ii) RMG instances: Let pure bads be the set of items that everyone values negatively. - PropMX allocation for general pure bads. - EFX+PropMX allocation for identically-ordered pure bads. - EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the $v_j$'s are the same, we strengthen the results to guarantee EFX$_0$ and PropMX$_0$ respectively.
• Abstract（参考訳）: 本研究では,あるエージェントに対して,各アイテムが良い(肯定的に価値が高い)もの,他のエージェントにとって悪い(否定的に価値が高い)もの,すなわち混合マンナに公平かつ効率的な割り当てを求める問題について検討する。 公平性の概念として、あらゆる項目(efx と efx$_0$)までエンビーフリーであり、最大善または悪(propmx と propmx$_0$)に比例するエンビーフリー性と比例性の最も強い緩和性を考える。 効率性の概念はpareto-optimality(po)です。 私たちは2種類の例を研究します 一 商品セットを商品及び悪品に分割することができる分離可能 (i)制限混合商品(RMG)各項目の$j$に対して、各エージェントが$j$の非正の値を持つか、同じ$v_j>0$の値を$j$とする。 下記の多項式時間アルゴリズムを得る。 (i) 分離可能なインスタンス: propmx$_0$ 割り当て。 (ii) rmgインスタンス:pure badsをみんなが否定的に評価するアイテムの集合とする。 -一般的な純悪に対するpropMXアロケーション。 - EFX+PropMX 同一順序の純悪に対するアロケーション。 - EFX+PropMX+PO が同一の純悪を割り当てる。 最後に、RMGインスタンスが、すべての$v_j$sが同じバイナリ混合グッズにさらに制限されている場合、それぞれEFX$_0$とPropMX$_0$を保証するように結果を強化します。

関連論文リスト

• Pushing the Frontier on Approximate EFX Allocations [14.101164748526159]
  本研究では, 付加的評価関数を持つエージェント群に対して, 分割不可能な商品群を割り当てる問題について検討する。 正確なEFXアロケーションが存在することが分かっている設定の厳密な一般化のために、我々は存在結果を得る。 この結果から, 近似EFXアロケーションの存在と計算のフロンティアを推し進めることができた。
  論文  参考訳（メタデータ） (2024-06-18T09:01:37Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。 競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
  論文  参考訳（メタデータ） (2024-05-31T19:26:05Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。 我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
  論文  参考訳（メタデータ） (2023-02-06T19:41:28Z)
• Fair Shares: Feasibility, Domination and Incentives [6.878547831852427]
  我々は、金額の異なる商品のセット$M$を、均等に権利を付与されたエージェントに公平に割り当てるが、金銭的譲渡は行わない。 付加価値については、実行可能、自己最大化、時間計算可能な共有を提示します。
  論文  参考訳（メタデータ） (2022-05-16T08:52:42Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  付加価値関数を持つ戦略エージェントの集合に、分割不可能な商品の集合をかなり割り当てるという問題を考察する。 我々の主なゴールは、全てのインスタンスに純粋なナッシュ平衡を持つメカニズムが存在するかどうかを探ることである。 対応するアロケーションは EFX だけでなく、最大シェアフェアネスも満足していることを示します。
  論文  参考訳（メタデータ） (2021-09-17T16:57:20Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning [66.94149388181343]
  本稿では,MARLのためのQ$-learningアルゴリズムの新バージョンを提案する。 Q*$をアクセスしても、最適なポリシーを回復できることを示します。 また,プレデレータープリとマルチエージェントのStarCraftベンチマークタスクの性能向上を実証した。
  論文  参考訳（メタデータ） (2020-06-18T18:34:50Z)
• Jealousy-freeness and other common properties in Fair Division of Mixed Manna [2.28438857884398]
  我々は、不特定項目をエージェントに割り当てる公平な区分について考察する。 エージェントに良く、他の人に悪いアイテムを区別します。
  論文  参考訳（メタデータ） (2020-04-23T21:39:12Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)

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

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