d4-conf-wine-2015-0006 (d4-conf-wine-2015-0006)

Given a finite type set \(T\) of size \(\tau\), rational masses \(\mu_t>0\) summing to \(1\), rational per-capita supply \(0<\lambda\le K\), and explicit rational monotone valuation tables \(v_t:\{0,\ldots,K\}\to\mathbb{Q}_{\ge0}\), find a competitive bundling equilibrium in time polynomial in \(K,\tau,L\), where \(L\) is the input bit length. A bundle has an integral size \(j\in\{1,\ldots,K\}\), mass \(q_j\), and price \(p_j\), with \(\sum_j jq_j=\lambda\). Each type’s mass may split across integral package-choice vectors \(z\in\mathbb{Z}_{\ge0}^K\) with \(\sum_j jz_j\le K\); every positive-mass choice must maximize \(v_t(\sum_j jz_j)-\sum_jp_jz_j\), and the assignment must clear each package type. The equilibrium welfare should be at least an \(1/O(\log(2+\min\{K,\tau\}))\) fraction of \(\mathrm{OPT}\), the maximum of \(\sum_{t,k}y_{t,k}v_t(k)\) over \(y_{t,k}\ge0\) satisfying \(\sum_k y_{t,k}=\mu_t\) and \(\sum_{t,k}ky_{t,k}=\lambda\).

A society is given by its support: a list \(T\) of \(\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.
The input also contains an integer \(K\ge1\), binary rational per-capita supply \(0<\lambda\le K\), and explicit monotone valuation tables \(v_t:\{0,\ldots,K\}\to\mathbb Q_{\ge0}\) with \(v_t(0)=0\). Let \(L\) be the total input bit length; \(K\) is the quantity parameter replacing \(m\), and running times are measured in \(K,\tau,L\).
A bundling consists of offered sizes \(J\subseteq\{1,\ldots,K\}\), positive rational package masses \(q_j\), and nonnegative rational anonymous prices \(p_j\), satisfying \(\sum_{j\in J}jq_j=\lambda\). Packages cannot be opened or resold.
An individual's feasible choices are \(Z_J=\{z\in\mathbb Z_{\ge0}^{J}:\sum_{j\in J}jz_j\le K\}\), including the empty choice. Only offered sizes may be purchased; their aggregate masses do not bound an individual's choice.
An equilibrium assigns rational masses \(x_{t,z}\ge0\), represented by their nonzero entries, satisfying \(\sum_zx_{t,z}=\mu_t\) and \(\sum_{t,z}x_{t,z}z_j=q_j\) for every \(j\in J\). Whenever \(x_{t,z}>0\), the choice \(z\) maximizes \(v_t(\sum_jjz_j)-\sum_jp_jz_j\) over \(Z_J\); any maximizing choices may share mass.
Its welfare is \(W=\sum_{t,z}x_{t,z}v_t(\sum_jjz_j)\). Define \(\mathrm{OPT}=\max\{\sum_{t\in T}\sum_{k=0}^Ky_{t,k}v_t(k):y_{t,k}\ge0,\ \sum_{k=0}^Ky_{t,k}=\mu_t,\ \sum_{t\in T}\sum_{k=0}^Kky_{t,k}=\lambda\}\).

Can an equilibrium with \(W\ge\mathrm{OPT}/[C\log(2+\min\{K,\tau\})]\), for some universal constant \(C>0\), always be computed in time \(\operatorname{poly}(K,\tau,L)\), or is this approximation guarantee unattainable in polynomial time?

For discrete multi-unit markets, a competitive bundling equilibrium with an \(O(\log(2+\min\{m,n\}))\) welfare approximation exists and is computable in polynomial time using demand queries; a matching logarithmic welfare loss is sometimes unavoidable even with subadditive valuations. [Source](https://arxiv.org/pdf/1406.0576)
No result settling this precise mass model was located.

Result. An equilibrium attaining \(W=\mathrm{OPT}\) can always be computed in time \(\operatorname{poly}(K,\tau,L)\). Offering only singleton packages suffices.

1. A welfare LP with a nonnegative supply price.

Consider the auxiliary linear program
\( \begin{aligned} A=\max_y\quad& \sum_{t\in T}\sum_{k=0}^{K}y_{t,k}v_t(k)\\ \text{subject to}\quad& \sum_{k=0}^{K}y_{t,k}=\mu_t &&(t\in T),\\ &\sum_{t\in T}\sum_{k=0}^{K}k y_{t,k}\leq\lambda,\\ &y_{t,k}\geq0. \end{aligned} \)

Its feasible set is nonempty, because assigning all mass quantity zero is feasible. It is compact, because each variable belongs to \([0,\mu_t]\). Thus an optimum exists.

We first prove \(A=\mathrm{OPT}\), including the existence of an optimum that uses exactly \(\lambda\) units.

Every feasible allocation defining \(\mathrm{OPT}\) is feasible for the auxiliary LP, so \(\mathrm{OPT}\leq A\). Let \(y\) attain \(A\), and write \(s=\sum_{t,k}k y_{t,k}\). If \(s=\lambda\), the reverse inequality follows immediately.

Otherwise \(s<\lambda\leq K\). Define the allocation \(h\) by \(h_{t,K}=\mu_t\) and \(h_{t,k}=0\) for \(k\neq K\). It uses exactly \(K\) units, since \(\sum_t\mu_t=1\). Set
\( \alpha=\frac{\lambda-s}{K-s}, \qquad \widehat y=(1-\alpha)y+\alpha h. \)
Here \(0<\alpha\leq1\), and \(\widehat y\) preserves all type masses and uses exactly \(\lambda\) units.

Monotonicity gives
\( \sum_t\mu_t v_t(K) \geq \sum_{t,k}y_{t,k}v_t(k)=A. \)
Consequently, the welfare of \(\widehat y\) is at least \(A\). Because \(\widehat y\) is feasible for the auxiliary LP, its welfare is also at most \(A\). It therefore attains \(A\) and is feasible for the defining LP of \(\mathrm{OPT}\). This proves \(A=\mathrm{OPT}\).

The dual of the auxiliary LP is
\( \begin{aligned} \min_{a,p}\quad& \sum_{t\in T}\mu_t a_t+\lambda p\\ \text{subject to}\quad& a_t+kp\geq v_t(k) &&(t\in T,\ 0\leq k\leq K),\\ &p\geq0, \end{aligned} \)
where each \(a_t\) is unrestricted in sign. The sign restriction \(p\geq0\) follows from the primal supply inequality.

Both programs have rational optimal solutions, and linear programming strong duality applies: the primal is feasible with finite optimum, and the dual is feasible, for example with \(p=0\) and \(a_t=v_t(K)\).

2. Optimal allocations are individually demanded.

Let \(\widehat y\) be a rational optimal primal allocation using exactly \(\lambda\), and let \((a,p)\) be a rational optimal dual solution. Strong duality yields
\( \begin{aligned} 0 &=\sum_t\mu_t a_t+\lambda p -\sum_{t,k}\widehat y_{t,k}v_t(k)\\ &=\sum_{t,k}\widehat y_{t,k} \bigl(a_t+kp-v_t(k)\bigr). \end{aligned} \)

Every summand is nonnegative by primal and dual feasibility. Thus
\( \widehat y_{t,k}>0 \quad\Longrightarrow\quad v_t(k)-kp=a_t. \)
Meanwhile, dual feasibility gives \(v_t(\ell)-\ell p\leq a_t\) for every \(\ell\in\{0,\ldots,K\}\). Hence every quantity receiving positive mass maximizes that type’s utility at unit price \(p\), including comparison with the empty choice.

3. Construction and polynomial running time.

Offer \(J=\{1\}\), with package mass \(q_1=\lambda>0\) and price \(p_1=p\).

For this bundling, an individual’s feasible choices are exactly \(z_1=k\), for \(k\in\{0,\ldots,K\}\). Assign
\( x_{t,(k)}=\widehat y_{t,k}. \)

The type constraints give \(\sum_k x_{t,(k)}=\mu_t\). Market clearance holds because
\( \sum_{t,k}x_{t,(k)}k=\lambda=q_1. \)
Section 2 proves utility maximization for every positive assignment. The resulting welfare is therefore
\( W=\sum_{t,k}\widehat y_{t,k}v_t(k)=\mathrm{OPT}. \)

For computation, solve the auxiliary rational LP and its dual using polynomial-time rational linear programming. If the computed primal optimum has slack supply, apply the explicit interpolation in Section 1.

There are \(\tau(K+1)\) primal variables and polynomially many explicitly represented constraints. Their coefficient bit lengths are polynomially bounded in the input length and \(\log K\). Rational linear programming supplies optimal solutions with polynomial encoding length; the interpolation also uses only polynomially many rational arithmetic operations and preserves polynomial encoding length. The output has at most \(\tau(K+1)\) nonzero allocation entries. Thus the entire construction runs in \(\operatorname{poly}(K,\tau,L)\) time.

4. Why the discrete welfare loss does not transfer.

The [cited theorem](https://arxiv.org/pdf/1406.0576) concerns finite consumers and indivisible allocations. Here each type’s mass may be divided among utility-maximizing quantities. The proof above shows that this permitted division implements the welfare LP exactly at an anonymous unit price. It also uses the stipulated rule that package supply does not restrict an individual’s feasible choices.

Exact optimality implies the requested logarithmic approximation for a suitable universal constant \(C>0\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The construction gives an equilibrium with welfare exactly \(\mathrm{OPT}\), and its running time and output length are polynomial in \(K,\tau,L\). No major or minor mathematical issues were found.

• Auxiliary LP and existence. The allocation assigning every type quantity zero is feasible. The type constraints and nonnegativity imply \(0\le y_{t,k}\le\mu_t\), so the feasible set is closed and bounded in a finite-dimensional space. The objective is linear, hence an optimum exists. These claims are correct.

• Equality with the exact-supply benchmark. Every allocation feasible for \(\mathrm{OPT}\) satisfies the auxiliary supply inequality. For an auxiliary optimum with supply \(s<\lambda\), the denominator \(K-s\) is strictly positive because \(s<\lambda\le K\). The stated interpolation coefficient therefore satisfies \(0<\alpha\le1\).

The allocation \(h\) preserves every type’s mass and consumes \(K\) units. The interpolation preserves type masses and consumes exactly \(\lambda\). Monotonicity justifies the claimed welfare comparison with \(h\); optimality of \(A\) then forces the interpolated welfare to equal \(A\). Consequently, the argument establishes \(A=\mathrm{OPT}\) and existence of an exact-supply optimum. The endpoint \(\lambda=K\), including the possible value \(\alpha=1\), is handled correctly.

• Dual formulation and theorem hypotheses. The dual is correctly written: each type equality has an unrestricted multiplier \(a_t\), and the supply inequality has a nonnegative multiplier \(p\). Its constraints correctly include quantity zero.

The supplied dual feasible point is valid because monotonicity implies \(v_t(k)\le v_t(K)\). The primal is feasible and has finite optimum. These are sufficient hypotheses for the invoked finite-dimensional LP strong-duality theorem and optimal attainment. Rational coefficients also permit rational optimal solutions. No hypothesis is missing.

• Utility maximization. The displayed primal–dual objective-gap identity is correct because \(\widehat y\) preserves type masses and uses exactly \(\lambda\). Every dual slack is nonnegative, and every allocation weight is nonnegative. Thus positive allocation weight forces zero dual slack.

The subsequent comparison with every quantity \(\ell\in\{0,\ldots,K\}\) establishes utility maximization over the full required domain. The empty choice is included. Arbitrary optimal primal and dual solutions can be paired here; no additional compatibility assumption is needed.

• Equilibrium construction. Offering \(J=\{1\}\) is permitted for every \(K\ge1\). The package mass \(q_1=\lambda\) is positive and rational, and the price is nonnegative and rational. With singleton packages, feasible individual choices are precisely the quantities used in the LP.

The allocation satisfies type-mass conservation, market clearance, and utility maximization for every positive entry. Its welfare is exactly \(\mathrm{OPT}\). The construction correctly uses the task’s explicit permission to divide type mass among maximizing choices and its rule that aggregate package supply does not restrict individual choices.

• Polynomial computation and representation. The LP has \(\tau(K+1)\) variables and polynomially many explicit constraints, with rational coefficients of polynomial encoding length. The invoked polynomial-time rational LP result applies to this representation and supplies exact optimal solutions of polynomial encoding length.

Computing \(s\), performing the stated interpolation when necessary, and writing the allocation require polynomially many rational operations. The arithmetic involves only polynomially many polynomial-length rational inputs, so the encoding-length claim is valid. The stated bound on the number of output entries is also correct.

• Discrete comparison and requested approximation. The cited paper concerns a finite set of consumers and allocations of indivisible goods, consistent with the prover’s description. This comparison is explanatory; the mass-model conclusion follows independently from the verified LP argument. [Cited paper](https://arxiv.org/pdf/1406.0576)

Exact optimality implies the requested approximation for a suitable universal constant: \(\min\{K,\tau\}\ge1\), so the logarithmic denominator is bounded away from zero. Zero welfare, zero prices, flat valuation tables, and support size one introduce no exception.

Actionable feedback: No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩