論文の概要: Optimal Efficiency-Envy Trade-Off via Optimal Transport

• arxiv url: http://arxiv.org/abs/2209.15416v1
• Date: Sun, 25 Sep 2022 00:39:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-09 17:20:18.337201
• Title: Optimal Efficiency-Envy Trade-Off via Optimal Transport
• Title（参考訳）: 最適輸送による最適効率・エンビートレードオフ
• Authors: Steven Yin, Christian Kroer
• Abstract要約: 本論では,各受取人に対して,各受取人に対して,各受取人に対して,各受取人に対して一定かつ所定の割合のアイテムを割り当てなければならないという問題を考察する。 この問題は半離散的最適輸送(OT)問題の変種として定式化でき、その場合の解構造は簡潔な表現と単純な幾何学的解釈を持つ。
• 参考スコア（独自算出の注目度）: 33.85971515753188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of allocating a distribution of items to $n$ recipients where each recipient has to be allocated a fixed, prespecified fraction of all items, while ensuring that each recipient does not experience too much envy. We show that this problem can be formulated as a variant of the semi-discrete optimal transport (OT) problem, whose solution structure in this case has a concise representation and a simple geometric interpretation. Unlike existing literature that treats envy-freeness as a hard constraint, our formulation allows us to \emph{optimally} trade off efficiency and envy continuously. Additionally, we study the statistical properties of the space of our OT based allocation policies by showing a polynomial bound on the number of samples needed to approximate the optimal solution from samples. Our approach is suitable for large-scale fair allocation problems such as the blood donation matching problem, and we show numerically that it performs well on a prior realistic data simulator.
• Abstract（参考訳）: 我々は,各受取人に対して,各受取人の固定的かつ事前指定された分数を割り当てなければならない場合に,各受取人に対してアイテムの分配を割り当てる問題を検討するとともに,各受取人があまり妬みを抱かないよう保証する。 この問題を半離散最適輸送問題(ot)の変種として定式化できることを示し、その解構造は簡潔な表現と単純な幾何学的解釈を持つことを示した。 エンビーフリーネスをハード制約として扱う既存の文献とは異なり、我々の定式化は効率とエンビーの連続的なトレードオフを可能にする。 さらに, 試料から最適解を近似するために必要な試料数に縛られた多項式を示すことで, OTに基づく割当ポリシの空間の統計的性質について検討する。 本手法は献血マッチング問題などの大規模フェアアロケーション問題に適しており,事前の現実的なデータシミュレータ上では良好であることが数値的に示される。

関連論文リスト

• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  本研究では, ベイズ条件付けを行い, 制約条件下でサンプルを描画する, トラクタブルな確率的手法を提案する。 提案手法はシーケンス全体を考慮し,現行のグリード法よりも大域的に最適に制約された生成を導出する。 提案手法は, 有害な世代からモデル出力を分離し, 脱毒化に対する同様のアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-17T00:49:53Z)
• Discrete Probabilistic Inference as Control in Multi-path Environments [84.67055173040107]
  本稿では,離散分布と構造化分布からサンプリングする問題を逐次決定問題として考察する。 我々は,GFlowNetが,フローの保存を強制することによって,報酬に比例してオブジェクトをサンプリングするポリシーを学習していることを示す。 また、GFlowNetの文献で見られるフローマッチングの目的が、精度の高いMaxEnt RLアルゴリズムと等価であることも証明した。
  論文  参考訳（メタデータ） (2024-02-15T20:20:35Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• New Perspectives on Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimization [8.564319625930892]
  本研究では, 有限の輸送コストで所定の基準分布による不確実な問題パラメータの分布を選択することができるような, 最適輸送に基づく分布安定度最適化問題について検討する。
  論文  参考訳（メタデータ） (2023-03-07T13:52:32Z)
• Information Theoretical Importance Sampling Clustering [18.248246885248733]
  多くのクラスタリング手法の現在の仮定は、トレーニングデータと将来のデータが同じ分布から取られるというものである。 我々は,クラスタリング問題(itisC)に対する情報理論的重要度サンプリングに基づくアプローチを提案する。 合成データセットの実験結果と実世界の負荷予測問題により,提案モデルの有効性が検証された。
  論文  参考訳（メタデータ） (2023-02-09T03:18:53Z)
• Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions [42.6763105645717]
  少数の破損したサンプルが与えられた場合、ゴールは確率の高い$mu$を正確に近似する仮説を効率的に計算することである。 本アルゴリズムは, 周辺次元と対数的にスケーリングするサンプルを多数使用して, 最適誤差を実現する。 我々の分析は、ある空間特性を満たす正の半定値に対する(非スペクトル)分解の繊細な設計を含む、独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2022-11-29T16:13:50Z)
• Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution [8.465228064780748]
  2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。 目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。 双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
  論文  参考訳（メタデータ） (2021-03-10T18:53:59Z)
• Efficient Discretizations of Optimal Transport [16.996068297291057]
  境界分布に対して与えられた点数で離散化を計算するアルゴリズムを提案する。 我々は近似の限界を証明し、幅広い問題について性能を実証する。
  論文  参考訳（メタデータ） (2021-02-16T04:31:52Z)
• Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
  我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。 複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
  論文  参考訳（メタデータ） (2020-10-21T13:43:48Z)
• Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation [120.69747175899421]
  ワッサーシュタインのような最適輸送(OT)距離は、GANやドメイン適応のようないくつかの領域で使用されている。 本稿では,現代のディープラーニングアプリケーションに適用可能な,ロバストなOT最適化の計算効率のよい2つの形式を提案する。 提案手法では, ノイズの多いデータセット上で, 外部分布で劣化したGANモデルをトレーニングすることができる。
  論文  参考訳（メタデータ） (2020-10-12T17:13:40Z)
• Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations [79.23797234241471]
  分布の区別は多くの科学分野において重要な問題である。 線形最適輸送(LOT)は分布の空間を$L2$-スペースに埋め込む。 複数の分布分類問題に対するLOTの利点を実証する。
  論文  参考訳（メタデータ） (2020-08-20T19:09:33Z)

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

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