Appendix C: Tax allocation algorithm

This appendix defines the Greedy Weighted Allocation Algorithm, which allocates each consumer’s tax contributions across public services according to their stated scores. All monetary amounts are denominated in integer units.

Input

Let \(C\) be the set of consumers and \(S\) be the set of services.

For each \(c \in C\), let \(\tau(c) \ge 0\) be the tax contributed by consumer \(c\).

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

For each \(c \in C\) and \(s \in S\), let \(\rho(c,s) \in K\) be the score assigned by consumer \(c\) to service \(s\). Negative scores express dispreference and are excluded from allocation.

For each \(s \in S\), let \(\beta(s) \ge 0\) be the maximum tax allocable to service \(s\) (its budget).

Let \[ w : K_{\ge 0} \to \mathbb{R}_{\ge 0} \] be a fixed weight function assigning a non‑negative weight to each non‑negative score. The canonical weighting used in this document is \[ w(k) = k, \] which treats higher scores as proportionally stronger expressions of preference. No assumption is made about \(w(0)\); it may be zero or positive.

Output

The algorithm computes the following outputs:

  • the tax allocation \(a(c,s)\) of consumer \(c\) to service \(s\) for each \(c \in C\) and \(s \in S\).
  • the final remaining unallocated tax \(\tau_{\text{avail}}(c)\) for each \(c \in C\). Under the constitution, this residual amount is allocated to the UBI pool.

Required properties

  • For all \(c \in C\): \[ \sum_{s \in S} a(c,s) \le \tau(c) \]
  • For all \(s \in S\): \[ \sum_{c \in C} a(c,s) \le \beta(s) \]
  • For all \(c \in C\) and \(s \in S\): \[ \rho(c,s) < 0 \;\Rightarrow\; a(c,s) = 0 \]
  • All allocations satisfy: \[ a(c,s) \ge 0. \]
  • All final unallocated amounts satisfy: \[ \tau_{\text{avail}}(c) \ge 0. \]

Total score of a service

For each service \(s\), define its total score: \[ \sigma(s) = \sum_{c \in C} \rho(c,s). \]

Algorithm

  1. Initialise remaining tax: \[ \tau_{\text{avail}}(c) := \tau(c) \quad \text{for all } c \in C. \]
  2. Initialise all allocations: \[ a(c,s) := 0 \quad \text{for all } c \in C,\, s \in S. \]
  3. Process services in non‑increasing order of total score \(\sigma(s)\). Ties may be broken arbitrarily.
    1. For the current service \(s\), define the per‑score tax buckets: \[ T_k = \sum_{\substack{c \in C \\ \rho(c,s) = k}} \tau_{\text{avail}}(c) \quad \text{for all } k \in K_{\ge 0}. \]
    2. Apply the weighted water‑filling allocation function of Appendix B: Weighted allocation function for a single service: \[ (F_0,\dots,F_{\rho_{\max}}) := \mathcal{F}^{\mathrm{wt}}\!\left( C,\, \rho_{\max},\, \rho(c,s),\, \tau_{\text{avail}}(c),\, \beta(s),\, w \right). \]
    3. For each consumer \(c\), compute: \[ a(c,s) := \begin{cases} 0, & \rho(c,s) < 0, \\[6pt] F_{\rho(c,s)} \,\tau_{\text{avail}}(c), & \rho(c,s) \ge 0. \end{cases} \]
    4. For each consumer \(c\), update: \[ \tau_{\text{avail}}(c) := \tau_{\text{avail}}(c) - a(c,s). \]

Computational complexity

The algorithm operates on two finite maps:

  • \(C \to \mathbb{R}_{\ge 0}\), mapping each consumer to their remaining allocable tax,
  • \(S \to \mathbb{R}_{\ge 0}\), mapping each service to its remaining unmet funding.

Let \(n = |C|\) and \(m = |S|\). When these maps and the per‑service score buckets are implemented using hash‑based structures, lookup, update, and deletion operations run in expected \(O(1)\) time.

Time complexity

Each iteration of the main loop eliminates either:

  • a consumer whose remaining tax has reached zero, or
  • a service whose remaining budget has reached zero.

Since each consumer and each service is removed at most once, the total number of iterations is bounded by \(n + m\). Thus the overall running time is:

\[ O(n + m) \]

Space complexity

The algorithm stores only the two maps, the per‑service score buckets, and a constant amount of auxiliary state. Space usage is therefore:

\[ O(n + m) \]

Practical considerations

Even for large populations, the values of \(n\) and \(m\) remain well within the capacity of a single modern machine. Contemporary hardware can maintain and update millions of map entries with sub‑millisecond operations. Because the algorithm is linear, memory‑bounded, and free of synchronisation bottlenecks, it can be executed comfortably on a single server without requiring distributed computation.