Appendix A: Pure waterfill allocation function for a single service

This appendix defines a pure function \(\mathcal{F}\).

\(\mathcal{F}(C, n, (\rho_c)_{c \in C}, (\tau_c)_{c \in C}, B)\) returns the tuple of tax allocation factors \((F_0,\dots,F_n)\), where:

  • \(C\) is a set of consumer identifiers,
  • \(n \in \mathbb{Z}\) and \(n \gt 0\) is the maximum score,
  • \(\rho_c \in \mathbb{Z}\) is the score assigned by consumer \(c \in C\), with \(-n \le \rho_c \le n\),
  • \(\tau_c \ge 0\) is the tax available from consumer \(c \in C\),
  • \(B \ge 0\) is the budget of the service.

Definitions

Let \(K_{\ge 0} = \{0,1,\dots,n\}\) be the set of non‑negative scores.

For each \(k \in K_{\ge 0}\), let \(C_k = \{c \in C \mid \rho_c = k\}\) be the set of consumers who assigned score \(k\) to the service.

Let \(T_k\) be their total available tax: \[ T_k = \sum_{c \in C_k} \tau_c \]

For each \(j \in K_{\ge 0}\), let \(M_j\) be the cumulative tax available from all consumers who assigned a score of at least \(j\): \[ M_j = \sum_{k=j}^{n} T_k \]

Allocation rule

The factors \((F_0,\dots,F_n)\) are determined by exactly one of the following cases:

  1. If \(M_0 \le B\) then the service is not overfunded, so all consumers fund the service fully.
    Therefore: \(F_k = 1\) for all \(k \in K_{\ge 0}\)
  2. If \(B \le T_n\) then \(C_n\) alone has enough tax to fund the service. Only that group contributes.
    Therefore: \(F_n = B/T_n\) and \(F_k = 0\) for all \(k < n\).
  3. Otherwise, because the sequence \((M_j)\) is monotone non‑increasing, there is a unique \(j \in \{0,\dots,n-1\}\) such that \(M_{j+1} \le B < M_j\). Consumers with scores greater than \(j\) contribute fully, those with scores less than \(j\) do not contribute, and consumers with score \(j\) contribute at a fractional rate. Hence: \[ F_k = \begin{cases} 0, & k < j,\\[4pt] (B - M_{j+1})/T_j, & k = j,\\[6pt] 1, & k > j. \end{cases} \]

Putting this together:

\[ F_k = \begin{cases} 0, & (B \le T_n \text{ and } k < n) \;\;\text{or}\;\; (M_{j+1} \le B < M_j \text{ and } k < j), \\[10pt] 1, & M_0 \le B \;\;\text{or}\;\; (M_{j+1} \le B < M_j \text{ and } k > j), \\[10pt] \dfrac{B}{T_n}, & B \le T_n \text{ and } k = n, \\[10pt] \dfrac{B - M_{j+1}}{T_j}, & M_{j+1} \le B < M_j \text{ and } k = j. \end{cases} \]

Post‑conditions

  • Range: \(0 \le F_k \le 1\) for all \(k\).
  • Monotonicity: if \(k_1 < k_2\) then \(F_{k_1} \le F_{k_2}\).
  • At most one partial group: at most one \(k\) satisfies \(0 < F_k < 1\).
  • Total allocation: \(\sum_{k=0}^n F_k T_k = \min(B, M_0)\).
  • Negative scores excluded: consumers with \(\rho_c < 0\) do not appear in any \(C_k\) and therefore do not contribute.