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.
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 ).
@cite_24 @cite_0 @cite_10
2141663593 2068852191 2057087699 2126170153
We consider the problem of makespan minimization on m unrelated machines in the context of algorithmic mechanism design, where the machines are the strategic players. This is a multidimensional scheduling domain, and the only known positive results for makespan minimization in such a domain are O(m)-approximation truthful mechanisms [22, 20]. We study a well-motivated special case of this problem, where the processing time of a job on each machine may either be "low" or "high", and the low and high values are public and job-dependent. This preserves the multidimensionality of the domain, and generalizes the restricted-machines (i.e., pj,∞ ) setting in scheduling. We give a general technique to convert any c-approximation algorithm to a 3c-approximation truthful-in-expectation mechanism. This is one of the few known results that shows how to export approximation algorithms for a multidimensional problem into truthful mechanisms in a black-box fashion. When the low and high values are the same for all jobs, we devise a deterministic 2-approximation truthful mechanism. These are the first truthful mechanisms with non-trivial performance guarantees for a multidimensional scheduling domain. Our constructions are novel in two respects. First, we do not utilize or rely on explicit price definitions to prove truthfulness; instead we design algorithms that satisfy cycle monotonicity. Cycle monotonicity [23] is a necessary and sufficient condition for truthfulness, is a generalization of value monotonicity for multidimensional domains. However, whereas value monotonicity has been used extensively and successfully to design truthful mechanisms in single-dimensional domains, ours is the first work that leverages cycle monotonicity in the multidimensional setting. Second, our randomized mechanisms are obtained by first constructing a fractional truthful mechanism for a fractional relaxation of the problem, and then converting it into a truthful-in-expectation mechanism. This builds upon a technique of [16], and shows the usefulness of fractional mechanisms in truthful mechanism design. We consider the makespan-minimization problem on unrelated machines in the context of algorithmic mechanism design. No truthful mechanisms with non-trivial approximation guarantees are known for this multidimensional domain. We study a well-motivated special case (also a multidimensional domain), where the processing time of a job on each machine is either "low" or "high." We give a general technique to convert any c-approximation algorithm (in a black-box fashion) to a 3c-approximation truthful-in-expectation mechanism. Our construction uses fractional truthful mechanisms as a building block, and builds upon a technique of Lavi and Swamy [Lavi, R., Swamy, C., 2005. Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th FOCS, pp. 595-604]. When all jobs have identical low and high values, we devise a deterministic 2-approximation truthful mechanism. The chief novelty of our results is that we do not utilize explicit price definitions to prove truthfulness. Instead we design algorithms that satisfy cycle monotonicity [Rochet, J., 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. J. Math. Econ. 16, 191-200], a necessary and sufficient condition for truthfulness in multidimensional settings; this is the first work that leverages this characterization. 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. 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.