d4-conf-aaai-2023-0100

My lead is a continuous version of the paper’s maximum-satisfied-agents problem. The anchor is Theorem 4.11: “\(\textsc{MaxSA-MRM}\) is NP-hard even when the number of rounds (\(k\)) is \(3\).” The paper proves this result here, by reducing from Minimum Vertex Cover on cubic graphs; it cites Garey and Johnson for that source problem’s NP-completeness. In \(\textsc{MaxSA-MRM}\), a solution is a collection of \(k\) matchings, and an agent counts as satisfied only if it is matched in all \(\rho_i\) rounds it requested. The objective is to maximize the number of satisfied agents.

Here is the continuous problem I would ask the authors to study. Call it Max-Satisfied-Mass Multi-Round Matching. An instance has a finite set \(T\) of agent types, with rational masses \(\mu_t\geq 0\) summing to \(1\); a finite set \(U\) of resource types, each with supply density \(\sigma_u\geq 0\) per unit population; and a compatibility relation between agent and resource types. Each agent type \(t\) has a permitted round set \(K_t\subseteq\{1,\ldots,k\}\) and request \(\rho_t\leq |K_t|\).

A full schedule \(p\) for type \(t\) assigns a compatible resource type to each of \(\rho_t\) distinct rounds in \(K_t\). Thus, every agent represented by that schedule receives an integral bundle of assignments. A solution chooses a nonnegative mass \(\lambda_{t,p}\) for each type and its full schedules, subject to
\[ \sum_{p}\lambda_{t,p}\leq \mu_t \quad\text{for each }t, \]
and
\[ \sum_{t,p:\,p(r)=u}\lambda_{t,p}\leq \sigma_u \quad\text{for each resource type }u\text{ and round }r. \]
The objective is to maximize \(\sum_{t,p}\lambda_{t,p}\), the mass of agents receiving all their requested rounds. The \(\lambda\)’s split a type’s population across complete schedules; they do not split an individual agent’s assignments.

A plausible regime is a large employer or public administration assigning staff to office-days over a three-day cycle. Employees with the same days, requested days, and compatible office types form a type; office supplies are desks of each type per employee. There can be many employees and relatively few such profiles. The paper itself describes office sharing and says its agents may be individuals or cohorts, so this remains its multi-round matching problem and its “number of satisfied agents” objective, expressed as a satisfied fraction. It also fits the programme’s scale adjustment: desk supply is recorded per unit of population.

I expect this continuous problem to be Class A, tractable, even though the discrete anchor is NP-hard. Its direct formulation is a linear program over all full schedules, potentially exponentially many if \(k\) is part of the input. But its pricing problem is simple. Given dual prices \(\beta_{ur}\) for resource capacities, the cheapest schedule for type \(t\) picks, for each allowed round \(r\), the compatible resource type with minimum \(\beta_{ur}\), then selects the \(\rho_t\) cheapest distinct rounds in \(K_t\). That gives polynomial-time separation, and hence an exact polynomial-time LP algorithm in the number of types, resource types, rounds, and input bit length. This is a genuine test of whether the discrete hardness dissolves when a type’s mass can be distributed among whole schedules.

The mirror covers Theorem 4.11 and its \(\textsc{MaxSA-MRM}\) problem. It does not claim to cover the paper’s advice-generation hardness or all its multi-round matching results. It raises useful follow-up questions: how closely can the mass solution be rounded for a finite high-multiplicity population, and does adding advice choices preserve tractability or restore hardness?

The soft spot is that the continuum permits different portions of a type to receive different full schedules. That is exactly what population mass means in the proposed model, but the discrete hardness reduction does not itself establish that this large-population regime is important: its construction has many distinct compatibility profiles. I would still defend the mirror because it retains the paper’s satisfaction criterion, rounds, compatibility constraints, and integral service for every served person. Only the aggregate population is continuous.