Answer: —
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor any given profile R ∈˜R, a Dutch price sequence (pt)T t=1 is unique, and pT is the unique minimum equilibrium price vector in ΠR. A final observation is that the price vectors in the a unique Dutch price sequence can be identified and connected by applying the “Vickrey-Dutch Auction” (Mishra and Parkes, 2009) in the case when preferences are quasi-linear, and by the Dutch counterpart of the “SA Auction” in Morimoto and Serizawa (2014) in the more general case. More explicitly, for any given profile in ˜R, the unique minimum equilibrium price vector can be obtained by adopting the following dynamic price process.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) housing classes, \(\tau\) tenant types with current classes \(h_t\), binary-rational masses \(\mu_t>0\) summing to \(1\), reservation prices \(\underline p_h\), and rational quasilinear values \(v_{t,0}\) and \(v_{t,h}\), let class supply be \(s_h=\sum_{t:h_t=h}\mu_t\). Each type’s mass can stay in its current home, buy that home at its reservation price, or buy another class at its market price; allocations must clear every class’s supply, and assigned mass must receive a utility-maximizing option. On instances with a componentwise least equilibrium price vector, compute that vector and a market-clearing equilibrium allocation maximizing total purchases, with running time measured in \(m,\tau\), and input bit length \(L\).
A society is given by its support: the list of \(\tau\) tenant types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) housing classes. Type \(t\) has current class \(h_t\), and each class has positive supply \(s_h=\sum_{t:h_t=h}\mu_t\). Reservation prices \(\underline p_h\) are nonnegative binary rationals; values \(v_{t,0},v_{t,h}\) are arbitrary signed binary rationals. Let \(L\) be the total input bit length.
At feasible prices \(p\in\mathbb R^m\) with \(p_h\geq\underline p_h\), type \(t\) can rent its current home with utility \(v_{t,0}\), buy its current home with utility \(v_{t,h_t}-\underline p_{h_t}\), or buy class \(h\neq h_t\) with utility \(v_{t,h}-p_h\). Renting another class is forbidden.
An allocation consists of nonnegative divisible masses \(r_t,b_t,x_{t,h}\), representing these options, with \(r_t+b_t+\sum_{h\neq h_t}x_{t,h}=\mu_t\) and \(\sum_{t:h_t=h}(r_t+b_t)+\sum_{t:h_t\neq h}x_{t,h}=s_h\).
Prices are equilibrium prices when such an allocation assigns positive mass only to utility-maximizing options; ties are allowed. At fixed equilibrium prices, an equilibrium allocation maximizes purchased mass \(\sum_t b_t+\sum_t\sum_{h\neq h_t}x_{t,h}\).
Inputs are promised to admit a componentwise least equilibrium price vector \(p^*\): it is an equilibrium price vector satisfying \(p^*\leq p\) for every equilibrium price vector \(p\).
Can \(p^*\) and an equilibrium allocation maximizing purchased mass at \(p^*\) be computed exactly in time polynomial in \(m,\tau,L\), or is this promised computation NP-hard?
For discrete tenants and individual houses, the Dutch price sequence is unique on a restricted preference domain and terminates at the unique least equilibrium price vector; finite termination is established without a polynomial bit-complexity bound. [Source](https://bibliothek.wzb.eu/pdf/2015/ii15-207.pdf).
No result settling this exact divisible-mass computation was located in the literature search.
The unrestricted promised computation remains unresolved here. I prove a stronger tractable case than fixing the total number of classes:
Construct a directed graph on classes, putting an arc from $h_t$ to $h\neq h_t$ whenever type $t$ could weakly prefer buying class $h$ to staying at reservation prices. If every strongly connected component has at most a fixed number $k$ of classes, the requested computation is polynomial-time solvable, even when $m$ is unrestricted.
In fact, on this subclass, one can determine whether a componentwise least equilibrium price exists and compute it when it does. I also prove that each single-coordinate section of the equilibrium-price set is an interval with polynomial-time computable endpoints. A promised three-class example shows why this interval property does not justify coordinate descent.
Define
$$
a_t=\max\{v_{t,0},\,v_{t,h_t}-\underline p_{h_t}\}.
$$
For class-assignment feasibility, renting and buying the current home can be combined into a staying option with utility $a_t$. Write
$$
u_{t,h}(p)=
\begin{cases}
a_t,&h=h_t,\\
v_{t,h}-p_h,&h\neq h_t.
\end{cases}
$$
An equilibrium class allocation is a nonnegative matrix $y$ satisfying
$$
\sum_h y_{t,h}=\mu_t,\qquad
\sum_t y_{t,h}=s_h,
$$
with $y_{t,h}>0$ only when $h$ maximizes $u_{t,h}(p)$.
This formulation preserves equilibrium feasibility. In one direction, every positively used original staying option must attain $a_t$. In the other direction, any assigned staying mass can be placed on an original staying option attaining $a_t$.
To recover the purchase objective, define
$$
\beta_t=
\begin{cases}
1,&v_{t,h_t}-\underline p_{h_t}\geq v_{t,0},\\
0,&v_{t,h_t}-\underline p_{h_t}<v_{t,0}.
\end{cases}
$$
At given equilibrium prices, the maximum purchased mass equals
$$
\max_y\left(
\sum_t\beta_t y_{t,h_t}
+\sum_t\sum_{h\neq h_t}y_{t,h}
\right),
$$
where $y$ ranges over equilibrium class allocations. Indeed, all external assignments are purchases. Staying mass can all be assigned to buying when $\beta_t=1$, including a utility tie; when $\beta_t=0$, buying the current home is not maximizing.
Given rational prices $p$ of encoding length $B$, equilibrium feasibility and, when feasible, maximum purchased mass are computable exactly in time polynomial in $m,\tau,L,B$.
Proof. First check $p_h\geq\underline p_h$ for every class. Define the demand set
$$
D_t(p)=\{h:u_{t,h}(p)=\max_j u_{t,j}(p)\}.
$$
Construct a network with source, type vertices, class vertices, and sink. Its capacities are:
A flow of value $1$ saturates every source-to-type and class-to-sink arc, because each collection of capacities sums to $1$. Consequently, such flows are exactly equilibrium class allocations.
Give an allowed type-to-class arc cost $-1$ when $h\neq h_t$, and cost $-\beta_t$ when $h=h_t$. Other costs are zero. Minimum cost among flows of value $1$ is the negative of maximum purchased mass.
For exact bit complexity, let $Q$ be the product of the denominators of the masses $\mu_t$. Its binary length is at most the sum of their denominator encoding lengths, hence is $O(L)$. Multiplying capacities and prescribed flow value by $Q$ produces integral capacities and integral flow value $Q$, with polynomial encoding length. The network has $O(\tau+m)$ vertices and $O(\tau m)$ arcs. Polynomial-time algorithms apply to this capacitated minimum-cost-flow problem; see [Orlin’s algorithm](https://pubsonline.informs.org/doi/10.1287/opre.41.2.338).
The integrality theorem used here states that a network-flow polytope with integral capacities and integral prescribed node balances has integral vertices. Our scaled capacities and balances satisfy these hypotheses. A feasible flow polytope is bounded, so a linear cost objective has an optimal vertex, which is integral. Thus an optimal allocation exists with every entry of the form $z/Q$, where $0\leq z\leq Q$.
Exact utility comparisons additionally take time polynomial in $L+B$. Finally, set $x_{t,h}=y_{t,h}$ externally, and assign all staying mass to buying or renting according to $\beta_t$. $\square$
The same argument applies to a submarket of total mass $M\leq1$: prescribe flow value $M$ rather than $1$.
The component algorithm will need a slight generalization of the collapsed model. Staying utilities $a_t$ are fixed constants, while external prices have specified lower bounds $b_h$. Increasing $b_h$ does not change $a_t$.
Consider such a submarket with $n$ classes, positive type masses, and supplies equal to the masses initially occupying each class.
A support pattern $D=(D_t)_t$ consists of a nonempty subset of classes for each type. It is transportation-feasible if some allocation with the required row and column sums uses only pairs $(t,h)$ with $h\in D_t$.
Let $P_D$ consist of prices satisfying $p_h\geq b_h$ and making every class in $D_t$ utility-maximizing for type $t$. Its inequalities are:
If $h_t\in D_t$, then
$$
p_k\geq v_{t,k}-a_t
\qquad(k\neq h_t).
$$
If $j\in D_t$ and $j\neq h_t$, then
$$
p_j\leq v_{t,j}-a_t
$$
and
$$
p_k\geq p_j+v_{t,k}-v_{t,j}
\qquad(k\neq h_t).
$$
Together with $p_h\geq b_h$, these are exactly the comparisons required for all selected options to maximize utility.
Introduce a vertex $0$ whose price is fixed at $p_0=0$. Represent each inequality
$$
p_j\geq p_i+c
$$
by an arc $i\to j$ of weight $c$. An upper bound $p_j\leq d$ becomes an arc $j\to0$ of weight $-d$. The lower bounds provide arcs $0\to h$ of weight $b_h$.
If $P_D$ is nonempty, it has a componentwise least element $d_D$, computable exactly in polynomial time.
Proof. A positive-weight directed cycle contradicts feasibility: summing its inequalities would give $p_i\geq p_i+c$ with $c>0$.
Conversely, suppose no positive-weight cycle exists. Every vertex is reachable from $0$ because of the lower-bound arcs. Let $d_i$ be the maximum weight of a directed walk from $0$ to $i$. Removing a cycle cannot decrease the walk’s weight, so a maximum is attained by a simple path. These maxima are finite, and $d_0=0$.
Appending an arc $i\to j$ of weight $c$ to a maximizing walk gives
$$
d_j\geq d_i+c.
$$
Thus $d$ satisfies all constraints, including those ending at $0$.
For any feasible $p$, summing constraints along a path from $0$ to $i$ shows that $p_i$ is at least its weight. Hence $p_i\geq d_i$. This proves componentwise leastness.
Negating arc weights reduces positive-cycle detection and computation of the maximum path weights to Bellman–Ford. Simple paths have at most $n$ arcs, so all rational arithmetic has polynomial bit length. $\square$
If $D$ is transportation-feasible, every price in $P_D$ is an equilibrium price. Conversely, any equilibrium allocation supplies a transportation-feasible positive support $D$, and its price lies in $P_D$.
Form a universal graph containing every arc that can occur in a support graph:
$$
\begin{aligned}
0&\to h &&\text{with weight }b_h,\\
0&\to k &&\text{with weight }v_{t,k}-a_t
&& (k\neq h_t),\\
j&\to0 &&\text{with weight }a_t-v_{t,j}
&& (j\neq h_t),\\
j&\to k &&\text{with weight }v_{t,k}-v_{t,j}
&& (j,k\neq h_t).
\end{aligned}
$$
Retain distinct weighted arcs with the same endpoints. If the submarket has $\tau'$ types, the number of arcs is
$$
N=O(n+\tau'n^2).
$$
For any feasible support graph, its least vector $d_D$ is determined by a directed spanning tree rooted at $0$ whose arcs are tight.
To justify this, choose a maximum-weight path from $0$ to any vertex $h$. For an arc $i\to j$ of weight $c$, its slack is
$$
d_j-d_i-c\geq0.
$$
The sum of these slacks along the chosen path is $d_h$ minus the path weight, hence zero. Every arc of the path is therefore tight. Every class is reachable from $0$ through tight arcs, so these arcs contain a rooted directed spanning tree. Tightness determines each coordinate as the sum of weights along its tree path.
Enumerate selections of $n$ universal arcs, retain those forming such a tree, and compute their induced price vectors. Check the lower bounds and equilibrium feasibility for each vector. Let $\mathcal V$ be the retained list.
This enumeration takes
$$
N^n\operatorname{poly}(n,\tau',K)
$$
time, where $K$ includes the encoding lengths of all submarket data. Moreover:
The list is nonempty. Indeed, sufficiently high prices make staying optimal for every type, giving an equilibrium; property 2 then supplies a candidate.
For fixed $n$, one can determine whether a componentwise least equilibrium price exists, and compute it when it does, in polynomial time.
Proof. Compute
$$
w_h=\min_{d\in\mathcal V}d_h
$$
coordinatewise, and test whether $w$ is an equilibrium price.
If it is, then for every equilibrium $p$, property 2 supplies $d\in\mathcal V$ with
$$
w\leq d\leq p.
$$
Thus $w$ is componentwise least.
Conversely, suppose a least equilibrium $p^*$ exists. Its positive allocation support has a least supporting price $d_D\leq p^*$. Since $d_D$ is an equilibrium, leastness gives $p^*\leq d_D$, so $p^*=d_D\in\mathcal V$. Every retained candidate is at least $p^*$, and therefore $w=p^*$. The equilibrium test succeeds. $\square$
Return to the original society. Define the directed graph $G$ on classes by including $i\to h$ when some type $t$ satisfies
$$
h_t=i,\qquad h\neq i,\qquad
v_{t,h}-a_t\geq\underline p_h.
$$
This graph is computable by $O(\tau m)$ exact rational comparisons.
The arc condition is necessary for external demand at any feasible price. Indeed, if class $h\neq h_t$ maximizes type $t$’s utility, then
$$
v_{t,h}-p_h\geq a_t,
$$
and consequently
$$
v_{t,h}-a_t\geq p_h\geq\underline p_h.
$$
An absent arc therefore means that the corresponding external option is strictly worse than staying at every feasible price.
Let $C_1,\ldots,C_r$ be the strongly connected components of $G$, ordered topologically: every arc between different components goes from an earlier component to a later one.
Every equilibrium allocation assigns each type only to classes in the component containing its current class.
Proof. For distinct classes $i,j$, let
$$
f_{ij}=\sum_{t:h_t=i}y_{t,j}.
$$
The allocation identities imply
$$
\sum_{j\neq i}f_{ij}
=s_i-\sum_{t:h_t=i}y_{t,i}
=\sum_{j\neq i}f_{ji}.
$$
Thus the external movement masses form a nonnegative circulation on classes. Every positive movement uses an arc of $G$, by the preceding utility comparison.
Aggregate the circulation over each strongly connected component. In the acyclic condensation graph, a source component has no incoming movement. Its balance equation forces its outgoing movement to be zero. Remove it and repeat in topological order. Every movement between different components is zero. $\square$
This lemma concerns allocations, not all preference comparisons. A tenant in an earlier component can still envy a later class. The next construction incorporates exactly those comparisons as lower bounds.
Define
$$
U_h=\max\left(
\{\underline p_h\}
\cup
\{v_{t,h}-a_t:h_t\neq h\}
\right).
$$
At prices $U$, every external option has utility at most $a_t$. Everyone can stay, so $U$ is an equilibrium price.
For a component $C$, its internal utility at prices $q_C$ is
$$
u_t^C(q_C)=
\max\left(
\{a_t\}
\cup
\{v_{t,h}-q_h:h\in C,\ h\neq h_t\}
\right),
\qquad h_t\in C.
$$
Process components in topological order. Suppose prices have been computed for $C_1,\ldots,C_{i-1}$, and let $u_t$ be each previously processed type’s internal utility at those prices. For $h\in C_i$, set
$$
b_h=
\max\left(
\{\underline p_h\}
\cup
\{v_{t,h}-u_t:h_t\in C_1\cup\cdots\cup C_{i-1}\}
\right).
$$
These bounds prevent earlier types from strictly preferring a class in $C_i$ to their assigned internal options.
Solve the internal submarket on $C_i$, with:
Apply Proposition 3. If no componentwise least internal equilibrium exists, stop and report that the original society has no componentwise least equilibrium. Otherwise retain that internal least vector and proceed.
Here $b_h$ is only a lower bound on external prices. The original staying utilities remain $a_t$.
The following property is central.
Lemma 5: extension by high prices. Suppose a processed prefix has internal equilibrium allocations and satisfies all lower bounds imposed during processing. Any internal equilibrium of the next component at its imposed lower bounds extends this prefix to a global equilibrium by setting every remaining price to $U_h$ and assigning all remaining types to stay.
Proof. Consider the possible utility comparisons.
For a type in the prefix or the newly added component:
For an unprocessed type, every option in a processed component is strictly worse than staying, since it would require a backward arc. Every other external option is priced at $U$ and has utility at most $a_t$. Thus staying is maximizing.
The allocations clear supply within each processed component. Unprocessed types occupy their current classes, clearing the remaining supplies. Hence the combined allocation is a global equilibrium allocation. $\square$
Lemma 6. If every component step succeeds, the concatenated vector $\widehat p$ is a componentwise least global equilibrium price.
Proof. The same comparisons as in Lemma 5 show that the concatenated internal allocations are a global equilibrium allocation.
Let $q$ be any global equilibrium price. By Lemma 4, its allocation stays within components. In particular, every type’s global maximizing utility equals its internal utility at $q$.
We prove $\widehat p_{C_i}\leq q_{C_i}$ by induction. For $C_1$, the restriction of $q$ is an internal equilibrium at the original reservation bounds. Leastness of the computed internal vector gives the inequality.
Suppose the inequality holds for every earlier component. For an earlier type $t$, lower internal external prices imply
$$
u_t^{C_j}(\widehat p_{C_j})
\geq u_t^{C_j}(q_{C_j}).
$$
Since $q$ is a global equilibrium, for $h\in C_i$ it satisfies
$$
q_h\geq v_{t,h}-u_t^{C_j}(q_{C_j})
\geq v_{t,h}-u_t^{C_j}(\widehat p_{C_j}).
$$
Together with $q_h\geq\underline p_h$, this proves that $q_{C_i}$ satisfies the bounds $b_h$ used by the algorithm.
Its restricted allocation is an internal equilibrium allocation. Therefore the computed internal least price satisfies
$$
\widehat p_{C_i}\leq q_{C_i}.
$$
Induction proves $\widehat p\leq q$ for every global equilibrium $q$. $\square$
Lemma 7. If the original society has a componentwise least equilibrium $p^*$, every component step succeeds and computes the corresponding restriction of $p^*$.
Proof. Proceed inductively, assuming the processed prefix equals the corresponding prefix of $p^*$.
By Lemma 4, the restriction of an equilibrium allocation at $p^*$ to $C_i$ is internal. Global utility maximization implies that $p^*_{C_i}$ satisfies all imposed lower bounds $b_h$. Thus it is a feasible internal equilibrium.
Let $q_{C_i}$ be any other feasible internal equilibrium at those bounds. Lemma 5 extends it, together with the processed prefix, to a global equilibrium. Global leastness gives
$$
p^*_{C_i}\leq q_{C_i}.
$$
Hence $p^*_{C_i}$ is the componentwise least internal equilibrium. Proposition 3 finds it. This establishes the induction. $\square$
Lemmas 6 and 7 prove that the algorithm correctly detects least-price existence and computes the least vector whenever it exists.
Let $\Delta$ be the product of the denominators of all input valuations and reservation prices, and put
$$
R=\max\left(
\{1\}\cup
\{|v_{t,0}|,|v_{t,h}|:t,h\}
\cup
\{\underline p_h:h\}
\right).
$$
Both have encoding length $O(L)$, and $\Delta a_t$ is integral. Also,
$$
|a_t|\leq2R,\qquad 0\leq U_h\leq3R.
$$
At every processing step,
$$
\underline p_h\leq b_h\leq U_h,
$$
because every preceding internal utility is at least its staying utility $a_t$.
The vector $U_{C_i}$ is an internal equilibrium satisfying these bounds: all internal external options have utility at most $a_t$. Therefore, whenever an internal least equilibrium exists, its coordinates lie between $b_h$ and $U_h$.
Inductively, all computed prices and all imposed bounds are integer multiples of $1/\Delta$:
All weights in a component support graph have absolute value at most $3R$. A tree path in a component of size $n$ has at most $n$ arcs. Thus candidate coordinates have absolute value at most $3nR$ and polynomial encoding length. Successful component outputs additionally satisfy the bound $3R$.
Consequently, the sequential processing introduces no exponential growth in rational encoding length.
Let $k$ be the largest number of classes in a strongly connected component of $G$. The component algorithm runs in time
$$
(m+\tau m^2)^k\operatorname{poly}(m,\tau,L).
$$
It determines whether a componentwise least equilibrium exists and computes it when it does. At that vector, a purchase-maximizing equilibrium allocation is then computable in polynomial time by Proposition 1.
In particular, for every fixed $k$, the promised computation is polynomial-time solvable with unrestricted $m$.
Proof. Component $C_i$ has at most $k$ classes and uses the fixed-dimensional solver of Proposition 3. Its universal graph has
$$
O(|C_i|+\tau_i|C_i|^2)
$$
arcs. Summing its candidate-enumeration costs over components gives the displayed bound, with all remaining work polynomial. The preceding lemmas prove correctness, and Section 4.4 proves the required bit bounds. $\square$
Acyclic case. If $G$ is acyclic, every component has one class. Lemma 4 then forces everyone to stay in every equilibrium allocation. Staying is maximizing exactly when
$$
p_h\geq U_h\qquad\text{for every }h.
$$
Thus the equilibrium-price set is precisely the orthant above $U$, and $U$ is its least element.
Fix a class $h$ and rational prices for all other classes. Let $z=p_h$ vary subject to $z\geq\underline p_h$.
For a type with $h_t\neq h$, let $B_t$ be its best utility among options other than class $h$, and let $A_t$ be the corresponding set of maximizing classes. Both are independent of $z$. Define
$$
c_t=v_{t,h}-B_t.
$$
Its demand set is
$$
D_t(z)=
\begin{cases}
\{h\},&z<c_t,\\
A_t\cup\{h\},&z=c_t,\\
A_t,&z>c_t.
\end{cases}
$$
For a type currently in $h$, its entire demand set is independent of $z$.
The set of feasible values of $z$ that give an equilibrium is empty or a closed interval, possibly unbounded above. Its endpoints are exactly computable using $O(\tau+1)$ equilibrium-flow tests.
Proof. For a subset $S$ of classes, define
$$
F_S(z)=\sum_{t:D_t(z)\subseteq S}\mu_t,
\qquad
s(S)=\sum_{j\in S}s_j.
$$
Equilibrium allocation feasibility is equivalent to the weighted Hall inequalities
$$
F_S(z)\leq s(S)
\qquad\text{for every }S.
$$
Necessity follows because all mass whose entire demand set lies in $S$ must be assigned there.
For sufficiency, consider the flow network from Proposition 1. Any cut of capacity less than $1$ cannot cut a type-to-class arc of capacity $1$. If $T$ is the set of type vertices on the source side and $S$ the class vertices there, this implies $D_t(z)\subseteq S$ for every $t\in T$. The cut capacity is
$$
1-\sum_{t\in T}\mu_t+s(S)
\geq1-F_S(z)+s(S)\geq1.
$$
Thus no cut has capacity below $1$. The max-flow/min-cut theorem supplies a flow of value $1$.
Now examine one type’s contribution to $F_S$.
If $h\in S$, its contribution is $1$ below $c_t$, and at and above $c_t$ it is the indicator of $A_t\subseteq S$. Consequently $F_S$ is nonincreasing in $z$, with each decrease occurring at its threshold. The inequality $F_S(z)\leq s(S)$ defines a closed upper ray, the whole line, or the empty set.
If $h\notin S$, its contribution is zero below and at $c_t$, and above $c_t$ it is the indicator of $A_t\subseteq S$. Hence $F_S$ is nondecreasing, and its inequality defines a closed lower ray, the whole line, or the empty set.
Contributions from types currently in $h$ are constant. Intersecting these conditions with $z\geq\underline p_h$ gives an empty set or a closed interval.
Demand changes only at the thresholds $c_t$. A finite lower endpoint is therefore $\underline p_h$ or a threshold; a finite upper endpoint is a threshold. Test $\underline p_h$, every distinct threshold at least $\underline p_h$, and one rational point above all thresholds and $\underline p_h$. The first feasible tested endpoint is the lower endpoint. The tail test determines whether the interval is unbounded above; otherwise its last feasible threshold is the upper endpoint. There are $O(\tau+1)$ tests, each polynomial-time by Proposition 1. $\square$
The running time includes the encoding length of the fixed prices.
Take three types with current classes $1,2,3$, reservation prices zero, and masses
$$
\mu_1=\mu_2=\frac38,\qquad \mu_3=\frac14.
$$
Set both staying valuations to zero, and every external valuation to $10$. Thus $a_t=0$.
The allocation
$$
y=
\begin{pmatrix}
0&\frac14&\frac18\\
\frac14&0&\frac18\\
\frac18&\frac18&0
\end{pmatrix}
$$
has the required row and column sums. At both $(0,0,0)$ and $(1,1,1)$, every external option is maximizing, so this allocation establishes equilibrium. Nonnegative reservation bounds make $(0,0,0)$ componentwise least.
Now lower only coordinate $h$ from $1$ to any $z\in[0,1)$. Every type not currently in $h$ strictly prefers class $h$: its utility there is $10-z>9$, while its other external utility is $9$ and staying utility is zero. The forced demand for $h$ is therefore
$$
1-s_h>s_h,
$$
because each supply is less than $1/2$. No equilibrium allocation exists.
Thus coordinate descent can stop at $(1,1,1)$ even though the promised least equilibrium is $(0,0,0)$. Simultaneous price changes remain essential.
For completeness, the unrestricted promised computation belongs to $\mathrm{FP}^{\mathrm{NP}}$. This does not settle whether polynomial time suffices.
First, the promised least price has polynomial encoding length. Choose its equilibrium allocation support $D$. Lemma 2 gives an equilibrium $d_D\leq p^*$, and leastness gives equality:
$$
p^*=d_D.
$$
Every support-graph weight is an integer multiple of $1/\Delta$, so
$$
\Delta p_h^*\in\mathbb Z.
$$
Because $U$ is an equilibrium,
$$
\underline p_h\leq p_h^*\leq U_h\leq3R.
$$
Next consider the decision problem asking whether some equilibrium price satisfies $p_h\leq c$. It belongs to $\mathrm{NP}$:
Acceptance supplies an equilibrium witness. Conversely, an equilibrium satisfying the bound has an allocation support whose least supporting price still satisfies it.
On promised inputs, an equilibrium with $p_h\leq c$ exists exactly when $p_h^*\leq c$. Binary search therefore finds the integer $\Delta p_h^*$ between the polynomial-length integer endpoints $\Delta\underline p_h$ and $\Delta U_h$. Doing this for every coordinate, followed by Proposition 1, gives the oracle upper bound.
The component theorem permits unboundedly many classes, but its exponent depends on the largest strongly connected component. It therefore leaves unresolved the case of a component whose size grows with the input.
Neither the interval theorem nor the component decomposition supplies a polynomial-time algorithm for that case. No promise-preserving NP-hardness reduction is proved here.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial, sound partial results, but does not resolve the unrestricted promised computation in USER_TASK. The bounded-component algorithm, the coordinate-section theorem, the coordinate-descent counterexample, and the unrestricted $\mathrm{FP}^{\mathrm{NP}}$ upper bound withstand verification. I found minor exposition issues, but no false central step.
The task asks for either an exact algorithm polynomial in $m,\tau,L$ on all promised inputs, or an NP-hardness result for that promised computation.
Theorem 8 gives a polynomial-time algorithm only when the largest strongly connected component has a fixed size $k$. Its displayed running time,
$$
(m+\tau m^2)^k\operatorname{poly}(m,\tau,L),
$$
does not give polynomial time when $k$ grows with the input. Section 6 establishes an oracle upper bound, which does not settle the requested alternative. No hardness reduction is supplied.
Severity: major relative to completing the assignment. This limitation is explicitly acknowledged; it is not a misrepresentation or an error in the partial results.
Minimum additional work: Resolve the unrestricted promised computation. Expositional changes alone cannot complete the assignment.
The collapse to the staying utility
$$
a_t=\max\{v_{t,0},v_{t,h_t}-\underline p_{h_t}\}
$$
is correct. Both original staying options occupy the same class, and at least one attains $a_t$. Thus combining them preserves class-allocation feasibility and utility maximization.
The coefficient $\beta_t$ correctly handles strict preferences and ties. If buying the current home attains $a_t$, all assigned staying mass may be purchased. Otherwise, buying the current home cannot receive positive equilibrium mass. External assignments are always purchases.
Consequently, the displayed linear objective correctly represents maximum purchased mass. No issue was found here.
The flow construction is correct:
The denominator scaling is also correct. The product $Q$ has binary length $O(L)$, and multiplying capacities by $Q$ makes the masses and supplies integral. This does not require an algorithm whose running time is polynomial in the numerical value of $Q$.
The stated integrality theorem applies: capacities and prescribed balances are integral, and the feasible flow polytope is bounded. The resulting allocation entries have polynomial-length representations $z/Q$.
The cited [Orlin paper](https://pubsonline.informs.org/doi/10.1287/opre.41.2.338) does establish a strongly polynomial algorithm for capacitated minimum-cost flow, so the algorithmic application is valid.
Minor issue: The write-up cites polynomial-time minimum-cost-flow algorithms without precisely stating the algorithmic theorem being invoked, as required by the verification standard.
Minimum clarification: State the applicable theorem for finite networks with binary-encoded integral capacities, balances, and costs, including its polynomial-time guarantee. The constructed network already satisfies these hypotheses.
The extension to submarkets of mass $M\leq1$ is valid: the prescribed flow value becomes $M$, and the capacity and scaling arguments still apply.
The support inequalities correctly express all required comparisons:
The graph encoding of upper bounds through arcs to the fixed vertex $0$ has the correct sign.
The longest-walk argument is valid. A positive cycle contradicts feasibility. Without positive cycles, removing cycles cannot decrease walk weight, so finite maxima are attained by simple paths. Lower-bound arcs make every class reachable from $0$.
The computed distances satisfy every arc inequality, including those ending at $0$, and every feasible vector dominates them. Thus the conclusion is componentwise leastness, rather than merely minimality.
Negating weights gives the stated Bellman–Ford computation. Simple paths have at most $n$ arcs, which supports the polynomial rational-bit bound. No substantive gap was found.
The universal graph contains every possible support-graph arc.
The tight-tree argument is correct: slacks are nonnegative, and their sum along a maximizing path is zero. Hence every arc of that path is tight. Reachability through tight arcs supplies a rooted spanning tree, whose weights determine the least supporting vector.
The candidate checks establish both claimed properties:
Nonemptiness follows from sufficiently high prices supporting the all-staying allocation.
Proposition 3 then correctly tests the coordinatewise candidate minimum. It does not assume that equilibrium prices are closed under coordinatewise minimum. Instead, it explicitly tests equilibrium feasibility. Its converse correctly proves that any existing least equilibrium is itself a retained candidate.
This establishes the fixed-dimensional solver and least-price existence test.
The graph condition is a valid necessary condition for external demand, including weak preferences at reservation prices. An absent arc makes the associated external option strictly worse than staying at every feasible price.
Lemma 4 correctly derives a nonnegative circulation from allocation balance. Aggregating over strongly connected components gives a circulation on an acyclic condensation graph; successive source-component balance forces every intercomponent movement to vanish.
The imposed bounds
$$
b_h=\max\left(\{\underline p_h\}\cup
\{v_{t,h}-u_t:\text{previously processed types }t\}\right)
$$
correctly prevent earlier types from strictly preferring newly processed classes. Keeping $a_t$ fixed is essential and is explicitly respected.
The three correctness lemmas are sound:
Together, these establish both successful computation and correct detection of nonexistence. No circular reasoning or missing substantive lemma was found.
The numerical bounds are correct:
$$
|a_t|\leq2R,\qquad 0\leq U_h\leq3R.
$$
Previously processed internal utilities are at least $a_t$, so
$$
\underline p_h\leq b_h\leq U_h.
$$
The vector $U$ supplies the required internal equilibrium upper bound.
The common-denominator induction is valid. Maxima select existing rational values, differences preserve the denominator grid, and supporting prices are sums of graph weights. Thus successful sequential processing does not introduce denominator growth.
The support-graph weights have absolute value at most $3R$, and tree paths have at most $n$ arcs. Candidate prices therefore have polynomial encoding length even before feasibility checks.
The enumeration and component processing give the stated running-time form. The final purchase-maximizing allocation follows from Proposition 1.
The acyclic specialization is also correct: all movement vanishes, so equilibrium is exactly the condition that every staying utility dominates every external utility, yielding the orthant above $U$.
The demand description at, below, and above each threshold $c_t$ correctly includes ties. Types currently in the varied class have demand independent of that class’s posted price.
The weighted Hall characterization is correctly proved through cuts. An insufficient cut cannot contain a type-to-class arc of capacity $1$, and the displayed cut inequality then gives the required contradiction. Max-flow/min-cut applies to this finite capacitated network.
The monotonicity and threshold inclusions correctly yield closed rays:
Their intersection with the reservation constraint is an empty set or a closed interval. The endpoint tests suffice: demand is constant between thresholds, finite endpoints occur at the stated candidates, and the tail test detects unboundedness.
Two minor issues need clarification.
Minor issue: weighted contributions. The proof says that a type’s contribution to $F_S$ is $1$ or an indicator. Literally, its contribution is $\mu_t$ times the corresponding indicator. The monotonicity argument survives because $\mu_t>0$.
Minimum clarification: Distinguish the membership indicator from the weighted contribution to $F_S$.
Minor issue: fixed-price feasibility. The proposition allows arbitrary rational values for the other prices, while the interval proof does not explicitly dispose of a fixed price below its reservation bound. In that case the section is empty regardless of the Hall inequalities. The proposed equilibrium tests already reject such prices.
Minimum clarification: State that fixed coordinates are first checked against reservation bounds, with an empty section returned if any check fails.
The matrix has row and column sums
$$
\left(\frac38,\frac38,\frac14\right).
$$
At both displayed uniform price vectors, external options maximize utility, so the allocation establishes equilibrium. Nonnegative reservation bounds make the zero vector componentwise least.
After decreasing a single coordinate, every type outside that class strictly demands it. Since every supply is below $1/2$,
$$
1-s_h>s_h,
$$
so its forced demand exceeds supply.
The example therefore correctly shows that feasible coordinatewise decreases can fail at a nonleast equilibrium. It does not claim a broader lower bound on algorithms.
The polynomial-size representation of promised least prices follows correctly from Lemma 2 applied to an equilibrium allocation support. Leastness forces equality with that support’s least supporting vector.
The certificate for coordinate-bounded equilibrium existence is valid. Its support uses polynomially many bits; transportation feasibility and support-price feasibility are polynomial-time checks. Comparing the least supporting coordinate against $c$ is sufficient in both directions.
On promised inputs, leastness gives the claimed equivalence between coordinate-bounded equilibrium existence and $p_h^*\leq c$. Searching the integer grid defined by $\Delta$ uses polynomially many oracle queries because the endpoint integers have polynomial binary length.
Thus the $\mathrm{FP}^{\mathrm{NP}}$ upper bound is established. It does not establish polynomial-time solvability or NP-hardness.
The partial results require only the three minor clarifications identified above. The unresolved assignment requires substantive additional mathematics for unrestricted component size. The output’s explicit “partial” claim is accurate, and its established content is meaningful progress.
⟨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.