We consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling @math 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 @math 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.
@cite_14: This work gives the first natural non-utilitarian problems for which the trivial napproxima-tion via VCG mechanisms is the best possible. That is, no truthful mechanism can be better than n approximate, where n is the number of agents. The problems we study are the min-max variant of the shortest path and the (directed) minimum spanning tree mechanism design problems. In these procurement auctions, agents own the edges of a network, and the corresponding edge costs are private. Instead of the total weight of the subnetwork, in the min-max variant we aim to minimize the maximum agent cost.
@cite_33: We study the problem of scheduling m tasks to n selfish, unrelated machines in order to minimize the makespan, in which the execution times are independent random variables, identical across machines. We show that the VCG mechanism, which myopically allocates each task to its best machine, achieves an approximation ratio of O(ln nf ln ln n). This improves significantly on the previously best known bound of O(m n) for prior-independent mechanisms, given by [7] under the additional assumption of Monotone Hazard Rate (MHR) distributions. Although we demonstrate that this is tight in general, if we do maintain the MHR assumption, then we get improved, (small) constant bounds for m ≥ n ln n i.i.d. tasks. We also identify a sufficient condition on the distribution that yields a constant approximation ratio regardless of the number of tasks.
@cite_8: This paper presents inapproximability results for paradigmatic multi-dimensional truthful mechanism design problems.
@cite_6: We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTASs) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the p-norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. Our results imply the existence of a truthful mechanism that can be implemented in polynomial time, where the social goal is approximated within arbitrary precision.
@cite_19: We provide polynomial-time approximately optimal Bayesian mechanisms for makespan minimization on unrelated machines as well as for max-min fair allocations of indivisible goods, with approximation factors of 2 and min m−k+1, O([EQUATION]k) respectively matching the approximation ratios of best known polynomial-time algorithms (for max-min fairness, the latter claim is true for certain ratios of the number of goods m to people k). Our mechanisms are obtained by establishing a polynomial-time approximation-sensitive reduction from the problem of designing approximately optimal mechanisms for some arbitrary objective O to that of designing bi-criterion approximation algorithms for the same objective O plus a linear allocation cost term. Our reduction is itself enabled by extending the celebrated "equivalence of separation and optimization" [27, 32] to also accommodate bi-criterion approximations. Moreover, to apply the reduction to the specific problems of makespan and max-min fairness we develop polynomial-time bi-criterion approximation algorithms for makespan minimization with costs and max-min fairness with costs, adapting the algorithms of [45], [10] and [4] to the type of bi-criterion approximation that is required by the reduction.
@cite_15: 
The truthful implementation of other objectives have been explored by Mu'alem and Schapi -ra @cite_8 for multi-dimensional problems and by Epstein and van Stee @cite_6 for single-dimensional ones, giving a PTAS for a wide range of objective functions. Leucci, Mamageishvili and Penna @cite_14 showed high lower bounds for other min-max objectives on some combinatorial optimization problems. In the Bayesian setting, Daskalakis and Weinberg @cite_19 showed a mechanism that is at most a factor of 2 from the optimal truthful mechanism , but not with respect to optimal makespan. @cite_15 provided bounds of prior-independent mechanisms (where the input comes from a probability unknown to the mechanism). Giannakopoulos and Kyropoulou @cite_33 showed that the VCG mechanism achieves an approximation ratio of @math under some distributional and symmetry assumptions.