隔離太空社群中的公平資源分配

封存文章

本文源自 IMMC 的火星基地貨物分配情境。舊版名義上使用 Nash social welfare，程式實際上卻最大化總效用；envy-free 與 proportionality 的公式亦有索引錯誤。本版本保留資料情境，重新建立可執行、可解釋的公平分配框架。

五位研究員要分配 30 件誤送且不可退回的貨物。每人對每件物品給出主觀價值，部分價值為負，代表維護、儲存或風險負擔。物品不可分割，而且物品組合可能有 complementarity 或 substitution。

這個問題不能只問「總分最高嗎」，還要問：

每件物品是否必須分配，還是可安全棄置／共用？
個人價值可否跨人直接比較？
負效用如何進入公平準則？
不可分割物品下，完整 envy-freeness 是否存在？
社會合作是改變效用，還是限制誰可共同使用資源？

一、基本配置模型

令研究員集合為 $N=\{1,\ldots,n\}$ ，貨物為 $M=\{1,\ldots,m\}$ 。 $v_{ij}$ 是研究員 $i$ 對物品 $j$ 的價值， $x_{ij}\in\{0,1\}$ 表示是否分給 $i$ ：

\sum_{i\in N}x_{ij}=1,\qquad j\in M.

若允許棄置，可增加 $x_{0j}$ ：

x_{0j}+\sum_i x_{ij}=1.

加性效用為

u_i(X_i)=\sum_jv_{ij}x_{ij}.

最大總價值

Utilitarian allocation 解

\max_x\sum_i\sum_jv_{ij}x_{ij}.

在沒有其他限制時，每件物品直接交給報價最高的人。它在給定的可比較數值尺度 上最大化總和，卻不保證每人得到合理份額。

import pulp

def utilitarian_allocation(values, people, items):
    model = pulp.LpProblem("utilitarian", pulp.LpMaximize)
    x = pulp.LpVariable.dicts(
        "x", ((i, j) for i in people for j in items), cat="Binary"
    )
    model += pulp.lpSum(values[i][j] * x[i, j] for i in people for j in items)
    for j in items:
        model += pulp.lpSum(x[i, j] for i in people) == 1
    model.solve(pulp.PULP_CBC_CMD(msg=False))
    return x, pulp.LpStatus[model.status]

舊結果中，Alice 的自評效用為 836、Bob 為 3015。這個差距提示 distribution 可能不均，但 836/3015=0.277 不是通用 fairness score：兩人的 cardinal scales 可能不同，而且比例在負效用時會失效。

二、正確的公平定義

1. Envy-freeness

配置 $X=(X_1,\ldots,X_n)$ 是 envy-free，若每個人按自己的價值評估時，都不偏好別人的 bundle：

u_i(X_i)\ge u_i(X_k), \qquad\forall i,k.

加性情況下：

\sum_jv_{ij}x_{ij} \ge \sum_jv_{ij}x_{kj}.

右邊必須仍使用 $v_{ij}$ ，而不是研究員 $k$ 對其 bundle 的自評。舊公式混合了 observer 與 owner 的索引，因而不能正確測量 envy。

2. Proportionality

若所有物品對 $i$ 都是 goods，proportionality 要求

u_i(X_i) \ge \frac1n u_i(M) =\frac1n\sum_jv_{ij}.

它不是把 $i$ 的 bundle 與其他人的自評總和比較。對含 chores 或 mixed manna 的問題，這一定義要更小心，因為 $u_i(M)$ 可為負。

3. EF1

不可分割 goods 未必存在完整 envy-free allocation。常用的放寬是 envy-free up to one good（EF1）：

\forall i,k,\ \exists g\in X_k: \quad u_i(X_i)\ge u_i(X_k\setminus\{g\}).

若 bundle 同時含 goods 與 chores，需要 EFX／EF1 的 mixed-manna 版本，或分開處理可取資源與必須承擔的負擔。

def is_ef1(allocation, values, people):
    for i in people:
        own = sum(values[i][j] for j in allocation[i])
        for k in people:
            if i == k:
                continue
            other = allocation[k]
            if own >= sum(values[i][j] for j in other):
                continue
            if not any(
                own >= sum(values[i][j] for j in other if j != removed)
                for removed in other
            ):
                return False
    return True

對正效用，

\operatorname{NSW}(X) =\prod_i u_i(X_i)

或等價地最大化

\sum_i\log u_i(X_i).

取 logarithm 把乘積轉成和，但不會把整個 mixed-integer problem 線性化。 $\log$ 仍是非線性 concave function。

舊 PuLP 程式建立 $u_i$ 後，目標卻寫成

prob += pulp.lpSum(u[i] for i in researchers)

它只是再次最大化總效用，不是 Nash welfare；而且舊片段沒有呼叫 prob.solve()。因此所謂「Nash allocation」不能由該程式支持。

正效用與基準

若某些 bundle 的效用非正， $\log u_i$ 未定義。不能隨意加大常數，因為 Nash product 對 translation 不 invariant，常數會改變解。可考慮：

把每人的 disagreement utility $d_i$ 明確定義；
最大化 $\sum_i\log(u_i-d_i)$ 並要求 $u_i>d_i$ ；
把 maintenance chores 與 desirable goods 分兩階段配置；
加入補償或工作量 credits。

小型 30-item 問題可用 mixed-integer nonlinear solver、enumeration／branch-and-bound，或以 piecewise-linear approximation 近似 $\log$ 。

四、物品之間的相依性

加性效用假設「有沒有另一件物品」不會改變價值，但情境明顯包含組合：

投影器與串流設備可能互補；
維修工具與故障 lightsaber 可能互補；
兩套餐具可能替代；
高稅物業與維護設備可能產生持續負擔。

可加入 pairwise terms：

u_i(X_i) =\sum_jv_{ij}x_{ij} +\sum_{j<k}q_{ijk}x_{ij}x_{ik}.

$q_{ijk}>0$ 表示 complement， $q_{ijk}<0$ 表示 substitute。線性化時增加 $y_{ijk}=x_{ij}x_{ik}$ ：

\begin{aligned} y_{ijk}&\le x_{ij},\\ y_{ijk}&\le x_{ik},\\ y_{ijk}&\ge x_{ij}+x_{ik}-1. \end{aligned}

這比把某兩位研究員的所有物品價值統一乘 1.1 更貼近題目。舊 social-adjustment 程式只是 shallow copy 後逐人放大整列估值，既不依賴誰獲得哪件物品，也可能被後一段關係覆寫；它沒有實作所列公式。

五、社會互動應如何建模

合作關係可透過不同機制進入：

共用效益

若 $j$ 可由相鄰研究員共用：

u_i =\sum_jv_{ij} \left[ x_{ij}+\sum_{k\ne i}\alpha_{ikj}x_{kj} \right].

$\alpha_{ikj}$ 應隨物品而變；共用顯微鏡可能合理，私人衣物則未必。

團隊任務

為維持基地功能，可加入 coverage constraints：

\sum_{i,j\in C_\ell}x_{ij}\ge r_\ell,

例如維修、醫療、通訊等類別至少有指定數量。

社會穩定

可把效率和 inequity 分開報告，而不是捏成一個難解釋分數：

\max \left( \sum_iu_i, \min_i \tilde u_i, -\operatorname{envy}(X) \right),

其中 $\tilde u_i$ 是經個人尺度正規化後的效用。

六、負值與棄置

題目要求全部貨物分配，但若某件物品對所有人都是負效用，這其實是 chore。硬性分給某人相當於分配負擔。公平分析應至少報告：

誰承擔總 maintenance cost；
是否有補償；
負擔是否輪換；
是否可放入公共 storage 或安全棄置；
長期資源／空間約束。

若必須分配，可設 individual rationality：

u_i(X_i)\ge d_i,

再加入最小化最大負擔或 leximin criterion。對「foldable real estate」等平均值接近零的物品，coefficient of variation 會因分母接近零而爆大；舊表的 CV=57.27 不宜當作穩健的爭議程度。可用 range、MAD 或 pairwise disagreement。

七、四個群組如何比較

題目要求 Alice–Bob、Alice–Charlie、三人及五人四個獨立配置。每個情景應用同一套 procedure：

選出參與者；
重新計算可行配置和個人 total value；
求 utilitarian、NSW／leximin 及 EF1 allocation；
檢查 envy graph、proportional share、總效用和負擔；
列出由 criterion 改變而重新分配的物品；
做 value perturbation sensitivity。

舊輸出曾報告三人及五人配置「proportional=True」，但因 checker 的比例公式錯誤，該布林結果需要由原始 bundle 重新計算，不能保留作結論。

建議的結果表

情景	規則	總效用	最低正規化效用	EF	EF1	最大 envy	chore burden
Alice–Bob	utilitarian	…	…	…	…	…	…
Alice–Bob	NSW	…	…	…	…	…	…
五人	leximin	…	…	…	…	…	…

這種表會讓讀者看到效率與公平交換，而不是把一個 min/max ratio 稱為最終答案。

八、實作驗證

每個 solver 都應有小型可手算測試：

def test_envy_uses_observers_values():
    values = {
        "A": {"g1": 10, "g2": 0},
        "B": {"g1": 1, "g2": 9},
    }
    allocation = {"A": ["g1"], "B": ["g2"]}
    assert is_ef1(allocation, values, ["A", "B"])

另外要驗證：

每件物品恰好一次；
solver status 是 optimal／feasible；
reported utilities 可由 allocation 重算；
negative utility 不會送入 log；
tie-breaking 可重現；
scaling 每人的估值後，公平結論是否合理；
互補項只在兩件物品同屬一人時生效。

結論

火星情境把公平分配中的幾個核心張力放在同一張表上：

最大總價值追求效率，但可集中資源；
Nash welfare 平衡乘法效用，但要求明確正基準；
indivisible goods 常需 EF1 而非完整 envy-free；
chores、共用品與 complementarity 不能由簡單加法完全表達；
社交網絡要透過具體共享或任務機制進入，而非任意放大整列價值。

原分析最重要的修正是：舊「Nash」結果其實不是 Nash，舊 proportional／envy checker 亦不能驗證所報告公平性。重新實作後，文章應呈現多個可追查的配置與 trade-off，讓社群先選擇公平原則，再由最佳化器執行，而不是由一個演算法替人定義公平。

參考資料

Brams, S. J., & Taylor, A. D. (1996). Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press.
Moulin, H. (2003). Fair Division and Collective Welfare. MIT Press.
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3).
Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061–1103.
Bouveret, S., Chevaleyre, Y., & Maudet, N. (2016). Fair allocation of indivisible goods. In Handbook of Computational Social Choice. Cambridge University Press.