論文の概要: On Scheduling Mechanisms Beyond the Worst Case
- arxiv url: http://arxiv.org/abs/2204.07223v1
- Date: Thu, 14 Apr 2022 20:57:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-18 12:57:04.462809
- Title: On Scheduling Mechanisms Beyond the Worst Case
- Title（参考訳）: 最悪の場合を超えたスケジューリング機構について
- Authors: Yansong Gao, JIe Zhang
- Abstract要約: 機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。
また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
- 参考スコア（独自算出の注目度）: 17.281501828240877
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of scheduling unrelated machines has been studied since the
inception of algorithmic mechanism design~\cite{NR99}. It is a resource
allocation problem that entails assigning $m$ tasks to $n$ machines for
execution. Machines are regarded as strategic agents who may lie about their
execution costs so as to minimize their allocated workload. To address the
situation when monetary payment is not an option to compensate the machines'
costs, \citeauthor{DBLP:journals/mst/Koutsoupias14} [2014] devised two
\textit{truthful} mechanisms, K and P respectively, that achieve an
approximation ratio of $\frac{n+1}{2}$ and $n$, for social cost minimization.
In addition, no truthful mechanism can achieve an approximation ratio better
than $\frac{n+1}{2}$. Hence, mechanism K is optimal. While approximation ratio
provides a strong worst-case guarantee, it also limits us to a comprehensive
understanding of mechanism performance on various inputs. This paper
investigates these two scheduling mechanisms beyond the worst case. We first
show that mechanism K achieves a smaller social cost than mechanism P on every
input. That is, mechanism K is pointwise better than mechanism P. Next, for
each task $j$, when machines' execution costs $t_i^j$ are independent and
identically drawn from a task-specific distribution $F^j(t)$, we show that the
average-case approximation ratio of mechanism K converges to a constant. This
bound is tight for mechanism K. For a better understanding of this distribution
dependent constant, on the one hand, we estimate its value by plugging in a few
common distributions; on the other, we show that this converging bound improves
a known bound \cite{DBLP:conf/aaai/Zhang18} which only captures the single-task
setting. Last, we find that the average-case approximation ratio of mechanism P
converges to the same constant.
- Abstract（参考訳）: 非関連マシンのスケジューリングの問題はアルゴリズム機構設計の開始から研究されている。
これは、実行のために$m$タスクを$n$マシンに割り当てるリソース割り当て問題である。
マシンは、割り当てられたワークロードを最小限にするために、実行コストについて嘘をつく戦略エージェントとみなされる。
機械のコストを補償するオプションではない状況に対処するため、 \citeauthor{DBLP:journals/mst/Koutsoupias14} [2014] は、社会的コスト最小化のために、それぞれ$\frac{n+1}{2}$と$n$の近似比を達成する2つの \textit{truthful} メカニズム、K と P を考案した。
さらに、真理的なメカニズムは$\frac{n+1}{2}$より近似比を達成できない。
したがって、機構kは最適である。
近似比は最悪のケースを強く保証するが、様々な入力における機構性能の包括的理解にも限界がある。
本稿では, この2つのスケジューリング機構について, 最悪の場合を超えて検討する。
まず,機構kが入力毎のメカニズムpよりも小さな社会的コストを達成することを示す。
次に、各タスク$j$に対して、マシンの実行コスト$t_i^j$がタスク固有の分散$f^j(t)$から独立かつ同一に引き出されるとき、メカニズムkの平均ケース近似比が定数に収束することを示す。
このバウンドはメカニズムkにとって厳密である。この分布依存定数をよりよく理解するために、いくつかの共通分布をプラグインすることでその値を推定する。一方、この収束バウンドは、単一のタスク設定のみをキャプチャする既知のバウンド \cite{dblp:conf/aaai/zhang18} を改善する。
最後に、メカニズムPの平均ケース近似比が同じ定数に収束していることが分かる。
関連論文リスト
- Contraction of Locally Differentially Private Mechanisms [8.547801169402923]
我々は、$PK$と$QK$の出力分布が$epsilon$-LDPメカニズムの$K$のばらつきに基づいて、厳密な境界を導出する。
次に、これらの境界を利用して、バンツリーの不等式、ル・カム、アスード、および相互情報手法の局所的プライベートバージョンを確立する。
論文 参考訳（メタデータ） (2022-10-24T16:38:12Z) - Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
プライバシランダム変数の数値合成のための新しいアルゴリズムを提案する。
本アルゴリズムは,メカニズムを自己コンパイルするタスクに対して,$mathrmpolylog(k)$の実行時間とメモリ使用量を達成する。
論文 参考訳（メタデータ） (2022-07-10T04:25:37Z) - Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the
Large-Composition Regime [12.420941209631742]
本研究では,多数の構成の限界における最適微分プライバシー機構の設計について検討する。
この体制では、最高のプライバシーメカニズムは、Kullback-Leiblerの発散を最小限にするものである。
我々は、量子化アプローチが最適なメカニズムに任意に近づくことができることを示す。
論文 参考訳（メタデータ） (2022-06-25T20:05:50Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
部分検証による自動機構設計の問題点について検討する。
私たちは、すべてのタイプが結果よりも同じ好みを共有する設定における真実のメカニズムに焦点を当てています。
論文 参考訳（メタデータ） (2021-04-12T03:29:31Z) - Towards Assessment of Randomized Smoothing Mechanisms for Certifying
Adversarial Robustness [50.96431444396752]
主な課題は、各ランダム化メカニズムの適切性を評価する方法である。
まず最初に、ガウスのメカニズムが$ell$-normを証明するための適切な選択肢であると結論付ける。
驚いたことに、ガウスのメカニズムは指数機構の代わりに$ell_infty$-normを証明するための適切な選択肢でもある。
論文 参考訳（メタデータ） (2020-05-15T03:54:53Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z) - Generalization Guarantees for Multi-item Profit Maximization: Pricing,
Auctions, and Randomized Mechanisms [86.81403511861788]
購入者の価値に根ざした分布が存在する場合のマルチイテム利益について検討する。
購入者の値の任意のセットに対して、利益はメカニズムのパラメーターにおいて断片的に線形である。
我々は、まだサンプルベースのメカニズム設計文献にはないメカニズムクラスに対する新しい境界を証明した。
論文 参考訳（メタデータ） (2017-04-29T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。