IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v111y2018icp64-74.html
   My bibliography  Save this article

No truthful mechanism can be better than n approximate for two natural problems

Author

Listed:
  • Leucci, Stefano
  • Mamageishvili, Akaki
  • Penna, Paolo

Abstract

This work gives the first natural non-utilitarian problems for which the trivial napproxima-tion via VCG mechanisms is the best possible. That is, no truthful mechanism can be better than n approximate, where n is the number of agents. The problems we study are the min-max variant of the shortest path and the (directed) minimum spanning tree mechanism design problems. In these procurement auctions, agents own the edges of a network, and the corresponding edge costs are private. Instead of the total weight of the subnetwork, in the min-max variant we aim to minimize the maximum agent cost.

Suggested Citation

  • Leucci, Stefano & Mamageishvili, Akaki & Penna, Paolo, 2018. "No truthful mechanism can be better than n approximate for two natural problems," Games and Economic Behavior, Elsevier, vol. 111(C), pages 64-74.
    • Handle: RePEc:eee:gamebe:v:111:y:2018:i:c:p:64-74
    DOI: 10.1016/j.geb.2018.05.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S089982561830071X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2018.05.003?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
    2. Sushil Bikhchandani & Shurojit Chatterji & Ron Lavi & Ahuva Mu'alem & Noam Nisan & Arunava Sen, 2006. "Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation," Econometrica, Econometric Society, vol. 74(4), pages 1109-1132, July.
    3. Lavi, Ron & Swamy, Chaitanya, 2009. "Truthful mechanism design for multidimensional scheduling via cycle monotonicity," Games and Economic Behavior, Elsevier, vol. 67(1), pages 99-124, September.
    4. Dobzinski, Shahar & Nisan, Noam, 2015. "Multi-unit auctions: Beyond Roberts," Journal of Economic Theory, Elsevier, vol. 156(C), pages 14-44.
    5. Itai Ashlagi & Shahar Dobzinski & Ron Lavi, 2012. "Optimal Lower Bounds for Anonymous Scheduling Mechanisms," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 244-258, May.
    6. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    7. Rochet, Jean-Charles, 1987. "A necessary and sufficient condition for rationalizability in a quasi-linear context," Journal of Mathematical Economics, Elsevier, vol. 16(2), pages 191-200, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Georgiou, Konstantinos & Swamy, Chaitanya, 2019. "Black-box reductions for cost-sharing mechanism design," Games and Economic Behavior, Elsevier, vol. 113(C), pages 17-37.
    2. Mu'alem, Ahuva & Schapira, Michael, 2018. "Setting lower bounds on truthfulness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 174-193.
    3. Carbajal, Juan Carlos & Müller, Rudolf, 2017. "Monotonicity and revenue equivalence domains by monotonic transformations in differences," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 29-35.
    4. Debasis Mishra & Anup Pramanik & Souvik Roy, 2013. "Implementation in multidimensional domains with ordinal restrictions," Discussion Papers 13-07, Indian Statistical Institute, Delhi.
    5. Rahul Deb & Debasis Mishra, 2013. "Implementation with securities," Discussion Papers 13-05, Indian Statistical Institute, Delhi.
    6. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    7. Paul H. Edelman & John A. Weymark, 2021. "Dominant strategy implementability and zero length cycles," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(4), pages 1091-1120, November.
    8. Mishra, Debasis & Pramanik, Anup & Roy, Souvik, 2014. "Multidimensional mechanism design in single peaked type spaces," Journal of Economic Theory, Elsevier, vol. 153(C), pages 103-116.
    9. Frongillo, Rafael M. & Kash, Ian A., 2021. "General truthfulness characterizations via convex analysis," Games and Economic Behavior, Elsevier, vol. 130(C), pages 636-662.
    10. Caleb Koch, 2020. "Implementation with ex post hidden actions," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 5(1), pages 1-35, December.
    11. Birgit Heydenreich & Rudolf Müller & Marc Uetz & Rakesh V. Vohra, 2009. "Characterization of Revenue Equivalence," Econometrica, Econometric Society, vol. 77(1), pages 307-316, January.
    12. Carbajal, Juan Carlos & McLennan, Andrew & Tourky, Rabee, 2013. "Truthful implementation and preference aggregation in restricted domains," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1074-1101.
    13. Ian Ball & Deniz Kattwinkel, 2019. "Probabilistic Verification in Mechanism Design," Papers 1908.05556, arXiv.org, revised Dec 2023.
    14. Bin Li & Dong Hao & Dengji Zhao, 2020. "Incentive-Compatible Diffusion Auctions," Papers 2001.06975, arXiv.org, revised Apr 2020.
    15. Blumrosen, Liad & Feldman, Michal, 2013. "Mechanism design with a restricted action space," Games and Economic Behavior, Elsevier, vol. 82(C), pages 424-443.
    16. Carbajal, Juan Carlos & Müller, Rudolf, 2015. "Implementability under monotonic transformations in differences," Journal of Economic Theory, Elsevier, vol. 160(C), pages 114-131.
    17. Archer, Aaron & Kleinberg, Robert, 2014. "Truthful germs are contagious: A local-to-global characterization of truthfulness," Games and Economic Behavior, Elsevier, vol. 86(C), pages 340-366.
    18. Rahul Deb & Debasis Mishra, 2014. "Implementation With Contingent Contracts," Econometrica, Econometric Society, vol. 82, pages 2371-2393, November.
    19. Berger, A. & Müller, R.J. & Naeemi, S.H., 2010. "Path-monotonicity and incentive compatibility," Research Memorandum 035, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    20. Itai Ashlagi & Shahar Dobzinski & Ron Lavi, 2012. "Optimal Lower Bounds for Anonymous Scheduling Mechanisms," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 244-258, May.

    More about this item

    Keywords

    Mechanism design; Truthful mechanisms; Inapproximability; Non-utilitarian problems; Lower bounds;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D82 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Asymmetric and Private Information; Mechanism Design
    • D4 - Microeconomics - - Market Structure, Pricing, and Design

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:111:y:2018:i:c:p:64-74. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.