The Complexity of Egalitarian Mechanisms for Linear Programming Games
Nelson A. Uhan (uhanusna.edu)
Abstract: We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P = NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming games is NP-hard.
Keywords: cost sharing mechanisms; cooperative games; computational complexity
Category 1: Other Topics (Game Theory )
Category 2: Combinatorial Optimization
Citation: Operations Research Letters 42(1) 76-81, 2014.
Entry Submitted: 07/18/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|