d4-conf-sagt-2023-0017 (d4-conf-sagt-2023-0017)

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.

Let \(J\) be a nonempty set of \(m\) schools. A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. School capacities satisfy \(q_j\in\mathbb Q_{>0}\) and \(\sum_jq_j=1\).
Each type has hidden values \(v_{tj}\in\mathbb Q_{\ge0}\) for every school and a hidden strict ranking consistent with these values, using fixed type-specific tie-breaking. All schools are acceptable. Let \(L\) be the total binary encoding length of masses, capacities, and the hidden value and ranking profile.
A measurable ordering is a measurable map \(\theta:[0,1]\to T\) with \(\lambda(\theta^{-1}(t))=\mu_t\), where \(\lambda\) denotes Lebesgue measure; different portions of one type may appear at different positions.
Its serial-dictatorship assignment \(a:[0,1]\to J\) satisfies, almost everywhere, that \(a(s)\) is type \(\theta(s)\)'s highest-ranked school with \(r_j(s)>0\), where \(r_j(s)=q_j-\int_0^s\mathbf1_{\{a(u)=j\}}\,du\ge0\). Each applicant receives one whole school; only the population mass is divisible.
Define \(W(\theta)=\int_0^1v_{\theta(s),a(s)}\,ds\) and \(\mathrm{OPT}=\sup_\theta W(\theta)\) over these measurable orderings. An algorithm represents its output by a finite list of type blocks with rational lengths; types may recur.
The algorithm knows only the support and capacities. A query specifies a type \(t\) and any rational residual vector \(0\le r_j\le q_j\) with \(\sum_jr_j>0\), and returns its highest-ranked school with positive residual capacity and that school's value. Queries are hypothetical and do not consume capacity; computation between queries is unrestricted.
Does a deterministic algorithm using \(\operatorname{poly}(m,\tau,L)\) type-level queries always compute an ordering with \(W(\theta)\ge\mathrm{OPT}/2\), or is this guarantee impossible with polynomially many queries?
Discrete: with \(n\) agents and \(n\) items, welfare within a factor \(2\) of the best ordering is achievable using \(O(n^2)\) value queries ([source](https://link.springer.com/article/10.1007/s00224-024-10196-6)); exact optimization is achievable using \(n^5\) queries returning the chosen item and its value ([source](https://arxiv.org/html/2407.04474v1)).
Continuous: no result settling this exact mass-ordering and query model was located.

Proven result. Under the stated hypothetical-residual oracle, a deterministic algorithm can compute an exactly optimal ordering using \(m\tau\) queries. Its output needs at most \(m\tau\) rational type blocks. Thus the factor-\(2\) guarantee is achievable.

1. Recovering the hidden profile

Fix a type \(t\). Start with \(S=J\) and query the residual vector
\(r_j=q_j\) for \(j\in S\), and \(r_j=0\) otherwise. Record the returned school and value, remove that school from \(S\), and repeat until \(S\) is empty.

Each query is legal because \(S\) is nonempty and every capacity is positive. The returned schools, in order, give the complete strict ranking of \(t\), including its tie-breaking. Their returned values give all \(v_{tj}\).

Doing this for every type uses exactly \(m\tau\) queries. Write \(\rho_t(j)\in\{1,\ldots,m\}\) for the recovered rank, with smaller ranks preferred.

2. A transportation upper bound

Define the transportation polytope
\[ P=\left\{x\in\mathbb R_{\geq0}^{T\times J}: \sum_{j\in J}x_{tj}=\mu_t\ \text{for every }t,\quad \sum_{t\in T}x_{tj}=q_j\ \text{for every }j \right\}. \]

For any admissible measurable ordering and its assignment, define
\(x^\theta_{tj}=\lambda(\{s:\theta(s)=t,\ a(s)=j\})\).
The row sums are \(\mu_t\). The column sums are at most \(q_j\), by nonnegative residual capacities. Since both total assigned mass and total capacity equal \(1\), every column sum must equal \(q_j\). Consequently \(x^\theta\in P\), and
\(W(\theta)=\sum_{t,j}v_{tj}x^\theta_{tj}\).

Therefore, writing
\(M=\max_{x\in P}\sum_{t,j}v_{tj}x_{tj}\),
we have \(\mathrm{OPT}\leq M\).

The polytope is nonempty: \(x_{tj}=\mu_tq_j\) is feasible. It is closed and bounded, so the maximum exists.

3. Selecting an optimum without trading cycles

Among all welfare-maximizing points of \(P\), choose \(x^*\) minimizing
\(H(x)=\sum_{t,j}\rho_t(j)x_{tj}\).

We may choose \(x^*\) rational. Indeed, the standard rational-polytope theorem states that a linear objective on a nonempty bounded rational polytope attains its optimum at a rational vertex. Its hypotheses hold for \(P\) and the rational welfare objective, so \(M\) is rational. The welfare-maximizing face
\(P_M=\{x\in P:\sum_{t,j}v_{tj}x_{tj}=M\}\)
is then a nonempty bounded rational polytope. Applying the same theorem to \(H\) on \(P_M\) gives a rational \(x^*\). The rationality assertion follows from solving the rational linear equations defining an optimal vertex.

Construct a directed graph on \(J\): include \(j\to k\) whenever some type \(t\) satisfies
\(x^*_{tj}>0\) and \(\rho_t(k)<\rho_t(j)\).

We prove that this graph is acyclic. Suppose it contains a simple directed cycle
\(j_1\to j_2\to\cdots\to j_\ell\to j_1\).
For each arc choose a witnessing type \(t_i\), and set
\(\delta=\min_i x^*_{t_i j_i}>0\), with \(j_{\ell+1}=j_1\).
For each \(i\), move mass \(\delta\) of type \(t_i\) from \(j_i\) to \(j_{i+1}\).

This modification is feasible:

• Each transfer preserves its type’s total mass.
• Each cycle school loses and receives exactly \(\delta\).
• The subtracted cells are distinct because the cycle schools are distinct. Every subtraction is at most the original cell mass. Additions therefore cannot cause a negative entry, even when witnessing types repeat.

Consistency of rankings with values gives
\(v_{t_i j_{i+1}}\geq v_{t_i j_i}\).
Hence welfare changes by
\(\delta\sum_i(v_{t_i j_{i+1}}-v_{t_i j_i})\geq0\).
If it increases, maximality of \(x^*\) is contradicted. Otherwise welfare remains maximal, while
\(H\) changes by
\(\delta\sum_i(\rho_{t_i}(j_{i+1})-\rho_{t_i}(j_i))<0\),
contradicting the choice of \(x^*\).

Thus the graph is acyclic. The secondary objective handles value ties: every cycle would strictly improve ranks even if it preserved welfare.

4. Realizing the optimum by rational blocks

Maintain a set \(S\) of schools not yet exhausted, initially \(J\). Repeat the following steps:

• Choose a sink \(j\) of the directed graph induced by \(S\).
• For each type \(t\) with \(x^*_{tj}>0\), append a block of type \(t\) of length \(x^*_{tj}\), using any fixed order of types.
• Remove \(j\) from \(S\).

Every nonempty finite acyclic directed graph has a sink: otherwise, repeatedly following an outgoing arc would eventually produce a cycle. Thus this procedure is well-defined.

We verify its serial-dictatorship behavior inductively. At the beginning of the phase for \(j\), previously processed schools are exhausted and every school in \(S\) retains its original capacity. For every type appearing in this phase, the sink property implies
\(\rho_t(j)<\rho_t(k)\) for every \(k\in S\setminus\{j\}\);
otherwise the graph would contain an outgoing arc \(j\to k\).

The phase’s block lengths sum to
\(\sum_t x^*_{tj}=q_j\).
Consequently, throughout every block interior, \(j\) has positive residual capacity and is that type’s highest-ranked available school. Serial dictatorship therefore assigns the entire phase to \(j\), exhausting it exactly at the phase endpoint. Block endpoints form a finite null set, so they do not affect the required almost-everywhere condition.

Every positive cell contributes one rational block. The total length assigned to type \(t\) is \(\sum_jx^*_{tj}=\mu_t\), so the resulting ordering is admissible. Its assignment realizes \(x^*\), giving
\(W(\theta)=\sum_{t,j}v_{tj}x^*_{tj}=M\).

Combined with \(\mathrm{OPT}\leq M\), this proves
\(W(\theta)=\mathrm{OPT}=M\).
In particular, the supremum defining \(\mathrm{OPT}\) is attained.

5. Query bound and the discrete comparison

All oracle calls occur during profile recovery: exactly \(m\tau\). Subsequent rational optimization and graph operations require no queries. Computation is unrestricted; rational optimization can, for example, be implemented by finite vertex enumeration. Fixed tie-breaking in every algorithmic choice makes the algorithm deterministic. There are at most \(m\tau\) output blocks.

The decisive oracle feature is access to arbitrary hypothetical residual supports. The cited discrete exact-optimization paper instead defines queries through preceding agent sequences, which constrain the available-item sets. [Caragiannis, Mehlhorn, and Rathi, Section 2](https://arxiv.org/html/2407.04474v1#S2). The profile-recovery step here follows directly from the stronger access specified in this task.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument establishes exact optimization with \(m\tau\) queries and at most \(m\tau\) rational type blocks. I found no mathematical gaps or false steps.

1. Profile recovery

Every queried residual vector is legal: its coordinates are rational, satisfy \(0\le r_j\le q_j\), and have positive total residual capacity whenever \(S\ne\varnothing\).

The oracle returns the highest-ranked school in \(S\). Removing each returned school therefore reveals the entire strict ranking, including the fixed tie-breaking. Every school is returned exactly once, so all values are recovered as well.

There are exactly \(m\) queries per type and \(m\tau\) queries overall. This uses the explicitly permitted hypothetical queries; the residual vectors need not arise from an actual preceding ordering.

Assessment: Correct.

2. Transportation upper bound

For any admissible ordering and assignment, the induced masses \(x^\theta_{tj}\) are nonnegative and have row sums \(\mu_t\).

Nonnegative residual capacities imply that each column sum is at most \(q_j\). Total assigned mass and total capacity both equal \(1\), so these inequalities must all be equalities. Thus \(x^\theta\in P\).

The welfare identity follows from partitioning the population by its finitely many type-school pairs. Consequently, \(\mathrm{OPT}\le M\).

The stated feasible point \(x_{tj}=\mu_tq_j\) satisfies both sets of marginal constraints. The polytope is closed and bounded, and the objective is continuous, so its maximum exists.

Assessment: Correct.

3. Rational secondary optimum

The invoked theorem is stated sufficiently precisely: a linear objective on a nonempty bounded rational polytope attains its optimum at a rational vertex.

Its hypotheses hold for \(P\): the masses and capacities are rational, the constraints are linear, and nonemptiness and boundedness have been established. The welfare objective has rational coefficients. Therefore \(M\) is rational.

The optimal face \(P_M\) is consequently another nonempty bounded rational polytope. The rank objective \(H\) has integer coefficients, so the same theorem supplies a rational minimizer \(x^*\).

Assessment: Correct; both theorem applications have their hypotheses verified.

4. Acyclicity of the preference graph

Each edge represents positive assigned mass whose type strictly prefers the destination school.

For a simple directed cycle, \(\delta=\min_i x^*_{t_i j_i}\) is positive. The proposed transfers preserve every row sum and every column sum.

The treatment of repeated witnessing types is valid. Distinct cycle schools ensure that the subtracted cells are distinct, so no cell undergoes multiple subtractions. Incoming additions cannot invalidate nonnegativity.

Ranking consistency gives \(v_{t_i j_{i+1}}\ge v_{t_i j_i}\). Hence the welfare change is nonnegative. A positive change contradicts welfare optimality; a zero change leaves the modified point in \(P_M\).

Every rank difference in the displayed change to \(H\) is strictly negative. Thus, in the zero-welfare-change case, the transfer contradicts minimality of \(H\).

The graph is therefore acyclic, including when values tie.

Assessment: Correct.

5. Realization by rational type blocks

Every nonempty induced subgraph has a sink because the original graph is finite and acyclic. The prover supplies the requisite justification.

For any positive cell \(x^*_{tj}\), the sink condition ensures that \(j\) is strictly preferred by type \(t\) to every other school remaining in \(S\). Strictness of the rankings justifies the displayed rank inequality.

The induction invariant is consistent: previously processed schools are exhausted, while every unprocessed school retains its original capacity. During the phase for \(j\), all participating types choose \(j\), and the phase lengths sum exactly to \(q_j\). Thus \(j\) remains available before the phase endpoint and is exhausted precisely there.

The finite set of block endpoints is null, so its treatment does not affect the almost-everywhere assignment requirement.

The blocks have rational lengths, their type totals equal \(\mu_t\), and their overall length equals \(1\). The resulting ordering is measurable and admissible. Its assignment realizes \(x^*\), establishing \(W(\theta)=M=\mathrm{OPT}\).

Assessment: Correct. The proof establishes attainment, not merely approximation to the supremum.

6. Algorithm, bounds, and edge cases

Finite exact vertex enumeration is sufficient under the task’s unrestricted-computation model. Fixed choices make the algorithm deterministic.

Each positive cell produces one block, giving at most \(m\tau\) blocks. All oracle calls occur during recovery, so the query bound is polynomial in the required parameters.

The argument also covers a single school, a single type, zero values, and tied values. Positive capacities and masses exclude empty school phases and absent support types. No division by welfare occurs, so \(\mathrm{OPT}=0\) causes no exception.

Assessment: Correct.

7. Discrete comparison and complexity classification

The cited comparison is accurate: the discrete paper defines queries by an agent and a preceding agent subsequence, with available items determined by that subsequence. [Section 2 of the cited paper](https://arxiv.org/html/2407.04474v1#S2) supports this statement.

The established complexity result is polynomial query complexity with exact optimization. The write-up permits unrestricted computation and gives finite vertex enumeration as an implementation; it does not establish polynomial running time. Accordingly, the requested continuous_status is "other" under the supplied definitions.

No repair or additional clarification is needed to verify the claimed resolution.

⟨structured verdict parsed — rendered above⟩