<p>First, a correction. What you are counting is the number of <em>total orders</em>. You forgot the possibility of <em>indifference</em>. For example, <span class="math-container">$A \sim B \sim C$</span> is a perfectly fine preference relation. The correct count of preference relations on <span class="math-container">$3$</span> elements should be <span class="math-container">$13$</span>.</p>
<p>Preference relations are also called <a href="https://en.wikipedia.org/wiki/Weak_ordering#Total_preorders" rel="nofollow noreferrer">total preorders or weak orders</a> in mathematics. According to this <a href="https://en.wikipedia.org/wiki/Weak_ordering#Combinatorial_enumeration" rel="nofollow noreferrer">wiki page</a>, the number of total preorders on a finite set of cardinality <span class="math-container">$n$</span> is given by the <a href="https://en.wikipedia.org/wiki/Ordered_Bell_number" rel="nofollow noreferrer">ordered Bell number <span class="math-container">$a(n)$</span></a>.</p>
<p>The ordered Bell number <span class="math-container">$a(n)$</span> satisfies the following recurrence relation:</p>
<p><span class="math-container">$$ a(n) = \sum_{i=1}^n {n \choose i} a(n-i) $$</span></p>
<p>The exact formula is given by the following double sum:</p>
<p><span class="math-container">$$ a(n) = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} {k \choose j} j^n $$</span></p>
<p>For large <span class="math-container">$n$</span>, we can approximate <span class="math-container">$a(n)$</span> by</p>
<p><span class="math-container">$$ a(n) \approx \frac{n!}{2 (\ln 2)^{n+1}} $$</span></p>
<p>I won't go into details, but using the <a href="https://en.wikipedia.org/wiki/Stirling%27s_approximation" rel="nofollow noreferrer">Stirling approximation</a>, you can prove that the number of required bits is on the order of</p>
<p><span class="math-container">$$ \log_2 a(n) = O(n \log_2 n) $$</span></p>
<p>Thus, you are correct that <strong>a preference relation on <span class="math-container">$n$</span> elements requires much less than <span class="math-container">$(n-1)^2$</span> bits to specify</strong>.</p>

CC BY-SA 4.0
2021-12-01T01:41:43.253Z
2021-12-01T03:55:36.867Z
2021-12-01T03:55:36.867Z
user141240
<p>I am reading this paper:</p>
<p><a href="https://www.researchgate.net/publication/5208445_The_market_for_preferences" rel="nofollow noreferrer">https://www.researchgate.net/publication/5208445_The_market_for_preferences</a></p>
<p>By P.E Earl and J.Potts</p>
<p>On page 3 the following is written:</p>
<p>&quot;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.&quot;</p>
<p>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</p>
<p>I.e</p>
<p>Good A &gt; Good B</p>
<p>However when we have 3 goods we only need 2, not as the formula suggests 4 as,</p>
<p>Good A &gt; Good B</p>
<p>Good B &gt; Good C</p>
<p>Where Good A &gt; Good C is implied due to transitivity, but even if not this comes out to 3 bits not 4</p>

<microeconomics><preferences><choice-theory>
In a setting with N goods how many combinatorial bits do we need to construct a preference map
ra514
# In a setting with N goods how many combinatorial bits do we need to construct a preference map

(Asked by: username_0 on 2021-11-30)

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

**Tags:** microeconomics, preferences, choice-theory


---

## 1 answers

### Answer by username_1 on 2021-12-01. Score: 2 | Accepted answer

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](https://en.wikipedia.org/wiki/Weak_ordering#Total_preorders) in mathematics. According to this [wiki page](https://en.wikipedia.org/wiki/Weak_ordering#Combinatorial_enumeration), the number of total preorders on a finite set of cardinality $n$ is given by the [ordered Bell number $a(n)$](https://en.wikipedia.org/wiki/Ordered_Bell_number).

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](https://en.wikipedia.org/wiki/Stirling%27s_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**.


---

