The computational complexity of rationalizing Pareto optimal choice behavior
We consider a setting where a coalition of individuals chooses one or several alternatives from each set in a collection of choice sets. We examine the computational complexity of Pareto rationalizability. Pareto rationalizability requires that we can endow each individual in the coalition with a preference relation such that the observed choices are Pareto efficient. We differentiate between the situation where the choice function is considered to select all Pareto optimal alternatives from a choice set and the situation where it only contains one or several Pareto optimal alternatives. In the former case we find that Pareto rationalizability is an NP-complete problem. For the latter case we demonstrate that, if we have no additional information on the individual preference relations, then all choice behavior is Pareto rationalizable. However, if we have such additional information, then Pareto rationalizability is again NP-complete. Our results are valid for any coalition of size greater or equal than two.
|Date of creation:||Jun 2011|
|Contact details of provider:|| Web page: http://feb.kuleuven.be/Economics/|
When requesting a correction, please mention this item's handle: RePEc:ete:ceswps:ces11.13. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (library EBIB)
If references are entirely missing, you can add them using this form.