IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v20y2010i3d10.1007_s10878-009-9209-x.html
   My bibliography  Save this article

Cost sharing and strategyproof mechanisms for set cover games

Author

Listed:
  • Xiang-Yang Li

    (Illinois Institute of Technology)

  • Zheng Sun

    (Google Inc.)

  • Weizhao Wang

    (Google Inc.)

  • Wei Lou

    (The Hong Kong Polytechnic University)

Abstract

We develop for set cover games several general cost-sharing methods that are approximately budget-balanced, in the core, and/or group-strategyproof. We first study the cost sharing for a single set cover game, which does not have a budget-balanced mechanism in the core. We show that there is no cost allocation method that can always recover more than $\frac{1}{\ln n}$ of the total cost and in the core. Here n is the number of all players to be served. We give a cost allocation method that always recovers $\frac{1}{\ln d_{\mathit{max}}}$ of the total cost, where d max is the maximum size of all sets. We then study the cost allocation scheme for all induced subgames. It is known that no cost sharing scheme can always recover more than $\frac{1}{n}$ of the total cost for every subset of players. We give an efficient cost sharing scheme that always recovers at least $\frac{1}{2n}$ of the total cost for every subset of players and furthermore, our scheme is cross-monotone. When the elements to be covered are selfish agents with privately known valuations, we present a strategyproof charging mechanism, under the assumption that all sets are simple sets; further, the total cost of the set cover is no more than ln d max times that of an optimal solution. When the sets are selfish agents with privately known costs, we present a strategyproof payment mechanism to them. We also show how to fairly share the payments to all sets among the elements.

Suggested Citation

  • Xiang-Yang Li & Zheng Sun & Weizhao Wang & Wei Lou, 2010. "Cost sharing and strategyproof mechanisms for set cover games," Journal of Combinatorial Optimization, Springer, vol. 20(3), pages 259-284, October.
  • Handle: RePEc:spr:jcomop:v:20:y:2010:i:3:d:10.1007_s10878-009-9209-x
    DOI: 10.1007/s10878-009-9209-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-009-9209-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/s10878-009-9209-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. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    2. Green, Jerry & Laffont, Jean-Jacques, 1977. "Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods," Econometrica, Econometric Society, vol. 45(2), pages 427-438, March.
    3. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    4. Green, Jerry & Laffont, Jean-Jacques, 1977. "On the revelation of preferences for public goods," Journal of Public Economics, Elsevier, vol. 8(1), pages 79-93, August.
    5. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    6. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    7. Shenker, Scott & Clark, David & Estrin, Deborah & Herzog, Shai, 1996. "Pricing in computer networks: Reshaping the research agenda," Telecommunications Policy, Elsevier, vol. 20(3), pages 183-201, April.
    8. Archer, Aaron & Feigenbaum, Joan & Krishnamurthy, Arvind & Sami, Rahul & Shenker, Scott, 2004. "Approximation and collusion in multicast cost sharing," Games and Economic Behavior, Elsevier, vol. 47(1), pages 36-71, April.
    9. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    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. Bergantiños, Gustavo & Gómez-Rúa, María & Llorca, Natividad & Pulido, Manuel & Sánchez-Soriano, Joaquín, 2020. "Allocating costs in set covering problems," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1074-1087.
    2. William N. Caballero & Brian J. Lunday & Darryl K. Ahner, 2020. "Incentive Compatible Cost Sharing of a Coalition Initiative with Probabilistic Inspection and Penalties for Misrepresentation," Group Decision and Negotiation, Springer, vol. 29(6), pages 1021-1055, December.

    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. Shao, Ran & Zhou, Lin, 2016. "Voting and optimal provision of a public good," Journal of Public Economics, Elsevier, vol. 134(C), pages 35-41.
    2. Yi, Jianxin & Li, Yong, 2016. "A general impossibility theorem and its application to individual rights," Mathematical Social Sciences, Elsevier, vol. 81(C), pages 79-86.
    3. Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
    4. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    5. Hiroki Saitoh & Shigehiro Serizawa, 2008. "Vickrey allocation rule with income effect," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(2), pages 391-401, May.
    6. Takashi Kunimoto & Cuiling Zhang, 2021. "On incentive compatible, individually rational public good provision mechanisms," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(2), pages 431-468, August.
    7. Tommy Andersson & Lars Ehlers & Lars-Gunnar Svensson & Ryan Tierney, 2022. "Gale’s Fixed Tax for Exchanging Houses," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3110-3128, November.
    8. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    9. Ledyard, John O., "undated". "Public Goods: A Survey of Experimental Research," Working Papers 861, California Institute of Technology, Division of the Humanities and Social Sciences.
    10. Rica Gonen & Anat Lerner, 2013. "The Incompatibility of Pareto Optimality and Dominant-Strategy Incentive Compatibility in Sufficiently-Anonymous Budget-Constrained Quasilinear Settings," Games, MDPI, vol. 4(4), pages 1-21, November.
    11. Duygu Yengin, 2017. "No-envy and egalitarian-equivalence under multi-object-demand for heterogeneous objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 81-108, January.
    12. Charles Laine, 1985. "Distribution of jointly owned private goods by the demand-revealing process: Applications to divorce settlements and estate administration," Public Choice, Springer, vol. 47(3), pages 437-457, January.
    13. Simon Loertscher & Leslie M. Marx, 2022. "To sell public or private goods," Review of Economic Design, Springer;Society for Economic Design, vol. 26(3), pages 385-415, September.
    14. Thirumulanathan, D. & Vinay, H. & Bhashyam, Srikrishna & Sundaresan, Rajesh, 2017. "Almost budget balanced mechanisms with scalar bids for allocation of a divisible good," European Journal of Operational Research, Elsevier, vol. 262(3), pages 1196-1207.
    15. Guo, Mingyu & Conitzer, Vincent, 2009. "Worst-case optimal redistribution of VCG payments in multi-unit auctions," Games and Economic Behavior, Elsevier, vol. 67(1), pages 69-98, September.
    16. Feldmann, Martin & Müller, Stephanie, 2003. "An incentive scheme for true information providing in Supply Chains," Omega, Elsevier, vol. 31(2), pages 63-73, April.
    17. Paul Resnick & Christopher Avery & Richard Zeckhauser, 1999. "The Market for Evaluations," American Economic Review, American Economic Association, vol. 89(3), pages 564-584, June.
    18. Alva, Samson & Manjunath, Vikram, 2019. "Strategy-proof Pareto-improvement," Journal of Economic Theory, Elsevier, vol. 181(C), pages 121-142.
    19. Soo Chew & Shigehiro Serizawa, 2007. "Characterizing the Vickrey combinatorial auction by induction," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 33(2), pages 393-406, November.
    20. Jing Chen & Silvio Micali, 2016. "Leveraging Possibilistic Beliefs in Unrestricted Combinatorial Auctions," Games, MDPI, vol. 7(4), pages 1-19, October.

    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:jcomop:v:20:y:2010:i:3:d:10.1007_s10878-009-9209-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.