Uniform Random Generation and Dominance Testing for CP-Nets
Uniform Random Generation and Dominance Testing for CP-Nets
复制标题
DOI：
10.1613/jair.5455
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Thomas E. Allen;J. Goldsmith;Hayden Elizabeth Justice;Nicholas Mattei;Kayla Raines
中科院分区：
文献类型：
--
作者：
Thomas E. Allen;J. Goldsmith;Hayden Elizabeth Justice;Nicholas Mattei;Kayla Raines
用于实验和实证测试的CP网络表示的偏好的生成通常以特设的方式进行，这可能在以前的实验工作中引入了较大的统计偏差。我们提出了一种新的多项式时间算法，用于生成具有n个节点和最大入度c的CP-网。我们将这一结果扩展到社会选择和偏好推理文献中常用的几种统计文化。一个CP-网是由一个图和基本的CP-语句;我们的算法是第一个可证明生成的图形结构和CP-语句，因此基本的偏好顺序本身，均匀随机。我们已经将此代码作为免费和开源项目发布。我们使用均匀生成算法来研究最大和期望的翻转长度，即，在所有结果o和o '上的最大长度，证明o优于o'的最小证明。使用我们的新的统计证据，我们推测，CP-网与二进制变量和完整的条件偏好表，预期的翻转长度是多项式的偏好变量的数量。这对CP网作为紧凑偏好模型的可用性具有积极的影响。
The generation of preferences represented as CP-nets for experiments and empirical testing has typically been done in an ad hoc manner that may have introduced a large statistical bias in previous experimental work. We present novel polynomial-time algorithms for generating CP-nets with n nodes and maximum in-degree c uniformly at random. We extend this result to several statistical cultures commonly used in the social choice and preference reasoning literature. A CP-net is composed of both a graph and underlying cp-statements; our algorithm is the first to provably generate both the graph structure and cp-statements, and hence the underlying preference orders themselves, uniformly at random. We have released this code as a free and open source project. We use the uniform generation algorithm to investigate the maximum and expected flipping lengths, i.e., the maximum length over all outcomes o and o', of a minimal proof that o is preferred to o'. Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. This has positive implications for the usability of CP-nets as compact preference models.