Answer: Polynomial-time solvable.
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe MULGA problem is computationally tractable. Sketch of proof: Consider the representation of the problem as an integer programming problem. Let g1, . . . , gm be the goods, let q(i) be the number of available units of good i, and let S1, . . . , Sn be the set of (linear) bids, where the price offer in Si is p(Si). Let xi be a 0/1 variable, where 1 denotes that Si appears in the winning com- bination.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given ordered goods \(g_1,\ldots,g_m\), per-capita capacities \(q_j\), and a distribution \(\mu\) over \(\tau\) bid types, where type \(t\) specifies an interval \(I_t\) and price \(p_t\), choose accepted masses \(x_t\) to maximize \(\sum_t p_t x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:\,g_j\in I_t}x_t\le q_j\) for every good \(g_j\). Each individual receives either the entire interval or nothing; \(x_t\) is the mass of type \(t\) whose bid is accepted.
Let \(m\ge1\) ordered goods be \(g_1,\ldots,g_m\), with nonnegative binary-rational per-capita capacities \(q_j\).
A society is given by its support: the list of its \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Type \(t\) submits one bid with a nonempty interval \(I_t=\{g_{a_t},\ldots,g_{b_t}\}\), where \(1\le a_t\le b_t\le m\), and a nonnegative binary-rational price \(p_t\) for the entire interval. Each accepted individual consumes one unit of every good in that interval and pays \(p_t\); rejected individuals consume nothing and pay nothing.
Mass within each type is divisible: any real accepted mass \(x_t\in[0,\mu_t]\) is permitted, while each individual receives the entire interval or nothing. Maximize \(\sum_{t=1}^{\tau}p_tx_t\), subject to \(\sum_{t:g_j\in I_t}x_t\le q_j\) for every \(j\). Let \(L\) be the total binary input length.
Is computing an exact revenue-maximizing feasible vector \(x\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many bids, each requesting one unit of every good in a nonempty interval, revenue maximization under nonnegative integer good capacities is polynomial-time solvable.
Computing an exact revenue-maximizing feasible vector is polynomial-time solvable in \(m,\tau,L\).
Divisibility makes the problem a rational linear program, which already establishes polynomial-time solvability. The interval structure gives a more explicit reduction to minimum-cost circulation. This reduction also explains why large rational denominators do not require expanding the population into individual bids.
Write every input rational with a positive integer denominator. Let \(D\) be the product of the denominators of all capacities \(q_j\) and masses \(\mu_t\), and let \(E\) be the product of the denominators of all prices \(p_t\). Define
\(Q_j=Dq_j,\qquad U_t=D\mu_t,\qquad P_t=Ep_t.\)
These are nonnegative integers. The binary lengths of \(D\) and \(E\) are at most the sums of the binary lengths of their respective factors, hence are \(O(L)\). Consequently, every \(Q_j,U_t,P_t\) has binary length \(O(L)\), and all these numbers can be computed in polynomial time.
Writing \(X_t=Dx_t\), the original optimization problem is equivalent to maximizing
\(\displaystyle \frac{1}{DE}\sum_{t=1}^{\tau}P_tX_t\)
subject to
\(\displaystyle 0\le X_t\le U_t,\qquad \sum_{t:a_t\le j\le b_t}X_t\le Q_j\quad(1\le j\le m).\)
At this stage, the variables \(X_t\) remain real.
Use vertices \(0,1,\ldots,m\), with two kinds of directed arcs:
Parallel arcs are allowed. A circulation is a nonnegative flow respecting arc capacities and satisfying flow conservation at every vertex.
Denote the flow on type \(t\)'s arc by \(X_t\), and the flow on good \(j\)'s arc by \(F_j\).
Fix \(j\), and sum flow conservation over the vertices \(S_j=\{0,\ldots,j-1\}\). Internal arcs cancel.
The only arc leaving \(S_j\) is the good arc \(j-1\to j\). A type arc enters \(S_j\) precisely when
\(a_t-1\le j-1<b_t,\)
equivalently, \(a_t\le j\le b_t\). No type arc leaves \(S_j\), because every type arc points from a larger vertex to a smaller vertex. Therefore,
\(\displaystyle F_j=\sum_{t:a_t\le j\le b_t}X_t.\)
The arc capacities now imply all the scaled allocation constraints.
Conversely, take any feasible real vector \(X\). Put flow \(X_t\) on each type arc and define
\(\displaystyle F_j=\sum_{t:a_t\le j\le b_t}X_t\)
on each good arc. All capacity constraints hold.
To check conservation, put \(F_0=F_{m+1}=0\). For each vertex \(k\in\{0,\ldots,m\}\), the definition of the \(F_j\) gives
\(\displaystyle F_{k+1}-F_k=\sum_{t:a_t=k+1}X_t-\sum_{t:b_t=k}X_t.\)
Rearranging yields
\(\displaystyle F_k+\sum_{t:a_t=k+1}X_t=F_{k+1}+\sum_{t:b_t=k}X_t.\)
The left side is total incoming flow at vertex \(k\), and the right side is total outgoing flow. Thus the constructed flow is a circulation.
The feasible allocations and feasible circulations consequently correspond exactly. The circulation cost is
\(\displaystyle -\sum_{t=1}^{\tau}P_tX_t=-DE\sum_{t=1}^{\tau}p_tx_t.\)
Since \(DE>0\), minimizing cost is equivalent to maximizing revenue.
We use the standard minimum-cost circulation theorem:
For a finite directed graph with integer arc costs and finite nonnegative integer capacities, a minimum-cost circulation can be found in time polynomial in the graph size and the binary encoding length of the numerical data. Moreover, an optimal circulation can be chosen integral, and an integral optimum can be returned.
All hypotheses hold here:
Apply this theorem and let \(X_t^*\) be the resulting integral flow on type \(t\)'s arc. Return
\(\displaystyle x_t^*=\frac{X_t^*}{D}\qquad(1\le t\le\tau).\)
The correspondence proved above shows that this vector is feasible and maximizes revenue over all real feasible allocations. Integrality of the returned flow does not restrict the optimum: the theorem guarantees an integral optimum for the circulation problem itself.
The output also has polynomial length. Since the masses are positive and sum to \(1\), each \(\mu_t\le1\), so
\(0\le X_t^*\le U_t=D\mu_t\le D.\)
Thus each output numerator and denominator has \(O(L)\) bits.
Although \(D\) has polynomial binary length, its numerical value can be exponentially large. Replacing type \(t\) by \(D\mu_t\) separate bids would therefore not establish a polynomial-time algorithm.
The circulation construction uses exactly one arc per type, with its mass encoded as a binary integer capacity. It avoids this expansion and proves the required polynomial-time bound.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes a polynomial-time algorithm that returns an exact optimum over all real feasible allocations. No major or minor issues were found.
The definitions of \(D\) and \(E\) are valid because every input rational can be represented with a positive integer denominator. Both products are positive, including when some capacities or prices are zero.
Each selected denominator contributes to the total input length \(L\). Therefore, the products \(D\) and \(E\) have \(O(L)\) bits. The scaled values \(Q_j\), \(U_t\), and \(P_t\) are integers with \(O(L)\) bits and can be computed by polynomial-time integer arithmetic.
The change of variables \(X_t=Dx_t\) is bijective because \(D>0\). It transforms the bounds and good-capacity constraints exactly as stated. The objective acquires the positive factor \(1/(DE)\), so its maximizers are preserved.
The prover explicitly keeps \(X_t\) real at this stage. Thus, scaling does not introduce an unjustified integrality restriction.
Every good arc has a valid nonnegative integer capacity \(Q_j\). Every type arc has capacity \(U_t\) and integer cost \(-P_t\).
The endpoint restrictions \(1\le a_t\le b_t\le m\) ensure that each type arc runs strictly backward, from \(b_t\) to \(a_t-1\). Singleton intervals are included without creating self-loops. Parallel arcs correctly allow distinct types with identical intervals.
The stated counts of \(m+1\) vertices and \(m+\tau\) arcs are correct.
For the prefix \(S_j=\{0,\ldots,j-1\}\), exactly one good arc leaves the set, namely \(j-1\to j\). No good arc enters it, and no backward type arc leaves it.
A type arc enters precisely when \(a_t-1\le j-1<b_t\). Since the endpoints are integers, this is equivalent to \(a_t\le j\le b_t\).
Summing conservation over the prefix therefore gives exactly the claimed identity
\(F_j=\sum_{t:a_t\le j\le b_t}X_t\).
The good-arc capacities enforce the good constraints, while the type-arc capacities enforce \(0\le X_t\le U_t\). This direction is rigorous.
The specified good flows are nonnegative and satisfy their capacities by allocation feasibility.
The identity for \(F_{k+1}-F_k\) correctly accounts for intervals starting at \(k+1\) and ending at \(k\). It also holds at \(k=0\) and \(k=m\), using the explicitly defined values \(F_0=F_{m+1}=0\).
The rearranged equality correctly identifies incoming and outgoing flow: type arcs enter at their interval’s left boundary and leave at its right boundary. Thus conservation holds at every vertex.
Together, the two directions establish the claimed exact correspondence. In particular, the good flows are uniquely determined by the type flows.
Only type arcs have nonzero costs. Consequently, the circulation cost is \(-\sum_tP_tX_t\).
Substituting \(P_t=Ep_t\) and \(X_t=Dx_t\) gives the stated value \(-DE\sum_tp_tx_t\). Since \(DE>0\), minimum circulation cost corresponds exactly to maximum revenue.
The quoted minimum-cost circulation theorem is a valid standard theorem, stated with the relevant numerical encoding and integrality guarantees. Its hypotheses are all satisfied:
Finite capacities also bound every arc flow, so negative costs do not cause unboundedness.
The network’s encoding length is polynomial in \(m,\tau,L\), as claimed. The theorem therefore supplies an integral optimal circulation in polynomial time.
Crucially, its optimality is for the circulation problem over real flows. The integrality guarantee permits returning an integral optimum without restricting the feasible set beforehand. The exact correspondence therefore establishes optimality over all real feasible allocations.
The bound \(0\le X_t^*\le D\mu_t\le D\) follows from the type capacity and the positive masses summing to \(1\). Hence each returned rational \(X_t^*/D\) has \(O(L)\) bits, and the complete output has polynomial length.
The proof covers zero capacities, zero prices, singleton intervals, and \(m=1\) or \(\tau=1\). No missing boundary case affects the conclusion.
The warning about population expansion is also correct: polynomial binary length of \(D\) does not imply polynomial numerical value.
None is required. The proof establishes the requested polynomial-time classification and exact output guarantee.
⟨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.