Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(12)
Best Approximation
Combinatorial Problems
Facility Location
Load Balance
Maximum Flow
Parallel Machines
Polynomial Time
Randomized Rounding
Timing Optimization
Weighted Sums
Lower Bound
Single Positive
Related Publications
(64)
Algorithmic Mechanism Design
An approximate truthful mechanism for combinatorial auctions with single parameter agents
Truth revelation in approximately efficient combinatorial auctions
Frugal path mechanisms
Truthful Approximation Mechanisms for Restricted Combinatorial Auctions
Subscribe
Academic
Publications
Truthful Mechanisms for OneParameter Agents
Truthful Mechanisms for OneParameter Agents,10.1109/SFCS.2001.959924,Aaron Archer,Éva Tardos
Edit
Truthful Mechanisms for OneParameter Agents
(
Citations: 224
)
BibTex

RIS

RefWorks
Download
Aaron Archer
,
Éva Tardos
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 3approximation mechanism based on
randomized rounding
of the optimal fractional solution. This problem is NPcomplete, and the standard approxima tion algorithms (greedy loadbalancing 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.
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 482491, 2001
DOI:
10.1109/SFCS.2001.959924
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.
(
reference.kfupm.edu.sa
)
(
eprints.kfupm.edu.sa
)
(
www.eecs.harvard.edu
)
(
cs.ucsb.edu
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(145)
...We refer the reader to the work by Archer and Tardos [
22
] for a concise treatment of Myerson’s principle of truthfulness in onedimensional settings...
Ajay Gopinathan
,
et 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 Aggarwal
,
et al.
Derandomization of auctions
...If ωi(ˆ vi, ˆ−i) is monotonically nondecreasing 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. Vidal
,
et 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 Wang
,
et al.
An approximate truthfulness motivated spectrum auction for dynamic spe...
...Archer and Tardos [
2
] considered the important case of algorithmic mechanism design for oneparameter agents...
...Archer and Tardos [
2
] showed that an algorithm A for an optimization problem with oneparameter 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 oneparameter 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 oneparameter setting: Fixing the bid vector a−i...
Clemens Thielen
,
et al.
Truthful Mechanisms for Selfish Routing and TwoParameter Agents
References
(39)
W theory of scheduling
(
Citations: 978
)
R. W. Conway
,
W. L. Maxwell
,
Asd Miller
Published in 1967.
Computationally feasible VCG mechanisms
(
Citations: 221
)
Noam Nisan
,
Amir Ronen
Conference:
ACM Conference on Electronic Commerce  EC
, pp. 242252, 2000
Theory of scheduling addisonwesley
(
Citations: 55
)
R. W. Conway
,
W. L. Maxwell
,
L. W. Miller
Published in 1967.
Competitive auctions and digital goods
(
Citations: 133
)
Andrew V. Goldberg
,
Jason D. Hartline
,
Andrew Wright
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 735744, 2001
Online Facility Location
(
Citations: 60
)
Adam Meyerson
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 426431, 2001
Sort by:
Citations
(224)
Strategyproof auctions for balancing social welfare and fairness in secondary spectrum markets
(
Citations: 1
)
Ajay Gopinathan
,
Zongpeng Li
,
Chuan Wu
Conference:
IEEE INFOCOM  INFOCOM
, pp. 30203028, 2011
Derandomization of auctions
Gagan Aggarwal
,
Amos Fiat
,
Andrew V. Goldberg
,
Jason D. Hartline
,
Nicole Immorlica
,
Madhu Sudan
Journal:
Games and Economic Behavior  GAME ECON BEHAV
, vol. 72, no. 1, pp. 111, 2011
Mechanism design with uncertain inputs (to err is human, to forgive divine)
Uriel Feige
,
Moshe Tennenholtz
Journal:
Computing Research Repository  CORR
, vol. abs/1103.2, pp. 549558, 2011
Flexible Dynamic Spectrum Allocation in Cognitive Radio Networks Based on GameTheoretical Mechanism Design
José R. Vidal
,
Vicent Pla
,
Luis Guijarro
,
Jorge MartínezBauset
Conference:
Networking  Networking
, pp. 164177, 2011
An approximate truthfulness motivated spectrum auction for dynamic spectrum access
Qinhui Wang
,
Baoliu Ye
,
Tianyin Xu
,
Sanglu Lu
Conference:
Wireless Communications and Networking, IEEE Conference  WCNC
, pp. 257262, 2011