We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.

We show that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n , as it was conjectured by Noam Nisan and Amir Ronen.

Abstract. We consider mechanisms for scheduling [Formula: see text] unrelated machines when the valuations of the players (i.e., machines) are submodular. We give a lower bound of [Formula: see text] on the approximation ratio of incentive compatible deterministic mechanisms. This lower bound holds for supermodular valuations and also when all players, except for one, have additive valuations. This is an information-theoretic impossibility result on the approximation ratio of mechanisms that provides strong evidence for the Nisan–Ronen conjecture, which states that the approximation ratio is [Formula: see text] when the valuations of all machines are additive. Our approach is based on a novel multiplayer characterization of appropriately selected instances that allows us to focus on a particular type of algorithm, linear mechanisms, and it is a potential stepping stone towards the full resolution of the Nisan–Ronen conjecture.

Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. This work validates the conjecture.

The Nisan-Ronen conjecture states that no truthful mechanism for makespan-minimization when allocating$m$tasks to$n$unrelated machines can have approximation ratio less than n. Over more than two decades since its formulation, little progress has been made in resolving it and the best known lower bound is still a small constant. This work makes progress towards validating the conjecture by showing a lower bound of 1+ ✓$n$-1.

We study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is a special case of the well-studied unrelated machines scheduling problem, in which every given task can be executed only by two pre-specified machines in the case of graphs or a given subset of machines in the case of hypergraphs. This corresponds to a multigraph whose nodes are the machines and its hyperedges are the tasks. This class of problems belongs to multidimensional mechanism design, for which there are no known general mechanisms other than the VCG and its generalization to affine minimizers. We propose a new class of mechanisms that are truthful and have significantly better performance than affine minimizers in many settings. Specifically, we provide upper and lower bounds for truthful mechanisms for general multigraphs, as well as special classes of graphs such as stars, trees, planar graphs, $k$-degenerate graphs, and graphs of a given treewidth. We also consider the objective of minimizing or maximizing the $L^p$-norm of the values of the players, a generalization of the makespan minimization that corresponds to $p=\infty$, and extend the results to any $p>0$.

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 Ω(√n) on the approximation ratio of incentive compatible deterministic mechanisms. This is a strong information-theoretic impossibility result on the approximation ratio of mechanisms that provides strong evidence for the Nisan-Ronen conjecture. This is the first non-constant lower bound that assumes no restriction on the mechanism side; in contrast, all previous general results hold for only special classes of mechanisms such as local, strongly monotone, and anonymous mechanisms. Our approach is based on a novel multi-player characterization of appropriately selected instances that allows us to focus on particular type of algorithms, linear mechanisms, and it is a potential stepping stone towards the full resolution of the conjecture.

We study the following simple Bayesian auction setting: m items are sold to n selfish bidders in m independent second-price auctions. Each bidder has a private valuation function that specifies his or her complex preferences over all subsets of items. Bidders only have beliefs about the valuation functions of the other bidders, in the form of probability distributions. The objective is to allocate the items to the bidders in a way that provides a good approximation to the optimal social welfare value. We show that if bidders have submodular or, more generally, fractionally subadditive (aka XOS) valuation functions, every Bayes-Nash equilibrium of the resulting game provides a 2-approximation to the optimal social welfare. Moreover, we show that in the full-information game, a pure Nash always exists and can be found in time that is polynomial in both m and n .

Novel algorithmic ideas for big data have not been accompanied by advances in the way central memory is allocated to concurrently running programs. Commonly, RAM is poorly managed since the programs’ trade offs between speed of execution and RAM consumption are ignored. This trade off is, however, well known to the programmers. We adopt mechanism design tools to truthfully elicit this (multidimensional) information with the aim of designing more clever RAM allocation algorithms. We introduce a novel paradigm wherein programs are bound to overbidding declarations of their running times. We show the limitations of this paradigm in the absence of transfers and prove how to leverage waiting times, as a currency, to obtain optimal money burning mechanisms for the makespan. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Scheduling on related machines ($Q||C_{\max}$) 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 explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested. Recently, a breakthrough result [P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden, Proceedings of the 49th IEEE Symposium of Foundations of Computer Science, Philadelphia, 2008, pp. 15--24] showed that a randomized, truthful-in-expectation PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8 [A. Kovács, Algorithms-ESA 2005, 13th Annual European Symposium, 2005, pp. 616--627, and A. Kovács, J. Discrete Algorithms, 7 (2009), pp. 327--340]. It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. In this paper we give a definitive answer to this important question by providing a truthful deterministic PTAS.

Scheduling on related machines (Q‖Cmax) 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 can be expressed via a single parameter, her speed. Archer and Tardos [4] showed that, in contrast to other similar problems, a (non-polynomial) 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 PTAS [9, 8]. This problem is the most well-studied in single-parameter Algorithmic Mechanism Design. It gives an excellent ground to explore the boundary between truthfulness and efficient computation. Since the work of Archer and Tardos, quite a lot of deterministic and randomized mechanisms have been suggested. Recently, a breakthrough result [7] showed that a randomized, truthful-in-expectation PTAS exists. On the other hand, for the deterministic case, the best known approximation factor is 2.8 [10, 11]. It has been a major open question whether there exists a deterministic truthful PTAS, or whether truthfulness has an essential, negative impact on the computational complexity of the problem. In this paper we give a definitive answer to this important question by providing a truthful deterministic PTAS.

Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a useful tool to design deterministic and randomized approximation algorithms. The mechanism design version of the scheduling problem was introduced by Nisan and Ronen. In this article, we consider the mechanism design version of the fractional variant of this problem. We give lower bounds for any fractional truthful mechanism. Our lower bounds also hold for any (randomized) mechanism for the integral case. In the positive direction, we propose a truthful mechanism that achieves approximation 3/2 for 2 machines, matching the lower bound. This is the first new tight bound on the approximation ratio of this problem, after the tight bound of 2, for 2 machines, obtained by Nisan and Ronen. For n machines, our mechanism achieves an approximation ratio of n +1/2. Motivated by the fact that all the known deterministic and randomized mechanisms for the problem assign each task independently from the others, we focus on an interesting subclass of allocation algorithms, the task-independent algorithms. We give a lower bound of n +1/2, that holds for every (not only monotone) allocation algorithm that takes independent decisions. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms.