IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v70y2018i4d10.1007_s10898-017-0586-x.html
   My bibliography  Save this article

Approximate efficiency and strategy-proofness for moneyless mechanisms on single-dipped policy domain

Author

Listed:
  • Qiaoming Han

    (Zhejiang University of Finance and Economics)

  • Donglei Du

    (University of New Brunswick
    Beijing University of Technology)

  • Dachuan Xu

    (Beijing University of Technology)

  • Yicheng Xu

    (Beijing University of Technology)

Abstract

The single-dipped domain can be used to model any allocation problem where a single output must be chosen in an interval with the assumption that agents’ preferences have a single most loathful point (the dip) in the interval, and the preferences are increasing as one moves away from that dip. Practical domains like this appear in political voting system where each voter has his most-hated candidate and alternative candidates are evaluated by their proximity to this candidate or in obnoxious location problem, where each agent prefers to have the obnoxious location to be distant from his own location, among others. We first characterize deterministic and anonymous strategy-proof and group strategy-proof mechanisms on single-dipped public policy domain, complementing the well-known results on single-peaked policy domain first investigated by Moulin (Pub. Choice 35:437–455, 1980). Then we consider the tradeoff between strategy-proofness and efficiency by applying our characterization. As concrete applications of our results, we extend existing models and results, and resolve several open questions related to the obnoxious facility location game from the algorithmic mechanism design literature.

Suggested Citation

  • Qiaoming Han & Donglei Du & Dachuan Xu & Yicheng Xu, 2018. "Approximate efficiency and strategy-proofness for moneyless mechanisms on single-dipped policy domain," Journal of Global Optimization, Springer, vol. 70(4), pages 859-873, April.
    • Handle: RePEc:spr:jglopt:v:70:y:2018:i:4:d:10.1007_s10898-017-0586-x
    DOI: 10.1007/s10898-017-0586-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-017-0586-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-017-0586-x?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. Barberà, Salvador & Berga, Dolors & Moreno, Bernardo, 2010. "Individual versus group strategy-proofness: When do they coincide?," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1648-1674, September.
    2. Kenneth J. Arrow, 1950. "A Difficulty in the Concept of Social Welfare," Journal of Political Economy, University of Chicago Press, vol. 58(4), pages 328-328.
    3. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2012. "Group strategy-proof social choice functions with binary ranges and arbitrary domains: characterization results," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(4), pages 791-808, November.
    4. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2012. "Domains, ranges and strategy-proofness: the case of single-dipped preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(2), pages 335-352, July.
    5. Nisan,Noam & Roughgarden,Tim & Tardos,Eva & Vazirani,Vijay V. (ed.), 2007. "Algorithmic Game Theory," Cambridge Books, Cambridge University Press, number 9780521872829, November.
    6. Noga Alon & Michal Feldman & Ariel D. Procaccia & Moshe Tennenholtz, 2010. "Strategyproof Approximation of the Minimax on Networks," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 513-526, August.
    7. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    8. Manjunath, Vikram, 2012. "Group strategy-proofness and voting between two alternatives," Mathematical Social Sciences, Elsevier, vol. 63(3), pages 239-242.
    9. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    10. H. Moulin, 1980. "On strategy-proofness and single peakedness," Public Choice, Springer, vol. 35(4), pages 437-455, January.
    11. Klaus, Bettina & Peters, Hans & Storcken, Ton, 1997. "Strategy-proof division of a private good when preferences are single-dipped," Economics Letters, Elsevier, vol. 55(3), pages 339-346, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dietzenbacher, Bas & Tamura, Yuki, 2023. "Fair and efficient allocations when preferences are single-dipped," Research Memorandum 009, Maastricht University, Graduate School of Business and Economics (GSBE).
    2. Yukun Cheng & Qiaoming Han & Wei Yu & Guochuan Zhang, 2019. "Strategy-proof mechanisms for obnoxious facility game with bounded service range," Journal of Combinatorial Optimization, Springer, vol. 37(2), pages 737-755, February.

    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. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2012. "Domains, ranges and strategy-proofness: the case of single-dipped preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(2), pages 335-352, July.
    2. Vikram Manjunath, 2014. "Efficient and strategy-proof social choice when preferences are single-dipped," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(3), pages 579-597, August.
    3. Barberà, Salvador & Berga, Dolors & Moreno, Bernardo, 2022. "Restricted environments and incentive compatibility in interdependent values models," Games and Economic Behavior, Elsevier, vol. 131(C), pages 1-28.
    4. Grisel Ayllón & Diego M. Caramuta, 2016. "Single-dipped preferences with satiation: strong group strategy-proofness and unanimity," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(2), pages 245-264, August.
    5. Mishra, Debasis, 2016. "Ordinal Bayesian incentive compatibility in restricted domains," Journal of Economic Theory, Elsevier, vol. 163(C), pages 925-954.
    6. Alcalde-Unzu, Jorge & Vorsatz, Marc, 2018. "Strategy-proof location of public facilities," Games and Economic Behavior, Elsevier, vol. 112(C), pages 21-48.
    7. Achille Basile & K. P. S. Bhaskara Rao & Anna De Simone & Ciro Tarantino, 2024. "Isotone Classes of Social Choice Functions with Binary Range," Games, MDPI, vol. 15(6), pages 1-18, December.
    8. Patrick Harless, 2015. "Reaching consensus: solidarity and strategic properties in binary social choice," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(1), pages 97-121, June.
    9. Basile, Achille & Rao, Surekha & Bhaskara Rao, K.P.S., 2022. "Anonymous, non-manipulable binary social choice," Games and Economic Behavior, Elsevier, vol. 133(C), pages 138-149.
    10. Freixas, Josep & Parker, Cameron, 2015. "Manipulation in games with multiple levels of output," Journal of Mathematical Economics, Elsevier, vol. 61(C), pages 144-151.
    11. Michel Breton & Vera Zaporozhets, 2009. "On the equivalence of coalitional and individual strategy-proofness properties," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 33(2), pages 287-309, August.
    12. Haeringer, Guillaume & Hałaburda, Hanna, 2016. "Monotone strategyproofness," Games and Economic Behavior, Elsevier, vol. 98(C), pages 68-77.
    13. Gopakumar Achuthankutty & Souvik Roy, 2018. "Dictatorship on top-circular domains," Theory and Decision, Springer, vol. 85(3), pages 479-493, October.
    14. Shurojit Chatterji & Arunava Sen, 2011. "Tops-only domains," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 46(2), pages 255-282, February.
    15. Reffgen, Alexander, 2015. "Strategy-proof social choice on multiple and multi-dimensional single-peaked domains," Journal of Economic Theory, Elsevier, vol. 157(C), pages 349-383.
    16. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2020. "Arrow on domain conditions: a fruitful road to travel," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 237-258, March.
    17. Chatterji, Shurojit & Zeng, Huaxia, 2018. "On random social choice functions with the tops-only property," Games and Economic Behavior, Elsevier, vol. 109(C), pages 413-435.
    18. Itai Feigenbaum & Jay Sethuraman & Chun Ye, 2017. "Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing L p Norm of Costs," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 434-447, May.
    19. Roy, Souvik & Sadhukhan, Soumyarup, 2021. "A unified characterization of the randomized strategy-proof rules," Journal of Economic Theory, Elsevier, vol. 197(C).
    20. Salvador Barberà & Dolors Berga & Bernardo Moreno, 2012. "Group strategy-proof social choice functions with binary ranges and arbitrary domains: characterization results," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(4), pages 791-808, November.

    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:spr:jglopt:v:70:y:2018:i:4:d:10.1007_s10898-017-0586-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.