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

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

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.