論文の概要: Time Fairness in Online Knapsack Problems

• arxiv url: http://arxiv.org/abs/2305.13293v1
• Date: Mon, 22 May 2023 17:51:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-23 13:41:23.458637
• Title: Time Fairness in Online Knapsack Problems
• Title（参考訳）: オンラインクナップサック問題における時間公平性
• Authors: Adam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali, Mohammad Hajiesmaili
• Abstract要約: オンラインのknapsack問題は、異なる値と重みのアイテムを、容量限定のknapsackにどのようにパックするかを問う。 我々は,オンラインのknapsack問題に対して,自然かつ実用的な時間フェアネスの概念を開発し,既存の最適アルゴリズムが,この基準の下では不十分であることを示す。 ランダム化は理論上は競争力と公正性を兼ね備えるほど強力であることを示すが、実際にはトレース駆動実験を用いてうまく動作しない。
• 参考スコア（独自算出の注目度）: 4.843670630080049
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The online knapsack problem is a classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriving online into a capacity-limited knapsack so as to maximize the total value of the admitted items. Although optimal competitive algorithms are known for this problem, they may be fundamentally unfair, i.e., individual items may be treated inequitably in different ways. Inspired by recent attention to fairness in online settings, we develop a natural and practically-relevant notion of time fairness for the online knapsack problem, and show that the existing optimal algorithms perform poorly under this metric. We propose a parameterized deterministic algorithm where the parameter precisely captures the Pareto-optimal trade-off between fairness and competitiveness. We show that randomization is theoretically powerful enough to be simultaneously competitive and fair; however, it does not work well in practice, using trace-driven experiments. To further improve the trade-off between fairness and competitiveness, we develop a fair, robust (competitive), and consistent learning-augmented algorithm with substantial performance improvement in trace-driven experiments.
• Abstract（参考訳）: オンラインknapsack問題は、オンラインアルゴリズムの分野で古典的な問題である。 その標準的なバージョンでは、オンラインに届くさまざまな値と重みのアイテムを容量制限されたナップサックに詰め込む方法が求められている。 最適競合アルゴリズムはこの問題で知られているが、それらは基本的に不公平である可能性があり、例えば個々のアイテムは異なる方法で不当に扱われることがある。 近年,オンライン環境での公平さに着想を得て,オンライン・クナップサック問題に対する時間公平性の概念を自然かつ実践的に発展させ,既存の最適アルゴリズムがこの基準の下では不十分であることを示す。 本稿では,パラメータが公正性と競争性の間のパレート最適トレードオフを正確に捉えるパラメータ化決定性アルゴリズムを提案する。 ランダム化は理論上は競争力と公正性を兼ね備えるほど強力であることを示すが、実際にはトレース駆動実験を用いてうまく動作しない。 公平性と競争力のトレードオフをさらに改善するため,トレース駆動実験において相当な性能向上を実現した,公平で堅牢(競争的)かつ一貫性のある学習型アルゴリズムを開発した。

関連論文リスト

• Nonstationary Dual Averaging and Online Fair Allocation [32.85609942201268]
  非定常入力モデルに基づく二値平均化アルゴリズムの新しいオンライン学習結果を開発した。 本研究は,非定常入力モデルとして,敵対的汚職,エルゴディック入力,ブロック非依存入力(周期的入力を含む)の2つに適用した。
  論文  参考訳（メタデータ） (2022-02-23T16:50:24Z)
• Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
  この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。 通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。 我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
  論文  参考訳（メタデータ） (2022-02-06T13:14:02Z)
• Fairer LP-based Online Allocation [13.478067250930101]
  本稿では,リニアプログラム(LP)に基づくオンラインリソース割り当て問題について考察する。 内部点LPソルバを用いて不公平な資源支出を動的に検出するフェアアルゴリズムを提案する。 提案手法は最適化インスタンスの制約としてフェアネス要件を定式化せず,アルゴリズム設計の観点からこの問題に対処する。
  論文  参考訳（メタデータ） (2021-10-27T17:45:20Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
  論文  参考訳（メタデータ） (2021-08-19T17:59:28Z)
• Can Active Learning Preemptively Mitigate Fairness Issues? [66.84854430781097]
  データセットバイアスは、機械学習における不公平な原因の1つです。 不確実性に基づくALで訓練されたモデルが保護クラスの決定において公平であるかどうかを検討する。 また,勾配反転(GRAD)やBALDなどのアルゴリズム的公正性手法の相互作用についても検討する。
  論文  参考訳（メタデータ） (2021-04-14T14:20:22Z)
• Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
  社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で最適化される。 最近の訴訟は、アルゴリズムによる価格設定の慣行を展開している企業を非難している。 凸最適化の文脈において、遠心自由というよく研究された公正性の概念を導入する。
  論文  参考訳（メタデータ） (2021-03-16T19:06:28Z)
• Cost-Efficient Online Hyperparameter Optimization [94.60924644778558]
  実験の単一実行でヒトのエキスパートレベルのパフォーマンスに達するオンラインHPOアルゴリズムを提案します。 提案するオンラインhpoアルゴリズムは,実験の1回で人間のエキスパートレベルのパフォーマンスに到達できるが,通常のトレーニングに比べて計算オーバーヘッドは少ない。
  論文  参考訳（メタデータ） (2021-01-17T04:55:30Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)
• Metrics and methods for a systematic comparison of fairness-aware machine learning algorithms [0.0]
  この研究はこの種の最も包括的なものである。 フェアネス、予測性能、キャリブレーション品質、28種類のモデリングパイプラインの速度を考慮に入れている。 また,フェアネスを意識したアルゴリズムは,予測力の低下を伴わずにフェアネスを誘導できることがわかった。
  論文  参考訳（メタデータ） (2020-10-08T13:58:09Z)
• Beyond Individual and Group Fairness [90.4666341812857]
  本稿では,不公平な不公平な苦情に導かれる公平さの新しいデータ駆動モデルを提案する。 我々のモデルは、複数のフェアネス基準をサポートし、それらの潜在的な不整合を考慮に入れている。
  論文  参考訳（メタデータ） (2020-08-21T14:14:44Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。 この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。 目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
  論文  参考訳（メタデータ） (2020-07-01T14:24:58Z)

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

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