English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study problems of scheduling jobs on related machines so as to minimizethe makespan in the setting where machines are strategic agents. In thisproblem, each job $j$ has a length $l_{j}$ and each machine $i$ has a privatespeed $t_{i}$. The running time of job $j$ on machine $i$ is $t_{i}l_{j}$. Weseek a mechanism that obtains speed bids of machines and then assign jobs andpayments to machines so that the machines have incentive to report true speedsand the allocation and payments are also envy-free. We show that  1. A deterministic envy-free, truthful, individually rational, and anonymousmechanism cannot approximate the makespan strictly better than $2-1/m$, where$m$ is the number of machines. This result contrasts with prior work giving adeterministic PTAS for envy-free anonymous assignment and a distinctdeterministic PTAS for truthful anonymous mechanism.  2. For two machines of different speeds, the unique deterministic scalableallocation of any envy-free, truthful, individually rational, and anonymousmechanism is to allocate all jobs to the quickest machine. This allocation isthe same as that of the VCG mechanism, yielding a 2-approximation to theminimum makespan.  3. No payments can make any of the prior published monotone and locallyefficient allocations that yield better than an $m$-approximation for $\qcmax$\cite{aas, at,ck10, dddr, kovacs} a truthful, envy-free, individually rational,and anonymous mechanism.

Lower Bound for Envy-Free and Truthful Makespan Approximation on Related Machines