Acyclic sets of linear orders
Acyclic sets of linear orders
复制标题
线性阶的非循环集
DOI：
10.1007/s003550050055
复制
发表时间：
1996
影响因子：
0.9
通讯作者：
P. Fishburn
中科院分区：
文献类型：
--
作者：
P. Fishburn
{1，2，n，n}上的线性序集是消圈的，如果它的序中没有三个有嵌入置换3-圈{abc，cab，bca}.设f（n）是{1，2，n，n}上线性阶的非循环集的最大基数。确定f（n）的问题多年来一直引起社会选择理论家的兴趣，因为当任意有限集合中的每个投票者都有这些顺序中的任何一个作为他或她的偏好顺序时，它是n个选择集合上保证多数偏好传递性的最大数量的线性顺序。本文给出了f（n）的改进的上下界.我们注意到f（5）= 20，并且n = 4，5的所有极大无圈集都是由一个"交替方案"生成的。 这个过程至少在n = 16时是次优的，此时一个"替换方案"超过了它，目前最好的大n下界约为f（n）≥（2.1708）n。
A set of linear orders on {1,2, ℕ,n} isacyclicif no three of its orders have an embedded permutation 3-cycle {abc, cab, bca}. Letf(n) be the maximum cardinality of an acyclic set of linear orders on {1,2, ℕ,n}. The problem of determiningf(n) has interested social choice theorists for many years because it is the greatest number of linear orders on a set ofnalternatives that guarantees transitivity of majority preferences when every voter in an arbitrary finite set has any one of those orders as his or her preference order. This paper gives improved lower and upper bounds forf(n). We note thatf(5)=20 and that all maximum acyclic sets atn=4, 5 are generated by an “alternating scheme.” This procedure becomes suboptimal at least byn=16, where a “replacement scheme” overtakes it. The presently-best large-nlower bound is approximatelyf(n)≥(2.1708)n.