The NIP graph of a social welfare function

摘要

We consider the fraction of pairs of m distinct alternatives on which a social welfare function f may be nondictatorially independent and Pareto when the domain of f satisfies the free k-tuple property. When k = 4 we improve the existing upper bound to . When there are at least 26 alternatives and we obtain an original upper bound, . To obtain these results we define and analyze the graph formed from the nondictatorial independent and Pareto pairs and combine the results of this analysis with known results from extremal graph theory.