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

11 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

Funding Information:
This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-1215985 and IIS-1649152. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. Some of this work was complete while Nicholas Mattei was supported by Data61, CSIRO (formerly NICTA) and UNSW, Australia. Data61, CSIRO (formerly NICTA) is funded by the Australian Government through the Department of Communications and the Australian Research Council (ARC) through the ICT Centre of Excellence Program.

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