Fugu-MT 論文翻訳(概要): Dividing Good and Better Items Among Agents with Submodular Valuations

論文の概要: Dividing Good and Better Items Among Agents with Submodular Valuations

arxiv url: http://arxiv.org/abs/2302.03087v2
Date: Wed, 12 Apr 2023 17:17:56 GMT
ステータス: 処理完了
システム内更新日: 2023-04-13 17:58:41.226240
Title: Dividing Good and Better Items Among Agents with Submodular Valuations
Title（参考訳）: 副次的評価を有するエージェント間の良質・良質な項目の分割
Authors: Cyrus Cousins, Vignesh Viswanathan and Yair Zick
Abstract要約: 本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。これは2つのよく研究された評価クラスの自然な一般化であり、二値加法評価と二値部分モジュラー評価である。
参考スコア（独自算出の注目度）: 20.774185319381985
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of fairly allocating a set of indivisible goods among agents with bivalued submodular valuations -- each good provides a marginal gain of either $a$ or $b$ ($a < b$) and goods have decreasing marginal gains. This is a natural generalization of two well-studied valuation classes -- bivalued additive valuations and binary submodular valuations. We present a simple sequential algorithmic framework, based on the recently introduced Yankee Swap mechanism, that can be adapted to compute a variety of solution concepts, including leximin, max Nash welfare (MNW) and $p$-mean welfare maximizing allocations when $a$ divides $b$. This result is complemented by an existing result on the computational intractability of leximin and MNW allocations when $a$ does not divide $b$. We further examine leximin and MNW allocations with respect to two well-known properties -- envy freeness and the maximin share guarantee. On envy freeness, we show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good (EF1). This is surprising since for the simpler classes of bivalued additive valuations and binary submodular valuations, MNW allocations are known to be envy free up to any good (EFX). On the maximin share guarantee, we show that MNW and leximin allocations guarantee each agent $\frac14$ and $\frac{a}{b+3a}$ of their maximin share respectively when $a$ divides $b$. This fraction improves to $\frac13$ and $\frac{a}{b+2a}$ respectively when agents have bivalued additive valuations.
Abstract（参考訳）: 我々は,二価のサブモジュラー価値を持つエージェント間で,一組の不可分な商品を公平に割り当てる問題について検討する。これは2つのよく研究された付値クラスの自然な一般化である。本稿では,最近導入されたYankee Swap機構に基づいて,レキシミン,最大ナッシュ福祉(MNW),および$a$が$b$を分割した場合のアロケーションを最大化する$p$平均福祉など,様々なソリューション概念を計算できる簡単な逐次アルゴリズムフレームワークを提案する。この結果は、$a$ が$b$ を割らない場合、レキシミンとmnwの割り当ての計算不能性に関する既存の結果によって補完される。さらに、よく知られた2つの性質、うらやましい自由度と最大シェア保証に関して、レキシミンとMNWの割り当てについて検討する。 envy freenessでは、レキシミンとmnwの割り当ては1つの良いものまでenvy freeであることが保証されていない(ef1)。二値加法評価と二値部分モジュラー評価のより単純なクラスでは、MNWアロケーションはどんな良いもの(EFX)にもうらやましいことが知られているので、これは驚くべきことである。マキシミン共有保証では、MNWとレキシミン割り当てが各エージェントの$\frac14$と$\frac{a}{b+3a}$をそれぞれ保証していることを示す。この分率は、エージェントが2値の付加価値を持つ場合、それぞれ$\frac13$と$\frac{a}{b+2a}$に改善される。

関連論文リスト

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications [0.0]
我々は、fair $k$submodular問題を研究し、実行時間$mathO(knB)$で$frac13$近似を開発する。我々は$k$-submodular関数がアクセスできないが、ほぼアクセス可能な場合にのみ近似を保証する。
論文参考訳（メタデータ） (2024-11-08T04:20:12Z)
Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文参考訳（メタデータ） (2024-07-05T18:37:09Z)
Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文参考訳（メタデータ） (2024-05-24T11:22:19Z)
Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文参考訳（メタデータ） (2024-01-14T14:14:19Z)
Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文参考訳（メタデータ） (2023-02-27T16:34:21Z)
Fair Shares: Feasibility, Domination and Incentives [6.878547831852427]
我々は、金額の異なる商品のセット$M$を、均等に権利を付与されたエージェントに公平に割り当てるが、金銭的譲渡は行わない。付加価値については、実行可能、自己最大化、時間計算可能な共有を提示します。
論文参考訳（メタデータ） (2022-05-16T08:52:42Z)
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
論文参考訳（メタデータ） (2022-02-06T01:29:50Z)
Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-09-01T14:10:38Z)
The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文参考訳（メタデータ） (2021-04-06T20:25:57Z)
Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文参考訳（メタデータ） (2021-02-09T07:46:34Z)
Finding Fair and Efficient Allocations When Valuations Don't Add Up [25.962505544590947]
エージェント評価がマトロイドのランク関数である場合、社会的に最適な(実用的社会福祉の最大化)手法は、1つの項目(EF1)までのうらやましい自由度が存在し、計算的に抽出可能であることを示す。これは、ナッシュの福祉を最大化する割り当てがEF1であると確立された付加的評価によって仮定されない最初の評価関数クラスである。
論文参考訳（メタデータ） (2020-03-16T07:42:27Z)

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

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