| paper | A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching |
| authors | Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, A. Voudouris |
| venue | AAAI 2021 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
Given finite \(T\) and \(J\), rational type masses \(\mu_t\) and item supplies \(q_j\) with \(\sum_t\mu_t=\sum_jq_j=1\), known rankings \(\succ_t\), and oracle access to each type's common valuation vector \(v_t\), design a deterministic algorithm that makes at most \(1+\lambda+\lambda\lceil\log_2|J|\rceil\) queries per positive-mass type and returns \(x=(x_{tj})\) satisfying \(x_{tj}\ge0\), \(\sum_jx_{tj}=\mu_t\), and \(\sum_tx_{tj}=q_j\); determine its worst-case distortion \(\sup_v \frac{\max_{x'\in\mathcal X(\mu,q)}W(x';v)}{W(x;v)}\), where \(W(x;v)=\sum_{t,j}x_{tj}v_t(j)\), and whether \(2\eta^{-1/(\lambda+1)}\) is achievable for \(\eta=\min(\{\mu_t:\mu_t>0\}\cup\{q_j:q_j>0\})\).
A high-multiplicity assignment market with finite agent types \(t\in T\), masses \(\mu_t\), finite item categories \(j\in J\), supplies \(q_j\), common valuation vectors \(v_t\) accessed by type-level queries, and a mass transport \(x_{tj}\) maximizing additive welfare.
The mirror assumes that agents sharing a complete valuation type are identifiable and that one query can be reused across their mass; the paper's original oracle does not provide this cohort information, so the query-sharing convention must be formalized explicitly.
fatal: False
The mirror securely covers the constructive tradeoff of Theorem 2; it leaves Theorem 1, Theorems 4–7, Theorem 8, and the general framework of Theorem 9 unmirrored.
There is a credible mirror here, although it is an algorithmic rather than a hardness-based case. The paper contains no named NP-hardness theorem of its own for One-Sided Matching; its strongest usable anchors are the proved query–distortion algorithms.
The natural high-multiplicity model is this. Let \(T\) be a finite set of latent agent types, with mass distribution \(\mu\), \(\sum_t\mu_t=1\). Type \(t\) has an ordinal ranking \(\succ_t\) and a private cardinal valuation \(v_t\). Let \(J\) be a finite set of item categories, with per-capita supplies \(q_j\), \(\sum_jq_j=1\). A feasible allocation is a mass transport
\[ x_{tj}\ge 0,\qquad \sum_jx_{tj}=\mu_t,\qquad \sum_tx_{tj}=q_j. \]
Every individual receives one whole item; \(x_{tj}\) is only the aggregate mass of identical agents receiving item \(j\). Its welfare is
\[ W(x;v)=\sum_{t,j}x_{tj}v_t(j), \]
and the benchmark is the maximum-welfare transport. When \(\mu\) and \(q\) are rational, clearing denominators gives an ordinary finite matching instance, and conversely every finite matching induces such an \(x\). This is therefore a genuine population continuization, not merely fractionalizing an individual’s bundle.
The lead anchor is Theorem 2, proved in this paper. It states that \(\lambda\)-TSF makes \(1+\lambda+\lambda\log n\) value queries per agent and achieves distortion \(2n^{1/(\lambda+1)}\) for unrestricted valuations. The algorithm queries each agent’s top value, uses binary search to locate value thresholds, constructs lower-bounding step-function valuations, and computes a maximum-weight matching under those simulated values.
Its continuous counterpart should be called Continuous \(\lambda\)-Query Mass Matching:
Given \((T,\mu,J,q,\succ)\), a query oracle returning \(v_t(j)\), and an integer \(\lambda\), design a deterministic query algorithm that asks at most \(1+\lambda+\lambda\lceil\log_2|J|\rceil\) queries per positive-mass type and returns \(x\in\mathcal X(\mu,q)\). Its distortion is
\[ \sup_v \frac{\max_{x'\in\mathcal X(\mu,q)}W(x';v)} {W(x;v)}. \]
A natural type-level analogue of \(\lambda\)-TSF uses
\[ \eta=\min\bigl(\{\mu_t:\mu_t>0\}\cup\{q_j:q_j>0\}\bigr) \]
and thresholds \(\alpha_\ell=\eta^{\ell/(\lambda+1)}\). The target theorem is
\[ \operatorname{dist}\le 2\eta^{-1/(\lambda+1)}. \]
When all agents and item copies have mass \(1/n\), this becomes exactly the paper’s \(2n^{1/(\lambda+1)}\) bound. The expected classification is Class A: after the queries, the simulated problem is a transportation LP, and the proof of Theorem 2 carries over with sums over agents replaced by sums over type mass. In a realistic regime with a few recurring resident, applicant, or patient profiles and item categories having macroscopic supplies, \(\eta\) is bounded away from zero and the guarantee becomes constant.
This is recognizable as the authors’ problem: ordinal preferences remain the initial information, cardinal values remain private and queryable, each agent still receives one item, and the objective is still welfare distortion. The only substantive change is that a query to one representative of type \(t\) reveals the common value shared by all members of that type.
A second, more specialized anchor is Theorem 3, also proved here. It says that on \(k\)-well-structured instances—where the items are partitioned into \(A_1,\ldots,A_{k+1}\), \(|A_1|=1\), \(|A_\ell|=\lceil\varepsilon n^{(\ell-1)/k}\rceil\) for \(2\le\ell\le k\), and every agent ranks every item in \(A_\ell\) above every item in \(A_{\ell+1}\)—the algorithm \(k\)-FMM makes \(k\) queries per agent and achieves distortion \(O(k n^{1/k})\). It queries the least-preferred item in each of \(A_1,\ldots,A_k\), assigns that value to the whole corresponding block, assigns zero to \(A_{k+1}\), and computes a maximum-weight matching.
The corresponding problem is Continuous \(k\)-WS Mass Matching. The instance contains the same block partition, a finite distribution of agent types whose rankings respect the block order, and rational type masses. The algorithm may query the least-preferred item in each of the first \(k\) blocks once per type, constructs the blockwise simulated valuation, and must return a feasible mass matching satisfying
\[ \operatorname{dist}\le Ck n^{1/k} \]
for a universal constant \(C\). The natural expectation is again Class A: the maximum-simulated-welfare step is a transportation LP, while the proof of Theorem 3 uses only block capacities, type masses, and ranking monotonicity. This is arguably the most convincing scenario-level mirror, since the paper’s own structured regime already describes populations that agree on broad item classes while differing within them.
The many-agent regime is plausible in national school placement, hospital allocation, public housing, or standardized job assignment: thousands of applicants may fall into a few recurring preference/value profiles, while the number of positions or position categories is much larger. The continuous model is useful precisely because it reports that \(16.8\%\) of a recurring profile receives a class of positions, rather than tracking every named applicant.
The main weakness is the query accounting. The paper charges queries per named agent, whereas the mirror charges them per type because identical agents share the same latent valuation vector. If the authors insist that cardinal values may differ within an ordinally identical group, then that group was not one type in the programme’s sense, and the mirror loses its high-multiplicity advantage. I think the type-level query convention is nevertheless the correct one: it follows directly from treating a type as a complete description and is exactly what makes the high-multiplicity regime computationally meaningful.
This case covers Theorems 2 and 3, not the paper’s lower bounds such as Theorems 6 and 7. Those adversarial constructions tailor valuations to individual agents and therefore provide much weaker continuous mirrors. The further questions are whether type-level query reuse improves the paper’s tradeoffs, whether the optimum distortion depends on \(|T|\) rather than \(\eta\), and whether finite-population rounding preserves the guarantees with a controlled additive loss.
The strongest negative case is that the proposed mirror changes the paper’s information model at exactly the point where its results obtain their content.
The paper does contain genuine computational anchors: Theorem 2 gives a query–distortion tradeoff for unrestricted valuation profiles, and Theorem 3 gives a structured-instance tradeoff. So “there is no named result to mirror” is unavailable. Nor is agent identity itself an obstruction: welfare is additive, and aggregate transport is mathematically legitimate.
The difficulty is that a high-multiplicity type must include the entire cardinal valuation vector, not merely the ordinal ranking. In the paper, two agents may have identical rankings but completely different cardinal values; indeed, that hidden cardinal heterogeneity drives the lower bounds. If agents with the same ranking but different values are kept distinct, there is no high multiplicity. If they are merged into one type, a single query reveals \(v_t(j)\) for every member of mass \(\mu_t\). That is not a harmless replacement of sums by integrals: it changes the query resource from “queries per private agent” to “queries per publicly identified valuation type.”
The type-level oracle also grants information absent from the paper. The algorithm must know which agents share a complete valuation type before one representative’s answer can be reused. If type labels are public, the model has added cohort information; if they are hidden, a query to one ordinally similar agent cannot safely be applied to the others. Either choice produces a different elicitation problem. The continuous theorem may be sensible, but it no longer mirrors the paper’s unrestricted query-distortion problem.
The parameter \(\eta\) exposes the same dilemma. If every item remains a distinct scarce item, then some \(q_j=1/n\), so \(\eta\le 1/n\) and the proposed bound \(2\eta^{-1/(\lambda+1)}\) merely reproduces the paper’s \(n\)-dependence after normalization. The population has been made continuous, but the relevant scarcity scale remains discrete. If instead items are aggregated into macroscopic categories so that \(\eta\) is bounded away from zero, the original item-level matching problem has been replaced by a finite transportation problem over categories. With finitely many types and categories, querying all type–category values gives the exact optimum after finitely many queries independent of population size. That is a reasonable cohort-assignment problem, but the paper’s asymptotic query tradeoff has disappeared rather than been continuized.
Theorem 3 is even less stable as a mirror. Its \(k\)-well-structured condition is built around item-block cardinalities depending on \(n\). Under mass normalization, the block \(A_\ell\) has mass \(|A_\ell|/n\); the first block has mass \(1/n\), while the important \(n^{1/k}\) factor is really the inverse scale of increasingly tiny item blocks. As \(n\to\infty\), the crucial singleton block becomes measure zero. Keeping those blocks preserves microscopic item atoms and hence the discrete construction; replacing them with positive-mass categories requires a new capacity-parameterized theorem, not a direct continuous mirror of Theorem 3.
Thus the best case against the proposal is a dichotomy: preserve the paper’s private, per-agent query semantics and high-multiplicity disappears; share full valuation types and the query problem changes; keep all item identities and the continuous guarantee retains the discrete scarcity scale; aggregate items and the structured theorem becomes a different transportation model.
This negative case is not airtight. A realistic cohort model—recurring applicant profiles, publicly known item categories, common cardinal values within cohorts—does give a coherent high-multiplicity assignment problem, and the Theorem 2 proof plausibly transfers to it. The honest conclusion is therefore that the universal claim “no worthwhile mirror in any scenario” cannot be sustained. The strongest objections defeat the proposed framing of the anchors, especially Theorem 3, but a genuine Class A mirror of Theorem 2 remains available.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.