Answer: polynomial-time solvable
Theorem 3.2 — class: algorithmic
Given finitely many agent types \(T\), type masses \(\mu_t\), type weights \(w_t>0\), binary approval vectors \(a_t\in\{0,1\}^q\), and rational per-capita supplies \(\rho_j\) for \(q\) good classes, choose a finite-support mass assignment \(\pi_{t,B}\) of type \(t\) agents to integral bundles \(B\in\mathbb{Z}_{\ge 0}^q\), satisfying \(\sum_B\pi_{t,B}=\mu_t\) and \(\sum_{t,B}\pi_{t,B}B_j\le\rho_j\). Maximize first \(P(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}\), then \(\Phi(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}w_t\log u_t(B)\), where \(u_t(B)=a_t\cdot B\), with all positively valued supply assigned and an anonymous type-level refinement if a canonical tie-broken output is required.
A society is given by its support: a list \(T=\{1,\ldots,\tau\}\) of types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) good classes (the supplied question's \(q=m\)), with binary-rational per-capita supplies \(\rho_j\geq0\). Each type has a binary-rational weight \(w_t>0\) and approval vector \(a_t\in\{0,1\}^m\); zero approval vectors are allowed. Let \(L\) be the total input bit length.
An assignment consists of nonnegative masses \(\pi_{t,B}\), with finite support over \(B\in\mathbb Z_{\geq0}^m\), satisfying \(\sum_B\pi_{t,B}=\mu_t\) and \(\sum_{t,B}\pi_{t,B}B_j\leq\rho_j\). Bundles have no additional size bound, and \(u_t(B)=a_t\cdot B\).
Require equality in the supply constraint whenever some type approves class \(j\); if no type approves it, require \(B_j=0\) whenever \(\pi_{t,B}>0\).
First maximize \(P(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}\), then \(\Phi(\pi)=\sum_{t,B:u_t(B)>0}\pi_{t,B}w_t\log u_t(B)\); empty sums are zero.
For an anonymous refinement, next lexicographically maximize \((\bar u_1,\ldots,\bar u_\tau)\), where \(\bar u_t=\mu_t^{-1}\sum_B\pi_{t,B}u_t(B)\), using the listed type order; remaining ties are arbitrary. An exact output is represented by finitely many integral bundles and binary-rational masses.
Is computing such an exact optimal assignment polynomial-time in \(m,\tau,L\), or is it NP-hard?
For finitely listed agents and indivisible goods with binary additive valuations, maximum weighted Nash welfare with lexicographic weighted-utility tie-breaking and allocation of exactly the valued goods is computable in polynomial time ([Suksompong–Teh](https://arxiv.org/pdf/2204.03803)).
No complexity result for this exact mass-assignment problem was located in the literature search.
Computing the specified exact optimal assignment is polynomial-time solvable in \(m,\tau,L\). This includes the anonymous lexicographic refinement.
The algorithm outputs at most \(\tau(m+1)\) bundles with rational masses of polynomial encoding length. If the input masses and supplies are dyadic rationals, the output masses can also be dyadic.
The proof has two main ingredients: a flow formulation with decreasing lexicographic marginal rewards, and a way to compute its greedy solution without enumerating all utility levels.
Let \(J\) be the set of classes approved by at least one type, and put
\[
\]
\(R=\sum_{j\in J}\rho_j\).
If \(R=0\), assigning the zero bundle to every type solves the problem. Henceforth assume \(R>0\), and define
\(K_t=\lceil R/\mu_t\rceil\).
For each type \(t\), introduce layers \((t,k)\), where \(0\leq k<K_t\). Each layer has capacity \(\mu_t\). Its vector of marginal rewards is
\(c_{t,0}=(1,0,\mathbf e_t/\mu_t)\),
and, for \(k\geq1\),
\(c_{t,k}=\bigl(0,w_t\log((k+1)/k),\mathbf e_t/\mu_t\bigr)\).
Here \(\mathbf e_t\) is the \(t\)-th coordinate vector in \(\mathbb R^\tau\). Reward vectors are compared lexicographically: their coordinates correspond to \(P,\Phi,\bar u_1,\ldots,\bar u_\tau\).
Within each type, these vectors strictly decrease with the layer index. Across types, layer \(0\) always precedes every positive-index layer; equal logarithmic gains are ordered by the listed type order.
For any mean utility mass \(x_t\in[0,R]\), define its *filled-prefix layers* by
\(y_{t,k}(x_t)=\min\{\mu_t,\max\{0,x_t-k\mu_t\}\}\).
Their total mass is \(x_t\). Their first reward coordinate is \(\min\{\mu_t,x_t\}\), and their remaining type coordinates give \(x_t/\mu_t\).
Their logarithmic reward, denoted by \(G_t(x_t)\), is zero when \(x_t\leq\mu_t\). When \(x_t\geq\mu_t\), writing \(k=\lfloor x_t/\mu_t\rfloor\), it is
\(G_t(x_t)=w_t\bigl((\mu_t-(x_t-k\mu_t))\log k+(x_t-k\mu_t)\log(k+1)\bigr)\).
This is precisely the welfare of a lottery supported on consecutive utilities.
Lemma 1. For any assignment \(\pi\), let
\(x_t=\sum_B\pi_{t,B}u_t(B)\).
Then its filled-prefix layers have a reward vector lexicographically at least as large as
\((P(\pi),\Phi(\pi),\bar u_1,\ldots,\bar u_\tau)\).
Proof. Let \(p_t\) be the mass of type \(t\) receiving positive utility. Since positive utilities are positive integers,
\(p_t\leq\mu_t\quad\text{and}\quad p_t\leq x_t\).
Thus \(P(\pi)\leq\sum_t\min\{\mu_t,x_t\}\).
If this inequality is strict, the claimed lexicographic comparison already follows. Otherwise every type satisfies \(p_t=\min\{\mu_t,x_t\}\).
When \(x_t\leq\mu_t\), equality \(p_t=x_t\) forces every positive utility to equal \(1\): the nonnegative sum
\(\sum_{B:u_t(B)>0}\pi_{t,B}(u_t(B)-1)\)
is zero. Consequently its logarithmic contribution is zero.
When \(x_t>\mu_t\), all the type's mass receives positive utility. Let \(h\) be the piecewise-linear interpolation of \(\log n\) at positive integers \(n\). Its successive slopes are \(\log((n+1)/n)\), which decrease, so \(h\) is concave. Jensen's inequality gives
\(\sum_B\pi_{t,B}w_t\log u_t(B)\leq\mu_tw_th(x_t/\mu_t)=G_t(x_t)\).
The mean utilities are unchanged. This proves the lemma. \(\square\)
The filled-prefix layers are also flow-feasible. Indeed, the assignment supplies the approved-good flow
\(f_{tj}=a_{tj}\sum_B\pi_{t,B}B_j\).
It has type totals \(x_t\) and class totals at most \(\rho_j\). Since all layers of a type have identical approvals, this flow can be split among that type's filled-prefix layers.
Thus optimizing layer rewards provides an upper bound on every feasible assignment, even if the original assignment uses very large bundles or gives some goods to unapproving types.
Let \(E\) denote the finite set of layers. This set can be exponentially large; it is used initially only for the proof.
For \(U\subseteq T\), define the weighted coverage function
\(H(U)=\sum_{j\in J:\,\exists t\in U,\ a_{tj}=1}\rho_j\).
It is normalized, monotone and submodular: each class contributes its nonnegative supply times the indicator that \(U\) intersects its approving types.
For \(S\subseteq E\), let \(r(S)\) be the maximum total flow deliverable to layers in \(S\). This flow uses class supplies \(\rho_j\), approval edges, and layer capacities \(\mu_t\). The max-flow/min-cut theorem gives
\(r(S)=\min_{U\subseteq T}\left(H(U)+\sum_{(t,k)\in S:\,t\notin U}\mu_t\right).\)
This value can be computed using a network with only \(m+\tau+2\) vertices: aggregate the layers in \(S\) into type capacity
\(C_t(S)=\mu_t|\{k:(t,k)\in S\}|\).
Use source-to-class capacities \(\rho_j\), class-to-type approval edges, and type-to-sink capacities \(C_t(S)\). Approval edges may have capacity \(R+1\), since no flow exceeds \(R\).
Lemma 2. The function \(r\) is normalized, monotone and submodular.
Proof. Normalization and monotonicity follow from its flow definition.
For submodularity, choose minimizing type sets \(U,V\) in the cut formula for \(r(A),r(B)\). The capacity terms satisfy
\(\sum_{e\in A:\,t(e)\notin U}\mu_{t(e)}+\sum_{e\in B:\,t(e)\notin V}\mu_{t(e)} \geq \sum_{e\in A\cup B:\,t(e)\notin U\cup V}\mu_{t(e)}+ \sum_{e\in A\cap B:\,t(e)\notin U\cap V}\mu_{t(e)}.\)
This inequality follows separately for each layer: a layer in both sets contributes equally to the two sides, and a layer in only one set contributes at least as much on the left.
Combining it with submodularity of \(H\), and then using the cut formula for the union and intersection, gives
\(r(A)+r(B)\geq r(A\cup B)+r(A\cap B)\).
\(\square\)
The feasible layer-flow vectors are exactly
\(Q=\{y\geq0:\ y(S)\leq r(S)\text{ for every }S\subseteq E\}\),
where \(y(S)=\sum_{e\in S}y_e\).
One inclusion follows by restricting any feasible flow to \(S\). For the reverse inclusion, the inequalities imply \(y_{t,k}\leq\mu_t\). If \(x_t=\sum_k y_{t,k}\), they also imply
\(\sum_{t\in U}x_t\leq H(U)\quad\text{for every }U\subseteq T\).
These are sufficient for a flow meeting all type demands \(x_t\): every cut in the corresponding network has capacity
\(H(U)+\sum_{t\notin U}x_t\geq\sum_t x_t\).
After obtaining that flow, split each type's inflow among its layers.
Finally, \(r(E)=R\). Every type's total layer capacity is \(K_t\mu_t\geq R\), so all valued supplies can be sent to approving types.
Order all layers as \(e_1,\ldots,e_N\) by decreasing reward vector. Let \(S_i=\{e_1,\ldots,e_i\}\), with \(S_0=\varnothing\), and define
\(y^*_{e_i}=r(S_i)-r(S_{i-1})\).
Lemma 3. This vector is feasible and lexicographically maximizes \(\sum_e c_e y_e\) over \(Q\).
Proof. Monotonicity gives nonnegativity. For any \(A\subseteq E\), submodularity gives, whenever \(e_i\in A\),
\(r(S_i)-r(S_{i-1})\leq r(A\cap S_i)-r(A\cap S_{i-1})\).
Summing yields \(y^*(A)\leq r(A)\), proving feasibility.
Write \(c_i=c_{e_i}\). For any \(y\in Q\), summation by parts gives
\(\sum_i c_i(y^*_{e_i}-y_{e_i}) =c_N(r(E)-y(E))+\sum_{i=1}^{N-1}(c_i-c_{i+1})(r(S_i)-y(S_i)).\)
Every scalar multiplying a vector is nonnegative. Every displayed vector is lexicographically positive: rewards are positive, and the ordering is strict.
A finite sum of nonnegative multiples of lexicographically nonnegative vectors is lexicographically nonnegative. To verify this, consider the earliest coordinate where any nonzero summand is nonzero; every contribution at that coordinate is nonnegative, and at least one is positive.
The claimed optimality follows. \(\square\)
The next lemma is what makes this exponentially large greedy construction computable efficiently.
Lemma 4. If a greedy layer \((t,k)\) receives less than \(\mu_t\), every later layer of type \(t\) receives zero.
Proof. Let \(S\) be the layers preceding \(e=(t,k)\), and suppose
\(r(S\cup\{e\})-r(S)<\mu_t\).
Choose a minimizing \(U\) in the cut formula for \(r(S\cup\{e\})\). If \(t\notin U\), that cut's value equals its value for \(S\), plus \(\mu_t\). Therefore
\(r(S\cup\{e\})\geq r(S)+\mu_t\),
a contradiction. Hence \(t\in U\).
For any other layer \(f\) of type \(t\), adding \(f\) does not change this cut's value. Monotonicity consequently gives
\(r(S\cup\{e,f\})=r(S\cup\{e\})\).
If \(A\) is the greedy prefix preceding a later such layer \(f\), then \(S\cup\{e\}\subseteq A\). Submodularity gives
\(0\leq r(A\cup\{f\})-r(A)\leq r(S\cup\{e,f\})-r(S\cup\{e\})=0\).
Thus \(f\) receives zero. \(\square\)
Since a type's layers appear in increasing index order, its greedy allocation consists of full layers, then possibly one partial layer, then zero layers. Consequently \(y^*\) is exactly the filled-prefix vector for its type totals
\(x_t^*=\sum_k y^*_{t,k}\).
For a layer \(e=(t,k)\), define
\(d_u(e)=|\{\ell:0\leq\ell<K_u,\ c_{u,\ell}>_{\mathrm{lex}}c_{t,k}\}|\).
Because each type's rewards strictly decrease, this count can be found by binary search on its layer indices.
Let \(V(d)\) be the maximum flow with type capacities \(\mu_ud_u\). The greedy mass of \(e\) is exactly
\(\delta_t(k)=V(d(e)+\mathbf e_t)-V(d(e))\).
Thus one layer-mass query requires binary searches for its prefix counts and two max-flow computations.
By Lemma 4, the predicate \(\delta_t(k)<\mu_t\) is monotone in \(k\). Binary search finds its first true index \(b_t\); set \(b_t=K_t\) if there is none. Then
\(x_t^*= \begin{cases} b_t\mu_t+\delta_t(b_t),&b_t<K_t,\\ K_t\mu_t,&b_t=K_t. \end{cases}\)
This recovers all type totals without constructing \(E\).
The binary searches require exact reward comparisons. Comparing layer \(0\) with another layer, or breaking an equal-gain tie, uses only the reward definition and listed type order.
For positive-index layers, write \(w_t=p_t/q_t\) and \(w_u=p_u/q_u\). Put \(A=p_tq_u\) and \(B=p_uq_t\). The comparison
\(w_t\log((k+1)/k)\geq w_u\log((\ell+1)/\ell)\)
is equivalent to
\((k+1)^A\ell^B\geq k^A(\ell+1)^B.\)
For a fixed number of factors, comparing products of integer powers with binary-encoded bases and exponents is unconditionally polynomial-time; equality is also polynomial-time decidable. These are Proposition 3.7(2) and Proposition 2.1 of [Etessami–Stewart–Yannakakis](https://arxiv.org/pdf/1304.5429).
The hypotheses hold here: each side has two factors, and all bases and exponents are positive integers of polynomial bit length. Thus every required comparison, including exact ties, is polynomial-time.
Obtain a flow \(f_{tj}\) with class supplies \(\rho_j\) and type demands \(x_t^*\). It exists because \(y^*\) is feasible. Since \(\sum_t x_t^*=R\), a flow of value \(R\) saturates every valued class supply and every type demand.
Fix a type \(t\), and abbreviate \(\mu=\mu_t\), \(f_j=f_{tj}\). We now construct at most \(m+1\) integral bundles whose masses sum to \(\mu\), whose expected class counts are \(f_j\), and whose utilities are consecutive integers.
Write
\(f_j=\mu q_j+r_j,\qquad q_j=\lfloor f_j/\mu\rfloor,\qquad 0\leq r_j<\mu.\)
Set \(s_0=0\) and \(s_j=\sum_{h=1}^j r_h\). For \(z\in[0,\mu)\), define
\(\varepsilon_j(z)=|\{n\in\mathbb Z_{\geq0}:z+n\mu\in[s_{j-1},s_j)\}|,\qquad B_j(z)=q_j+\varepsilon_j(z).\)
Each interval has length less than \(\mu\), so \(\varepsilon_j(z)\in\{0,1\}\). Thus \(B(z)\) is integral and nonnegative. Furthermore,
\(\int_0^\mu B_j(z)\,dz=\mu q_j+r_j=f_j.\)
All interval indicators can change only at the residues \(s_j\bmod\mu\). Partitioning \([0,\mu)\) at these residues gives at most \(m+1\) intervals. On each interval \(B(z)\) is constant; output that bundle with mass equal to the interval length.
To check utility levels, put \(S=\sum_jr_j\). Since the intervals \([s_{j-1},s_j)\) partition \([0,S)\),
\(\sum_j\varepsilon_j(z)=|\{n\in\mathbb Z_{\geq0}:z+n\mu\in[0,S)\}|.\)
This number is either \(\lfloor S/\mu\rfloor\) or \(\lceil S/\mu\rceil\). Therefore every resulting bundle has total size either
\(\lfloor x_t^*/\mu_t\rfloor\quad\text{or}\quad\lceil x_t^*/\mu_t\rceil.\)
Only approved classes have nonzero flow, so total bundle size equals utility. This lottery achieves \(P_t=\min\{\mu_t,x_t^*\}\) and logarithmic welfare \(G_t(x_t^*)\).
Consequently the reconstructed assignment's objective vector is exactly \(\sum_e c_e y_e^*\). Lemmas 1 and 3 prove that it dominates every feasible assignment, including at every coordinate of the anonymous refinement. It also uses exactly every valued class supply and assigns no unvalued class.
Every \(K_t=\lceil R/\mu_t\rceil\) has polynomial bit length: binary-encoded rational supplies and positive masses have at most exponentially large values and reciprocals.
Let \(b=1+\max_t\lceil\log_2(K_t+1)\rceil\). The implicit algorithm uses:
All capacities have polynomial encoding length.
For output arithmetic, let \(D\) be the product of the denominators of the input masses and supplies. Its bit length is at most their total input length. After scaling by \(D\), integral max-flow algorithms show that every rank value, computed \(x_t^*\), and reconstructed flow \(f_{tj}\) belongs to \(D^{-1}\mathbb Z\).
The bundle construction uses integer multiples, sums, differences and residues modulo \(\mu_t\). Hence its output masses also belong to \(D^{-1}\mathbb Z\). Every bundle's utility is at most \(K_t\), so bundle coordinates have polynomial bit length.
The algorithm therefore computes the requested exact optimal assignment in polynomial time, with at most \(\tau(m+1)\) output bundles.
⟨structured verdict parsed — rendered above⟩
Result: proved. The output establishes a polynomial-time algorithm for the exact mass-assignment problem, including the anonymous lexicographic refinement. I found no major or minor mathematical issues requiring repair.
The proof addresses the stated problem directly. It uses the listed support types, rational masses and supplies, arbitrary positive rational weights, and unrestricted integral bundles.
The definition \(R=\sum_{j\in J}\rho_j\) correctly excludes classes approved by no type. For every feasible assignment, \(\sum_t x_t\leq R\), because each utility counts only approved goods.
The case \(R=0\) is handled correctly: all utilities must be zero, the zero-bundle assignment satisfies the supply requirements, and every objective coordinate is zero.
When \(R>0\), each \(K_t=\lceil R/\mu_t\rceil\) is a positive integer. The layers indexed by \(0\leq k<K_t\) suffice for every possible type total \(x_t\leq R\). Zero-approval types cause no difficulty: their layers receive no flow, and reconstruction gives them the zero bundle.
The marginal rewards correctly encode the objectives:
The rewards strictly decrease within a type. Across distinct types, the mean-utility coordinates resolve equal earlier coordinates according to the listed type order. Thus the full ordering is strict.
The filled-prefix formula correctly sums to \(x_t\), including when \(x_t=0\), when \(x_t\) is an integer multiple of \(\mu_t\), and when the last available layer is full.
Lemma 1 is valid. The inequalities \(p_t\leq\mu_t\) and \(p_t\leq x_t\) follow from integral positive utilities. Equality in their aggregate upper bound forces equality separately for every type.
For \(x_t\leq\mu_t\), the stated nonnegative sum correctly shows that every positive utility equals \(1\). For \(x_t>\mu_t\), equality forces all type mass to receive positive utility. Consequently Jensen’s inequality is applied within the domain of the concave interpolation \(h\), with normalized probabilities and finite support. Its resulting bound is exactly the displayed \(G_t(x_t)\).
The associated approved-good flow is feasible even if the original assignment gives some goods to unapproving types. Such goods are excluded from both \(f_{tj}\) and \(x_t\). Splitting each type’s inflow among its prefix layers is legitimate because those layers have identical approval edges.
The cut formula for \(r(S)\) is correct. Aggregating layers into capacities \(C_t(S)\) preserves the maximum-flow value. Approval-edge capacity \(R+1\) is sufficient: a cut of capacity at most \(R\) always exists, so a minimum cut cannot cross such an edge.
Lemma 2 is valid. Normalization and monotonicity follow from the flow definition. The displayed capacity inequality holds separately for each layer, including layers belonging to both sets. Together with coverage submodularity, it gives the claimed submodularity of \(r\).
The characterization of \(Q\) is correct in both directions:
The claim \(r(E)=R\) is also valid. Each type’s aggregate capacity is at least \(R\), and each class in \(J\) has an approving type. This includes classes whose supplies are zero.
Lemma 3 is valid. The stated diminishing-returns inequality follows from submodularity with the required set containment. Summing it establishes feasibility.
The summation-by-parts identity is correct. Its scalar coefficients are nonnegative by the rank inequalities. Both \(c_N\) and each successive reward difference are lexicographically positive.
The explanation for sums of lexicographically nonnegative vectors is sound: at the earliest nonzero coordinate among nonzero summands, contributions cannot cancel. Therefore the proof establishes optimization of the entire objective vector, including all refinement coordinates.
No numerical approximation of the objective values is assumed here.
Lemma 4 is valid. If a minimizing cut after adding \(e\) excluded its type, its value would be at least \(r(S)+\mu_t\), contradicting the hypothesized increment. A minimizing cut therefore includes that type, and adding another layer of the same type leaves this cut value unchanged.
The subsequent submodularity application has the correct containment and yields zero increment for every later layer of that type.
Accordingly, each type has full layers, at most one partially filled layer, and then zero layers. This establishes both the filled-prefix structure and the monotonicity needed by the outer binary search.
The counts \(d_u(e)\) describe exactly the layers preceding \(e\). Strictly decreasing rewards within each type justify the inner binary searches. The formula for \(\delta_t(k)\) is the correct greedy rank increment, and the recovery formula for \(x_t^*\) handles both a first non-full layer and the case of no such layer.
Cross-multiplying the positive rational weights and exponentiating gives the stated equivalent comparison:
\[ (k+1)^A\ell^B\geq k^A(\ell+1)^B. \]
All bases and exponents are positive integers; positive-index comparisons have \(k,\ell\geq1\). Their encoding lengths are polynomial.
The external citation is accurate. Proposition 2.1 supplies polynomial-time equality testing, and Proposition 3.7(2) supplies unconditional polynomial-time inequality testing when both product lengths are fixed. Here each side has exactly two factors, so the hypotheses hold independently of the number of types or layers. Bases equal to \(1\) are permitted by the stated comparison problem. [Etessami–Stewart–Yannakakis](https://arxiv.org/pdf/1304.5429)
Thus the algorithm does not rely on a conjectural comparison oracle or on expanding exponentially large powers.
The final flow exists by layer feasibility. Because its value is \(R\), it saturates all valued class supplies and all type demands.
The reconstruction is correct:
The half-open intervals consistently handle endpoints. Zero-length pieces need not be output, and the positive interval lengths sum to \(\mu\).
Unapproved coordinates have zero flow and therefore zero bundle coordinates. Bundle size consequently equals utility. The resulting lottery attains both the positive-utility bound and the interpolated logarithmic welfare, while retaining the selected mean utilities.
This closes the upper-bound argument: the reconstructed feasible assignment attains the greedy objective vector. It also satisfies the additional requirements on valued and unvalued supplies.
The bit-length and operation-count claims are valid. Binary searches depend on the encoding lengths of \(K_t\), rather than their potentially exponential numerical values. Every flow network has polynomial size and polynomial-length rational capacities.
The common denominator \(D\) has polynomial bit length. Scaling capacities by \(D\) allows integral maximum-flow computations, establishing the stated denominator control for rank values, type totals, and reconstructed flows.
The reconstruction preserves this denominator lattice. Bundle coordinates have polynomial bit length, since their utilities are bounded by \(K_t\). For dyadic inputs, \(D\) is a power of two, so the output masses are dyadic as claimed.
The output bound of \(\tau(m+1)\) bundles is justified, including types with zero utility.
Required repair or clarification: none.
⟨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.