Fair Division with Prioritized Agents

Yes, there is a credible mirror, but only in a genuine replicated-goods regime. The best case is not cake cutting: each individual still receives an indivisible bundle, while the population and the supply of interchangeable item copies are represented by masses.

Let \(G\) be a finite catalogue of item types, with \(q_g\in\mathbb Q_{\ge0}\) copies of item \(g\) per unit population. An individual bundle is still an integral vector \(b\in\mathbb Z_{\ge0}^{G}\), drawn from a finite allowed bundle family \(\mathcal B\). A type is a complete valuation \(v_\theta\) over \(\mathcal B\), together with its priority status \(p_\theta\in\{P,Q\}\). The society is a rational mass vector \(\mu\), with \(\mu_\theta\) the fraction of agents of type \(\theta\).

The decision variable is

\[ y_{\theta,b}=\text{mass of type }\theta\text{ agents receiving bundle }b. \]

It satisfies

\[ \sum_b y_{\theta,b}=\mu_\theta,\qquad \sum_{\theta,b} b_g y_{\theta,b}\le q_g. \]

A complete allocation has equality in every supply constraint. EF1 is imposed supportwise: whenever \(y_{\theta,b},y_{\theta',b'}>0\), type \(\theta\) must either weakly prefer \(b\) to \(b'\), or prefer \(b\) to \(b'\) after removing one item from \(b'\). EFPRIOR additionally requires

\[ v_\theta(b)\ge v_\theta(b') \]

for every realized bundle \(b\) of a prioritized type and every realized bundle \(b'\) of a non-prioritized type.

This is population continuization, not outcome-space fractionalization. If all quantities have denominator \(N\), multiplying by \(N\) gives \(N\mu_\theta\) discrete agents and \(Nq_g\) indivisible copies. Conversely, every such finite allocation produces \(y\) by normalization. The continuous object records bundle frequencies, so the one-item EF1 repair remains meaningful.

My lead anchor is Theorem 7, proved in this paper: “An EFPRIOR allocation always exists and can be found in polynomial time when all agents in \(P\) have identical valuations.”

The corresponding problem is P-Homogeneous Complete-EFPRIOR\(_\infty\):

Given \((G,q,\Theta,\mu,\mathcal B)\), with all prioritized types sharing one valuation \(v_P\), find a complete mass allocation \(y\) satisfying the supportwise EF1 conditions and no envy from any realized prioritized bundle to any realized non-prioritized bundle.

The natural regime is a large course-registration or benefits-allocation system: millions of applicants, capacities scaling with the applicant population, and a small number of recurring cohorts. For example, many senior students may share the same course requirements and valuation, while ordinary students belong to several other valuation types. Priority, valuation, eligibility, and any other relevant parameter are part of the type, so this is genuine high multiplicity rather than an assumption that different people are interchangeable when they are not. The intended regime has \(N\gg\tau\), with \(\tau\) fixed or at least moderate.

I expect this mirror to be Class A. Theorem 7’s source-agent and cycle-elimination invariant does not depend on the names of the agents in \(P\); in the replicated setting, operations can be batched over type mass. The resulting algorithmic target is polynomial in \(|G|,\tau\), the valuation/bundle-description size, and the encoding length of \(q\) and \(\mu\), rather than in the enormous population size. If the bundle family is exponential, the natural formulation becomes a configuration problem whose pricing oracle is the relevant computational question. That is precisely the kind of continuous-optimization boundary the ChoCo programme is meant to expose.

The paper’s main general result gives a second, more ambitious anchor: Theorem 10, proved here. It states that for arbitrary valuations there is a polynomial-time algorithm producing a partial EFPRIOR allocation with

\[ |B|<\min(|P|,|Q|) \]

and \(v_i(B)\le v_i(A_i)\) for every agent.

Its continuous counterpart is Partial-EFPRIOR\(_\infty\). The solution consists of \(y\) and an unallocated item-mass vector \(r\), satisfying

\[ \sum_{\theta,b} b_g y_{\theta,b}+r_g=q_g, \]

supportwise EFPRIOR, and

\[ \|r\|_1<\min(\mu(P),\mu(Q)). \]

The pool condition becomes \(V_\theta(r)\le v_\theta(b)\) for every type \(\theta\) and every bundle \(b\) in its support, where \(V_\theta\) is the type’s explicitly supplied valuation of an aggregate multiset of remaining item copies. A natural optimization version minimizes \(\|r\|_1\), although Theorem 10 itself promises only the stated bound.

I would also expect this to be Class A in a replicated-item model with an explicit or efficiently queryable bundle/value representation. The four update rules \(U_0\)–\(U_3\) suggest a type-level batched algorithm, and the theorem’s residual bound scales exactly: \(|B|/N\) becomes \(\|r\|_1\), while \(|P|/N\) and \(|Q|/N\) become the two population masses. But this is a weaker positive claim than for Theorem 7. The paper’s \(O(n^2m\max(n^2,m))\) runtime is polynomial in the named-agent input, not automatically polynomial in \(\tau\) and \(\log N\). Establishing the required batching, and solving the resulting bundle-pricing problem, would be genuine new work.

Theorem 8 gives the symmetric \(Q\)-homogeneous complete mirror, but I would not count it as a separate pillar: it is useful confirmation that the idea applies whether the common valuation belongs to the prioritized or non-prioritized cohort, rather than an independent conceptual case.

The mirror does not cover the paper wholesale. It covers Theorem 7 emphatically, and Theorem 10 as a broader extension. It does not claim a solution to the paper’s open problem of complete EFPRIOR under fully general valuations. Nor does it rely on the paper’s cake-cutting background: cake cutting is continuity of the resource, whereas this construction keeps the resources indivisible and continuizes the population.

The weakest point is that the replicated-goods scenario is an extension of the paper’s motivating examples, not their only literal interpretation. If the instance has a fixed number of unique items and an enormous number of agents, EF1 becomes mostly a statement about empty bundles and the mirror degenerates. Likewise, if every item copy is individually distinctive or every agent has an idiosyncratic valuation, then \(\tau\) grows with \(N\) and the high-multiplicity gain disappears. The strongest honest case therefore depends on large administrative markets with recurring item categories, repeated valuation types, and capacities that scale with population. In that regime, however, the mirror preserves the paper’s distinctive question—ex-post fairness for indivisible bundles with priority-sensitive envy—rather than replacing it with ordinary fractional fair division.