論文の概要: Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations

• arxiv url: http://arxiv.org/abs/2206.08495v5
• Date: Mon, 3 Apr 2023 22:14:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-05 19:02:45.412273
• Title: Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations
• Title（参考訳）: yankee swap:matroidランクバリュエーションのための高速で簡単なフェアアロケーションメカニズム
• Authors: Vignesh Viswanathan and Yair Zick
• Abstract要約: エージェントがマトロイドランクの評価値を持つ場合、不特定商品の公平な割り当てについて検討する。 我々の主な貢献は、証明可能な公平かつ効率的なロレンツ支配割り当てを計算する単純なアルゴリズムである。
• 参考スコア（独自算出の注目度）: 16.013563937696297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study fair allocation of indivisible goods when agents have matroid rank valuations. Our main contribution is a simple algorithm based on the colloquial Yankee Swap procedure that computes provably fair and efficient Lorenz dominating allocations. While there exist polynomial time algorithms to compute such allocations, our proposed method improves on them in two ways. (a) Our approach is easy to understand and does not use complex matroid optimization algorithms as subroutines. (b) Our approach is scalable; it is provably faster than all known algorithms to compute Lorenz dominating allocations. These two properties are key to the adoption of algorithms in any real fair allocation setting; our contribution brings us one step closer to this goal.
• Abstract（参考訳）: エージェントがマトロイドランクの評価値を持つ場合、不特定商品の公平な割り当てについて検討する。 我々の主な貢献は、明快で効率的なロレンツ支配割り当てを計算する、口語的ヤンキースワップ手順に基づく単純なアルゴリズムである。 このような割り当てを計算する多項式時間アルゴリズムはあるが、提案手法は2つの方法で改善する。 (a)我々のアプローチは容易に理解でき、複雑なマトロイド最適化アルゴリズムをサブルーチンとして使用しません。 (b)我々のアプローチはスケーラブルであり、ロレンツ支配割当を計算するのに既知のアルゴリズムよりも高速である。 これらの2つの特性は、実際の公平な割り当て設定におけるアルゴリズムの採用の鍵となります。

関連論文リスト

• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Efficiently Explaining CSPs with Unsatisfiable Subset Optimization (extended algorithms and examples) [14.163888405810635]
  我々は,制約満足度問題の解法を段階的に説明する手法を最近提案した。 ここでは、コスト関数を用いて単純さを定量化する単純な推論ステップの列を説明する。
  論文  参考訳（メタデータ） (2023-03-21T10:03:36Z)
• Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy [6.170898159041277]
  本稿では,関連関数をプロキシとして利用することにより,目的物を計算困難勾配で最小化するアルゴリズムを提案する。 我々のアルゴリズムは、$delta$-smooth目的の勾配降下に一致する速度で収束を保証する。 我々のアルゴリズムは機械学習に多くの可能性があり、合成データ、物理シミュレータ、混合公開データ、プライベートデータなどを活用するための原則化された手段を提供する。
  論文  参考訳（メタデータ） (2023-02-07T15:50:49Z)
• Conjugated Discrete Distributions for Distributional Reinforcement Learning [0.0]
  最も成功した方法の1つは、非決定論的プロセスがある場合、最適なポリシーを得られないことを示します。 我々は、分散強化学習が、この状況を完全に改善するのに役立つと論じている。
  論文  参考訳（メタデータ） (2021-12-14T14:14:49Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• How to Solve Fair $k$-Center in Massive Data Models [5.3283669037198615]
  我々は、$k$-center問題に対して、新しいストリーミングおよび分散アルゴリズムを設計する。 主な貢献は、(a)最初の分散アルゴリズム、(b)証明可能な近似保証付き2パスストリーミングアルゴリズムである。
  論文  参考訳（メタデータ） (2020-02-18T16:11:40Z)

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

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