2020/07/08 by Shahar Dobzinski, Dobzinski, Shahar, Ariel Shaulker +1
Computer Science · Decision Sciences · Engineering · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2007.04362
openalex publication_date 2020/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of scheduling unrelated machines by a truthful mechanism to minimize the makespan was introduced in the seminal "Algorithmic Mechanism Design" paper by Nisan and Ronen. Nisan and Ronen showed that there is a truthful mechanism that provides an approximation ratio of min(m,n), where n is the number of machines and m is the number of jobs. They also proved that no truthful mechanism can provide an approximation ratio better than 2. Since then, the lower bound was improved to 1 +√ 2 ≈ 2.41 by Christodoulou, Kotsoupias, and Vidali, and then to 1+ϕ≈ 2.618 by Kotsoupias and Vidali. Very recently, the lower bound was improved to 2.755 by Giannakopoulos, Hammerl, and Pocas. In this paper we further improve the bound to 3-δ, for every constant δ>0. Note that a gap between the upper bound and the lower bounds exists even when the number of machines and jobs is very small. In particular, the known 1+√(2) lower bound requires at least 3 machines and 5 jobs. In contrast, we show a lower bound of 2.2055 that uses only 3 machines and 3 jobs and a lower bound of 1+√ 2 that uses only 3 machines and 4 jobs. For the case of two machines and two jobs we show a lower bound of 2. Similar bounds for two machines and two jobs were known before but only via complex proofs that characterized all truthful mechanisms that provide a finite approximation ratio in this setting, whereas our new proof uses a simple and direct approach.