I am reading this paper:


By P.E Earl and J.Potts

On page 3 the following is written:

"If we think of individual preference orderings as units, then if there are n goods and we ignore computational overheads, each preference map will require (n-1)^2 combinatorial bits to construct."

This confused me a little bit because with just trial and error you can see that in a market with 2 goods, 1 combinatorial bit is needed


Good A > Good B

However when we have 3 goods we only need 2, not as the formula suggests 4 as,

Good A > Good B

Good B > Good C

Where Good A > Good C is implied due to transitivity, but even if not this comes out to 3 bits not 4


1 Answer 1


First, a correction. What you are counting is the number of total orders. You forgot the possibility of indifference. For example, $A \sim B \sim C$ is a perfectly fine preference relation. The correct count of preference relations on $3$ elements should be $13$.

Preference relations are also called total preorders or weak orders in mathematics. According to this wiki page, the number of total preorders on a finite set of cardinality $n$ is given by the ordered Bell number $a(n)$.

The ordered Bell number $a(n)$ satisfies the following recurrence relation:

$$ a(n) = \sum_{i=1}^n {n \choose i} a(n-i) $$

The exact formula is given by the following double sum:

$$ a(n) = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} {k \choose j} j^n $$

For large $n$, we can approximate $a(n)$ by

$$ a(n) \approx \frac{n!}{2 (\ln 2)^{n+1}} $$

I won't go into details, but using the Stirling approximation, you can prove that the number of required bits is on the order of

$$ \log_2 a(n) = O(n \log_2 n) $$

Thus, you are correct that a preference relation on $n$ elements requires much less than $(n-1)^2$ bits to specify.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.