skip to main content
article

Searching for the possibility: impossibility border of truthful mechanism design

Published: 01 December 2007 Publication History
First page of PDF

References

[1]
ARCHER, A. AND TARDOS, É. 2001. Truthful mechanisms for one-parameter agents. In The Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS). 482-491.
[2]
ARROW, K. 1951. Social Choice and Individual Values. Wiley.
[3]
BARTAL, Y., GONEN, R., AND NISAN, N. 2003. Incentive compatible multi-unit combinatorial auctions. In The Proc. of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK'03).
[4]
BIKHCHANDANI, S., CHATTERJEE, S., LAVI, R., MU'ALEM, A., NISAN, N., AND SEN, A. 2006. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica 74(4), 1109-1132.
[5]
CHRISTODOULOU, G., KOUTSOUPIAS, E., AND KOVÁCS, A. 2007. Mechanism design for fractional scheduling on unrelated machines. In The Proc. of the 34th International Colloquium on Automata, Languages and Programming (ICALP).
[6]
CLARKE, E. 1971. Multipart pricing of public goods. Public Choice 8, 17-33.
[7]
DOBZINSKI, S. 2007. Two randomized mechanisms for combinatorial auctions. In The Proc. of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX).
[8]
DOBZINSKI, S. AND NISAN, N. 2007. Mechanisms for multi-unit auctions. In The Proc. of the 8th ACM Conference on Electronic Commerce (ACM-EC).
[9]
DOBZINSKI, S., NISAN, N., AND SCHAPIRA, M. 2006. Truthful randomized mechanisms for combinatorial auctions. In The Proc. of the 38th ACM Symposium on Theory of Computing (STOC).
[10]
FEIGE, U. 2006. On maximizing welfare when utility functions are subadditive. In The Proc. of the 38th ACM Symposium on Theory of Computing (STOC).
[11]
GROVES, T. 1973. Incentives in teams. Econometrica 41(4), 617-631.
[12]
KOUTSOUPIAS, E. AND VIDALI, A. 2007. A lower bound of 1+φ for truthful scheduling mechanisms. In The Proc. of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS).
[13]
LAVI, R., MU'ALEM, A., and NISAN, N. 2003. Towards a characterization of truthful combinatorial auctions. In The Proc. 44th Annual Symposium on Foundations of Computer Science (FOCS). 574-583.
[14]
LAVI, R., MU'ALEM, A., AND NISAN, N. 2007. An impossibility result for ex-post implementable multi-item auctions with private values. Manuscript.
[15]
LAVI, R. AND SWAMY, C. 2005. Truthful and near-optimal mechanism design via linear programming. In The Proc. of the 46th Annual Symposium on Foundations of Computer Science (FOCS).
[16]
LAVI, R. AND SWAMY, C. 2007. Truthful mechanism design for multidimensional scheduling. In The Proc. of the 8th ACM Conference on Electronic Commerce (ACM-EC).
[17]
LEHMANN, D., O'CALLAGHAN, L., AND SHOHAM, Y. 2002. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM 49(5), 577-602.
[18]
MU'ALEM, A. AND SCHAPIRA, M. 2007. Setting lower bounds on truthfulness. In The Proc. of the 18th Symposium on Discrete Algorithms (SODA).
[19]
NISAN, N. AND RONEN, A. 2001. Algorithmic mechanism design. Games and Economic Behavior 35, 166-196.
[20]
ROBERTS, K. 1979. The characterization of implementable choice rules. In Aggregation and Revelation of Preferences, J.-J. Laffont, Ed. North-Holland, 321-349.
[21]
ROCHET, J. C. 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. Journal of Mathematical Economics 16, 191-200.
[22]
SAKS, M. AND YU, L. 2005. Weak monotonicity suffices for truthfulness on convex domains. In The Proc. of the 6th ACM Conference on Electronic Commerce (ACM-EC). 286-293.
[23]
VICKREY, W. 1961. Counterspeculations, auctions, and competitive sealed tenders. Journal of Finance 16, 8-37.

Cited By

View all
  • (2015)A characterization of n-player strongly monotone scheduling mechanismsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832328(568-574)Online publication date: 25-Jul-2015
  • (2011)Extending characterizations of truthful mechanisms from subdomains to domainsProceedings of the 7th international conference on Internet and Network Economics10.1007/978-3-642-25510-6_36(408-414)Online publication date: 11-Dec-2011

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGecom Exchanges
ACM SIGecom Exchanges  Volume 7, Issue 1
December 2007
70 pages
EISSN:1551-9031
DOI:10.1145/1345037
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2007
Published in SIGECOM Volume 7, Issue 1

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)A characterization of n-player strongly monotone scheduling mechanismsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832328(568-574)Online publication date: 25-Jul-2015
  • (2011)Extending characterizations of truthful mechanisms from subdomains to domainsProceedings of the 7th international conference on Internet and Network Economics10.1007/978-3-642-25510-6_36(408-414)Online publication date: 11-Dec-2011

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media