論文の概要: Fair Algorithm Design: Fair and Efficacious Machine Scheduling
- arxiv url: http://arxiv.org/abs/2204.06438v2
- Date: Sun, 9 Jul 2023 16:16:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-13 20:47:25.152619
- Title: Fair Algorithm Design: Fair and Efficacious Machine Scheduling
- Title（参考訳）: 公正なアルゴリズム設計:公正で効率的なマシンスケジューリング
- Authors: April Niu, Agnes Totschnig, Adrian Vetta
- Abstract要約: 公正なアルゴリズムは低い社会福祉ソリューションをもたらすが、福祉最適化アルゴリズムは非常に不公平である。
本稿では,この二分法が,無視できる量のバイアスを許容すれば克服できることを実証する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by a plethora of practical examples where bias is induced by
automated-decision making algorithms, there has been strong recent interest in
the design of fair algorithms. However, there is often a dichotomy between
fairness and efficacy: fair algorithms may proffer low social welfare solutions
whereas welfare optimizing algorithms may be very unfair. This issue is
exemplified in the machine scheduling problem where, for $n$ jobs, the social
welfare of any fair solution may be a factor $\Omega(n)$ worse than the optimal
welfare. In this paper, we prove that this dichotomy between fairness and
efficacy can be overcome if we allow for a negligible amount of bias: there
exist algorithms that are both "almost perfectly fair" and have a constant
factor efficacy ratio, that is, are guaranteed to output solutions that have
social welfare within a constant factor of optimal welfare. Specifically, for
any $\epsilon>0$, there exist mechanisms with efficacy ratio
$\Theta(\frac{1}{\epsilon})$ and where no agent is more than an $\epsilon$
fraction worse off than they are in the fairest possible solution (given by an
algorithm that does not use personal or type data). Moreover, these bicriteria
guarantees are tight and apply to both the single machine case and the multiple
machine case. The key to our results are the use of Pareto scheduling
mechanisms. These mechanisms, by the judicious use of personal or type data,
are able to exploit Pareto improvements that benefit every individual; such
Pareto improvements would typically be forbidden by fair scheduling algorithms
designed to satisfy standard statistical measures of group fairness. We
anticipate this paradigm, the judicious use of personal data by a fair
algorithm to greatly improve performance at the cost of negligible bias, has
wider application.
- Abstract（参考訳）: 自動決定アルゴリズムによってバイアスが誘導される多くの実践例に動機付けられ、近年、公正アルゴリズムの設計に強い関心が寄せられている。
しかし、公正性と有効性の間には二分されることが多く、公正なアルゴリズムは低い社会福祉の解決をもたらすが、福祉最適化アルゴリズムは非常に不公平である。
この問題は、機械スケジューリング問題において例示されており、$n$ジョブの場合、公正なソリューションの社会的福祉は、最適な福祉よりも悪い$\Omega(n)$ファクタである可能性がある。
本稿では, 公平性と有効性の二分法が, 「ほぼ完全に公平」であり, 一定の因子有効率を持つアルゴリズムが存在すること, すなわち, 社会福祉を最適福祉の一定の要因内に持つ解を出力することが保証されていることを証明した。
具体的には、$\epsilon>0$に対して、有効率$\Theta(\frac{1}{\epsilon})$のメカニズムが存在し、最も公平なソリューション(個人データや型データを使用しないアルゴリズムによって)に比較して$\epsilon$分の1以上のエージェントは存在しない。
さらに、これらのbicriteriaの保証は厳密であり、単一マシンケースと複数マシンケースの両方に適用できる。
私たちの結果の鍵は、Paretoスケジューリングメカニズムの使用です。
これらのメカニズムは、個人またはタイプデータの司法的利用によって、個々の個人に利益をもたらすパレートの改善を利用することができる。
このパラダイムは、偏見を無視するコストで性能を大幅に向上させる公平なアルゴリズムによる個人データの司法的利用であり、幅広い応用が期待できる。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳（メタデータ） (2023-08-17T08:34:58Z) - Designing Equitable Algorithms [1.9006392177894293]
現在、予測アルゴリズムは、我々の社会の資源と制裁の大部分を分配するのに使われています。
これらのアルゴリズムは意思決定の効率と公平性を改善することができる。
しかし、彼らは特に人種、民族、性別のラインで格差を拡大し、悪化させる可能性がある。
論文 参考訳（メタデータ） (2023-02-17T22:00:44Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - FAIRLEARN:Configurable and Interpretable Algorithmic Fairness [1.2183405753834557]
トレーニングサンプルから生じるバイアスや、データサンプルに関する暗黙の仮定を緩和する必要がある。
最適化の異なる段階でバイアスを検出し緩和することで、学習アルゴリズムを公平にするために多くのアプローチが提案されている。
本稿では,ユーザの制約を最適化手順に組み込むことで,公平なアルゴリズムを生成するFAIRLEARN手順を提案する。
論文 参考訳（メタデータ） (2021-11-17T03:07:18Z) - Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds
Global Optima [114.31577038081026]
本稿では,デザイナーとエージェントの問題を同時に1ループで解くための効率的な手法を提案する。
設計者は平衡問題を何度も解決しないが、エージェントに対するインセンティブの全体的な影響を予測できる。
このアルゴリズムは,幅広い種類のゲームに対して,サブ線形速度で大域的最適値に収束することを示す。
論文 参考訳（メタデータ） (2021-10-04T06:53:59Z) - An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning [5.634825161148484]
私たちはマルファールを定義し、(幸福ではなく)社会全体の危害を測定する
そこで本稿では,計算および統計的学習の課題について検討する。
適切な修正を加えて、多くの標準的なPAC学習者がフェアPAC学習者に変換できる幅広い条件を示す。
論文 参考訳（メタデータ） (2021-04-29T17:18:17Z) - Individually Fair Gradient Boosting [86.1984206610373]
我々は、グラデーションブーストにおいて個人の公平性を強制するタスクを検討する。
アルゴリズムがグローバルに収束し、一般化することを示す。
また,アルゴリズムバイアスの影響を受けやすい3つのml問題に対するアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2021-03-31T03:06:57Z) - Metrics and methods for a systematic comparison of fairness-aware
machine learning algorithms [0.0]
この研究はこの種の最も包括的なものである。
フェアネス、予測性能、キャリブレーション品質、28種類のモデリングパイプラインの速度を考慮に入れている。
また,フェアネスを意識したアルゴリズムは,予測力の低下を伴わずにフェアネスを誘導できることがわかった。
論文 参考訳（メタデータ） (2020-10-08T13:58:09Z) - The Fairness-Accuracy Pareto Front [19.556904444436523]
アルゴリズムフェアネスは、機械学習アルゴリズムのバイアス源を特定し、修正しようとする。
アルゴリズムの公正性において、この基本的な緊張を和らげるための公式なツールを提供する。
論文 参考訳（メタデータ） (2020-08-25T03:32:15Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。