In a setting with N goods how many combinatorial bits do we need to construct a preference map

Question

I am reading this paper:

https://www.researchgate.net/publication/5208445_The_market_for_preferences

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

I.e

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

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.