論文の概要: Dividing Good and Better Items Among Agents with Bivalued Submodular
Valuations
- arxiv url: http://arxiv.org/abs/2302.03087v3
- Date: Wed, 19 Jul 2023 21:50:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-21 18:26:39.951903
- Title: Dividing Good and Better Items Among Agents with Bivalued Submodular
Valuations
- Title（参考訳）: 2値サブモジュラー・バリュエーションを持つエージェント間で良い項目と良い項目を分ける
- Authors: Cyrus Cousins, Vignesh Viswanathan and Yair Zick
- Abstract要約: 本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。
我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
- 参考スコア（独自算出の注目度）: 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 {\em 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 max Nash welfare (MNW), leximin and $p$-mean welfare
maximizing allocations when $a$ divides $b$. This result is complemented by an
existing result on the computational intractability of MNW and leximin
allocations when $a$ does not divide $b$. We show that MNW and leximin
allocations guarantee each agent at least $\frac25$ and $\frac{a}{b+2a}$ of
their maximin share, respectively, when $a$ divides $b$. We also 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).
- Abstract（参考訳）: 各商品は、a$または$b$(a < b$)の限界利得を提供し、商品は、限界利得を減少させている。
これは2つのよく研究された評価クラスの自然な一般化であり、二値加法評価と二値部分モジュラー評価である。
本稿では,最近導入されたYankee Swap機構に基づいて,最大ナッシュ福祉(MNW)やレキシミン,および$p$平均福祉など,様々なソリューション概念を計算できる簡単な逐次アルゴリズムフレームワークを提案する。
この結果は、$a$ が$b$ を割らない場合に mnw と leximin の割り当ての計算不能性に関する既存の結果によって補完される。
MNWとレキシミンの割り当ては、$a$が$b$を割り切るとき、各エージェントがそれぞれ$\frac25$と$\frac{a}{b+2a}$の最大シェアを保証することを示す。
また、レキシミンとMNWの割り当てが1つの善(EF1)まで自由にできる保証はないことを示した。
二値加法評価と二値部分モジュラー評価のより単純なクラスでは、MNWアロケーションはどんな良いもの(EFX)にもうらやましいことが知られているので、これは驚くべきことである。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。