| paper | Improving Welfare in One-Sided Matchings using Simple Threshold Queries |
| authors | Thomas L. Ma, Vijay Menon, Kate Larson |
| venue | IJCAI 2021 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Both unit-sum and unit-range valuations have tight uniform worst-case ratio \(\Theta(\tau)\) under the stated unrestricted priority vectors. A polynomial-time algorithm guarantees \(\tau\), and every deterministic one-query-per-pair algorithm has ratio at least \(\tau-1\) on suitable inputs. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given rational type masses \(\mu_\theta\), ordinal preferences and acceptability data, object capacities \(q_j\), a priority vector \(p\), and hidden type-level valuations \(v_\theta\) consistent with the unit-sum or unit-range model, choose one threshold \(t_{\theta j}\) non-adaptively for every type-category pair, observe the bits \(Q(\theta,j,t_{\theta j})\), and output a feasible priority-\(p\) mass assignment \(y\) minimizing the worst-case ratio \(\max_{z\in S_p} SW(z\mid v)/SW(y\mid v)\).
A high-multiplicity one-sided matching market with complete latent types \((P_\theta,A_\theta,v_\theta)\), public masses \(\mu_\theta\), repeated object categories with capacities \(q_j\), mass assignment variables \(y_{\theta j}\), welfare \(SW(y\mid v)=\sum_{\theta,j}y_{\theta j}v_\theta(j)\), and one reusable threshold answer per type-category pair.
The paper's independent agent-object queries become shared cohort-category queries, so its \(\Omega(\sqrt{n})\) construction does not itself establish an \(\Omega(\sqrt{\tau})\) bound for the continuous model.
fatal: False
The mirror covers the adaptive and non-adaptive threshold-query results in Theorems 3–8 over repeated agent types and capacitated object categories; it leaves the purely ordinal lower bound and full-information matching result in Theorems 1–2 outside the main question.
The strongest positive case is a high-multiplicity version of the paper’s threshold-query problem, with repeated agent and object types. My lead anchor is Theorem 3; Theorem 8 supplies a useful lower-bound companion.
Take a large course or school-allocation market with finitely many object categories \(H=\{1,\ldots,r\}\), each having many identical copies. A population type \(\theta\) consists of a complete ordinal preference order \(P_\theta\), acceptability information, and a cardinal valuation vector \(v_\theta\). The society is a rational distribution \(\mu\) over \(\tau\) such types. Category \(j\) has per-capita capacity \(q_j\). Thus \(y_{\theta j}\) denotes the mass of type \(\theta\) assigned to category \(j\), with
\[ \sum_j y_{\theta j}=\mu_\theta,\qquad \sum_\theta y_{\theta j}\le q_j. \]
This is not divisible-object allocation: every individual receives at most one integral object copy; \(y\) records only the aggregate assignment. For rational \(\mu,q,y\), clearing denominators produces an ordinary finite matching with repeated copies.
The welfare is
\[ SW(y\mid v)=\sum_{\theta,j}y_{\theta j}v_\theta(j). \]
A priority-\(p\) assignment maximizes the paper’s rank-based edge weights \(p_{\operatorname{rank}_\theta(j)}\); suitable \(p\) encode rank-maximal, max-cardinality rank-maximal, and fair matchings. A threshold query \(Q(\theta,j,t)\) asks the whole cohort of type \(\theta\) whether \(v_\theta(j)\ge t\). One answer is therefore reusable for all agents of that type.
My lead problem is Continuous Adaptive Threshold Priority Matching, mirroring Theorem 3. Its instance is \((\mu,P,q,p,\epsilon)\), together with hidden type-level valuations consistent with \(P\), under either the unit-sum or unit-range model. The task is to design a deterministic adaptive threshold-query protocol which returns a feasible priority-\(p\) assignment \(y\) satisfying
\[ SW(y\mid v)\ge \frac{1}{1+\epsilon} \max_{z\in S_p}SW(z\mid v), \]
where \(S_p\) is the set of feasible priority-\(p\) assignments. The solution consists of the queries and the resulting assignment; the desired query bound is polynomial in \(\tau,r\), the valuation bit length, and \(\log(1/\epsilon)\), rather than in the total population size.
The anchor is Theorem 3, proved by the authors rather than cited. It states that, for \(\epsilon>0\), Algorithm 2 adaptively asks \(O(c\log n)\) queries per agent, with
\[ c=\left\lceil \frac{\log(n^2/\epsilon)} {\log(1+\epsilon/2)} \right\rceil, \]
and returns either a Pareto-optimal matching with a \((1+\epsilon)\)-approximation to the best Pareto-optimal welfare when \(p=0\), or a priority-\(p\) matching with a \((1+\epsilon)\)-approximation to the best priority-\(p\) welfare when \(p\in\mathcal P\). I would mirror the second branch, since it avoids the extra TTC/Pareto argument while preserving the paper’s central computational problem.
The continuous version is highly plausible. It preserves the agents’ ordinal information, cardinal welfare, threshold queries, rank-based feasibility requirement, and approximation objective. The only change is that many indistinguishable agents are represented by mass and the matching computation becomes a maximum-weight transportation or flow problem. The paper itself explicitly notes that allowing multiple agents to receive the same object requires only capacity copies, which is precisely the large-market scenario above. The expected classification is Class A: geometric threshold rounding followed by a polynomial-time max-weight flow should give the analogue of Theorem 3, with query complexity depending on the number of types and object categories rather than population size.
The main follow-up questions are whether the \((1+\epsilon)\) guarantee survives arbitrary rational type masses, how the query bound depends on the smallest positive mass and input bit length, and whether the Pareto-optimal/TTC branch also admits a clean type-level implementation.
The second problem is Continuous One-Bit Priority Matching, mirroring Theorem 8. Given \((\mu,P,q,p)\), a deterministic protocol must choose one threshold \(t_{\theta j}\) for every type-category pair before seeing any answers. It receives the bits \(Q(\theta,j,t_{\theta j})\) and must output a feasible priority-\(p\) assignment. The question is to determine the smallest worst-case welfare-loss factor
\[ \Lambda_{\mathrm{1bit}}(\tau,r) = \inf_A\; \sup_{v} \frac{\max_{z\in S_p}SW(z\mid v)} {SW(A(v)\mid v)}. \]
Theorem 8, also an in-paper result rather than an outside citation, says that if \(X\) is any of Pareto-optimal, rank-maximal, max-cardinality rank-maximal, or fair, then every deterministic non-adaptive algorithm which always outputs an \(X\)-matching and asks at most one query per agent-object pair has worst-case welfare loss \(\Omega(\sqrt n)\), for both unit-sum and unit-range valuations.
The natural continuous question is whether the corresponding bound is \(\Omega(\sqrt{\tau})\), with \(\tau\) replacing the number of named agents. A finite hard instance can be replicated \(M\) times by duplicating every agent and object copy; the population becomes \(M\tau\), while the number of distinct types remains \(\tau\) and the welfare ratio is unchanged. Thus the lower bound would become a genuine statement about type-level information, not about the absolute population size. I expect a type-parameterized Class A boundary: flow computation remains polynomial for fixed query information, but one-bit elicitation retains an information-theoretic approximation barrier of roughly \(\sqrt{\tau}\). Whether that barrier disappears when \(\tau\) is fixed is itself an interesting continuum question.
The weakest point is that repeated object categories and capacities are an extension of the paper’s exact one-copy-per-object presentation, even though the authors themselves identify this extension as essentially immediate. Also, Theorem 8’s lower-bound construction may require many distinct valuation types, so it does not show a lower bound when \(\tau\) is genuinely constant. Those are real limitations, but they do not undermine the main mirror: in a large market with repeated cohorts and repeated object slots, the paper’s threshold-query problem remains recognisably the same problem, while its computational parameters shift from population size to the number of economically meaningful types.
The sharpest negative case is that the proposed mirror changes the information model at exactly the point where Theorem 3 gets its content.
In the paper, the input is \(I=(N,H,P)\); the cardinal valuation profile \(v\) is not part of the instance. Each agent may independently have any \(v_i\in V_I\), and threshold queries reveal information about those private values. Under ChoCo’s definition, however, a type must include every feature relevant to the problem, including \(v_i\). This creates a dilemma.
If \(\mu\) is genuinely a distribution over complete types \((P,A,v)\), then the valuation vectors are already part of the society description. The threshold queries are redundant. If \(\mu\) records only ordinal types while the \(v\)'s remain hidden, then it is not a distribution over complete types, and the mass vector does not determine welfare. The proposed instance \((\mu,P,q,p,\epsilon)\) is therefore not a continuous society in the programme’s central sense; it is a partially observed society with an additional oracle model.
The best repair is the proponent’s cohort interpretation: a publicly identified cohort \(\theta\) has mass \(\mu_\theta\), common ordinal preferences, and one hidden shared valuation vector \(v_\theta\). A threshold query is asked once of the cohort. This is coherent, but it is no longer the paper’s original uncertainty model. It restricts the valuation profile to the diagonal case in which all agents in a cohort have identical cardinal utilities. The paper’s theorem concerns independent private information; the proposed theorem concerns batch elicitation from publicly known cohorts.
Moreover, after those cohort-level answers are received, the remaining problem is simply a transportation problem:
\[ \sum_j y_{\theta j}=\mu_\theta,\qquad \sum_\theta y_{\theta j}\le q_j. \]
For rational data, clearing denominators turns \(y\) back into an ordinary matching with repeated copies. Thus the continuum contributes no new matching object or new computational structure; it is a compressed encoding of a finite repeated instance. That may be a useful engineering model, but it is not clearly a continuous-population version of the paper’s computational question. The threshold part is a new cohort-query problem, while the allocation part is ordinary weighted matching in disguise.
Theorem 8 is weaker still as a population anchor. Its \(\Omega(\sqrt n)\) lower bound is driven by \(n\) independently varying agent–object valuation relationships. Replicating every hard agent \(M\) times does not make the lower bound population-driven: the number of distinct complete types remains \(n\), every copy gives the same answer, and the lower bound remains \(\Omega(\sqrt n)=\Omega(\sqrt{\tau})\), independent of \(M\). This is the original hard instance written with normalized masses.
Conversely, if one keeps \(\tau\) small while allowing agents with the same ordinal preferences to have heterogeneous cardinal values, then those agents are not the same complete type. A threshold answer cannot be reused across them. One must introduce a distribution over hidden valuation vectors, split mass according to query responses, and specify whether queries reveal individual answers or only aggregate response masses. Either choice defines a new statistical-elicitation model, not the paper’s one-bit-per-agent–object model. In particular, an aggregate answer is not what Theorem 8 lower-bounds.
This defeats the proponent’s literal formulations: Theorem 3 has been converted into a batch-query problem over hidden cohort parameters, and Theorem 8 does not yield a genuinely population-based lower bound. But the universal negative case is ultimately weak. The repaired cohort model is sensible, the aggregate assignment remains integral after denominator clearing, and the programme explicitly permits high-multiplicity restrictions and co-modifications forced by them. Under that permissive standard, Continuous Adaptive Threshold Priority Matching is a legitimate mirror of Theorem 3. I cannot honestly claim that no worthwhile mirror exists; the strongest defensible conclusion is that Theorem 3 survives, while Theorem 8 is poor evidence for a specifically continuous phenomenon.
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.