d4-conf-wine-2018-0022 (d4-conf-wine-2018-0022)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to one, per-capita supply \(s\), and explicit normalized, nondecreasing, subadditive valuation tables \(v_t(0),\ldots,v_t(Q)\), define \(\mathrm{OPT}\) as the maximum of \(\sum_{t,q} y_{t,q}v_t(q)\), subject to \(\sum_q y_{t,q}=\mu_t\), \(\sum_{t,q} qy_{t,q}\le s\), and \(y_{t,q}\ge0\). Does there exist a uniform per-item price \(p\), computable from the instance, such that every measurable arrival schedule with type masses \(\mu_t\), and every adversarial resolution of ties, yields welfare at least \(\mathrm{OPT}/3\)? Each infinitesimal buyer chooses an integral bundle size maximizing \(v_t(q)-pq\), subject to available stock; aggregate stock and welfare evolve with arriving mass.

A society is given by its support: the list of \(\tau=|T|\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. Let \(m:=Q\ge1\) be the maximum integral bundle size, let \(s>0\) be rational per-capita supply, and let \(L\) be the total input bit length.
Each type has an explicit nonnegative rational valuation table \(v_t(0),\ldots,v_t(m)\), normalized, nondecreasing, and subadditive. Define \(\mathrm{OPT}=\max\{\sum_{t,q}y_{t,q}v_t(q):\sum_qy_{t,q}=\mu_t,\ \sum_{t,q}qy_{t,q}\le s,\ y_{t,q}\ge0\}\), with \(q\in\{0,\ldots,m\}\).
An arrival schedule is a measurable map \(a:[0,1]\to T\) satisfying \(\lambda(a^{-1}(t))=\mu_t\), where \(\lambda\) is Lebesgue measure. A uniform static price \(p\ge0\) is posted before arrivals.
An outcome consists of measurable integral choices \(q(x)\) and absolutely continuous remaining stock \(R(x)\ge0\), with \(R(0)=s\) and \(R'(x)=-q(x)\) almost everywhere. While \(R(x)>0\), choose any \(q(x)\in\arg\max_{0\le j\le m}\{v_{a(x)}(j)-pj\}\); after exhaustion choose \(q(x)=0\). Thus a mass element \(dx\) choosing \(q\) consumes \(q\,dx\), and exhaustion can split arriving type mass.
Welfare is \(W=\int_0^1v_{a(x)}(q(x))\,dx\); all measurable resolutions of demand ties are adversarial.

Does every instance admit a nonnegative rational uniform static price \(p\), computable in time polynomial in \(m,\tau,L\), guaranteeing \(W\ge\mathrm{OPT}/3\) for every arrival schedule and every adversarial resolution of ties?

For finite buyers with symmetric subadditive valuations, uniform static prices guarantee \(1/3\) of optimal welfare, and no larger constant is universally guaranteed. [Source](https://arxiv.org/html/1705.06623)
No result settling this precise nonatomic approximation question was located in the literature search.

Yes. The following construction gives the requested guarantee in polynomial time. In fact, the proof does not require subadditivity.

1. Demand and a critical price

For each type \(t\) and price \(z\ge 0\), define
\[ U_t(z):=\max_{0\le q\le m}\{v_t(q)-zq\}, \qquad D_t(z):=\arg\max_{0\le q\le m}\{v_t(q)-zq\}. \]
Write \(d_t^-(z):=\min D_t(z)\) and \(d_t^+(z):=\max D_t(z)\), and define
\[ F(z):=sz+\sum_t\mu_t U_t(z). \]

For every feasible allocation \(y\) in the definition of \(\mathrm{OPT}\), the inequality \(v_t(q)\le U_t(z)+zq\) gives
\[ \sum_{t,q}y_{t,q}v_t(q) \le \sum_t\mu_tU_t(z)+z\sum_{t,q}qy_{t,q} \le F(z). \]
Consequently, \(\mathrm{OPT}\le F(z)\) for every \(z\ge0\).

We can compute a rational minimizer \(b\) of \(F\) by evaluating it at the finite set
\[ \mathcal B:= \{0\}\cup \left\{ \frac{v_t(k)-v_t(j)}{k-j}: t\in T,\ 0\le j<k\le m \right\}. \]
Every member is nonnegative by monotonicity. All changes in the maximizing affine functions defining \(U_t\) occur at members of \(\mathcal B\). Thus \(F\) is affine between consecutive members. Beyond the largest member, every type uniquely demands zero, so \(F(z)=sz\), which is strictly increasing. It follows that a global minimum occurs in \(\mathcal B\).

Set
\[ r_t:=d_t^-(b),\qquad h_t:=d_t^+(b),\qquad C:=\sum_t\mu_t r_t,\qquad H:=\sum_t\mu_t h_t. \]
Then
\[ C\le s, \qquad\text{and, if }b>0,\qquad s\le H. \]

Here is an explicit justification. At price \(b\), every nonmaximizing quantity has a strictly positive utility gap. Since there are finitely many quantities, these gaps remain positive under sufficiently small price changes. Among the quantities maximizing at \(b\), increasing the price selects \(r_t\), whereas decreasing it selects \(h_t\). Therefore, for sufficiently small \(\varepsilon>0\),
\[ F(b+\varepsilon)=F(b)+\varepsilon(s-C). \]
Minimality gives \(C\le s\). If \(b>0\), we can also take \(\varepsilon<b\), obtaining
\[ F(b-\varepsilon)=F(b)+\varepsilon(H-s). \]
Minimality then gives \(H\ge s\).

Finally, define
\[ A:=\sum_t\mu_t v_t(r_t). \]
Since \(r_t\in D_t(b)\), we have \(U_t(b)=v_t(r_t)-br_t\). Hence
\[ \mathrm{OPT}\le F(b)=A+b(s-C)\le A+bs. \tag{1} \]

2. A rational price guaranteeing welfare \(A\)

We construct a price \(p_{\mathrm{high}}>b\) at which every type uniquely demands \(r_t\).

For every \(t\) and \(j<r_t\), let
\[ g_{t,j}:=U_t(b)-\bigl(v_t(j)-bj\bigr). \]
These gaps are strictly positive: equality would put \(j\) in \(D_t(b)\), contradicting the minimality of \(r_t\).

Choose
\[ \delta:= \min\left( \{1\}\cup \left\{ \frac{g_{t,j}}{2(r_t-j)}: t\in T,\ 0\le j<r_t \right\} \right), \qquad p_{\mathrm{high}}:=b+\delta. \]
This also defines \(\delta=1\) when the second set is empty.

For \(j<r_t\), the utility advantage of \(r_t\) over \(j\) at \(p_{\mathrm{high}}\) is
\[ g_{t,j}-\delta(r_t-j)\ge g_{t,j}/2>0. \]
For \(j>r_t\), that advantage is
\[ U_t(b)-\bigl(v_t(j)-bj\bigr)+\delta(j-r_t)>0. \]
Thus \(D_t(p_{\mathrm{high}})=\{r_t\}\).

Fix any arrival schedule and any outcome at this price. The total consumption if everyone receives their demand is
\[ \int_0^1r_{a(x)}\,dx=C\le s. \]
We claim that the outcome gives \(q(x)=r_{a(x)}\) almost everywhere.

Indeed, absolute continuity and the stock equation imply
\[ R(x)=s-\int_0^xq(u)\,du. \]
Thus \(R\) is continuous and nonincreasing. Before exhaustion, uniqueness of demand forces \(q(x)=r_{a(x)}\). If exhaustion occurs at some \(e<1\), then
\[ s=\int_0^e r_{a(x)}\,dx \le \int_0^1r_{a(x)}\,dx=C\le s. \]
All inequalities are therefore equalities, and \(\int_e^1r_{a(x)}\,dx=0\). Since this integrand is nonnegative, it vanishes almost everywhere after exhaustion. The claim follows; exhaustion only at the endpoint has no effect on the integral.

Consequently, every outcome at \(p_{\mathrm{high}}\) has welfare
\[ W=\int_0^1v_{a(x)}(r_{a(x)})\,dx =\sum_t\mu_t v_t(r_t)=A. \tag{2} \]

If \(b=0\), inequality (1) already gives \(\mathrm{OPT}\le A\). Therefore \(p_{\mathrm{high}}\) settles this case.

3. A second price guaranteeing welfare \(bs/2\)

Suppose now that \(b>0\), and set \(p_{\mathrm{low}}:=b/2\).

We first establish demand monotonicity, including arbitrary ties. If \(z_1<z_2\), \(q_1\in D_t(z_1)\), and \(q_2\in D_t(z_2)\), optimality gives
\[ v_t(q_1)-z_1q_1\ge v_t(q_2)-z_1q_2, \]
\[ v_t(q_2)-z_2q_2\ge v_t(q_1)-z_2q_1. \]
Adding yields \((z_2-z_1)(q_1-q_2)\ge0\), so \(q_1\ge q_2\).

In particular, every quantity demanded by type \(t\) at \(p_{\mathrm{low}}\) is at least \(h_t\).

Every outcome at \(p_{\mathrm{low}}\) exhausts supply by time \(1\). To prove this, suppose instead that \(R(1)>0\). Monotonicity of stock then implies \(R(x)>0\) throughout the interval. Hence
\[ \int_0^1q(x)\,dx \ge\int_0^1h_{a(x)}\,dx =H\ge s. \]
But the stock equation gives \(\int_0^1q(x)\,dx=s-R(1)<s\), a contradiction.

While stock is positive, demand optimality against the zero bundle, together with \(v_t(0)=0\), gives \(v_{a(x)}(q(x))\ge p_{\mathrm{low}}q(x)\). After exhaustion both quantities are zero. Integrating and using \(R(1)=0\), we obtain
\[ W\ge p_{\mathrm{low}}\int_0^1q(x)\,dx =\frac{bs}{2}. \tag{3} \]
This bound holds for every schedule and every measurable resolution of ties.

4. Price selection and polynomial running time

When \(b=0\), output \(p_{\mathrm{high}}\). Otherwise, output
\[ p:= \begin{cases} p_{\mathrm{high}},& A\ge bs/2,\\ p_{\mathrm{low}},& A<bs/2. \end{cases} \]
Equations (2) and (3) guarantee
\[ W\ge M:=\max\{A,bs/2\}. \]
Since \(A\le M\) and \(bs\le2M\), inequality (1) implies
\[ \mathrm{OPT}\le A+bs\le3M\le3W. \]
Thus the selected price guarantees \(W\ge\mathrm{OPT}/3\).

The set \(\mathcal B\) has \(O(\tau m^2)\) members. Evaluating \(F\) at each member requires \(O(\tau m)\) rational operations. Computing \(r_t,h_t,A,C,H\), and \(\delta\) requires polynomially many further operations. Every candidate price is formed from input rationals by differences and division by integers of magnitude at most \(m\); all subsequent sums, comparisons, and price calculations have polynomial bit length in \(m,\tau,L\). Exact rational arithmetic therefore implements the entire construction in polynomial time.

The output is a nonnegative rational price, and the proof covers all the instances in the question.

⟨structured verdict parsed — rendered above⟩

Verification report

The proof is correct and resolves the assigned question. The construction gives a nonnegative rational price in polynomial time and establishes the guarantee for every permitted arrival schedule and measurable resolution of demand ties. No major or minor mathematical issues were found.

The proof uses normalization as \(v_t(0)=0\), consistent with the task. Its stronger assertion that subadditivity is unnecessary is supported by the argument.

1. Upper bound and critical price

The inequality \(v_t(q)\le U_t(z)+zq\) holds by the definition of \(U_t\). Summing it over a feasible allocation correctly uses the type-mass constraints. The subsequent supply bound requires \(z\ge0\), which is explicitly imposed. Thus \(\mathrm{OPT}\le F(z)\) is valid.

The proposed candidate set contains every possible intersection of distinct affine functions defining each \(U_t\). Monotonicity makes all listed intersection prices nonnegative. Consequently, \(F\) is affine between consecutive candidate prices.

Beyond the largest candidate, zero uniquely maximizes each type’s utility: its intersection with every positive quantity is among the candidates. Normalization therefore gives \(F(z)=sz\) there. Since \(s>0\), the tail is strictly increasing. These observations justify the existence of a minimizer in the finite candidate set, including the possibility of a constant segment.

The perturbation argument at \(b\) is valid. Finiteness permits a common sufficiently small perturbation preserving all strict utility gaps. Increasing price selects the smallest maximizing quantity; decreasing price selects the largest. The stated expressions for \(F(b+\varepsilon)\) and \(F(b-\varepsilon)\) have the correct signs. Minimality yields \(C\le s\), and yields \(H\ge s\) when \(b>0\).

The identity \(F(b)=A+b(s-C)\) follows directly from the utility equality at \(r_t\). Because \(b,C\ge0\), the upper bound \(\mathrm{OPT}\le A+bs\) is correct.

2. The higher price

Every gap \(g_{t,j}\) with \(j<r_t\) is strictly positive, as claimed. The definition of \(\delta\) therefore produces a positive rational number, including when the indexed set is empty.

Both utility comparisons are correct:

• For \(j<r_t\), the chosen \(\delta\) preserves a strictly positive advantage.
• For \(j>r_t\), the original advantage is nonnegative and the price increase adds a strictly positive term.

Thus each type uniquely demands \(r_t\) at \(p_{\mathrm{high}}\).

The exhaustion argument correctly addresses arbitrary schedules. Before exhaustion, uniqueness forces the designated demand. If exhaustion occurs before time \(1\), the equality chain using \(C\le s\) forces the remaining designated consumption to vanish almost everywhere. Actual and designated quantities consequently agree almost everywhere throughout the interval.

Normalization ensures that quantities equal to zero after exhaustion contribute zero welfare. The conclusion \(W=A\) is valid. When \(b=0\), the earlier upper bound reduces to \(\mathrm{OPT}\le A\), so this case is fully settled.

3. The lower price

The demand-monotonicity calculation is correct and applies to every pair of maximizing quantities, including ties. Since \(b/2<b\), every demanded quantity at \(p_{\mathrm{low}}\) is at least \(h_t\).

The contradiction argument establishes exhaustion by time \(1\). If \(R(1)>0\), nonincreasing stock remains positive throughout, so total consumption is at least \(H\ge s\). This contradicts the stock equation, which gives consumption strictly below \(s\).

Demand optimality against the zero bundle gives \(v_{a(x)}(q(x))\ge p_{\mathrm{low}}q(x)\) while stock is positive. After exhaustion, normalization makes the same inequality valid with both sides zero. Integration therefore correctly yields \(W\ge bs/2\).

4. Selection, quantifiers, and complexity

The selection rule chooses the price associated with the larger established lower bound. Hence \(W\ge M=\max\{A,bs/2\}\), and the calculation \(\mathrm{OPT}\le A+bs\le3M\le3W\) is correct.

Both component guarantees hold independently of arrival order and tie resolution. The selected price depends only on the input, so the required universal quantifiers are preserved.

The candidate count and evaluation costs are polynomial. Rational differences, divisions by bounded integers, weighted sums, and comparisons have polynomial bit complexity here. The construction requires no search over schedules or outcomes.

Degenerate valuation tables, empty gap sets, endpoint exhaustion, and supply exceeding total possible consumption are covered by the written argument.

Required feedback

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩