## Abstract

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 _{1} and o _{2} , of a minimal proof that o _{1} is preferred to o _{2} . 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.

Original language | English |
---|---|

Pages (from-to) | 771-813 |

Number of pages | 43 |

Journal | Journal of Artificial Intelligence Research |

Volume | 59 |

DOIs | |

State | Published - May 2017 |

### Bibliographical note

Publisher Copyright:© 2017 AI Access Foundation. All rights reserved.

## ASJC Scopus subject areas

- Artificial Intelligence