Simultaneously Achieving Ex-ante and Ex-post Fairness (d4-conf-wine-2020-0034)

Given a finite type set \(T\) with rational masses \(\mu_t\), complete preference and utility types \(u_t\), item categories \(O\), rational supplies \(\sigma_o\) with \(\sum_o \sigma_o=1\), and a rational target incidence \(x\) satisfying \(\sum_o x_{t,o}=\mu_t\) and \(\sum_t x_{t,o}=\sigma_o\), decide whether there is a finite lottery over measurable assignments in which every agent receives one integral item, every realization is EF1 and Pareto optimal (or SD-EF1 and Pareto optimal), and \(\mathbb{E}[x^{B}]=x\).

A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Realize it as disjoint atomless intervals \(A_t\) of lengths \(\mu_t\), with Lebesgue measure \(\lambda\).
There are \(m\geq1\) item categories \(O\), positive rational supplies \(\sigma_o\) summing to \(1\), and strictly positive rational additive utilities \(u_t(o)\). Complete weak rankings are induced by these utilities; ties are retained. The rational target \(x\geq0\) satisfies \(\sum_o x_{t,o}=\mu_t\) and \(\sum_t x_{t,o}=\sigma_o\). Let \(L\) be the total input bit length.
A realization is a measurable map \(B:A\to O\) giving each agent one integral item and satisfying \(\lambda(B^{-1}(o))=\sigma_o\). Its incidence is \(x^B_{t,o}=\lambda(A_t\cap B^{-1}(o))\).
Pareto optimality excludes any measurable allocation of finite integral bundles \(C:A\to\mathbb Z_{\geq0}^{m}\), with \(\int_A C_o\,d\lambda=\sigma_o\), that weakly improves each agent's additive utility almost everywhere and strictly improves it on a set of positive measure. Bundle sizes in this comparison are unrestricted.
Fairness is required for almost every ordered pair of agents. Use standard EF1; SD-EF1 means that removing at most one item from the envied bundle makes the envier's bundle weakly dominate it in cumulative item counts at every weak ranking threshold.
The implementation question asks whether there exist finitely many realizations \(B^1,\ldots,B^K\) and real weights \(\alpha_k>0\), with \(\sum_k\alpha_k=1\) and \(\sum_k\alpha_k x^{B^k}=x\), every realization being EF1 and Pareto optimal; define the second variant by replacing EF1 with SD-EF1.

For each variant, is this continuous implementation problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite societies with equally many agents and items and strictly positive utilities, both implementation variants are NP-hard. [Aziz](https://arxiv.org/pdf/2004.02554)
In the related discrete single-unit assignment model with strict rankings, testing implementability by Pareto-optimal assignments is NP-complete. [Aziz, Mackenzie, Xia, and Ye](https://arxiv.org/pdf/1409.6076)
No result settling the exact continuous problem defined above was located.

Result

Both continuous implementation variants are \(\mathrm{NP}\)-hard. This holds even when \(\tau=m\), every type mass and category supply equals \(1/m\), all rankings are strict, and the utilities are positive integers.

The proof transfers discrete implementation hardness while explicitly accounting for atomless agents and unrestricted bundle comparisons.

1. Fairness and bundle comparisons

Every realization gives each agent exactly one item. Removing the sole item from an envied bundle leaves the empty bundle. The envier’s singleton has positive utility and has nonnegative cumulative counts at every ranking threshold. Thus every realization is both EF1 and SD-EF1, including with ties.

Consequently, the two implementation questions coincide: both ask for implementation by Pareto-optimal realizations.

The following observation addresses the unrestricted bundles in the definition of Pareto optimality.

Lemma 1. Any feasible bundle allocation that weakly improves a realization almost everywhere gives almost every agent exactly one item.

Proof. Let \(B\) be a realization and \(C\) a feasible weak improvement. For an agent \(a\) of type \(t\), the original utility \(u_t(B(a))\) is strictly positive. Therefore, wherever the improvement inequality holds, \(C(a)\) cannot be empty.

Define the measurable integer-valued function \(s(a)=\sum_{o\in O}C_o(a)\). We have \(s(a)\geq1\) almost everywhere. Feasibility and normalization give

\( \displaystyle \int_A s(a)\,d\lambda(a)=\sum_{o\in O}\sigma_o=1=\lambda(A). \)

Hence the nonnegative function \(s-1\) has integral zero, so \(s=1\) almost everywhere. Modifying a null set if necessary, \(C\) is therefore a singleton realization with the same supplies. \(\square\)

2. The discrete hardness result used

Consider a discrete assignment problem with \(n\) agents, \(n\) objects, strict rankings, and a rational doubly stochastic matrix \(p\). A deterministic assignment is a bijection from agents to objects. It is Pareto optimal if no other bijection weakly improves every agent and strictly improves at least one.

Testing whether \(p\) belongs to the convex hull of the Pareto-optimal permutation matrices is \(\mathrm{NP}\)-complete. This is [Theorem 2 of Aziz, Mackenzie, Xia, and Ye](https://arxiv.org/pdf/1409.6076).

We reduce this problem to the continuous problem. The essential step is an exact equivalence for equal type masses and category supplies.

3. Supported permutations of a continuous realization

Fix \(N\) types and \(N\) categories, with \(\mu_i=\sigma_o=1/N\). Utilities may have ties in this section.

For a realization \(B\), write \(y=x^B\) and define \(D=Ny\). Its entries are nonnegative, and its row and column sums are all \(1\). Thus \(D\) is doubly stochastic.

A bijection \(\pi\) is supported by \(B\) if \(y_{i,\pi(i)}>0\) for every \(i\).

Lemma 2. If \(B\) is Pareto optimal, every supported bijection \(\pi\) is Pareto optimal in the discrete singleton assignment problem with the same utilities.

Proof. Suppose that a supported bijection \(\pi\) is not Pareto optimal. There is another bijection \(\rho\) satisfying

\( \displaystyle u_i(\rho(i))\geq u_i(\pi(i))\quad\text{for every }i, \)

with strict inequality for some \(i_0\).

For every \(i\), the measurable set \(E_i=A_i\cap B^{-1}(\pi(i))\) has positive measure. Choose

\( \displaystyle 0<\varepsilon<\min_{1\leq i\leq N}\lambda(E_i). \)

By atomlessness, each \(E_i\) contains a measurable subset \(F_i\) of measure \(\varepsilon\). Change the item of every agent in \(F_i\) from \(\pi(i)\) to \(\rho(i)\), leaving everyone else unchanged.

For each category \(o\), this change removes mass \(\varepsilon\) from its unique preimage under \(\pi\) and adds mass \(\varepsilon\) through its unique preimage under \(\rho\). Thus every supply is preserved.

Every changed agent weakly improves, and every agent in \(F_{i_0}\) strictly improves. Since \(\lambda(F_{i_0})=\varepsilon>0\), this contradicts Pareto optimality of \(B\). \(\square\)

We use the Birkhoff–von Neumann theorem in the following precise form: every real doubly stochastic matrix is a finite convex combination of permutation matrices. After discarding zero coefficients, every permutation in such a decomposition uses only positive entries of the matrix. Indeed, a zero matrix entry cannot be a positive weighted sum containing a permutation entry equal to \(1\).

Applying the theorem to \(D=Ny\), Lemma 2 yields:

Corollary 3. If \(B\) is Pareto optimal, \(Nx^B\) is a finite convex combination of discrete Pareto-optimal permutation matrices.

4. Discrete Pareto-optimal assignments yield continuous ones

For a bijection \(\pi\), define \(B^\pi(a)=\pi(i)\) for every \(a\in A_i\). Each category receives mass \(1/N\), so \(B^\pi\) is a realization.

Lemma 4. If \(\pi\) is discrete Pareto optimal, \(B^\pi\) is Pareto optimal under the task’s unrestricted bundle comparisons.

Proof. Suppose there were a feasible bundle allocation weakly improving \(B^\pi\) almost everywhere and strictly improving it on a positive-measure set. By Lemma 1, it gives almost every agent a singleton. Let \(C\) denote the corresponding measurable category assignment.

Define

\( \displaystyle Q_{i,o}=N\lambda\bigl(A_i\cap C^{-1}(o)\bigr). \)

Every row sum equals \(N\lambda(A_i)=1\), and every column sum equals \(N\sigma_o=1\). Therefore \(Q\) is doubly stochastic.

Moreover, whenever \(Q_{i,o}>0\), we must have \(u_i(o)\geq u_i(\pi(i))\): otherwise the weak-improvement inequality would fail on a positive-measure set.

The strict-improvement set is partitioned into finitely many type-category cells. At least one cell has positive measure, so there exist \(i_0,o_0\) with

\( Q_{i_0,o_0}>0 \quad\text{and}\quad u_{i_0}(o_0)>u_{i_0}(\pi(i_0)). \)

Decompose \(Q\) into finitely many permutation matrices with positive coefficients. Each constituent bijection weakly improves every agent relative to \(\pi\), because it uses only positive entries of \(Q\). Since \(Q_{i_0,o_0}>0\), at least one constituent assigns \(o_0\) to \(i_0\), and hence strictly improves that agent.

This constituent bijection Pareto dominates \(\pi\), contradicting its discrete Pareto optimality. \(\square\)

Together, the preceding results give the required equivalence.

Proposition 5. For equal masses and supplies \(1/N\), a target \(x\) admits a finite implementation by continuous Pareto-optimal realizations if and only if \(Nx\) belongs to the convex hull of the discrete Pareto-optimal permutation matrices.

Proof. If \(x=\sum_k\alpha_kx^{B^k}\) is such an implementation, Corollary 3 decomposes each \(Nx^{B^k}\) into finitely many discrete Pareto-optimal permutation matrices. Combining these finite decompositions gives one for \(Nx\).

Conversely, a finite convex decomposition of \(Nx\) into discrete Pareto-optimal permutation matrices induces, through the realizations \(B^\pi\), a decomposition of \(x\). Lemma 4 guarantees that every induced realization is Pareto optimal. Zero coefficients can be discarded, as required. \(\square\)

5. Polynomial reduction, including dyadic masses

To accommodate even the interpretation that “binary-rational” masses must be dyadic, pad the discrete instance to a power-of-two size.

Let \(N=2^{\lceil\log_2 n\rceil}\). Add \(N-n\) dummy agents and dummy objects, and define the rational doubly stochastic matrix

\( \displaystyle p'=\begin{pmatrix}p&0\\0&I_{N-n}\end{pmatrix}. \)

Each original agent retains its original ranking and ranks all dummy objects below all original objects. Each dummy agent ranks its own dummy object uniquely first; complete all remaining rankings strictly in any fixed order.

Every permutation matrix appearing with positive weight in a convex decomposition of \(p'\) must assign each dummy agent its own dummy object. This follows from nonnegativity and the zero entries of \(p'\).

For any original bijection \(\pi\), let \(\widehat\pi\) extend it by these fixed dummy assignments. Then

\( \displaystyle \widehat\pi\text{ is Pareto optimal}\quad\Longleftrightarrow\quad\pi\text{ is Pareto optimal}. \)

For the forward implication, any improvement of \(\pi\) extends to an improvement of \(\widehat\pi\). For the reverse implication, any weak improvement of \(\widehat\pi\) must leave every dummy agent with its uniquely best object. The remaining assignment therefore permutes only original objects among original agents; a strict improvement would contradict Pareto optimality of \(\pi\).

Consequently, \(p'\) is a convex combination of Pareto-optimal permutations exactly when \(p\) is.

Now construct the continuous input with \(\tau=m=N\) and

\( \displaystyle \mu_i=\frac1N,\qquad \sigma_o=\frac1N,\qquad x_{i,o}=\frac{p'_{i,o}}N. \)

These masses are positive dyadic rationals. The target has row sums \(1/N\) and column sums \(1/N\), as required.

Let \(r_i(o)\) be the position of object \(o\) in agent \(i\)’s padded strict ranking, with position \(1\) best. Set

\( \displaystyle u_i(o)=i\bigl(N+1-r_i(o)\bigr). \)

These strictly positive integer utilities induce exactly the chosen rankings. They also make the utility vectors pairwise distinct: type \(i\)’s maximum utility is \(iN\). Thus the construction has exactly \(N\) supported types even if identical utility vectors would otherwise be identified.

All utilities are at most \(N^2\), and \(N<2n\). Padding, constructing utilities, and scaling the rational target increase the input length only polynomially.

By Proposition 5, the continuous target is implementable by Pareto-optimal realizations exactly when \(p'\), and therefore \(p\), is discretely implementable.

6. Conclusion

This is a polynomial-time many-one reduction from the cited \(\mathrm{NP}\)-complete discrete problem to each continuous variant. Fairness imposes no additional restriction on these singleton realizations.

Therefore both continuous implementation problems are \(\mathrm{NP}\)-hard. Unless \(\mathrm P=\mathrm{NP}\), neither has an algorithm with running time polynomial in \(m,\tau,L\).

⟨structured verdict parsed — rendered above⟩

The proof resolves both variants: the reduction is correct, and the cited hardness theorem applies to the discrete problem stated. I found no major or minor mathematical issues.

Step-by-step verification

1. Fairness imposes no restriction

This is correct for the realizations in USER_TASK.

Every agent receives a singleton. Removing the sole item from the envied agent’s bundle leaves the empty bundle. The envier’s singleton has strictly positive utility, so the EF1 inequality holds. Its cumulative item counts are nonnegative at every weak ranking threshold, whereas those of the empty bundle are zero, so SD-EF1 also holds.

The argument applies to every ordered pair, which is stronger than the required almost-everywhere condition. Ties cause no difficulty.

Thus both variants reduce to the same implementation question using Pareto-optimal realizations.

2. Lemma 1: unrestricted bundle comparisons

The lemma is correct and addresses a crucial feature of the task.

Strict positivity ensures that an empty bundle cannot weakly improve an agent’s original singleton. Consequently, the measurable total bundle size satisfies \(s(a)\geq1\) almost everywhere.

The displayed integral calculation is valid: there are finitely many categories, feasibility fixes each category’s integral, and both total supply and total agent measure equal \(1\). Hence \(s-1\) is nonnegative almost everywhere and has integral zero, implying \(s=1\) almost everywhere.

The possible exceptional null set does not affect supplies or the positive-measure strict-improvement requirement. The stated null-set modification is therefore legitimate.

No assumption bounding comparison bundle sizes is used.

3. The cited discrete hardness theorem

The citation is accurate. The paper defines its setting using equally many agents and objects with strict preferences, defines random assignments as doubly stochastic matrices, and defines ex post efficiency as membership in the convex hull of Pareto-optimal deterministic assignments. Its Theorem 2 states NP-completeness of testing ex post efficiency. These are exactly the source problem and preference restrictions used by the prover. [Aziz, Mackenzie, Xia, and Ye, *Structure and complexity of ex post efficient random assignments*](https://arxiv.org/pdf/1409.6076)

There is no mismatch between ordinal Pareto optimality in the source problem and the singleton utility comparisons in the reduction: the constructed utilities induce exactly the source rankings.

4. Lemma 2: supported permutations

The argument is correct.

A supported bijection supplies one positive-measure cell for every type. Since there are finitely many types, the minimum of those positive measures is positive, so the chosen \(\varepsilon\) exists. Atomlessness permits measurable subsets of the prescribed measure.

Both the old and new assignments are bijections on categories. Therefore, the changes remove and add exactly \(\varepsilon\) for every category, preserving all supplies. Typewise utility inequalities apply to every selected agent, and the strict inequality produces strict improvement on a set of measure \(\varepsilon>0\).

This contradicts continuous Pareto optimality exactly as defined in the task.

5. Birkhoff–von Neumann and Corollary 3

The theorem is stated in the needed form, and its hypotheses are satisfied: \(D=Ny\) is a finite square, nonnegative real matrix with every row and column sum equal to \(1\).

The support claim is also correct. With positive coefficients and nonnegative permutation entries, a zero entry of \(D\) cannot be used by any constituent permutation.

Lemma 2 therefore applies to every constituent, establishing Corollary 3. The use of real rather than rational incidence entries creates no problem.

6. Lemma 4: discrete assignments yield continuous Pareto optimality

The proof is correct.

Lemma 1 reduces any proposed bundle improvement to a singleton assignment almost everywhere. The resulting matrix \(Q\) has the asserted row and column sums.

A positive entry associated with a strictly worse category would contradict weak improvement on a positive-measure set. Conversely, because there are finitely many type-category cells, a positive-measure strict-improvement set must contain a positive-measure strictly improving cell.

Every positive-weight permutation in the decomposition uses only positive entries of \(Q\), so each weakly improves every discrete agent. The selected strictly improving entry must occur in at least one constituent permutation. That constituent Pareto dominates \(\pi\), giving the required contradiction.

This verifies the converse transfer despite atomless agents and unrestricted bundle comparisons.

7. Proposition 5: implementation equivalence

Both directions follow from the preceding results.

In the forward direction, combining finitely many finite decompositions preserves finiteness, positivity of retained coefficients, and total weight \(1\). In the reverse direction, the realizations \(B^\pi\) have incidence matrices equal to the corresponding permutation matrices divided by \(N\), so their weighted incidence is exactly \(x\).

The proposition establishes the required existence equivalence; it does not require an algorithm for finding the decompositions.

8. Padding and input encoding

The padding argument is sound.

The block matrix \(p'\) is doubly stochastic. Its zero entries force every positive-weight constituent permutation to fix each dummy assignment. The stated equivalence of Pareto optimality for \(\pi\) and \(\widehat\pi\) is valid: dummy agents receive uniquely best objects and therefore cannot surrender them in a weak improvement.

The construction satisfies the continuous input requirements:

• The masses and supplies are positive and normalized.
• Power-of-two padding makes the masses dyadic.
• The target is nonnegative and has the required margins.
• The utilities are strictly positive integers and preserve every padded strict ranking.
• Distinct maximum utilities ensure pairwise distinct utility vectors, justifying the claimed support size.

The bound \(N<2n\) holds for every \(n\geq1\), including \(n=1\). Utilities are at most \(N^2\), and division of target entries by \(N\) increases their bit lengths only polynomially. Thus the construction is a polynomial-time many-one reduction.

9. Final conclusion and scope

The reduction preserves yes-instances and no-instances. Since every realization automatically satisfies both fairness conditions, it establishes NP-hardness of both continuous variants under the stated restrictions.

The conditional exclusion of polynomial-time algorithms unless \(\mathrm P=\mathrm{NP}\) follows. The prover does not claim NP membership or NP-completeness for the continuous problems, and neither is needed to answer the task.

No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩