Academic
Publications
Truthful Mechanisms for One-Parameter Agents

Truthful Mechanisms for One-Parameter Agents,10.1109/SFCS.2001.959924,Aaron Archer,Éva Tardos

Truthful Mechanisms for One-Parameter Agents   (Citations: 224)
BibTex | RIS | RefWorks Download
In this paper, we 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 combinato- rial optimization to which the celebrated VCG mechanism does not apply. For scheduling related parallel machines ( ), we give a 3-approximation mechanism based on randomized rounding of the optimal fractional solution. This problem is NP-complete, and the standard approxima- tion algorithms (greedy load-balancing or the PTAS) can- not be used in truthful mechanisms. We show our mecha- nism 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, (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 (minimizing the weighted sum of completion times), we prove a lower bound of for the best approximation ratio achievable by a truthful mechanism.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...We refer the reader to the work by Archer and Tardos [22] for a concise treatment of Myerson’s principle of truthfulness in one-dimensional settings...

    Ajay Gopinathanet al. Strategyproof auctions for balancing social welfare and fairness in se...

    • ...Related formulations to the one given here have appeared in numerous places in recent literature (e.g., [1, 13, 6, 10])...

    Gagan Aggarwalet al. Derandomization of auctions

    • ...If ωi(ˆ vi, ˆ−i) is monotonically non-decreasing in ˆ vi and v 0 is the valuation under which i cannot win, the truthfulness condition for a normalized mechanism is [1]...
    • ...However, the proof of the condition expressed by (14) holds for both functions [1]...

    José R. Vidalet al. Flexible Dynamic Spectrum Allocation in Cognitive Radio Networks Based...

    • ...Approximate truthfulness is related to a randomized mechanism, and there have been various attempts to find it. One approach is to guarantee truthfulness in expectation, i.e., truthful bidding maximizes a buyer’s expected profit [18]...

    Qinhui Wanget al. An approximate truthfulness motivated spectrum auction for dynamic spe...

    • ...Archer and Tardos [2] considered the important case of algorithmic mechanism design for one-parameter agents...
    • ...Archer and Tardos [2] showed that an algorithm A for an optimization problem with one-parameter agents can be used in a truthful mechanism M = (A ,P) if and only if A is monotone, meaning that, for every agent, the amount of work assigned to her does not increase if her bid increases...
    • ...For generalized oneparameter agents, setting βi = bi = 0 for all i in the proof of Theorem 8 yields the following result, which generalizes the one-parameter monotonicity result of Archer and Tardos [2]:...
    • ...When considering voluntary participation for the case of generalized oneparameter agents, we can apply the same argumentation as used by Archer and Tardos [2] to obtain the characterization of truthful mechanisms satisfying voluntary participation for the classical one-parameter setting: Fixing the bid vector a−i...

    Clemens Thielenet al. Truthful Mechanisms for Selfish Routing and Two-Parameter Agents

Sort by: