On Scheduling Mechanisms Beyond the Worst Case

• URL: http://arxiv.org/abs/2204.07223v1
• Date: Thu, 14 Apr 2022 20:57:50 GMT
• Title: On Scheduling Mechanisms Beyond the Worst Case
• Authors: Yansong Gao, JIe Zhang
• Abstract summary: We find that mechanism K achieves a smaller social cost than mechanism P on every input. We also find that the average-case approximation ratio of mechanism P converges to the same constant.
• Score: 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.

Related papers

• Contraction of Locally Differentially Private Mechanisms [8.547801169402923]
  We derive tight bounds on the divergence between $PK$ and $QK$ output distributions of an $epsilon$-LDP mechanism $K$. We then utilize these bounds to establish locally private versions of the van Trees inequality, Le Cam's, Assouad's, and the mutual information methods.
  arXiv  Detail & Related papers  (2022-10-24T16:38:12Z)
• Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
  We introduce a new algorithm for numerical composition of privacy random variables. Our algorithm achieves a running time and memory usage of $mathrmpolylog(k)$ for the task of self-composing a mechanism.
  arXiv  Detail & Related papers  (2022-07-10T04:25:37Z)
• Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime [12.420941209631742]
  We study the design of optimal differential privacy mechanisms in the limit of a large number of compositions. In this regime the best privacy mechanism is the one that minimizes the Kullback-Leibler divergence. We show that our quantization approach can be arbitrarily close to an optimal mechanism.
  arXiv  Detail & Related papers  (2022-06-25T20:05:50Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
  We study the problem of automated mechanism design with partial verification. We focus on truthful mechanisms in the setting where all types share the same preference over outcomes.
  arXiv  Detail & Related papers  (2021-04-12T03:29:31Z)
• Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness [50.96431444396752]
  We argue that the main difficulty is how to assess the appropriateness of each randomized mechanism. We first conclude that the Gaussian mechanism is indeed an appropriate option to certify $ell$-norm. Surprisingly, we show that the Gaussian mechanism is also an appropriate option for certifying $ell_infty$-norm, instead of the Exponential mechanism.
  arXiv  Detail & Related papers  (2020-05-15T03:54:53Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms [86.81403511861788]
  We study multi-item profit when there is an underlying distribution over buyers' values. For any set of buyers' values, profit is piecewise linear in the mechanism's parameters. We prove new bounds for mechanism classes not yet in the sample-based mechanism design literature.
  arXiv  Detail & Related papers  (2017-04-29T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.