Fairness in Repeated Matching: A Maximin Perspective

There is a defensible mirror, and I would lead with a deliberately Class B example: the continuous-population version of the paper’s identical-valuation problem.

My anchor is Theorem 5.4, the paper’s optimalidenticalhardness result, proved in this paper. It states that, given a repeated-matching instance \(\mathcal I=(N,G,T,\{u_i\}_{i\in N})\) in which all agents have the same valuation function, finding a sequence of matchings maximizing the final bottleneck value is NP-complete. In decision form: given \(\kappa\), deciding whether there is a sequence \(S\) of \(T\) matchings with \(b^T(S)\ge \kappa\) is NP-hard even when \(u_i=u_{i'}\) for every pair of agents. The proof establishes this through Promise Balanced Partition, using instances with \(n=m=k\), \(T=k/2\), and utilities \(u_i(g_j)=e_j\) independent of \(i\).

I would call the mirror Continuous Identical-Type Repeated Matching. Its population consists of one agent type \(a\) with mass \(\mu_a=1\). The type is completely described by a common utility function \(u:G\to\mathbb Q_{\ge0}\). There are \(T\) rounds and a finite set of goods \(G\). Each good \(g\) has per-round supply \(q_g\), measured in population mass. A feasible outcome is a measurable assignment of every infinitesimal agent to a sequence \(\sigma=(g_1,\ldots,g_T)\in G^T\), subject to \(\lambda(\{x:g_t(x)=g\})\le q_g\) for every round \(t\) and good \(g\). Every unit of mass still receives one integral good in every round; only the mass of agents assigned to different sequences is divisible.

The decision question is:

\[ \text{Does there exist a feasible assignment such that } \operatorname*{ess\,inf}_{x}\sum_{t=1}^{T}u(g_t(x))\ge \kappa? \]

Equivalently, let \(y_\sigma\) be the mass assigned to sequence \(\sigma\). Then \(\sum_\sigma y_\sigma=1\), \(\sum_{\sigma:\sigma_t=g}y_\sigma\le q_g\), and every sequence with \(y_\sigma>0\) must have utility at least \(\kappa\). The optimization version maximizes this essential minimum.

The regime is a large homogeneous population: many devices competing for communication channels, or a large cohort of workers repeatedly assigned to task types, where agents have the same channel- or task-utility vector. Thus the number of agents can be arbitrarily large while the number of types is \(\tau=1\). For the exact high-multiplicity scaling of an \(n\)-agent instance, set \(q_g=1/n\): one discrete use of a good becomes \(1/n\) units of population mass. This is a capacity normalization, not a change to divisible goods.

The authors should recognize this as their problem. It preserves the one-good-per-agent-per-round constraint, repeated additive utility, exclusive per-round use of each good after scaling, and the maximin objective. The only change is replacing named identical agents by a continuum of indistinguishable copies.

I expect hardness to transfer, rather than disappear. Take the paper’s Promise Balanced Partition instance \(E=\{e_1,\ldots,e_k\}\), with total \(\tau\), and construct the continuous instance with \(k\) goods, \(T=k/2\), \(q_g=1/k\), common utility \(u(g_j)=e_j\), and threshold \(\kappa=\tau/2\). Since the total capacity in each round is \(1\), all goods are fully used. The average utility of the continuum is therefore \(T\tau/k=\tau/2=\kappa\). If every infinitesimal agent receives at least \(\kappa\), then almost every agent must receive exactly \(\kappa\). The promise rules out any size-\(k/2\) multiset containing repetitions and summing to \(\tau/2\), so every positive-mass trajectory uses \(k/2\) distinct goods of total value \(\tau/2\). Its complement is a balanced partition. Conversely, a balanced partition yields a feasible continuous schedule by replacing each discrete agent with mass \(1/k\).

Thus the combinatorics live in the goods and their valuation values, not in population multiplicity. This is exactly the programme’s Class B phenomenon: the continuous mirror is meaningful, but the discrete hardness survives because it is driven by the agenda of goods rather than by individually named agents.

The scope claim is intentionally narrow. This mirrors Theorem 5.4, not every result in the paper. It does not claim that the general multi-type version, the anytime version, or the approximation questions have the same complexity. Natural follow-up questions are whether finite type distributions admit a compact flow or column-generation formulation, when continuous schedules can be rounded to large finite populations, and whether changing the supply ratios or allowing several utility types creates Class A cases.

The weakest point is that this mirror has only one population type, so it does not demonstrate a new tractable algorithmic regime; it demonstrates a natural continuous formulation whose hardness transfers. An opponent could also say that the fine-grained capacity \(q_g=1/k\) retains much of the discrete structure. I concede that. But under this programme, that is a limitation of the computational outcome, not a failure of the mirror: a one-type high-multiplicity society is a legitimate continuous population, and Theorem 5.4 is unusually strong evidence that this particular problem remains hard for reasons independent of population multiplicity.