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_24: We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines ( @math ), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomial-time, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming @math ). Our algorithmic techniques are flexible and also yield a monotone deterministic quasi-PTAS for @math and a monotone randomized PTAS for max-min scheduling on related machines.
@cite_0: Scheduling on related machines ( @math ) is one of the most important problems in the field of algorithmic mechanism design. Each machine is controlled by a selfish agent and her valuation function can be expressed via a single parameter, her speed. Archer and Tardos [Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, 2001, pp. 482--491] showed that, in contrast to other similar problems, a (nonpolynomial) allocation that minimizes the makespan can be truthfully implemented. On the other hand, if we leave out the game-theoretic issues, the complexity of the problem has been completely settled---the problem is strongly NP-hard, while there exists a polynomial-time approximation scheme (PTAS) [D. S. Hochbaum and D. B. Shmoys, SIAM J. Comput., 17 (1988), pp. 539--551, and L. Epstein and J. Sgall, Algorithmica, 39(1) (2004), pp. 43--57]. This problem is the most well studied in single-parameter algorithmic mechanism design. It gives an excellent ground to ...
@cite_10: The authors show how to design truthful (dominant strategy) mechanisms for several combinatorial problems where each agent's secret data is naturally expressed by a single positive real number. The goal of the mechanisms we consider is to allocate loads placed on the agents, and an agent's secret data is the cost she incurs per unit load. We give an exact characterization for the algorithms that can be used to design truthful mechanisms for such load balancing problems using appropriate side payments. We use our characterization to design polynomial time truthful mechanisms for several problems in combinatorial optimization to which the celebrated VCG mechanism does not apply. For scheduling related parallel machines (Q spl par C sub max ), we give a 3-approximation mechanism based on randomized rounding of the optimal fractional solution. This problem is NP-complete, and the standard approximation algorithms (greedy load-balancing or the PTAS) cannot be used in truthful mechanisms. We show our mechanism to be frugal, in that the total payment needed is only a logarithmic factor more than the actual costs incurred by the machines, unless one machine dominates the total processing power. We also give truthful mechanisms for maximum flow, Q spl par spl Sigma C sub j (scheduling related machines to minimize the sum of completion times), optimizing an affine function over a fixed set, and special cases of uncapacitated facility location. In addition, for Q spl par spl Sigma w sub j C sub j (minimizing the weighted sum of completion times), we prove a lower bound of 2 spl radic 3 for the best approximation ratio achievable by truthful mechanism.
An interesting special case, which is well-understood, is the single-dimensional mechanism design in which the values of the vector are linear expressions of a single parameter. The principal representative is the problem of scheduling related machines, where the cost of each machine can be expressed via a single parameter, its speed . This was first studied by Archer and Tardos @cite_10 who showed that, in contrast to the unrelated machines version, an algorithm that minimizes the makespan can be truthfully implemented --- albeit in exponential time. It was subsequently shown that truthfulness has essentially no impact on the computational complexity of the problem. Specifically, a randomized truthful-in-expectation This is one of the two main definitions of truthfulness for randomized mechanisms, where truth-telling maximizes the expected utility of each player. PTAS was given in @cite_24 and a deterministic PTAS was given in @cite_0 ; a PTAS is the best possible algorithm even for the pure algorithmic problem (unless @math ).