Optimization Online


The Complexity of Egalitarian Mechanisms for Linear Programming Games

Nelson A. Uhan (uhan***at***usna.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
Entry Accepted: 07/22/2011
Entry Last Modified: 01/02/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society