d4-conf-wine-2015-0015 (d4-conf-wine-2015-0015)

Given slot categories \(J\), mediators \(I\), advertiser types \(\Theta\) with mediator map \(i(\theta)\), binary-rational masses \(\mu_\theta\) summing to \(1\), per-unit supplies \(q_j\), and gross-substitutes valuations \(v_\theta:2^J\to\mathbb{Q}_{\ge 0}\), find a three-party equilibrium. A unit of type mass receives an integral bundle \(S\subseteq J\), while its mass may be divided among bundles. For each mediator \(i\), define \(V_i(z)\) as the maximum of \(\sum_{\theta:i(\theta)=i}\sum_{S\subseteq J}x_{\theta,S}v_\theta(S)\), subject to \(\sum_S x_{\theta,S}=\mu_\theta\), \(\sum_{\theta,S:j\in S}x_{\theta,S}\le z_j\), and \(x_{\theta,S}\ge0\). Find central prices \(r\), mediator quantities \(y_i\), local prices \(p_i\), and assignments \(x\) such that \(\sum_i y_{ij}=q_j\), each \(y_i\) maximizes \(V_i(z)-r\cdot z\), and \(x_{\theta,S}>0\) only when \(S\) maximizes \(v_\theta(S)-p_{i(\theta)}(S)\). Require local use not to exceed \(y_i\), \(p_i\ge r\), and \(p_{ij}=r_j\) wherever mediator \(i\)'s acquired supply is locally unallocated; use the componentwise-minimum envy-free local prices. Valuations may be accessed by demand oracles, with oracle cost stated separately.

Let \(J\) be \(m\ge1\) slot categories and \(I\) a nonempty mediator set. A society is given by its support: \(\tau\) types \(\Theta\), their positive binary-rational masses \(\mu_\theta\) summing to \(1\), and a map \(i:\Theta\to I\); \(\tau\) counts supported types, not possible valuations. Supplies \(q_j\) are nonnegative binary rationals.
Each type has a normalized, monotone gross-substitutes valuation \(v_\theta:2^J\to\mathbb Q_{\ge0}\). Valuations are accessible through exact value and demand oracles; a demand query returns any maximizing bundle, with ties allowed. Let \(L\) include the explicit input bit length and a bound on valuation-answer bit lengths; account separately for oracle calls and their cost.
Write \(p(S)=\sum_{j\in S}p_j\). Mass may split among integral bundles, including the empty bundle. For \(z\in\mathbb R_{\ge0}^J\), define \(V_i(z)=\max\{\sum_{\theta:i(\theta)=i}\sum_{S\subseteq J}a_{\theta,S}v_\theta(S):a\ge0,\ \sum_Sa_{\theta,S}=\mu_\theta,\ \sum_{\theta:i(\theta)=i}\sum_{S\ni j}a_{\theta,S}\le z_j\}\).
An equilibrium has nonnegative central prices \(r\), quantities \(y_i\ge0\), local prices \(p_i\ge r\), and assignments \(x\ge0\), with \(\sum_i y_{ij}=q_j\), \(y_i\in\arg\max_{z\ge0}(V_i(z)-r\cdot z)\), and \(\sum_Sx_{\theta,S}=\mu_\theta\).
For each mediator set \(J_i=\{j:y_{ij}>0\}\). Choose the componentwise-minimum prices above \(r\) permitting a capacity-feasible assignment of its type masses to demanded bundles among \(2^{J_i}\), and extend these prices by \(p_{ij}=r_j\) outside \(J_i\). Among assignments at these prices, maximize total local payments \(\sum_{\theta:i(\theta)=i,S}x_{\theta,S}p_i(S)\).
Require additionally that every positively assigned bundle is demanded among all of \(2^J\), that local use \(u_{ij}=\sum_{\theta:i(\theta)=i}\sum_{S\ni j}x_{\theta,S}\) satisfies \(u_{ij}\le y_{ij}\), and that \(u_{ij}<y_{ij}\) implies \(p_{ij}=r_j\). All remaining allocation ties are unrestricted; represent assignments by their nonzero bundle masses.

Is finding such an equilibrium polynomial-time solvable in \(m,\tau,|I|,L\), with oracle cost accounted for separately, or is it NP-hard?

For finite bidders, envy-free mediators using minimum local prices and payment-maximizing allocations have exactly the demand of aggregate welfare bidders, with corresponding optimal allocations; equilibrium computation is polynomial-time for gross-substitutes valuations ([Ben-Zwi, Henzinger and Loitzenbauer](https://arxiv.org/pdf/1604.05562)).
No result settling this exact mass-and-capacity model was located in the literature search.

Result

Finding an equilibrium is polynomial-time solvable in the stated oracle model. The algorithm uses polynomially many exact value and demand queries, and returns an assignment with at most \(m+\tau\) nonzero bundle masses.

In fact, the construction works for arbitrary normalized, monotone valuations with the stated exact oracles. Gross substitutes is unnecessary here because masses may split among integral bundles.

The key is to construct an equilibrium with \(p_i=r\) for every mediator. We prove that these prices satisfy both local price minimality and local payment maximization.

1. The fractional welfare program

Write \(\Theta_i=\{\theta:i(\theta)=i\}\). Consider the global welfare linear program

\( \displaystyle \begin{aligned} \text{maximize}\quad& W(x)=\sum_{\theta\in\Theta}\sum_{S\subseteq J} x_{\theta,S}v_\theta(S)\\ \text{subject to}\quad& \sum_{S\subseteq J}x_{\theta,S}=\mu_\theta &&(\theta\in\Theta),\\ & \sum_{\theta\in\Theta}\sum_{S\ni j}x_{\theta,S}\le q_j &&(j\in J),\\ &x_{\theta,S}\ge0. \end{aligned} \)

This program is feasible: assign every type its entire mass on the empty bundle. Its feasible region is compact, since each variable lies between zero and its type’s mass. Consequently, an optimum exists.

Its dual is

\( \displaystyle \begin{aligned} \text{minimize}\quad& \sum_{\theta\in\Theta}\mu_\theta\alpha_\theta +\sum_{j\in J}q_jr_j\\ \text{subject to}\quad& \alpha_\theta+r(S)\ge v_\theta(S) &&(\theta\in\Theta,\ S\subseteq J),\\ &r_j\ge0 &&(j\in J). \end{aligned} \)

The variables \(\alpha_\theta\) are formally unrestricted, but the empty-bundle constraints imply \(\alpha_\theta\ge0\).

Define

\( h_\theta(r)=\max_{S\subseteq J}\bigl(v_\theta(S)-r(S)\bigr). \)

Thus dual feasibility is equivalent to \(r\ge0\) and \(\alpha_\theta\ge h_\theta(r)\) for every type.

Choose optimal primal and dual solutions \(x\) and \((\alpha,r)\). Strong linear programming duality applies because the primal is feasible and has a finite optimum.

Let

\( u_j=\sum_{\theta\in\Theta}\sum_{S\ni j}x_{\theta,S}. \)

The difference between the dual and primal objectives is

\( \displaystyle \sum_{\theta,S}x_{\theta,S} \bigl(\alpha_\theta+r(S)-v_\theta(S)\bigr) +\sum_jr_j(q_j-u_j)=0. \)

Every summand is nonnegative. Therefore,

\( x_{\theta,S}>0 \quad\Longrightarrow\quad \alpha_\theta=v_\theta(S)-r(S), \)

and

\( r_j(q_j-u_j)=0 \qquad(j\in J). \)

Because \(\mu_\theta>0\), each type has at least one positively assigned bundle. Dual feasibility then gives

\( \alpha_\theta=h_\theta(r). \)

In particular, every positively assigned bundle is globally demanded at \(r\).

2. Computing exact, succinct optimal solutions

We use the standard exact oracle linear programming theorem: for a rational linear program with polynomially many rows and possibly exponentially many columns, a strong separation oracle for its dual permits exact optimization and recovery of an optimal primal solution supported on polynomially many columns. The running time and number of oracle calls are polynomial in the number of rows and the encoding bounds. Recovery uses an ellipsoid optimality certificate and then solves the finite primal restricted to the certificate’s columns. This is the standard construction described in [Roughgarden and Kearns, Theorem 2.2 and the proof of Theorem 3.5](https://www.timroughgarden.algorithmsilluminated.org/papers/marg.pdf).

We verify the relevant hypotheses here.

Separation using arbitrary demand representatives

The dual has \(d=m+\tau\) variables. Given a candidate \((\alpha,r)\), first check nonnegativity. A negative \(\alpha_\theta\) violates the empty-bundle constraint; a negative \(r_j\) violates its explicit constraint.

Otherwise, for each type, obtain any demand representative

\( D_\theta\in\arg\max_{S\subseteq J} \bigl(v_\theta(S)-r(S)\bigr) \)

and query its value. If

\( \alpha_\theta+r(D_\theta)<v_\theta(D_\theta), \)

return that violated dual constraint. If no type produces a violation, the candidate is feasible.

This is an exact strong separation oracle. Arbitrary tie-breaking is harmless: every maximizing representative has utility \(h_\theta(r)\), so it detects a violation whenever one exists.

Each separation call uses at most \(\tau\) demand queries and \(\tau\) value queries.

Encoding bounds and bounded optimal prices

Let

\( B=\max_{\theta\in\Theta}v_\theta(J), \)

which is obtained with \(\tau\) value queries. Monotonicity and normalization give \(0\le v_\theta(S)\le B\).

There is an optimal dual solution with

\( 0\le r_j\le B, \qquad 0\le\alpha_\theta\le B. \)

To see this, take any feasible dual solution and replace its coordinates by

\( \widehat r_j=\min\{r_j,B\}, \qquad \widehat\alpha_\theta=\min\{\alpha_\theta,B\}. \)

For any dual constraint, if its bundle contains a clipped price coordinate, then \(\widehat r(S)\ge B\ge v_\theta(S)\). If its type coordinate was clipped, then \(\widehat\alpha_\theta=B\ge v_\theta(S)\). If neither happened, the constraint is unchanged. Hence clipping preserves feasibility. It cannot increase the objective, since its coefficients are nonnegative.

All dual constraint coefficients are zero or one, and their right-hand sides are valuation answers with the given bit-length bound. The objective coefficients are explicitly supplied rationals. Thus exact oracle LP optimization has polynomial encoding bounds and makes queries at prices of polynomial bit length.

Assignment support

Introduce one nonnegative slack variable for each supply constraint. The primal then has \(m+\tau\) equality constraints. An optimal basic feasible solution has at most \(m+\tau\) positive variables, including slacks. Consequently, we can recover an optimal assignment satisfying

\( \bigl|\{(\theta,S):x_{\theta,S}>0\}\bigr|\le m+\tau. \)

Its nonzero masses have polynomial bit length: a basis has dimension at most \(d\), has zero-one coefficients, and has rational right-hand sides from the input; Cramer’s rule gives a polynomial encoding bound.

We henceforth use such a recovered optimal assignment.

3. Clearing central quantities

For each mediator define its use vector by

\( u_{ij}=\sum_{\theta\in\Theta_i}\sum_{S\ni j}x_{\theta,S}. \)

Let the global residual supply be

\( e_j=q_j-\sum_i u_{ij}\ge0. \)

Section 1 gives \(r_je_j=0\).

Choose any mediator \(i_0\in I\), which exists by hypothesis, and set

\( y_i= \begin{cases} u_i+e,&i=i_0,\\ u_i,&i\ne i_0. \end{cases} \)

Then

\( \sum_i y_{ij}=q_j, \qquad u_i\le y_i, \qquad r\cdot(y_i-u_i)=0. \)

This also handles supplies larger than total possible use: their residual quantities have zero central price.

4. Each mediator receives an aggregate-demand quantity

Define

\( H_i=\sum_{\theta\in\Theta_i}\mu_\theta h_\theta(r). \)

For any \(z\ge0\), let \(a\) be any assignment feasible in the definition of \(V_i(z)\), and let \(w(a)\) be its use vector. Because \(r\ge0\) and \(w(a)\le z\),

\( \displaystyle \begin{aligned} \sum_{\theta\in\Theta_i,S}a_{\theta,S}v_\theta(S)-r\cdot z &\le \sum_{\theta\in\Theta_i,S} a_{\theta,S}\bigl(v_\theta(S)-r(S)\bigr)\\ &\le \sum_{\theta\in\Theta_i}\mu_\theta h_\theta(r) =H_i. \end{aligned} \)

Maximizing over feasible assignments gives

\( V_i(z)-r\cdot z\le H_i \qquad(z\ge0). \)

The restriction of \(x\) to \(\Theta_i\) is feasible at capacity \(y_i\). Every positively assigned bundle is demanded at \(r\), so

\( \displaystyle \begin{aligned} \sum_{\theta\in\Theta_i,S}x_{\theta,S}v_\theta(S)-r\cdot y_i &= H_i+r\cdot u_i-r\cdot y_i\\ &=H_i. \end{aligned} \)

Therefore \(V_i(y_i)-r\cdot y_i=H_i\), and hence

\( y_i\in\arg\max_{z\ge0}\bigl(V_i(z)-r\cdot z\bigr). \)

The argument includes mediators with no supported types, for which \(H_i=0\).

5. Minimum local prices and maximum local payments

Set \(p_i=r\) for every mediator.

Fix a mediator and recall \(J_i=\{j:y_{ij}>0\}\). If \(x_{\theta,S}>0\) for a type in \(\Theta_i\), then every \(j\in S\) satisfies

\( y_{ij}\ge u_{ij}\ge x_{\theta,S}>0. \)

Thus \(S\subseteq J_i\). Since \(S\) is globally demanded at \(r\), it is also demanded among the bundles in \(2^{J_i}\).

Consequently, the restriction of \(x\) provides a capacity-feasible assignment of all the mediator’s type masses to locally demanded bundles at \(r|_{J_i}\). This price vector is admissible. Every admissible local price vector must be componentwise at least \(r|_{J_i}\), so the componentwise minimum is exactly \(r|_{J_i}\). Extending outside \(J_i\) as required gives \(p_i=r\).

Now consider any capacity-feasible assignment \(a\) at these local prices. Its total payments satisfy

\( \sum_{\theta\in\Theta_i,S}a_{\theta,S}p_i(S) =r\cdot w(a) \le r\cdot y_i. \)

The constructed assignment attains this upper bound:

\( \sum_{\theta\in\Theta_i,S}x_{\theta,S}p_i(S) =r\cdot u_i =r\cdot y_i. \)

It therefore maximizes local payments among the required assignments.

Finally, all additional conditions hold:

• Every positively assigned bundle is globally demanded at \(p_i=r\), by Section 1.
• Local use satisfies \(u_i\le y_i\), by construction.
• Whenever \(u_{ij}<y_{ij}\), the required equality \(p_{ij}=r_j\) holds because \(p_i=r\) everywhere.

Thus \((r,y,p,x)\) is an equilibrium of exactly the specified model.

6. Complexity conclusion

Exact LP optimization and recovery take polynomial time in \(m,\tau,L\), excluding oracle execution costs, and use polynomially many value and demand queries. Constructing and writing the mediator quantities and local prices adds polynomial time in \(m,\tau,|I|,L\).

More explicitly, the total running time has the form

\( \operatorname{poly}(m,\tau,|I|,L) +\sum_{\text{demand calls}} C_D(\theta,p) +\sum_{\text{value calls}} C_V(\theta,S), \)

where both sums contain polynomially many calls and all query prices have polynomial bit length. The output lists at most \(m+\tau\) nonzero bundle masses.

This settles the requested finding problem in the exact oracle model.

⟨structured verdict parsed — rendered above⟩

The prover’s claimed polynomial-time result is correct in the stated exact oracle model. The construction verifies every equilibrium requirement, including minimum local prices, payment maximization, and global demand. I found no major or minor mathematical issues.

• Fractional welfare program and dual.

The primal accurately represents assignment of each supported type’s entire mass, subject to global supply inequalities. Assigning all mass to the empty bundle proves feasibility. There are finitely many variables, each bounded by its type’s mass; the feasible region is closed and bounded, so an optimum exists.

The dual is correctly derived: type-mass equalities produce unrestricted variables \(\alpha_\theta\), and supply inequalities produce nonnegative prices \(r_j\). Normalization makes the empty-bundle constraint exactly \(\alpha_\theta\ge0\).

The use of strong LP duality is justified by primal feasibility and boundedness of its objective.

• Complementary slackness and global demand.

The displayed objective-gap identity is correct. All its terms are nonnegative because both solutions are feasible. Equality of optimal objectives therefore implies
\[ x_{\theta,S}>0\implies \alpha_\theta=v_\theta(S)-r(S), \qquad r_j(q_j-u_j)=0. \]

Positive type masses ensure that every type has a positively assigned bundle. Combining its equality with all dual constraints gives \(\alpha_\theta=h_\theta(r)\). Thus every positively assigned bundle is globally demanded at \(r\), including when demand has ties.

• Exact oracle optimization and primal recovery.

The separation procedure is valid. Negative coordinates are rejected using explicit nonnegativity constraints or empty-bundle constraints before any demand query. For nonnegative \(r\), any maximizing demand representative detects a violated constraint whenever \(\alpha_\theta<h_\theta(r)\). Arbitrary oracle tie-breaking causes no loss.

The stated oracle LP result applies to a rational dual with \(m+\tau\) variables, uniformly bounded constraint encodings, and an exact separation oracle. The cited source supports both separation-based optimization and recovery through a polynomial collection of dual constraints; its Theorem 3.5 proof explicitly uses the corresponding restricted primal. [Roughgarden and Kearns, Theorem 2.2 and proof of Theorem 3.5](https://www.timroughgarden.algorithmsilluminated.org/papers/marg.pdf).

The prover supplies the necessary encoding and boundedness checks. In particular, monotonicity gives \(v_\theta(S)\le B\), and the clipping argument preserves every dual constraint:

• A bundle containing a clipped price has total clipped price at least \(B\).
• A clipped type coordinate contributes \(B\).
• Otherwise the constraint is unchanged.

Nonnegative objective coefficients ensure that clipping cannot increase the objective. Consequently, bounded optimal dual solutions exist. This reasoning remains valid when \(B=0\).

Exact rational LP optimization therefore yields polynomially encoded prices and polynomially many oracle calls. The assumption on valuation-answer lengths bounds the encodings of constraints returned by separation.

• Assignment support and mass encoding.

Adding supply slacks gives \(m+\tau\) equality constraints. An optimal basic feasible solution has at most \(m+\tau\) positive variables, including slacks, so the claimed assignment-support bound follows.

The basic constraint matrix has integer entries of bounded magnitude, and the right-hand side consists of input rationals. The stated Cramer’s-rule argument gives polynomial bit lengths for recovered masses. Obtaining a basic optimum of the finite restricted primal is covered by standard polynomial-time rational LP methods.

• Central clearing and residual supply.

Global primal feasibility gives \(e_j\ge0\), and complementary slackness gives \(r_je_j=0\). Assigning all residual supply to one mediator therefore yields
\[ \sum_i y_{ij}=q_j,\qquad u_i\le y_i,\qquad r\cdot(y_i-u_i)=0. \]

The construction requires only the stipulated nonemptiness of \(I\). It correctly accommodates supplies exceeding possible consumption and a chosen mediator with no supported types.

• Mediator aggregate demand.

For every capacity vector \(z\), nonnegative prices and capacity feasibility justify the first inequality in Section 4. The definition of \(h_\theta(r)\) justifies the second. Hence \(V_i(z)-r\cdot z\le H_i\).

The constructed assignment is feasible at \(y_i\). Its demanded bundles and zero-priced residual capacity make its welfare minus \(r\cdot y_i\) equal to \(H_i\). The upper bound and attained lower bound establish
\[ V_i(y_i)-r\cdot y_i=H_i, \]
proving the required aggregate-demand condition. Empty type sets also satisfy the argument.

• Minimum local prices.

If \(x_{\theta,S}>0\), each item in \(S\) has strictly positive local use and therefore strictly positive capacity. Thus \(S\subseteq J_i\).

A globally demanded bundle contained in \(J_i\) is also demanded over \(2^{J_i}\). The constructed assignment therefore witnesses local feasibility at \(r|_{J_i}\). Since every admissible local price must lie componentwise above this vector, it is the componentwise minimum. The prescribed extension gives \(p_i=r\).

• Payment maximization and remaining conditions.

Every capacity-feasible assignment has payments bounded by \(r\cdot y_i\), using \(r\ge0\). The constructed assignment attains this bound because \(r\cdot u_i=r\cdot y_i\). It therefore maximizes payments over the required locally demanded assignments.

Global demand, local capacity feasibility, and the price equality whenever capacity is underused all follow exactly as stated. No unrestricted allocation tie is improperly constrained.

• Complexity and scope.

The oracle-call counts, polynomial query encodings, succinct assignment representation, and mediator-output construction support the claimed polynomial running time with oracle execution costs charged separately.

Gross substitutes is indeed unused. The broader assertion remains conditional on access to exact demand oracles; the prover correctly separates their execution cost. It does not claim polynomial implementation of demand queries for arbitrary valuations.

No additional clarification is needed to make the argument verifiable.

⟨structured verdict parsed — rendered above⟩