Answer: Polynomial-time solvable in the prefix-oracle model, using \(O(\tau^2m^3)\) queries independent of \(D\), and outputting at most \(\tau m\) blocks.
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor n-agent OSM instances with query ac- cess, Algorithm 1 uses O(n5) queries to compute a welfare- optimal action sequence. Our algorithm and its analysis is based on a potential- function based argument.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given publicly known household types T, apartment types J, rational household masses μ and apartment capacities ν, but hidden common values and tie-breaking orders for each type, with an oracle that returns the apartment type and value chosen by type t after any finite rational prefix mass schedule, compute a welfare-maximizing finite block serial-dictatorship schedule using a number of queries polynomial in |T|, |J|, and encoding length, independent of the cleared-denominator population size.
Public input consists of household types \(T\), apartment types \(J\), and positive binary-rational masses \(\mu_t,\nu_j\), with \(\sum_t\mu_t=\sum_j\nu_j=1\). A society is given by its support: the list of types with positive mass and their masses. Write \(\tau=|T|\) for support size, not the number of possible types, and \(m=|J|\).
Each household receives one apartment per unit of mass. Every household type accepts every apartment type and has hidden common values \(w_{tj}\in\mathbb Q_{\geq0}\) and a hidden fixed strict order on \(J\) refining decreasing value. These determine all choices, including ties.
A finite block schedule is \(S=((t_1,a_1),\ldots,(t_k,a_k))\), with positive rational block masses and \(\sum_{\ell:t_\ell=t}a_\ell=\mu_t\). Types may recur. During a block, its mass takes the highest-ranked apartment type with positive remaining capacity, switching when that capacity is exhausted, until the block is served.
A prefix satisfies \(\sum_{\ell:t_\ell=t}a_\ell\leq\mu_t\) for every type. A query \(Q(t,P)\) is allowed when type \(t\) has positive unserved mass after prefix \(P\); it returns the apartment type chosen by the next infinitesimal mass of \(t\) and its exact value. Each query evaluates its prefix from the original capacities, without committing allocations; the prefix may contain earlier mass of \(t\).
If the schedule allocates mass \(x_{tj}\), its welfare is \(\sum_{t,j}w_{tj}x_{tj}\). Optimize over all finite rational block schedules. Let \(L\) be a public upper bound on the total binary encoding length of the instance, including hidden values and orders; let \(D\) be the least common multiple of the public mass denominators.
Is computing a welfare-maximizing schedule in \(\mathrm P\) in this oracle model, with running time polynomial in \(m,\tau,L\) rather than \(D\), or is it NP-hard?
Separately, can such a schedule be computed using polynomially many queries in \(m,\tau,L\), independent of \(D\), with unrestricted computation between queries?
For the discrete model with \(n\) individual agents and \(n\) items, an optimal serial-dictatorship order can be found using \(O(n^5)\) prefix-choice queries, including value ties; the query bound permits unrestricted computation between queries. [Source](https://arxiv.org/html/2407.04474v1)
No result settling this exact continuous prefix-oracle problem was located in the literature search.
Both questions have affirmative algorithmic answers. A welfare-maximizing schedule can be computed in the prefix-oracle model in time polynomial in \((m,\tau,L)\), using \(O(\tau^2m^3)\) queries. The query bound is independent of \(D\).
The algorithm handles hidden value ties and outputs at most \(\tau m\) rational blocks. In fact, its welfare equals the optimum over all feasible fractional allocations.
Define the transportation polytope
\(\displaystyle \mathcal X=\left\{x\in\mathbb R_{\geq0}^{T\times J}:\sum_jx_{tj}=\mu_t\text{ for every }t,\quad\sum_tx_{tj}=\nu_j\text{ for every }j\right\}.\)
This polytope is nonempty: \(x_{tj}=\mu_t\nu_j\) is feasible. It is compact because its coordinates are nonnegative and sum to \(1\). Every complete schedule induces an allocation in \(\mathcal X\).
We first prove a structural lemma for known values and orders.
Lemma. Let \(u_{tj}\) be nonnegative rational values, and let \(r_t(j)\in\{1,\ldots,m\}\) be strict ranks refining decreasing \(u_{tj}\), with smaller ranks preferred. Choose \(x\in\mathcal X\) that first maximizes
\(\displaystyle U(x)=\sum_{t,j}u_{tj}x_{tj},\)
and, among its maximizers, maximizes
\(\displaystyle H_r(x)=-\sum_{t,j}r_t(j)x_{tj}.\)
Then \(x\) can be realized under these orders by a schedule with at most \(\tau m\) blocks. Each block receives only one apartment type. A rational such \(x\), and its realizing schedule, can be computed in polynomial time from the explicitly given data.
Proof. Construct a directed graph on \(J\). Include an arc \(j\to h\) if some type \(t\) satisfies \(x_{tj}>0\) and \(r_t(h)<r_t(j)\).
We claim this graph is acyclic. Suppose it contains a simple directed cycle
\(j_1\to j_2\to\cdots\to j_q\to j_1.\)
For each arc choose a witnessing type \(t_i\), so that
\(x_{t_i j_i}>0,\qquad r_{t_i}(j_{i+1})<r_{t_i}(j_i),\)
where \(j_{q+1}=j_1\). Choose
\(0<\varepsilon\leq\min_i x_{t_i j_i},\)
and form
\(\displaystyle x'=x+\varepsilon\sum_{i=1}^q\left(E_{t_i,j_{i+1}}-E_{t_i,j_i}\right),\)
where \(E_{t,j}\) denotes the corresponding unit matrix.
Every summand preserves its row sum, and the cycle preserves all column sums. The subtracted entries have distinct columns, so each is subtracted from at most once; consequently \(x'\) is nonnegative. Thus \(x'\in\mathcal X\), even if some witnessing types recur.
Because the orders refine the values,
\(\displaystyle U(x')-U(x)=\varepsilon\sum_i\left(u_{t_i,j_{i+1}}-u_{t_i,j_i}\right)\geq0.\)
A strictly positive difference contradicts the optimality of \(U(x)\). If the difference is zero, then
\(\displaystyle H_r(x')-H_r(x)=\varepsilon\sum_i\left(r_{t_i}(j_i)-r_{t_i}(j_{i+1})\right)>0,\)
contradicting the secondary optimality. This proves acyclicity.
Choose a sink \(j\). For every \(t\) with \(x_{tj}>0\), apartment type \(j\) is that type’s favorite among all remaining apartment types: otherwise there would be an outgoing arc from \(j\).
Append the blocks \((t,x_{tj})\) for these types, in any order. All their mass chooses \(j\). Their total mass is \(\nu_j\), so these blocks exactly exhaust \(j\), without any block switching apartment types.
Remove \(j\) and repeat on the induced graph. Remaining row sums equal the corresponding unserved household masses. Thus the construction remains feasible and eventually realizes all of \(x\). Each apartment type contributes at most \(\tau\) blocks, giving at most \(\tau m\) blocks.
For computation, first solve the rational linear program maximizing \(U\). Then maximize \(H_r\) subject additionally to \(U(x)=U^*\), where \(U^*\) is the first optimum. Both programs are nonempty and bounded. Exact rational linear programming is polynomial-time solvable and supplies optimal rational solutions of polynomial encoding length; this is the standard rational LP theorem originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319). The graph construction and sink removal are polynomial-time operations. \(\square\)
In particular, applying this lemma to the true values and orders proves that the best schedule welfare equals the unrestricted transportation optimum. The remaining issue is obtaining such a schedule through the oracle.
Write \(j\succ_t h\) for the hidden strict order of type \(t\).
For each type \(t\), maintain:
Because all its arcs are true strict comparisons, \(C_t\) is acyclic.
Initialization. Query \(Q(t,\varnothing)\) once for each type. If it returns value \(v_t\), then
\(v_t=\max_j w_{tj}.\)
Set \(u_{tj}=v_t\) for every \(j\), and initialize \(C_t\) with no arcs. This takes \(\tau\) queries and establishes all invariants.
Proxy orders. For each \(t\), construct a strict order by decreasing \(u_{tj}\). Within each group of equal upper bounds, use a topological order of \(C_t\) restricted to that group.
These proxy orders refine decreasing \(u\) and respect every comparison in \(C_t\). Indeed, an arc between unequal bounds already points from the larger bound to the smaller one, and an arc between equal bounds is respected by the topological ordering.
No claim is made that the proxy orders equal the hidden orders.
Using the current upper bounds and proxy orders, apply the lemma. It produces a proxy-optimal allocation \(x\) and a realizing schedule with at most \(\tau m\) blocks.
Retain, for verification, the intended apartment type of every block. Thus a candidate block has the form \((t,a)\), with intended apartment type \(k\), and all its mass receives \(k\) under the proxy orders.
Verify the blocks sequentially. Before a block, let \(P\) be the prefix of all preceding blocks and query \(Q(t,P)\).
If the response is exactly \((k,u_{tk})\), accept this block and continue. Otherwise update the information as described below and restart with a newly computed candidate.
The verification uses only legal queries: the upcoming block has positive mass, so \(t\) has positive unserved mass after \(P\). Earlier appearances of \(t\) in \(P\) are expressly permitted by the model.
We need the following induction.
Verification property. After any accepted prefix, its actual allocation equals its proxy allocation.
Initially the assertion is immediate. Suppose it holds before a block whose intended apartment is \(k\). Actual and proxy remaining capacities therefore coincide. If the query also chooses \(k\), it is the actual favorite among the currently positive capacities. During this block, no other capacity decreases. Hence \(k\) remains the favorite until exhausted. The intended block mass is at most its remaining capacity, so the entire block receives \(k\), establishing the induction step.
Consequently, at the first failed verification, actual and proxy remaining capacities coincide, and the intended apartment type \(k\) is available.
Suppose the failed query for type \(t\) returns apartment type \(j\) and value
\(v=w_{tj}.\)
Apartment type \(j\) is available. Since the proxy would choose \(k\), its ordering implies
\(u_{tk}\geq u_{tj}\geq v.\)
Moreover, the actual choice of \(j\), with \(k\) available, implies
\(w_{tk}\leq v.\)
If \(j\ne k\), it also reveals the true strict comparison \(j\succ_t k\).
Perform these updates:
All updates preserve the upper-bound invariant. The first two do so by the inequalities just proved. For propagation along a true comparison \(a\succ_t b\),
\(w_{tb}\leq w_{ta}\leq u_{ta},\)
so lowering \(u_{tb}\) to \(\min\{u_{tb},u_{ta}\}\) is safe.
Propagation is computable in polynomial time. More explicitly, if \(\widetilde u\) denotes the bounds immediately before propagation, the final bound at \(b\) is
\(\displaystyle u_{tb}=\min\{\widetilde u_{ta}:a=b\text{ or there is a directed path from }a\text{ to }b\text{ in }C_t\}.\)
Every ancestor \(a\) truly precedes \(b\), so this formula also directly verifies that the resulting bound is at least \(w_{tb}\).
Progress claim. Every failed verification either strictly decreases an upper bound or adds a previously absent comparison arc.
If \(j=k\), failure means \(v\ne u_{tk}\). Since \(v\leq u_{tk}\), the bound strictly decreases.
Suppose \(j\ne k\), and no bound decreases. Then the first two updates imply
\(u_{tj}=u_{tk}=v.\)
The proxy selected \(k\) while \(j\) was available, so it ranks \(k\) ahead of \(j\). If \(C_t\) already contained the arc \(j\to k\), the proxy order would rank \(j\) ahead of \(k\). Therefore this arc was absent, and adding it gives new information.
This argument explicitly covers value ties.
Every upper bound in row \(t\) is always one of that row’s true values:
There are at most \(m\) distinct true values in a row. Bounds never increase, so each entry decreases strictly at most \(m-1\) times. Across all entries there are at most
\(\tau m(m-1)\)
strict decreases.
Every added comparison has the orientation specified by the hidden strict order. Thus each unordered apartment pair can contribute at most one arc per type, for a total of at most
\(\displaystyle \tau\binom m2\)
arc additions.
By the progress claim, the number of failed candidate verifications is at most
\(\displaystyle R=\tau m(m-1)+\tau\binom m2=\frac32\tau m(m-1).\)
Therefore some candidate eventually passes every verification.
For that candidate, the actual allocation is \(x\), and every used entry has its actual value equal to its upper bound. Hence
\(\displaystyle \sum_{t,j}w_{tj}x_{tj}=\sum_{t,j}u_{tj}x_{tj}=\max_{y\in\mathcal X}\sum_{t,j}u_{tj}y_{tj}.\)
For every feasible allocation \(y\in\mathcal X\), nonnegativity and the upper-bound invariant give
\(\displaystyle \sum_{t,j}w_{tj}y_{tj}\leq\sum_{t,j}u_{tj}y_{tj}\leq\max_{z\in\mathcal X}\sum_{t,j}u_{tj}z_{tj}=\sum_{t,j}w_{tj}x_{tj}.\)
Thus \(x\) is a true welfare-maximizing transportation allocation. Its verified schedule realizes it, so the schedule is welfare-maximizing.
Initialization takes \(\tau\) queries. Each candidate verification takes at most \(\tau m\) queries. There are at most \(R\) failed verifications and one successful verification. The total is therefore at most
\(\displaystyle \tau+\tau m\left(1+\frac32\tau m(m-1)\right)=O(\tau^2m^3).\)
This bound does not depend on \(D\), or even on \(L\).
For the running time, every stored upper bound is a true input value, so its encoding length is at most \(L\). The comparison graphs and proxy ranks have polynomial size. Each iteration solves two rational linear programs of polynomial encoding length, performs polynomial-time graph operations, and makes polynomially many queries.
The LP theorem also bounds the encoding lengths of the resulting allocations. Consequently, all block masses and all queried prefixes have polynomial encoding length. There are polynomially many iterations, so the entire oracle algorithm runs in time polynomial in \((m,\tau,L)\).
The output contains at most \(\tau m\) blocks. No expansion into \(D\) individual units is required.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions in substance: its algorithm computes a welfare-maximizing schedule in polynomial oracle time and uses polynomially many queries independently of \(D\). The proof handles recurring household types and hidden value ties correctly.
There is one minor issue: the structural lemma is stated for an arbitrary real optimal allocation, although schedules must have rational block masses. Its computational version explicitly chooses a rational allocation, so the algorithm and its conclusions survive this correction.
The feasibility and compactness claims are correct. The allocation \(x_{tj}=\mu_t\nu_j\) satisfies both sets of marginal constraints, and every coordinate of a feasible allocation lies in \([0,1]\).
Every complete schedule induces an allocation in \(\mathcal X\). Total household demand equals total apartment capacity, and all apartment types are acceptable, so completing the schedule consumes every capacity. Thus the transportation optimum is an upper bound on schedule welfare.
The acyclicity argument is correct.
A simple directed cycle has distinct apartment vertices. Consequently, each subtracted matrix entry occurs at most once, even if a witnessing household type recurs. The stated choice of \(\varepsilon\) therefore ensures nonnegativity. Row sums are preserved separately by each transfer, and column sums are preserved around the cycle.
Each transfer moves mass to an apartment ranked strictly higher by its witnessing type. Because ranks refine decreasing values, every value difference is nonnegative. A positive total contradicts primary optimality; a zero total leaves primary welfare unchanged and strictly improves the secondary objective. Both contradictions are valid.
The sink argument is also correct. A positive allocation entry \(x_{tj}\) at a sink implies that no remaining apartment is preferred to \(j\) by \(t\). Processing the positive entries in that column exhausts exactly its remaining capacity.
Removing exhausted apartment types and considering the induced graph correctly restricts comparisons to available apartments. The remaining row sums equal unserved household masses. There are at most \(\tau\) positive blocks per column, hence at most \(\tau m\) blocks.
Where: The lemma begins “Choose \(x\in\mathcal X\)” and then claims that this \(x\) can be realized by a schedule.
As written, \(x\) may be irrational, whereas the task requires rational block masses.
For a concrete counterexample to this unrestricted statement, take two household types and two apartment types, all masses equal to \(1/2\), all values zero, and both orders ranking apartment \(1\) ahead of apartment \(2\). Every feasible allocation maximizes both objectives: primary welfare is zero, and the secondary objective is fixed by the column sums.
In particular,
\[
x=
\begin{pmatrix}
\alpha & 1/2-\alpha\\
1/2-\alpha & \alpha
\end{pmatrix},
\qquad
\alpha=\sqrt{2}/4,
\]
is such an optimizer, but has irrational entries. A finite schedule with rational block masses and rational initial capacities produces rational allocation entries, so it cannot realize this \(x\).
Severity: Minor for the submitted algorithm. The proof explicitly computes a rational optimum before constructing any candidate schedule, and the unrestricted irrational version is unnecessary.
Minimum clarification: Restrict the lemma’s realization claim to rational \(x\), or state that a rational lexicographic optimizer exists and can be realized. No change to the algorithm is needed.
The invoked theorem is the standard rational linear programming theorem: explicitly encoded rational linear programs can be solved exactly in polynomial bit complexity, with polynomial-size rational optimal solutions when a finite optimum exists. The cited [Khachiyan reference](https://www.mathnet.ru/eng/dan42319) is the foundational polynomial-time linear programming paper.
The applications satisfy the required hypotheses. The first feasible region is nonempty and compact. Its rational optimal value \(U^*\) has polynomial encoding length. Adding \(U(x)=U^*\) leaves a nonempty, bounded rational feasible region for the second optimization. The secondary objective has integer coefficients of polynomial encoding length.
Initialization is valid because all public apartment capacities are positive. The empty-prefix response therefore reveals the type’s maximum value, providing an upper bound for every entry in its row.
Every stored comparison is a true strict comparison, so each comparison graph is acyclic.
The proxy-order construction respects every stored arc. An arc whose endpoint bounds differ points from the larger bound to the smaller bound by the maintained invariant; an arc within an equal-bound group is respected by the chosen topological ordering. The proxy order also refines decreasing proxy values, as required by the structural lemma.
The algorithm does not assume these proxy orders equal the hidden orders.
All queries are legal. Before a positive candidate block, its type has positive unserved mass because the complete candidate schedule has the prescribed row totals.
The accepted-prefix induction is correct. Once actual and proxy capacities agree, a response choosing the intended apartment establishes that it is the actual favorite among available apartments. During that block, only its capacity decreases, so it remains the favorite while its capacity is positive. The block mass does not exceed that capacity.
Exact exhaustion at the block endpoint causes no problem: there is no additional mass in that block requiring another choice.
Thus, at the first failed verification, actual and proxy capacities agree and both the intended apartment and the returned apartment are available.
At a failed query, the inequalities
\[
u_{tk}\geq u_{tj}\geq v,
\qquad
w_{tk}\leq v
\]
follow respectively from the proxy choice, the upper-bound invariant, and the actual choice. When \(j\ne k\), the strict comparison \(j\succ_t k\) is revealed even when the values tie.
Both direct bound updates are safe. Propagation is safe because a true comparison \(a\succ_t b\) implies
\[
w_{tb}\leq w_{ta}\leq u_{ta}.
\]
The ancestor-minimum formula has the stated direction and enforces all comparison inequalities. It is computable in polynomial time on the finite acyclic graph.
The progress claim is correct:
This covers hidden value ties without an unstated tie-breaking assumption.
Every bound remains one of its row’s true values. Initialization, direct revelation, and minima during propagation all preserve this property.
A row has at most \(m\) distinct values, so each entry decreases at most \(m-1\) times. Comparisons are only added, and their true orientations allow at most one directed arc per unordered pair per household type.
Consequently, the failure bound
\[
R=\tau m(m-1)+\tau\binom m2
=\frac32\tau m(m-1)
\]
is correct. Failures causing several changes only consume the available progress faster.
The case \(m=1\) is covered: initialization learns the sole value, and the first candidate passes. Zero values and equal values are also covered.
Successful verification establishes both that the actual allocation equals the candidate allocation and that every positive candidate entry has its actual value equal to its proxy upper bound.
The displayed optimality chain is valid. Nonnegativity of feasible allocations permits coordinatewise upper bounds to be summed, and the candidate maximizes the proxy transportation objective. Hence its actual welfare dominates every feasible transportation allocation, including every schedule allocation.
This proves the claimed stronger conclusion: the output schedule attains the unrestricted transportation optimum.
The explicit query bound
\[
\tau+\tau m\left(1+\frac32\tau m(m-1)\right)
\]
correctly counts initialization, failed candidates, and the successful candidate. It is \(O(\tau^2m^3)\), independently of \(D\).
The running-time argument also checks out in the stated oracle model. Stored values have encoding length bounded by \(L\); comparison graphs and ranks have polynomial size; both linear programs have polynomial encoding length; and their rational outputs have polynomial encoding length. Each queried prefix contains at most \(\tau m\) polynomial-size rational blocks.
Thus the algorithm uses polynomial local computation and polynomially many polynomial-size oracle calls. It never expands the masses into \(D\) units.
The only required repair is the rationality restriction in the structural lemma.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.