Open AccessThe computational complexity of rationalizing Pareto optimal choice behavior
Author(s) -
Thomas Demuynck
Publication year - 2013
Publication title -
social choice and welfare
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.504
H-Index - 52
eISSN - 1432-217X
pISSN - 0176-1714
DOI - 10.1007/s00355-013-0735-1
Subject(s) - rationalizability , pareto principle , preference , choice function , preference relation , set (abstract data type) , mathematical economics , pareto efficiency , pareto optimal , mathematical optimization , mathematics , economics , multi objective optimization , computer science , statistics , nash equilibrium , programming language
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 computationalcomplexity 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. Inthe former casewe find that Pareto rationalizability is an NP-complete problem. For the latter case we demonstrate that, if we have no additional information on the individualpreference 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.status: publishe
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom