d4-conf-ijcai-2019-0639

I would build the case around Proposition 2, and stop at one anchor. The paper does not give an NP-hardness or polynomial-time complexity classification; its named algorithmic result is an approximation guarantee. Proposition 2 states that the sequential protocol Max achieves approximation ratio \(1/2\): it considers application pairs \((s_i,t_j)\) in non-increasing order of \(v(s_i,t_j)\), makes a fixed offer of \(t_j\) to \(s_i\) if that student has not already accepted, and stops after \(k\) acceptances or when it has considered every pair. The resulting acceptable matching \(M\) has \(v(M)\ge \tfrac12 v(M^\ast)\), where \(M^\ast\) is the best matching using the students’ actual acceptable topics. This is a result of the paper, though its proof is omitted as similar to the greedy matching argument cited there.

A plausible high-multiplicity setting is a large internship or research-grant programme with many applicants and repeated project tracks. Applicants share standardized public profiles: the same tracks applied to, the same ranking of those tracks, and the same score vector used by the jury. A public type \(q\) records that information and has mass \(\mu_q\). The number of applicants \(n\) can be very large while the number of such types \(\tau\) remains much smaller. Competing offers give applicants different private outside options, so the jury still does not know which offers they will accept. Track capacities and total grants scale with the population; each person receives at most one integral assignment, while assignments aggregated over a type can be fractional.

Here is the mirror I would hand to a prover: Continuous Fixed-Offer Grant Allocation. An instance has finite public types \(q\), topics \(j\), rational masses \(\mu_q\), application sets \(C_q\), rankings \(\succsim_q\), values \(v_{qj}\), topic capacities \(b_j\), and total grant capacity \(\kappa\). A complete type also includes a private outside-option tier \(r\), which determines the acceptable set \(A_{q,r}\), an upper contour set of the ranking or the empty set. The actual mass \(\nu_{q,r}\) of each complete type is hidden; the jury knows \(\sum_r\nu_{q,r}=\mu_q\), but not the decomposition. A protocol may sequentially offer a fixed topic to a chosen mass of a public type. Responses give the exact accepted and rejected masses; acceptors commit to that topic, and rejected mass may receive later offers. The guarantee is worst-case over hidden acceptance profiles and response histories consistent with them, with no probability model.

For the realized hidden society, the benchmark is the omniscient optimum

\[ \operatorname{OPT}(\nu)= \max \sum_{q,r,j\in A_{q,r}}v_{qj}x_{q,r,j}, \]

subject to \(\sum_j x_{q,r,j}\le \nu_{q,r}\), \(\sum_{q,r}x_{q,r,j}\le b_j\), and \(\sum_{q,r,j}x_{q,r,j}\le\kappa\). The continuous problem is: given only the public instance, compute a polynomial-time sequential fixed-offer policy whose final accepted assignment has value at least \(\tfrac12\operatorname{OPT}(\nu)\) for every admissible hidden society. Its solution is the adaptive offer policy and the resulting feasible mass assignment. This asks whether Proposition 2’s guarantee survives when the population and supplies are scaled together, not whether a fractional outcome space is useful.

I expect a \(1/2\)-guarantee to be tractable: the finite result gives a concrete greedy lead, the type support is finite, and the clairvoyant benchmark is a capacitated matching optimization problem. That is a conjecture about the mirror, not a result of the paper. Fractional mass may allow batching or rationing that improves the guarantee, so I would leave open whether \(1/2\) is tight. Further questions include how many aggregate offer rounds are needed, whether the guarantee changes when topic capacities do not scale with population, and which response information suffices for a type-compressed policy.

The scope is just Proposition 2’s sequential fixed-offer approximation problem; I would not claim this mirrors the paper’s flexible-offer or mixed-protocol results. The paper’s original LAMSADE scenario has few, individually distinctive candidates, so the high-multiplicity case needs a different but recognizable application regime. My weakest point is the information model: preserving the paper’s unknown acceptance requires keeping outside-option tiers private, whereas the standard continuous society is often supplied as a known distribution over complete types. The mirror therefore supplies public type masses and treats the latent decomposition as adversarial uncertainty. That extension is deliberate and is the main point a referee could reject. The underlying question still preserves the authors’ matching objective, fixed offers, acceptance uncertainty, and comparison with the best matching under actual acceptances.