d4-conf-atal-2006-0163 (d4-conf-atal-2006-0163)

Given a finite item set \(I\), a rational distribution \(\mu\) over positive-valued single-minded incumbent bid types \(t=(B_t,v_t)\), and two explicit colluders, can the colluders win all items with zero VCG payment?

Consider a forward auction with free disposal on an item set \(I\), where \(m=|I|\geq 2\) and each item has unit supply. A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types.
Each incumbent type is \(t=(B_t,v_t)\), with \(\varnothing\neq B_t\subseteq I\), positive rational \(v_t\), and mass \(\mu_t>0\), where \(\sum_t\mu_t=1\). Serving mass \(x_t\in[0,\mu_t]\) consumes \(x_t\) units of every item in \(B_t\) and contributes welfare \(v_tx_t\).
Two explicit colluders may each submit one bid \((C_c,w_c)\), choosing a nonempty bundle \(C_c\subseteq I\) and an unrestricted nonnegative rational value \(w_c\). Their acceptance variables are \(z_c\in\{0,1\}\); accepting a colluder consumes one unit of every item in its bundle.
Winner determination maximizes \(a=\sum_t v_tx_t+\sum_{c=1}^{2}w_cz_c\), subject to \(\sum_{t:s\in B_t}x_t+\sum_{c:s\in C_c}z_c\leq1\) for every \(s\in I\). Among maximizers, choose the lexicographically largest \((z_1,z_2,x_1,\ldots,x_\tau)\), using the input order of types.
Let \(a_{-c}\) be the maximum welfare after removing colluder \(c\), leaving the incumbent society unchanged. Its Clarke-pivot payment is \(p_c=a_{-c}-(a-w_cz_c)\). The decision problem asks whether bids exist for which \(z_1=z_2=1\), \(C_1\mathbin{\dot\cup}C_2=I\), and \(p_1=p_2=0\); no self-enforcement requirement is imposed. Let \(L\) be the total binary input length.

Is this continuous zero-payment collusion decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite incumbent bidders, the corresponding two-colluder decision problem is NP-complete: partitioning items into two parts so that no positive incumbent bundle lies wholly in either part is NP-complete. [Conitzer–Sandholm](https://www.cs.cmu.edu/~conitzer/vcgfailuresAAMAS06.pdf)
No result settling the exact mass-incumbent problem defined here was located in the literature search.

Result

The decision problem is \(\mathrm{NP}\text{-complete}\), even when every incumbent value equals \(1\) and every mass is dyadic. Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

The key characterization is exact: successful bids exist if and only if the items admit a partition into two nonempty parts such that every incumbent bundle intersects both parts.

1. Incumbent welfare on available items

For \(S\subseteq I\), define
\[ V(S)=\sum_{t:B_t\subseteq S}\mu_t v_t, \qquad V=V(I). \]

This is exactly the maximum incumbent welfare when only the items in \(S\) are available.

Indeed, a type whose bundle is not contained in \(S\) cannot receive positive mass. All remaining types can simultaneously receive their full masses: for every available item \(s\),
\[ \sum_{t:B_t\subseteq S,\ s\in B_t}\mu_t \leq \sum_t\mu_t=1. \]
This allocation attains \(V(S)\). Conversely, the upper bounds \(x_t\leq\mu_t\) imply that no feasible allocation exceeds \(V(S)\).

Because every \(\mu_t v_t\) is strictly positive,
\[ V(S)=0 \quad\Longleftrightarrow\quad \text{no incumbent bundle is contained in }S. \]
Also, \(V>0\).

2. Exact characterization of successful bids

Fix a partition \(C_1\mathbin{\dot\cup}C_2=I\) with both parts nonempty.

If both colluders are accepted, every item’s entire supply is consumed. Since every incumbent bundle is nonempty, this forces \(x_t=0\) for every type. Consequently,
\[ a=w_1+w_2. \]

After removing colluder \(1\), there are two possibilities. Rejecting colluder \(2\) yields maximum welfare \(V\). Accepting colluder \(2\) leaves exactly \(C_1\) available to incumbents and yields maximum welfare \(w_2+V(C_1)\). Therefore,
\[ a_{-1}=\max\{V,w_2+V(C_1)\}, \]
and, conditional on both colluders being accepted,
\[ p_1=\max\{V-w_2,V(C_1)\}. \]
Likewise,
\[ p_2=\max\{V-w_1,V(C_2)\}. \]

Since \(V(C_1)\) and \(V(C_2)\) are nonnegative, zero payments require
\[ V(C_1)=V(C_2)=0, \qquad w_1\geq V,\qquad w_2\geq V. \]
In particular, every incumbent bundle must intersect both parts.

Conversely, suppose every incumbent bundle intersects both parts. Then \(V(C_1)=V(C_2)=0\). Choose the rational bids
\[ w_1=w_2=V. \]
Accepting both colluders yields welfare \(2V\). Accepting exactly one yields welfare \(V\), because no incumbent can be served alongside that colluder. Accepting neither yields welfare \(V\). Since \(V>0\), every maximizing allocation accepts both colluders. Thus the specified tie-breaking rule also accepts both.

The payment formulas now give \(p_1=p_2=0\).

We have proved:
\[ \text{successful bids exist} \quad\Longleftrightarrow\quad \text{there is a nonempty two-part partition splitting every }B_t. \]

3. Polynomial-time reduction establishing hardness

Use the known \(\mathrm{NP}\text{-complete}\) problem of partitioning a ground set into two parts so that no listed subset lies wholly in either part. This is DIVIDE-SUBSETS with two parts, equivalently hypergraph two-colorability; see Theorem 3 of [Conitzer–Sandholm](https://www.cs.cmu.edu/~conitzer/vcgfailuresAAMAS06.pdf).

We may assume the ground set \(I\) has at least two items and the family consists of \(q\geq1\) distinct nonempty subsets \(B_1,\ldots,B_q\). These restrictions preserve hardness: instances with an empty subset, no subsets, or fewer than two items are directly decidable and can be replaced by fixed instances satisfying the restrictions. For example, on two items \(a,b\), the family consisting of \(\{a,b\}\) is a yes-instance, whereas the family consisting of \(\{a\}\) is a no-instance. Duplicate subsets can be deleted.

Let \(N\) be the smallest power of two strictly greater than \(q\). Construct the society as follows:

• For each \(B_j\), create type \((B_j,1)\) with mass \(1/N\).
• Add type \((I,1)\) with mass \((N-q)/N\).
• If \((I,1)\) already occurs, merge its two masses into one support entry.

Every resulting mass is a positive dyadic rational, all values equal \(1\), and the masses sum to
\[ \frac{q}{N}+\frac{N-q}{N}=1. \]
Merging preserves these properties. The support has at most \(q+1\) entries.

The additional bundle \(I\) intersects both parts of every nonempty partition. Consequently, the constructed society admits a partition splitting all its bundles if and only if the original family does. Because \(q\geq1\), any partition splitting the original family necessarily has both parts nonempty.

By the characterization in Section 2, the original instance is therefore a yes-instance if and only if the constructed auction admits successful zero-payment bids.

Finally, \(N\leq2q\), so each mass requires only \(O(\log q)\) bits. The construction and its output length are polynomial in the source input length. This proves \(\mathrm{NP}\text{-hardness}\) under all the stated auction hypotheses.

4. Membership and conclusion

A certificate is an assignment of each item to one of two parts. Verify that both parts are nonempty and that every listed incumbent bundle contains an item from each part. This requires time polynomial in \(m,\tau,L\).

Section 2 proves that this verification accepts exactly the yes-instances. No unbounded bid values or continuous allocations need to be included in the certificate.

Hence the continuous zero-payment collusion decision problem is \(\mathrm{NP}\text{-complete}\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The characterization, reduction, and membership argument are correct under the exact mass-incumbent model in USER_TASK. I found no major or minor issues.

• Incumbent welfare on available items.

The formula \(V(S)=\sum_{t:B_t\subseteq S}\mu_t v_t\) is correct. Any bundle using an unavailable item must have zero served mass. All remaining types can receive their full masses simultaneously: their total consumption of each item is at most \(\sum_t\mu_t=1\). The individual bounds \(x_t\leq\mu_t\), together with positive values, give the matching upper bound.

Strict positivity of every \(\mu_t v_t\) justifies the equivalence between \(V(S)=0\) and the absence of an incumbent bundle contained in \(S\). The normalization and positive values also imply \(V>0\).

• Necessary conditions for successful bids.

A partition covering all items, with both colluders accepted, exhausts every item’s supply. Since incumbent bundles are nonempty, every incumbent served mass must be zero. Hence \(a=w_1+w_2\).

After removing colluder \(1\), the two possible acceptance states of colluder \(2\) are exhaustive. They give welfare \(V\) and \(w_2+V(C_1)\), respectively. Substitution into the specified pivot-payment formula correctly gives \(p_1=\max\{V-w_2,V(C_1)\}\). The symmetric expression for \(p_2\) is also correct.

Because \(V(C_1)\) and \(V(C_2)\) are nonnegative, both payments vanish exactly when \(V(C_1)=V(C_2)=0\), \(w_1\geq V\), and \(w_2\geq V\), conditional on acceptance. For a nonempty incumbent bundle in a two-part partition, being contained in neither part is equivalent to intersecting both. The necessity argument is complete.

• Sufficiency and tie-breaking.

For a partition splitting every incumbent bundle, the proposed values \(w_1=w_2=V\) are permitted nonnegative rational bids.

Accepting both colluders yields \(2V\). Accepting exactly one prevents every incumbent from being served and yields \(V\); accepting neither also yields \(V\). Since \(V>0\), both colluders are accepted in every welfare-maximizing allocation. Thus the specified lexicographic rule introduces no unresolved tie. The payment formulas give zero payments.

This establishes both directions of the claimed characterization.

• Cited hardness theorem.

The cited source defines DIVIDE-SUBSETS as partitioning a ground set into parts so that no listed subset is contained in one part. Its Theorem 3 explicitly establishes NP-completeness even for two parts. This matches the source problem stated by the prover. [Conitzer–Sandholm, Definition 1 and Theorem 3](https://www.cs.cmu.edu/~conitzer/vcgfailuresAAMAS06.pdf)

The restrictions to at least two items and at least one distinct nonempty subset preserve hardness as explained. Exceptional instances are directly decidable, the proposed fixed yes- and no-instances have the required properties, and deleting duplicate subsets preserves feasibility.

• Reduction and encoding bounds.

Choosing the smallest power of two \(N>q\) gives \(q<N\leq2q\). Consequently, all assigned masses are positive dyadic rationals and sum to one. Merging the full-ground-set type when necessary preserves positivity, normalization, and the bundle constraints.

The added bundle \(I\) intersects both parts of every nonempty partition. Conversely, because the original family contains a nonempty bundle, any partition splitting every original bundle already has two nonempty parts. Therefore the added type preserves the answer in both directions.

The support bound of \(q+1\), the \(O(\log q)\) mass-encoding bound, and the polynomial output-size claim are correct. Every constructed instance satisfies the auction hypotheses, with all incumbent values equal to one.

• NP membership and conclusion.

An item-to-part assignment has polynomial size. Checking nonemptiness of both parts and that each explicitly listed bundle meets both parts takes polynomial time in \(m,\tau,L\).

The proved characterization makes this certificate sound and complete. Neither bid values nor continuous allocations need to be certified. Thus NP membership and NP-hardness jointly establish NP-completeness for the exact continuous problem.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩