| paper | d4-conf-sagt-2023-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Yes. Exact optimization is achievable deterministically with \(m\tau\) type-level queries and at most \(m\tau\) rational type blocks. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a finite school set \(J\), supported applicant types \(T\) with rational masses \(\mu_t\), and rational capacities \(q_j\), where each unit of type mass receives one whole school, can a measurable serial-dictatorship ordering be computed using polynomially many type-level queries so that its welfare is at least half the maximum welfare of any such ordering? In the proposed query model, each query returns the type's favorite school with positive remaining capacity and its value.
Types \(t\in T\) carry masses \(\mu_t\); schools \(j\in J\) have capacities \(q_j\). A schedule orders the population mass, each unit choosing its most-preferred school with remaining capacity. The objective is total welfare, evaluated with type-level queries for the favorite available school and its value.
Theorem 10's oracle returns only \(v_i(S)\), while Mass-OSM-Query also returns the favorite school; the case does not show that its polynomial-query guarantee holds with the paper's value-only information.
fatal: False
The mirror covers the OSM welfare-approximation question in Theorem 10 and proposes a related transportation realization question for Corollary 15. It leaves the Sat-AS hardness result in Theorem 22, the OSA and OSS results, and the truthfulness results without continuous mirrors.
The strongest case I see is narrow: the paper’s matching model has a natural high-multiplicity regime, and its serial-dictatorship question survives aggregation.
My lead anchor is Theorem 10, proved in the paper. For an \(n\)-agent OSM instance, Algorithm 1 uses \(O(n^2)\) value queries and returns an action sequence whose social welfare is at least half the maximum achievable by any action sequence. The benchmark matters: it is the best serial-dictatorship sequence, not the best matching among all feasible matchings.
A second, structural anchor is Corollary 15, also proved in the paper. It says the price of serial dictatorship for maximum-weight perfect bipartite matching is \(1\): for every instance, some maximum-weight matching can be produced by a serial-dictatorship order. This relies on the Pareto-optimality characterization in Theorem 14, which the paper proves while crediting the earlier characterization of Abdulkadiroğlu and Sönmez.
Here is the regime I would use. Consider a large school-placement cohort and a fixed set of schools. Applicants with the same ranking and the same values for schools form a type; the complete type includes both. The city has \(N\) applicants but only \(\tau\) supported types, with \(\tau\) much smaller than \(N\). School capacities scale with the cohort. This is a conditional scenario: it fits markets with recurring preference profiles and proportional capacity, and fits poorly when individualized priorities make nearly every applicant a distinct type.
The mirror keeps each unit’s choice integral. An infinitesimal applicant gets one whole school; the aggregate assignment can be fractional because portions of a type may receive different schools at different positions in the order.
I would give a prover two closely related problems, one for each anchor.
Mass-OSM-Query, mirroring Theorem 10: an instance has a finite school set \(J\), supported applicant types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational school capacities \(q_j\) summing to \(1\), and a best-response oracle. A query gives a type’s favourite school with positive remaining capacity and its value for that school, after a specified prefix state. A solution is a measurable ordering \(\sigma:[0,1]\to T\) whose type masses are \(\mu\), together with the induced school choices and welfare. The question is to compute a high-welfare ordering with few queries. The coordinate in \([0,1]\) records position in the population order.
The direct continuous analogue of Algorithm 1 is to query each type’s current best available school, choose the type with the highest current value, and place as much of that type as possible next—up to the point where either that type’s remaining mass or that school’s capacity is exhausted. Each step exhausts a type or a school, so there are at most \(\tau+|J|\) steps and \(O(\tau(\tau+|J|))\) type queries. The resulting schedule is a valid serial dictatorship. It is a 2-approximation: the block procedure is the greedy capacitated matching algorithm, which achieves at least half the value of an optimal fractional matching; the best serial-dictatorship schedule cannot exceed that fractional optimum. I expect this mirror to be Class A for constant-factor approximation.
Mass-PoSD-Realization, mirroring Corollary 15: with the same masses and capacities, and explicit rational values \(w_{tj}\), find a maximum-welfare mass assignment and a serial-dictatorship schedule that realizes it, or show that no such schedule exists. The assignment variables satisfy \(x_{tj}\ge 0\), \(\sum_j x_{tj}=\mu_t\), and \(\sum_t x_{tj}=q_j\); the welfare is \(\sum_{t,j}x_{tj}w_{tj}\). The proposed result is that an optimum of this transportation LP can always be realized by a mass ordering, giving an exact polynomial-time solution.
There is a natural proof route for that claim. Among maximum-welfare assignments, choose one that maximizes a secondary score for rank improvements, so it is Pareto efficient with respect to the strict rankings. Make a precedence graph whose vertices are the positive cells \((t,j)\): every cell assigning type \(t\) a school preferred to \(j\) must precede \((t,j)\). A cycle would let a small equal mass rotate around the cycle, making every participating portion of a type strictly better off. So the graph is acyclic. Processing its cells in topological order realizes the assignment: by the time a portion of type \(t\) receives \(j\), every school that type prefers to \(j\) has been exhausted. This is a continuum analogue of the paper’s exact matching result, with fractional type flows arising from population mass.
The two problems use different information models. The query version preserves the flavour of Theorem 10. With explicit type values, the LP and schedule construction give a stronger exact result. The high-multiplicity bridge is direct: for rational masses and capacities, clear denominators to obtain a finite cohort with \(N\mu_t\) applicants of each type and \(Nq_j\) places at each school.
I would leave Theorem 22 outside this mirror. It proves that Sat-AS—given a weighted-clause instance and a target Boolean assignment, decide whether some action sequence produces that assignment—is NP-hard. Its reduction encodes Exact-3-Cover through incidence among distinct set and element variables. Aggregating replicated variables into types removes those individual incidence roles; keeping every variable distinct makes the support grow with the population. I do not have a credible continuous SAT-AS formulation that preserves that reduction.
The soft spot in the matching case is whether the authors and a referee accept proportional school capacities and recurring preference types as a faithful high-multiplicity regime. Real placement markets can have individualized priorities, and including them in complete types may make \(\tau\) large. If the finite-support regime is accepted, though, the mirror retains their central operation—agents act in an order and take their best available item—and the continuous question has a concrete LP and schedule construction. Further questions are whether exact optimization remains query-efficient, what lower bounds depend on \(\tau\) and \(|J|\), and how much finite-cohort behavior differs from the mass limit.
The strongest objection is that the proposed mirrors change the information problem. Theorem 10 is about choosing an order when agents’ valuations are available only through value queries. In the high-multiplicity version, a type’s preference list and values can be queried once and reused across its entire mass. If the query also returns the favorite school, as the proposed Mass-OSM-Query does, the oracle gives more information than the theorem’s scalar value query. If those data are explicit, the problem becomes a capacitated matching problem. So the proposed \(O(\tau(\tau+|J|))\) guarantee is not simply Theorem 10 with \(n\) replaced by support size.
That is a real caveat about what result is being mirrored, but it does not defeat the anchor. One can define a faithful type-level oracle and ask how query complexity depends on \(\tau\), \(|J|\), and the bit length of masses and capacities. And the explicit-input version is still a sensible continuous computational question. The block-greedy argument appears to extend: repeatedly assign the highest-valued currently available type-school pair until its type mass or the school capacity is exhausted. The resulting flow is a standard greedy capacitated matching and gives a constant-factor bound against the fractional matching optimum, hence against the best serial-dictatorship schedule. That answer may be familiar, but under ChoCo’s criterion, an easy tractable answer is still a worthwhile mirror.
Corollary 15 is harder to defeat. In the proposed continuum, a maximum-welfare transportation assignment can be chosen Pareto efficient, with a secondary rank-based tie-break if necessary. Build precedence constraints requiring every allocation to a school preferred by type \(t\) to occur before \(t\)’s allocation to a less-preferred school. A directed cycle would permit a small mass rotation along the cycle, improving every participating type while preserving capacities. Pareto efficiency therefore rules out cycles. A topological order of the allocation blocks then gives a serial-dictatorship schedule realizing the assignment: when a block is served, every school its type prefers has already been exhausted. This is a credible exact polynomial-time mirror, not merely an analogy.
The cleanest negative point is thus that these are matching results, and their continuous versions may collapse quickly to a transportation LP plus a precedence argument. But that is a claim about the likely shape or simplicity of the answer, not a reason the questions are ill-posed or outside the programme. Repeated applicant types and proportionally scaling school capacities form a plausible high-multiplicity regime; preferences and values belong in the type, as the programme requires. I cannot honestly make the universal case that no worthwhile mirror survives: both anchors survive their stronger versions. The SAT-AS result is a separate possible anchor, but the other analyst did not rely on it.
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.