Answer: Polynomial-time solvable, with deterministic welfare exactly \(\mathrm{OPT}\), for both XOS and subadditive CTRs.
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 3 gives an allocation and non- linear pricing rule guaranteeing competitive equilibrium and 1/4 approximation of the efficient allocation for XOS valua- tions and O( log log m log m ) approximation for subadditive valua- tions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\mu_t\) of advertiser types, where type \(t\) has bid \(b_t\) and CTR function \(\theta_t\), and per-position supply \(\rho\) across \(m\) ordered slots, find mass assignments \(x_{t,S}\) to the empty bundle or an interval \(S\), together with common total bundle prices \(p(S)\). Require \(\sum_S x_{t,S}\le\mu_t\), \(\sum_{t,S:\,j\in S}x_{t,S}\le\rho\), and that every \(S\) with \(x_{t,S}>0\) maximizes \(b_t\theta_t(S)-p(S)\), including the empty bundle. Determine whether this can be computed with the paper’s competitive-equilibrium conditions and welfare guarantees: \(1/4\) for XOS CTRs and \(O(\log\log m/\log m)\) for subadditive CTRs.
Let \(M=[m]\), with \(m\ge3\) ordered slots, and let \(\mathcal I\) contain the empty set and all intervals of slots. A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\); \(\tau\) is the support size, not the number of possible types. Masses need not sum to one.
Each type has a nonnegative rational bid \(b_t\) and rational interval CTR values, promised to extend to a nonnegative monotone set function \(\theta_t\) on \(2^M\), with \(\theta_t(\varnothing)=0\) and \(\theta_t(M)=1\). Consider separately XOS and subadditive extensions. Each slot has binary-rational supply \(\rho>0\); \(L\) is the total input bit length.
An allocation consists of rational masses \(x_{t,S}\ge0\), satisfying \(\sum_{S\in\mathcal I}x_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni j}x_{t,S}\le\rho\). Empty assignments represent unserved advertisers.
For market clearance, include an auxiliary zero-valued type of mass \(m\rho\), assigned the residual supply so that every slot constraint becomes equality; its remaining mass receives the empty bundle. Include this type in the equilibrium conditions below.
Common total bundle prices satisfy \(p(\varnothing)=0\) and \(p(S)\in\mathbb Q_{\ge0}\cup\{+\infty\}\). Infinite prices exclude bundles from the offered menu; every positively assigned bundle has finite price. Prices need not be additive.
Require \(x_{t,S}>0\) only when \(S\in\operatorname*{arg\,max}_{T\in\mathcal I}\{b_t\theta_t(T)-p(T)\}\), allowing arbitrary splitting among ties. Thus every advertiser, including unserved mass, receives a utility-maximizing bundle. Payments go entirely to the seller, with no subsidies or outside transfers.
Define \(W(x)=\sum_{t,S}x_{t,S}b_t\theta_t(S)\), excluding the auxiliary type, and let \(\mathrm{OPT}\) be the maximum welfare over feasible mass allocations without pricing requirements.
Can such equilibria be computed in time polynomial in \(m,\tau,L\), with expected welfare at least \(\mathrm{OPT}/4\) for XOS CTRs and at least \(c(\log\log m/\log m)\mathrm{OPT}\) for subadditive CTRs, for some universal \(c>0\), or is achieving either guarantee computationally intractable?
For finite advertisers, a published result guarantees polynomial-time bundle-price equilibrium construction with welfare ratios \(1/4\) for XOS and order \(\log\log m/\log m\) for subadditive CTRs, allowing infinite prices for unoffered bundles. [Ghiasi et al.](https://www.ijcai.org/proceedings/2019/0043.pdf)
No result settling this precise mass-allocation equilibrium problem was located.
The problem is polynomial-time solvable, with welfare exactly \(\mathrm{OPT}\). A deterministic algorithm suffices. Moreover, the proof applies to arbitrary explicitly supplied interval valuations; neither the XOS nor the subadditive promise is needed.
The crucial feature is that advertisers’ masses may be split among bundles. Thus the welfare linear program already describes admissible allocations. For comparison, the finite-advertiser algorithm of [Ghiasi et al.](https://www.ijcai.org/proceedings/2019/0043.pdf) rounds a configuration LP; that rounding is unnecessary here.
Write \(\mathcal I^+=\mathcal I\setminus\{\varnothing\}\) and \(v_t(S)=b_t\theta_t(S)\). Consider the following linear program, whose variables describe only nonempty assignments:
\(\displaystyle \max_{x\ge0}\ \sum_{t=1}^{\tau}\sum_{S\in\mathcal I^+}v_t(S)x_{t,S}\),
subject to
\(\displaystyle \sum_{S\in\mathcal I^+}x_{t,S}\le\mu_t\quad(t=1,\ldots,\tau)\),
\(\displaystyle \sum_{t=1}^{\tau}\sum_{\substack{S\in\mathcal I^+\\j\in S}}x_{t,S}\le\rho\quad(j=1,\ldots,m)\).
Every feasible solution becomes an allocation satisfying the required type equalities by setting
\(\displaystyle x_{t,\varnothing}=\mu_t-\sum_{S\in\mathcal I^+}x_{t,S}\).
Conversely, deleting the empty assignments from any feasible allocation gives a feasible LP solution with the same welfare. Hence this LP has optimum \(\mathrm{OPT}\).
Its dual has a nonnegative variable \(u_t\) for each type constraint and a nonnegative variable \(q_j\) for each slot constraint:
\(\displaystyle \min_{u,q\ge0}\ \sum_{t=1}^{\tau}\mu_tu_t+\rho\sum_{j=1}^{m}q_j\),
subject to
\(\displaystyle u_t+\sum_{j\in S}q_j\ge v_t(S)\quad(t=1,\ldots,\tau,\ S\in\mathcal I^+)\).
The primal is feasible, since the zero vector is feasible. Its feasible region is bounded, because \(0\le x_{t,S}\le\mu_t\). The dual is feasible: take \(q_j=0\) and \(u_t=b_t\), using the promised monotonicity and normalization to obtain \(\theta_t(S)\le1\).
Consequently, strong LP duality gives optimal primal and dual solutions \(x,u,q\) with equal objective values. Choose rational optimal solutions.
For each slot define its residual supply by
\(\displaystyle r_j=\rho-\sum_{t=1}^{\tau}\sum_{\substack{S\in\mathcal I^+\\j\in S}}x_{t,S}\ge0\).
Expanding the difference between the dual and primal objectives gives
\(\displaystyle 0=\sum_{t=1}^{\tau}u_tx_{t,\varnothing}+\sum_{j=1}^{m}q_jr_j+\sum_{t=1}^{\tau}\sum_{S\in\mathcal I^+}x_{t,S}\left(u_t+\sum_{j\in S}q_j-v_t(S)\right)\).
Every summand is nonnegative, by primal and dual feasibility. Therefore:
Define common bundle prices by
\(\displaystyle p(S)=\sum_{j\in S}q_j\quad(S\in\mathcal I)\).
These prices are rational and nonnegative, and \(p(\varnothing)=0\). All bundles have finite prices.
Dual feasibility implies that every nonempty bundle satisfies \(v_t(S)-p(S)\le u_t\). The empty bundle also satisfies this inequality, since its utility is zero and \(u_t\ge0\).
Every positively assigned nonempty bundle attains utility \(u_t\). Whenever the empty bundle is positively assigned, it also attains utility \(u_t=0\). Thus every positive assignment is utility-maximizing over the entire menu, including all unserved advertiser mass.
Give the auxiliary zero-valued type, denoted \(0\), the assignments
\(\displaystyle x_{0,\{j\}}=r_j\quad(j=1,\ldots,m)\),
\(\displaystyle x_{0,\varnothing}=m\rho-\sum_{j=1}^{m}r_j\),
and zero mass on every other bundle.
These assignments are feasible because \(0\le r_j\le\rho\), so \(\sum_jr_j\le m\rho\). Their total mass is exactly \(m\rho\), and they make every slot constraint an equality.
The auxiliary type’s maximum utility is zero: every price is nonnegative, and the empty bundle has price zero. If \(r_j>0\), the preceding calculation gives \(q_j=0\), hence \(p(\{j\})=0\). Therefore every positively assigned auxiliary bundle is utility-maximizing as well.
All payments are nonnegative and go to the seller. In fact, total payments, including the auxiliary type, are
\(\displaystyle \sum_{t=0}^{\tau}\sum_{S\in\mathcal I}x_{t,S}p(S)=\sum_{j=1}^{m}q_j\left(\sum_{t=0}^{\tau}\sum_{\substack{S\in\mathcal I\\j\in S}}x_{t,S}\right)=\rho\sum_{j=1}^{m}q_j\).
The auxiliary type pays zero. No subsidy or outside transfer is used.
We have therefore constructed an equilibrium satisfying every stated requirement. Its real-advertiser welfare is the primal optimum, namely \(\mathrm{OPT}\).
There are \(m(m+1)/2\) nonempty intervals. The primal has \(\tau m(m+1)/2\) variables and \(\tau+m\) resource constraints; the dual also has polynomial size.
All coefficients are rational with encoding lengths polynomial in \(L\): the objective coefficients are products of the supplied bids and CTR values. The standard polynomial-time theorem for rational linear programming therefore computes exact rational optimal primal and dual solutions with polynomial encoding length. Computing the empty assignments, residual assignments, and bundle prices requires only polynomially many rational arithmetic operations.
In particular, the algorithm never expands a mass into individual advertisers. Its running time is polynomial in \(m,\tau,L\), including when masses have very large binary-encoded numerators or denominators.
The output is deterministic and satisfies \(W(x)=\mathrm{OPT}\). Hence its expected welfare meets both requested guarantees. With natural logarithms, one may take \(c=1\), since \(0<\log\log m/\log m<1\) for \(m\ge3\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly constructs a deterministic, polynomial-time equilibrium with welfare exactly \(\mathrm{OPT}\). It settles both requested guarantees for the stated mass-allocation model. No major or minor mathematical issues were found.
The primal correctly represents the allocation problem after removing empty-bundle variables. Its type inequalities ensure that the reconstructed empty assignments are nonnegative, and empty assignments consume no supply and contribute no welfare. The correspondence preserves feasibility and welfare in both directions, so its optimum is exactly \(\mathrm{OPT}\).
The displayed dual is correct: each nonempty assignment variable contributes to its type constraint and precisely those slot constraints belonging to its interval. All primal resource constraints are upper bounds, so the dual variables are nonnegative.
The hypotheses for strong LP duality are satisfied:
Thus the primal has a finite attained optimum, and strong duality supplies an attained dual optimum with the same value. Rational optimal solutions exist because the LP data are rational.
Assessment: correct.
The objective-gap identity is algebraically correct. Substituting the definitions of empty mass and residual supply cancels the type-price and slot-price terms, leaving exactly the dual objective minus the primal objective.
Every summand is nonnegative:
Equality of the optimal objective values therefore implies all three stated complementary-slackness consequences.
The common prices \(p(S)=\sum_{j\in S}q_j\) are permitted by the task. Although prices need not be additive, additive prices are allowed. They are finite, rational, nonnegative, and give the empty bundle price zero.
Dual feasibility bounds every bundle’s utility above by \(u_t\), including the empty bundle. Every positively assigned nonempty bundle attains this bound, and every positively assigned empty bundle attains it because its positive mass forces \(u_t=0\).
There is no hidden demand-attainment gap: each real type has positive total mass, and the menu is finite, so at least one bundle receives positive mass. Hence the upper bound \(u_t\) is attained for each type.
Assessment: every positive real-type assignment satisfies the required utility-maximization condition, including unserved mass.
Each singleton is an allowed interval. The residual quantities satisfy \(0\le r_j\le\rho\), so the auxiliary empty assignment is nonnegative and its total assigned mass is exactly \(m\rho\).
Assigning auxiliary mass \(r_j\) to singleton \(\{j\}\) fills exactly the residual supply of slot \(j\). Thus all slot constraints become equalities.
The auxiliary type has utility at most zero on every bundle and achieves zero on the empty bundle. Whenever its singleton assignment is positive, complementary slackness gives \(q_j=0\), making that singleton’s utility zero as well. Its positive assignments are therefore all utility-maximizing.
The payment calculation is also correct. Interchanging the finite sums expresses total bundle payments as slot prices times cleared slot quantities, giving \(\rho\sum_jq_j\). Every positive auxiliary assignment has price zero, so the auxiliary type pays nothing. All other payments are nonnegative and go to the seller.
Assessment: the construction satisfies clearance, auxiliary demand, and the payment restrictions exactly.
The interval count \(m(m+1)/2\) is correct. Both LPs have polynomially many variables, constraints, and explicitly representable coefficients.
Products of rational bids and rational CTR values have encoding lengths polynomial in the input length. The rational linear-programming theorem invoked here provides exact optimal rational solutions, with polynomial output encoding length, in time polynomial in the encoded LP size. Its hypotheses are met: the LPs have rational data, are feasible, and have finite optimal values.
The subsequent sums, differences, and price calculations involve polynomially many rational operands of polynomial encoding length. Their computation and output sizes are consequently polynomial in \(m,\tau,L\).
The algorithm uses the support directly and never enumerates individual advertisers according to their masses. Large binary-encoded masses therefore do not invalidate the complexity bound.
Assessment: the claimed polynomial-time bound is justified.
The auxiliary type contributes no welfare, so the constructed equilibrium retains the primal optimum: \(W(x)=\mathrm{OPT}\). Determinism makes its expected welfare equal to this value.
The constant claim is correct. For \(m\ge3\), natural logarithms satisfy \(0<\log\log m/\log m<1\), so \(c=1\) meets the requested subadditive guarantee. Exact optimal welfare also meets the XOS guarantee.
Neither XOS nor subadditivity is used in the construction. The broader scope statement is valid within the task’s remaining valuation assumptions; the proof still uses monotonicity and normalization to exhibit dual feasibility.
The introductory comparison with configuration-LP rounding agrees with the cited [Ghiasi et al. paper](https://www.ijcai.org/proceedings/2019/0043.pdf). That comparison is contextual and is not needed for the proof.
Required clarification or repair: 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.