在有 N 個商品的設置中，我們需要多少個組合位來建構偏好圖
我正在閱讀這篇論文：
https://www.researchgate.net/publication/5208445_The_market_for_preferences
作者：PE Earl 和 J.Potts
在第 3 頁上寫了以下內容：
“如果我們將個人偏好排序視為單位，那麼如果有 n 個商品並且我們忽略計算成本，則每個偏好映射將需要 (n-1)^2 個組合位來建構。”
這讓我有點困惑，因為通過反複試驗，您可以看到在有 2 種商品的市場中，需要 1 個組合位
是的
好 A > 好 B
但是，當我們有 3 件商品時，我們只需要 2 件，而不是公式建議的 4 件，
好 A > 好 B
好 B > 好 C
由於傳遞性，暗示了 Good A > Good C，但即使不是這樣，結果也是 3 位而不是 4
首先，修正。您計算的是總訂單數。你忘記了冷漠的可能性。例如， $ A \sim B \sim C $ 是一個完美的偏好關係。偏好關係的正確計數 $ 3 $ 元素應該是 $ 13 $ .
偏好關係在數學中也稱為總預序或弱序。根據這個wiki 頁面，在有限基數集上的總預購數量 $ n $ 由有序的貝爾號給出 $ a(n) $ .
有序的貝爾號 $ a(n) $ 滿足以下遞歸關係：
$$ a(n) = \sum_{i=1}^n {n \choose i} a(n-i) $$
確切的公式由以下雙和給出：
$$ a(n) = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} {k \choose j} j^n $$
對於大 $ n $ , 我們可以近似 $ a(n) $ 經過
$$ a(n) \approx \frac{n!}{2 (\ln 2)^{n+1}} $$
我不會詳細介紹，但是使用斯特林近似，您可以證明所需的位數大約為
$$ \log_2 a(n) = O(n \log_2 n) $$
因此，您認為偏好關係是正確的 $ n $ 元素需要的遠少於 $ (n-1)^2 $ 要指定的位。