Cost sharing and strategyproof mechanisms for set cover games

DOI10.1007/S10878-009-9209-XzbMATH Open1205.91044OpenAlexW2111234732MaRDI QIDQ604756FDOQ604756

Xiangyang Li, Wei Lou, Zheng Sun, Weizhao Wang

Publication date: 12 November 2010

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.142.5020

Recommendations

• STACS 2005
• Mechanism design for set cover games with selfish element agents
• Algorithmic Applications in Management
• Set-weighted games and their application to the cover problem
• New techniques for cost sharing in combinatorial optimization games
• A complete characterization of group-strategyproof mechanisms of cost-sharing
• A complete characterization of group-strategyproof mechanisms of cost-sharing
• scientific article; zbMATH DE number 7042522

zbMATH Keywords

pricingset covermechanism designselfish agent

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial games (91A46)

Cites Work

• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem
• Title not available (Why is that?)
• Applications of approximation algorithms to cooperative games
• Incentives in Teams
• Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods
• Strategyproof sharing of submodular costs: budget balance versus efficiency
• Algorithmic mechanism design
• Approximation and collusion in multicast cost sharing
• Atomic resource sharing in noncooperative networks
• Truth revelation in approximately efficient combinatorial auctions
• A Tight Analysis of the Greedy Algorithm for Set Cover
• STACS 2005
• Sharing the cost of multicast transmissions
• A BGP-based mechanism for lowest-cost routing
• Hardness results for multicast cost sharing.
• Limitations of cross-monotonic cost sharing schemes
• Non-cooperative Facility Location and Covering Games
• Algorithmic Applications in Management
• Title not available (Why is that?)
• The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms

Cited In (8)

• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• Algorithmic Applications in Management
• Algorithms and Computation
• STACS 2005
• Mechanism design for set cover games with selfish element agents
• A game theoretic approach for minimal connected dominating set
• Cost allocation and strategyproof mechanism for cover-set games
• Allocating costs in set covering problems

This page was built for publication: Cost sharing and strategyproof mechanisms for set cover games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q604756)