En un entorno con N bienes, ¿cuántos bits combinatorios necesitamos para construir un mapa de preferencias

Question

Estoy leyendo este documento:

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

Por P.E Earl y J.Potts

En la página 3 está escrito lo siguiente:

"Si pensamos en los ordenamientos de preferencias individuales como unidades, entonces si hay n bienes e ignoramos los gastos generales de computación, cada mapa de preferencias requerirá (n-1)^2 bits combinatorios para construirse".

Esto me confundió un poco porque con sólo probar y equivocarse se puede ver que en un mercado con 2 bienes, se necesita 1 bit combinatorio

Es decir

Bueno A > Bueno B

Sin embargo cuando tenemos 3 bienes sólo necesitamos 2, no como sugiere la fórmula 4 como,

Bueno A > Bueno B

Buena B > Buena C

Donde Bueno A > Bueno C está implícito debido a la transitividad, pero aunque no sea así esto sale a 3 bits no a 4

Answer 1

Primero, una corrección. Lo que está contando es el número de total de pedidos . Olvidaste la posibilidad de indiferencia . Por ejemplo, $A \sim B \sim C$ es una relación de preferencia perfecta. El recuento correcto de las relaciones de preferencia en $3$ los elementos deben ser $13$ .

Las relaciones de preferencia también se denominan total de prepedidos o pedidos débiles en matemáticas. De acuerdo con esto página wiki el número de preórdenes totales en un conjunto finito de cardinalidad $n$ viene dada por el pedido Número de campana $a(n)$ .

El número de campana ordenado $a(n)$ satisface la siguiente relación de recurrencia:

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

La fórmula exacta viene dada por la siguiente suma doble:

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

Para los grandes $n$ podemos aproximar $a(n)$ por

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

No voy a entrar en detalles, pero utilizando el Aproximación de Stirling se puede demostrar que el número de bits necesarios es del orden de

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

Por lo tanto, tiene razón en que una relación de preferencia sobre $n$ elementos requiere mucho menos que $(n-1)^2$ bits para especificar .