Uniform random generation and dominance testing for CP-nets

Thomas E. Allen, Judy Goldsmith, Hayden Elizabeth Justice, Nicholas Mattei, Kayla Raines

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 languageEnglish
Pages (from-to)771-813
Number of pages43
JournalJournal of Artificial Intelligence Research
Volume59
DOIs
StatePublished - May 2017

Bibliographical note

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

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Uniform random generation and dominance testing for CP-nets'. Together they form a unique fingerprint.

Cite this