Answer: \(\text{Polynomial-time solvable with exact optimal GFT}\)
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe expected total-GFT of both Lottery-MUDA and Vickrey-MUDA is at least a fraction 1 −O(M q ln k k ) of the maximum total-GFT. The proof is given in Section 5. While Vickrey-MUDA attains more total-GFT than Lottery-MUDA, their asymp- totic behavior is similar — both of them approach the optimal total-GFT when the market size (k) is large, as long as the market-concentration factor (represented by M) is kept constant.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many buyer and seller types with rational masses \(\mu_t\), capacity at most \(M\), and explicit rational DMR valuation tables over integral quantities \(q\in\{0,\ldots,M\}\), compute a price \(p\) and allocation masses \(x_{t,q}\). Require \(\sum_q x_{t,q}=\mu_t\), equal total quantities bought and sold, and that every assigned quantity maximizes its type’s gain at \(p\); among such allocations, maximize total GFT.
A society is given by its support: the list of the \(\tau\) buyer and seller types with positive binary-rational masses \(\mu_t\). Here \(\tau\) is the support size, not the number of possible types; masses need not sum to one. There is one good, so \(m=1\); let \(L\) be the total input bit length.
Each buyer has an integral capacity \(c_t\le M\), each seller an integral endowment \(c_t\le M\), and \(M\ge1\). Each type has an explicit rational valuation table on \(\{0,\ldots,c_t\}\), normalized by \(v_t(0)=0\), with weakly decreasing marginal values; values and prices may have either sign. Buyers have no monetary budget constraint.
For integral \(q\in\{0,\ldots,c_t\}\), define buyer gain \(g_t(q,p)=v_t(q)-pq\) and seller gain \(g_t(q,p)=pq+v_t(c_t-q)-v_t(c_t)\).
An admissible output consists of a rational price \(p\) and nonnegative rational allocation masses \(x_{t,q}\), satisfying \(\sum_qx_{t,q}=\mu_t\), \(\sum_{t\in B,q}qx_{t,q}=\sum_{t\in S,q}qx_{t,q}\), and \(x_{t,q}>0\Rightarrow q\in\arg\max_r g_t(r,p)\). Ties may be resolved centrally, including splitting a type's mass among maximizing quantities.
Total GFT is \(G(x)=\sum_{t\in B,q}x_{t,q}v_t(q)+\sum_{t\in S,q}x_{t,q}[v_t(c_t-q)-v_t(c_t)]\). Let \(\mathrm{OPT}\) maximize this expression subject to mass conservation and material balance; let \(k\) be the largest traded quantity among its maximizers.
Can an algorithm polynomial in \(m,\tau,M,L\) always produce an admissible output, and, whenever \(\mathrm{OPT}>0\), guarantee expected GFT at least \((1-O(M\sqrt{\ln k/k}))\mathrm{OPT}\) as \(k\to\infty\), with a universal implied constant, or is this approximation guarantee unattainable in polynomial time?
For finite traders, Lottery-MUDA and Vickrey-MUDA attain this expected approximation guarantee while being truthful, individually rational, and budget balanced; their allocations need not give every trader a maximizing quantity at their posted price. [Verified source](https://ojs.aaai.org/index.php/AAAI/article/download/11450/11309).
No result settling precisely the mass-allocation approximation question above was verified in the consulted sources.
Under the stated mass-splitting and centralized tie-breaking rules, a deterministic polynomial-time algorithm produces an admissible output with GFT exactly equal to \(\mathrm{OPT}\). Thus the requested approximation guarantee holds with no loss.
The proof below constructs the price and allocation directly.
For each buyer type \(t\), define its marginal values by
\(b_{t,j}=v_t(j)-v_t(j-1),\qquad 1\le j\le c_t.\)
By hypothesis, these are weakly decreasing. Moreover,
\(g_t(q,p)=\sum_{j=1}^{q}(b_{t,j}-p).\)
Define
\(\ell_t(p)=|\{j:b_{t,j}>p\}|,\qquad u_t(p)=|\{j:b_{t,j}\ge p\}|.\)
The increments of buyer gain are first positive, then possibly zero, then negative. Consequently, its maximizing quantities are exactly
\(\arg\max_q g_t(q,p)=\{\ell_t(p),\ell_t(p)+1,\ldots,u_t(p)\}.\)
For each seller type \(t\), define the opportunity cost of its \(j\)-th unit sold by
\(s_{t,j}=v_t(c_t-j+1)-v_t(c_t-j),\qquad 1\le j\le c_t.\)
These costs are weakly increasing: they list the weakly decreasing valuation marginals in reverse order. Telescoping gives
\(g_t(q,p)=\sum_{j=1}^{q}(p-s_{t,j}).\)
For sellers, define
\(\ell_t(p)=|\{j:s_{t,j}<p\}|,\qquad u_t(p)=|\{j:s_{t,j}\le p\}|.\)
Again, gain increments are first positive, then possibly zero, then negative. Thus the seller’s maximizing quantities are exactly
\(\arg\max_q g_t(q,p)=\{\ell_t(p),\ell_t(p)+1,\ldots,u_t(p)\}.\)
These conclusions also cover zero capacities and signed valuations and prices.
Define the smallest and largest aggregate maximizing demands and supplies:
\(D_{\min}(p)=\sum_{t\in B}\mu_t\ell_t(p),\qquad D_{\max}(p)=\sum_{t\in B}\mu_tu_t(p),\)
\(S_{\min}(p)=\sum_{t\in S}\mu_t\ell_t(p),\qquad S_{\max}(p)=\sum_{t\in S}\mu_tu_t(p).\)
The smallest and largest excess demands obtainable from maximizing quantities are
\(E_-(p)=D_{\min}(p)-S_{\max}(p),\qquad E_+(p)=D_{\max}(p)-S_{\min}(p).\)
We will find a rational price satisfying
\(E_-(p)\le 0\le E_+(p).\)
Let \(A\) be the set of all buyer marginal values and seller opportunity costs. If \(A\) is empty, every capacity is zero; output \(p=0\) and \(x_{t,0}=\mu_t\). This is admissible and optimal.
Otherwise, sort its distinct elements as
\(a_1<a_2<\cdots<a_h.\)
Choose the smallest index \(i\) for which \(E_-(a_i)\le 0\), and set \(p=a_i\).
Such an index exists. At the largest breakpoint, no buyer marginal strictly exceeds the price, and every seller opportunity cost is at most the price. Therefore
\(E_-(a_h)=-\sum_{t\in S}\mu_tc_t\le 0.\)
The selected price also satisfies \(E_+(p)\ge 0\). If \(i=1\), every buyer marginal is at least \(a_1\), while no seller opportunity cost is strictly below \(a_1\). Hence
\(E_+(a_1)=\sum_{t\in B}\mu_tc_t\ge 0.\)
If \(i>1\), minimality gives \(E_-(a_{i-1})>0\). There are no marginal values or opportunity costs strictly between \(a_{i-1}\) and \(a_i\). It follows that
\(D_{\max}(a_i)=D_{\min}(a_{i-1}),\qquad S_{\min}(a_i)=S_{\max}(a_{i-1}).\)
Indeed, a buyer marginal is at least \(a_i\) exactly when it strictly exceeds \(a_{i-1}\); a seller opportunity cost is strictly below \(a_i\) exactly when it is at most \(a_{i-1}\). Thus
\(E_+(a_i)=E_-(a_{i-1})>0.\)
This proves the required pair of inequalities.
Fix the price from Section 2. Define two quantities for each type:
Write these quantities as \(q_t^-\) and \(q_t^+\), respectively. Every chosen quantity maximizes the corresponding type’s gain at \(p\). The two configurations have excess demands \(E_-(p)\) and \(E_+(p)\).
If \(E_+(p)=E_-(p)\), the inequalities already proved force both to be zero. Set \(\lambda=0\).
Otherwise, set
\(\lambda=\dfrac{-E_-(p)}{E_+(p)-E_-(p)}.\)
Because \(E_-(p)\le 0\le E_+(p)\), we have \(0\le\lambda\le 1\). Define
\(x_{t,q}=\mu_t\bigl((1-\lambda)\mathbf 1_{\{q=q_t^-\}}+\lambda\mathbf 1_{\{q=q_t^+\}}\bigr).\)
When the two quantities coincide, the two contributions are added.
All these masses are nonnegative rational numbers, and each type’s masses sum to \(\mu_t\). Their aggregate excess demand is
\((1-\lambda)E_-(p)+\lambda E_+(p)=0.\)
Thus material balance holds. Every quantity receiving positive mass is maximizing at the common price, so the output is admissible. Each type uses at most two quantities.
This establishes optimality without invoking an equilibrium theorem.
For each type, let
\(H_t(p)=\max_{0\le q\le c_t}g_t(q,p).\)
Consider any nonnegative allocation \(y\) satisfying mass conservation and material balance, whether or not it is admissible. Summing the gain definitions gives
\(\sum_{t,q}y_{t,q}g_t(q,p)=G(y)-p\bigl(\sum_{t\in B,q}qy_{t,q}-\sum_{t\in S,q}qy_{t,q}\bigr)=G(y).\)
The price terms cancel by material balance. Since \(g_t(q,p)\le H_t(p)\), mass conservation implies
\(G(y)\le\sum_t\mu_tH_t(p).\)
For the constructed allocation \(x\), every quantity receiving positive mass attains \(H_t(p)\). Consequently,
\(G(x)=\sum_t\mu_tH_t(p).\)
Therefore \(G(y)\le G(x)\) for every feasible allocation \(y\), proving
\(G(x)=\mathrm{OPT}.\)
The feasible set is nonempty, since assigning every type quantity zero is feasible. It is also closed and bounded: each allocation coordinate lies between zero and its type’s mass. Hence the maximum defining \(\mathrm{OPT}\) exists. The same compactness argument ensures that the largest traded quantity \(k\) among optimal allocations exists.
Let \(N=\sum_t c_t\), so \(N\le\tau M\). The algorithm:
A direct implementation takes \(O(N\log N+N^2)\) rational arithmetic operations: evaluating a candidate price requires inspecting at most \(N\) marginal entries.
These operations have polynomial bit complexity. Every breakpoint is a difference of two input rational values, so its numerator and denominator have bit lengths bounded polynomially in \(L\). Every aggregate quantity is a sum of input masses multiplied by integers of magnitude at most \(M\). A common denominator can be taken to be the product of the input mass denominators, whose bit length is at most their total input encoding length. The resulting numerators have polynomial bit length in \(L\), \(\log M\), and \(\log\tau\).
The formula for \(\lambda\) uses one subtraction and one division of these aggregates. Each nonzero output mass is then a product involving \(\lambda\) and an input mass. Hence the price and all output masses have polynomial encoding length. There are at most \(2\tau\) nonzero allocation entries; even a dense output has at most \(\tau(M+1)\) entries.
Thus the algorithm runs in polynomial time in the requested parameters. It never expands a type into individual traders, and unnormalized masses cause no difficulty.
The algorithm is deterministic and satisfies
\(\mathbb E[G(x)]=G(x)=\mathrm{OPT}.\)
In particular, whenever \(\mathrm{OPT}>0\) and \(k>1\),
\(\mathbb E[G(x)]\ge\bigl(1-M\sqrt{\ln k/k}\bigr)\mathrm{OPT}.\)
This supplies a universal implied constant and proves a stronger guarantee than requested. Computing \(k\) is unnecessary.
The distinction from truthful finite-trader mechanisms matters: the task does not require incentive compatibility. The cited [MUDA paper](https://ojs.aaai.org/index.php/AAAI/article/download/11450/11309) itself distinguishes welfare-maximizing Walrasian pricing from truthful mechanisms. The argument above directly establishes exact optimization for the specified mass-allocation problem.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The construction produces a rational, admissible allocation attaining exact optimal GFT in polynomial time. No major or minor mathematical gaps were found.
The buyer marginal identity is correct:
\[
g_t(q,p)=\sum_{j=1}^{q}(b_{t,j}-p).
\]
Weakly decreasing marginals imply that the increments consist of positive increments, followed by zero increments, followed by negative increments. Therefore the maximizing integral quantities are exactly those from \(\ell_t(p)\) through \(u_t(p)\), inclusive.
For sellers, reversing the valuation marginals correctly gives weakly increasing opportunity costs. The telescoping identity
\[
g_t(q,p)=\sum_{j=1}^{q}(p-s_{t,j})
\]
has the correct sign and indices. Its increments likewise have the required ordering, establishing the stated maximizing interval.
Empty marginal lists give \(\ell_t(p)=u_t(p)=0\), so zero capacities are covered. None of these arguments assumes nonnegative values or prices.
The definitions of \(E_-(p)\) and \(E_+(p)\) correctly describe the extreme excess demands obtained by choosing maximizing quantities.
At the largest breakpoint, buyer minimum demand is zero and seller maximum supply equals total endowment mass. Thus the claimed inequality \(E_-(a_h)\le 0\) holds, and the selected index exists.
At the smallest breakpoint, buyer maximum demand equals total capacity mass and seller minimum supply is zero, establishing \(E_+(a_1)\ge 0\).
For consecutive distinct breakpoints, the absence of intervening marginal entries justifies both identities
\[
D_{\max}(a_i)=D_{\min}(a_{i-1}),\qquad
S_{\min}(a_i)=S_{\max}(a_{i-1}).
\]
Consequently, minimality of the selected index establishes \(E_+(a_i)>0\) when \(i>1\).
The argument also covers an empty buyer or seller side. If the breakpoint set is empty, all capacities are zero, and the proposed output is admissible and optimal.
Both configurations use maximizing quantities. When \(E_+=E_-\), the established inequalities force their common value to be zero.
Otherwise, the denominator defining \(\lambda\) is strictly positive, and the inequalities imply \(0\le\lambda\le1\). The proposed masses are rational, nonnegative, and sum to each type’s prescribed mass.
The balance computation is correct:
\[
(1-\lambda)E_-+\lambda E_+=0.
\]
If the two quantities coincide, adding their contributions preserves mass conservation. Positive allocation masses occur only at maximizing quantities. Hence the output meets every admissibility requirement.
For every feasible allocation \(y\), summing gains gives
\[
\sum_{t,q}y_{t,q}g_t(q,p)=G(y).
\]
The price terms cancel with the correct signs under material balance.
Pointwise maximization and mass conservation then yield
\[
G(y)\le\sum_t\mu_tH_t(p).
\]
The constructed allocation attains equality because all quantities receiving positive mass maximize gain. This proves \(G(x)=\mathrm{OPT}\) over the full feasible set specified in the task.
The existence claims are also valid. The feasible set is nonempty and compact, and GFT is continuous. The optimal set is consequently nonempty and compact; total traded quantity is a continuous linear function, so its largest value \(k\) is attained.
No equilibrium theorem or unstated economic assumption is needed.
There are \(N\le\tau M\) marginal entries. Computing them, sorting breakpoints, and inspecting entries at each candidate price requires polynomially many rational arithmetic operations. Reading types and writing the output also require only polynomial time.
The bit-length argument is sufficient:
Thus the arithmetic-operation bound translates into polynomial bit complexity. Both sparse and dense output sizes are polynomial in the requested parameters. Unnormalized masses and potentially large numerical masses do not invalidate these bounds.
Deterministic exact optimality gives
\[
\mathbb E[G(x)]=\mathrm{OPT}.
\]
For \(k>1\), the displayed approximation inequality follows because \(M\sqrt{\ln k/k}\ge0\). It supplies the requested universal constant and applies throughout the asymptotic regime. Computing \(k\) is unnecessary.
The distinction concerning truthfulness is appropriate: incentive compatibility is absent from the assigned output requirements. The ancillary statement about Walrasian optimality versus truthfulness is supported by the introduction of the [cited MUDA paper](https://ojs.aaai.org/index.php/AAAI/article/download/11450/11309); the proof itself does not depend on that citation.
No additional clarification or repair is required.
⟨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.