  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 +\sqrt 2 \approx 2.41$ by
Christodoulou, Kotsoupias, and Vidali, and then to $1+\phi\approx 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-\delta$, for every constant $\delta>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+\sqrt{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+\sqrt 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.
