Expressive efficiency of two kinds of specific CP-nets

CP-nets (conditional preference networks) are a graphical model for compactly expressing conditional ceteris paribus   (all other things being equal) preference statements on multi-attribute domains. In this paper, we investigate the expressive efficiency of two kinds of binary-valued CP-nets, the first kind is set-structured CP-nets, and the second kind is equal difference CP-nets. For the first kind, we prove that it can express 3n-2n3n-2n preference relations with n   preference rules, and has an expressive efficiency of (3n-2n)/n(3n-2n)/n. For the second kind, we show that it can express a total order of 2n-1∗(2n-1)2n-1∗(2n-1) preference relations with 2n-12n-1 preference rules, and has an expressive efficiency of 2n-12n-1. For the future research, we propose an open problem: given an acyclic CP-net N   with the in-degree sequence of (d1,d2,…,dn)(d1,d2,…,dn), how many preference relations can be expressed by N?