  We consider incentive compatible mechanisms for a domain that is very close
to the domain of scheduling $n$ unrelated machines: the single exception is
that the valuation of just one machine is submodular. For the scheduling
problem with such cost functions, we give a lower bound of $\Omega(\sqrt{n})$
on the approximation ratio of incentive compatible deterministic mechanisms.
This is a strong information-theoretic impossibility result on the
approximation ratio of mechanisms on relatively simple domains. The lower bound
of the current work assumes no restriction on the mechanism side, but an
expanded class of valuations, in contrast to previous general results on the
Nisan-Ronen conjecture that hold for only special classes of mechanisms such as
local, strongly monotone, and anonymous mechanisms. Our approach is based on a
novel characterization of appropriately selected smaller instances that allows
us to focus on particular type of algorithms (linear mechanisms), from which we
extract a locality property that gives the lower bound.
