論文の概要: Fair Shares: Feasibility, Domination and Incentives
- arxiv url: http://arxiv.org/abs/2205.07519v1
- Date: Mon, 16 May 2022 08:52:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 22:16:07.888553
- Title: Fair Shares: Feasibility, Domination and Incentives
- Title（参考訳）: フェアシェア:可能性、支配、インセンティブ
- Authors: Moshe Babaioff and Uriel Feige
- Abstract要約: 我々は、金額の異なる商品のセット$M$を、均等に権利を付与されたエージェントに公平に割り当てるが、金銭的譲渡は行わない。
付加価値については、実行可能、自己最大化、時間計算可能な共有を提示します。
- 参考スコア（独自算出の注目度）: 6.878547831852427
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider fair allocation of a set $M$ of indivisible goods to $n$
equally-entitled agents, with no monetary transfers. Every agent $i$ has a
valuation $v_i$ from some given class of valuation functions. A share $s$ is a
function that maps a pair $(v_i,n)$ to a value, with the interpretation that if
an allocation of $M$ to $n$ agents fails to give agent $i$ a bundle of value at
least equal to $s(v_i,n)$, this serves as evidence that the allocation is not
fair towards $i$. For such an interpretation to make sense, we would like the
share to be feasible, meaning that for any valuations in the class, there is an
allocation that gives every agent at least her share. The maximin share was a
natural candidate for a feasible share for additive valuations. However,
Kurokawa, Procaccia and Wang [2018] show that it is not feasible.
We initiate a systematic study of the family of feasible shares. We say that
a share is \emph{self maximizing} if truth-telling maximizes the implied
guarantee. We show that every feasible share is dominated by some
self-maximizing and feasible share. We seek to identify those self-maximizing
feasible shares that are polynomial time computable, and offer the highest
share values. We show that a SM-dominating feasible share -- one that dominates
every self-maximizing (SM) feasible share -- does not exist for additive
valuations (and beyond). Consequently, we relax the domination property to that
of domination up to a multiplicative factor of $\rho$ (called
$\rho$-dominating). For additive valuations we present shares that are
feasible, self-maximizing and polynomial-time computable. For $n$ agents we
present such a share that is $\frac{2n}{3n-1}$-dominating. For two agents we
present such a share that is $(1 - \epsilon)$-dominating. Moreover, for these
shares we present poly-time algorithms that compute allocations that give every
agent at least her share.
- Abstract（参考訳）: 我々は、金額の異なる商品のセット$M$を、均等に権利を付与されたエージェントに公平に割り当てるが、金銭的譲渡は行わない。
すべてのエージェント$i$は、特定のクラスの評価関数から$v_i$を持つ。
Share $s$ は、ペア $(v_i,n)$ を値にマッピングする関数であり、$M$ から $n$ エージェントへの割り当てがエージェント $i$ を少なくとも $s(v_i,n)$ に等しい値の束を与えるのに失敗すると、これは$i$ が$i$ に対して公平でないことを示す証拠となる。
そのような解釈が理にかなうためには、共有が実現可能でありたい。つまり、クラスのどの評価においても、すべてのエージェントに少なくとも彼女の共有を与えるアロケーションがある。
マクシミンのシェアは、付加価値に対する実現可能なシェアの自然な候補であった。
しかし, 黒川, Procaccia, Wang [2018] は実現不可能であることを示している。
実現可能な共有の家族の体系的な研究を開始する。
真理測定が暗黙の保証を最大化するなら、シェアは \emph{self maximizing} であると言う。
すべての実現可能な共有は、自己の最大化と実現可能な共有によって支配されていることを示している。
我々は,多項式時間計算可能な自己最大化可能な共有株を特定し,最も高い共有価値を提供する。
すべての自己最大化(SM)可能なシェアを支配しているSM支配可能なシェアは、追加的な評価(およびそれ以上)には存在しないことを示す。
その結果、支配性は支配性に緩和され、乗算係数は$\rho$($\rho$-dominatingと呼ばれる)となる。
付加的評価については、実行可能、自己最大化、多項式時間計算が可能な共有を示す。
n$エージェントに対しては、$\frac{2n}{3n-1}$-dominatingというシェアを提示します。
2つのエージェントに対して、そのようなシェアは(1- \epsilon)$-dominateである。
さらに、これらの共有のために、各エージェントに少なくともシェアを与える割り当てを計算する多時間アルゴリズムを提案する。
関連論文リスト
- 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) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Dividing Good and Better Items Among Agents with Bivalued Submodular
Valuations [20.774185319381985]
本稿では,2値のサブモジュラー評価を持つエージェント間で,分割不可能な商品の集合を適切に割り当てる問題について検討する。
我々は、レキシミンとMNWの割り当てが1つの利益まで自由になされることは保証されていないことを示す。
論文 参考訳（メタデータ） (2023-02-06T19:41:28Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
論文 参考訳（メタデータ） (2022-05-12T19:46:35Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - (Almost) Envy-Free, Proportional and Efficient Allocations of an
Indivisible Mixed Manna [10.933894827834825]
エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。
公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
論文 参考訳（メタデータ） (2022-02-06T01:29:50Z) - Coordinated Attacks against Contextual Bandits: Fundamental Limits and
Defense Mechanisms [75.17357040707347]
オンラインレコメンデーションシステムによってモチベーションされた我々は,文脈的包帯における最適政策の発見問題を提案する。
目標は、優れたユーザに対する報酬を可能な限り少ないユーザインタラクションで最大化するポリシーを、しっかりと学習することだ。
効率的なロバストな平均推定器を用いることで、$tildeO(min(S,A)cdot alpha/epsilon2)$ upper-boundを実現できることを示す。
論文 参考訳（メタデータ） (2022-01-30T01:45:13Z) - 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) - Finite Continuum-Armed Bandits [0.0]
エージェントが$T$Ressourcesを持ち、より多くのアクションに割り当てる状況を考える。
エージェントの目標は、彼女の累積報酬を最大化することです。
論文 参考訳（メタデータ） (2020-10-23T08:48:45Z) - A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。
このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-06-29T03:03:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。