d4-conf-wine-2015-0023 (d4-conf-wine-2015-0023)

For a finite set of item categories \(\Omega\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_j\), and a price increment \(\varepsilon\), let each complete bidder type \(t\) have a monotone, \(\alpha\)-near-submodular valuation \(v_t(S)\) over integral bundles \(S\subseteq\Omega\). In a specified mass-SMRA with uniform category prices, type-state masses choose truthful conditional bids, category capacity is \(q_j\), and standing-high-bid mass is updated with a fixed measurable tie rule. Is every terminal outcome’s welfare at least \(\beta\,\mathrm{OPT}(\mu,q)\), where \(\mathrm{OPT}\) maximizes welfare over feasible allocations of integral bundles subject to the type masses and category supplies; in particular, does the bound \(\beta=1/(1+\alpha)\) hold, with \(\alpha\)-individual rationality almost everywhere?

Let \(\Omega\) contain \(m\ge1\) categories. A society is given by its support: the list of its \(\tau\) positive-mass types, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Supplies satisfy \(q_j\in\mathbb Q\cap(0,1]\), and \(\varepsilon\in\mathbb Q_{>0}\). Each individual receives an integral bundle, containing at most one unit per category.
Each type has an explicitly tabulated monotone valuation \(v_t:2^\Omega\to\mathbb Q_{\ge0}\), normalized by \(v_t(\varnothing)=0\). For rational \(\alpha\ge1\), near-submodularity means \(\alpha[v_t(A\cup\{j\})-v_t(A)]\ge v_t(B\cup\{j\})-v_t(B)\) whenever \(A\subseteq B\subseteq\Omega\setminus\{j\}\).
Represent individuals by disjoint intervals \(I_t\subseteq[0,1)\) of lengths \(\mu_t\), in support-list order, with Lebesgue measure. Initially all provisional bundles \(S^0(u)\) and category prices \(p_j^0\) are empty and zero, respectively; write \(p^r(A)=\sum_{j\in A}p_j^r\).
In round \(r\), an individual of type \(t\) holding \(S\) chooses \(T\subseteq\Omega\setminus S\) maximizing \(v_t(S\cup T)-v_t(S)-\sum_{j\in T}(p_j^r+\varepsilon)\). Resolve ties first by minimum cardinality, then lexicographically under a fixed category order; incumbent bids cannot be withdrawn.
For category \(j\), let \(N_j=\{u:j\in T^r(u)\}\) and \(H_j=\{u:j\in S^r(u)\}\). If \(N_j\) has zero mass, preserve its price and holders. Otherwise increase \(p_j\) by \(\varepsilon\), select the first \(\min(q_j,|N_j|)\) mass of \(N_j\) in increasing coordinate order, and retain the first \(\min(|H_j|,q_j-\min(q_j,|N_j|))\) mass of \(H_j\); these are its new holders. Here \(|\cdot|\) denotes Lebesgue measure.
Selections for all categories occur simultaneously and determine the next provisional bundles. All holders, including retained incumbents, face the updated uniform category price. Stop when nonempty conditional bids have zero mass, and allocate the provisional bundles at those prices.
Define \(\mathrm{OPT}(\mu,q)=\max_{x\ge0}\sum_{t,S}x_{t,S}v_t(S)\), subject to \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni j}x_{t,S}\le q_j\). Terminal welfare is \(W=\sum_t\int_{I_t}v_t(S(u))\,du\). Let \(L\) be the total binary input length; state any running times in \(m,\tau,L\) and the numerical parameters.
Does every terminal outcome satisfy \(W\ge\mathrm{OPT}(\mu,q)/(1+\alpha)\), and does \(\alpha v_t(S^r(u))\ge p^r(S^r(u))\) hold almost everywhere in every round?
For discrete single-item SMRA, conditional truthful bidding is stated to guarantee welfare at least \(1/(1+\alpha)\) of optimum and \(\alpha\)-individual rationality. [Bousquet, Cai and Vetta](https://www.cs.yale.edu/homes/cai/publication/smra/smra.pdf)
No result settling this precisely specified mass auction was located.

Conclusion

Both assertions are false for the specified auction, even with one category and \(\alpha=1\).

The welfare assertion fails because the bid increment is positive. The rationality assertion has a further obstruction: retained incumbents can face repeated price increases without placing new bids. This failure persists as the increment tends to zero.

1. Welfare: the worst-case ratio is zero

For one category \(\Omega=\{a\}\), every normalized monotone valuation is submodular: the only permitted pair in the near-submodularity condition is \(A=B=\varnothing\). Thus all examples below satisfy the condition with \(\alpha=1\).

The immediate counterexample has one type of mass \(1\), supply \(q_a=1\), and
\[ v(\{a\})=\frac{\varepsilon}{2}. \]
Its conditional bid has utility \(-\varepsilon/2\), so the auction stops immediately. Consequently,
\[ W=0, \qquad \mathrm{OPT}=\frac{\varepsilon}{2}>0. \]

The failure also occurs with positive bidding activity. Fix \(\varepsilon=1\), \(q_a=1\), and a positive dyadic rational \(\delta<1\). Use the following support, in the displayed order:

| Type | Mass | Value of \(\{a\}\) |
|---|---:|---:|
| Low | \(1-\delta\) | \(1/2\) |
| High | \(\delta\) | \(2\) |

Initially, the low type strictly prefers the empty bid, while the high type strictly bids for \(a\). All high individuals receive it, and its price becomes \(1\).

In the next round, high individuals already hold the only category. Low individuals obtain conditional utility \(1/2-2<0\) from bidding. Thus this is terminal, with
\[ W=2\delta. \]
Since supply is \(1\) and both valuations are positive, allocating \(a\) to everyone is feasible and optimal. Hence
\[ \mathrm{OPT} =\frac{1-\delta}{2}+2\delta =\frac{1+3\delta}{2}, \qquad \frac{W}{\mathrm{OPT}} =\frac{4\delta}{1+3\delta}. \]

This ratio tends to zero as \(\delta\) tends to zero. For any prescribed rational \(\alpha\ge1\), these valuations are also \(\alpha\)-near-submodular, and choosing
\[ 0<\delta<\frac{1}{1+4\alpha} \]
gives
\[ W<\frac{\mathrm{OPT}}{1+\alpha}. \]

Thus no positive multiplicative welfare guarantee holds under the stated hypotheses, even among instances with a nonempty updating round.

2. Rationality: retained holders can be overcharged arbitrarily

This construction uses fixed positive valuations and permits arbitrarily small increments.

Let \(\Omega=\{a\}\), \(q_a=3/4\), and choose integers \(K\ge2\) and \(n\ge2\). Set \(\varepsilon=1/n\). The support consists of two types:

| Type | Interval | Mass | Value of \(\{a\}\) |
|---|---|---:|---:|
| Low | \([0,1/2)\) | \(1/2\) | \(1\) |
| High | \([1/2,1)\) | \(1/2\) | \(K\) |

All valuations are normalized, monotone, and \(1\)-near-submodular.

Write
\[ J_0=[1/2,3/4), \qquad J_1=[3/4,1). \]

First update

At price zero, every individual strictly bids for \(a\), since \(1>\varepsilon\). The first \(3/4\) mass is selected. Therefore
\[ p_a^1=\frac1n, \qquad H_a^1=[0,1/2)\cup J_0. \]

Subsequent updates

Suppose that after \(r\ge1\) updates,
\[ p_a^r=\frac rn, \qquad H_a^r=[0,1/2)\cup J_i \]
for some \(i\in\{0,1\}\).

Every low individual holds \(a\), so has no category available to bid for. The high holders likewise cannot bid. The remaining high individuals, precisely \(J_{1-i}\), bid if and only if
\[ K-\frac{r+1}{n}>0. \]
At equality, the empty bid wins by minimum cardinality.

Whenever this inequality holds, newcomers have mass \(1/4\), and all are selected. The remaining capacity is \(1/2\). The first \(1/2\) mass of incumbents is exactly the entire low interval. Consequently,
\[ p_a^{r+1}=\frac{r+1}{n}, \qquad H_a^{r+1}=[0,1/2)\cup J_{1-i}. \]

This proves the asserted pattern inductively.

Terminal state and violation

There are exactly \(nK-1\) updating rounds. At their end,
\[ p_a=K-\frac1n. \]
The unallocated high individuals would obtain utility
\[ K-(p_a+\varepsilon)=0, \]
so choose the empty bid. Everyone else holds \(a\); hence the auction terminates.

Throughout, every low individual remains allocated \(a\). At termination, for every individual in its interval,
\[ v_{\mathrm{Low}}(\{a\})=1 < K-\frac1n =p_a. \]
Thus \(1\)-individual rationality fails on a set of mass \(1/2\).

More generally, for any prescribed \(\alpha\ge1\), choose \(K>\alpha+1/n\). The same valuations satisfy \(\alpha\)-near-submodularity, but
\[ \alpha v_{\mathrm{Low}}(\{a\}) =\alpha < p_a. \]

The ratio of price to the low type’s value is \(K-1/n\), so the violation is unbounded. For fixed \(K\), letting \(n\) tend to infinity makes \(\varepsilon\) tend to zero while the terminal price tends to \(K\). Therefore this failure does not disappear with small increments.

For completeness, this family’s welfare is
\[ W=\frac12+\frac K4, \qquad \mathrm{OPT}=\frac K2+\frac14. \]
The optimal allocation gives \(a\) to all high individuals and to mass \(1/4\) of low individuals. Its optimality follows because high value exceeds low value and total supply is \(3/4\). Hence
\[ \frac{W}{\mathrm{OPT}}=\frac{K+2}{2K+1}\longrightarrow\frac12. \]
This family demonstrates the rationality failure; it does not itself violate the welfare bound with \(\alpha=1\).

3. Finite termination and exact simulation

The counterexamples do not depend on a termination ambiguity. In fact, every specified instance terminates.

For each category define its maximum marginal value
\[ D_j= \max_{\substack{t\\A\subseteq\Omega\setminus\{j\}}} \bigl(v_t(A\cup\{j\})-v_t(A)\bigr). \]

If a chosen conditional bid \(T\) contains \(j\), optimality and minimum-cardinality tie-breaking imply
\[ v_t(S\cup T)-v_t\bigl(S\cup(T\setminus\{j\})\bigr) > p_j^r+\varepsilon. \]
Indeed, if the left side were smaller, deleting \(j\) would improve utility; if equal, deleting it would preserve utility and reduce cardinality.

Thus any price increase satisfies
\[ p_j^{r+1}=p_j^r+\varepsilon<D_j. \]
Starting from zero, category \(j\) can therefore increase at most
\[ C_j=\max\left\{0,\left\lceil\frac{D_j}{\varepsilon}\right\rceil-1\right\} \]
times. Every nonterminal round increases at least one category: a positive-mass set of nonempty bids is the finite union of the sets \(N_j\), so some \(N_j\) has positive mass. Consequently, the number \(R\) of updating rounds satisfies
\[ R\le\sum_{j\in\Omega}C_j. \]

An exact simulation can maintain a partition into intervals on which type and provisional bundle are constant. Initially there are \(\tau\) intervals. Each category update introduces at most two new endpoints, one for the newcomer prefix and one for the incumbent prefix. After \(R\) updates there are therefore at most \(\tau+2mR\) intervals.

Enumerating conditional bids on each interval and performing the prefix selections yields a bit-running-time bound of
\[ O\!\left( (R+1)(\tau+2mR)m\,2^m \operatorname{poly}\!\bigl(L+m+\log(R+2)\bigr) \right). \]
Endpoints remain integer multiples of the reciprocal of a common denominator of the input masses and supplies, whose binary length is \(O(L)\). Prices are integer multiples of \(\varepsilon\). Thus the arithmetic has polynomial bit complexity in the displayed arguments. The bound depends on the numerical ratios \(D_j/\varepsilon\), and need not be polynomial in \(L\).

4. Why the cited proof does not transfer

The rationality induction in [Bousquet, Cai and Vetta, Section 3.1](https://www.cs.yale.edu/homes/cai/publication/smra/smra.pdf) uses the fact that an incumbent retained across a round keeps the same item price. The specified mass rule permits retention together with a price increase; Section 2 above exhibits the resulting failure.

Their welfare proof also uses full allocation of every positive-price item. Here a positive-price category can remain undersupplied, as in Section 1.

Finally, terminal conditional optimality in the stated auction gives, for any comparison bundle \(A\), almost everywhere,
\[ v_t(A) \le v_t(S\cup A) \le v_t(S)+p(A\setminus S)+\varepsilon|A\setminus S|. \]
The first inequality is monotonicity. The second compares the empty terminal bid with \(A\setminus S\). Thus positive increments must also be accounted for in any attempted welfare argument.

These counterexamples completely settle both assertions for the auction as specified.

⟨structured verdict parsed — rendered above⟩

The prover correctly resolves both assertions negatively. The counterexamples obey the specified auction rules, including coordinate priority, simultaneous updates, uniform incumbent prices, and minimum-cardinality tie-breaking. No major or minor mathematical issues were found.

1. Admissibility of the examples

With one category, the near-submodularity condition only compares the marginal at the empty set with itself. The displayed nonnegative valuations therefore satisfy the condition for every rational \(\alpha\ge1\).

All examples have positive rational support masses summing to one, admissible supplies, positive rational increments, and explicitly specified normalized monotone valuations. The constructions use the actual support size correctly.

2. Welfare counterexamples

Immediate termination. For the single type, the singleton bid has utility \(-\varepsilon/2\), whereas the empty bid has utility zero. Everyone chooses the empty bid, so immediate termination and welfare zero follow. Allocating the category to everyone is feasible and gives the stated positive optimum. This alone disproves the proposed welfare guarantee.

Positive bidding activity. In the two-type example:

• Initially, low individuals have singleton utility \(-1/2\); high individuals have singleton utility \(1\).
• The newcomer mass is \(\delta<q_a=1\), so all high individuals receive the category, and its price becomes one.
• Subsequently, high holders have no available category, and low individuals have singleton utility \(1/2-2<0\).

Thus the stated terminal allocation and welfare are correct. Since supply permits allocating the category to everyone and both values are positive, the stated optimum is correct.

The ratio \(4\delta/(1+3\delta)\) is computed correctly. Its comparison with \(1/(1+\alpha)\) is equivalent to
\(\delta(1+4\alpha)<1\), exactly the stated restriction. Positive dyadic rationals satisfying this restriction exist for every prescribed \(\alpha\).

The claim that no positive uniform multiplicative welfare guarantee holds is established.

3. Rationality counterexample

First update. Because \(n\ge2\), both types strictly prefer bidding at the initial price. Coordinate priority selects precisely the initial interval of length \(3/4\), giving the stated holders and price.

Inductive transition. Under the asserted holder pattern, every low individual and every allocated high individual holds the only category and must submit the empty conditional bid. The remaining high interval has mass \(1/4\) and bids precisely when
\(K-(r+1)/n>0\).

Whenever it bids, all newcomers are selected. The remaining incumbent capacity is \(1/2\). The low interval precedes all high incumbents and has exactly this mass, so it is retained in full. The high holder interval consequently switches as claimed. This follows directly from the specified selection rule.

Stopping index. The first update occurs, and subsequent updates occur precisely while \(r+1<nK\). Hence there are exactly \(nK-1\) updates, with terminal price \(K-1/n\). At that state, unallocated high individuals have singleton utility zero and choose the empty bid by minimum cardinality. All holders also submit empty bids.

Violation. Every low individual remains allocated the category. For the stipulated ranges, \(K-1/n>1\), so individual rationality fails on mass \(1/2\). Choosing \(K>\alpha+1/n\) establishes the claimed violation for any prescribed \(\alpha\). The unbounded price-to-value ratio and persistence as the increment tends to zero both follow from the displayed terminal price.

The supplementary welfare and optimum calculations are also correct. Their ratio approaches \(1/2\) from above, consistently with the prover’s statement that this family does not violate the welfare bound for \(\alpha=1\).

4. Termination bound

The deletion comparison is valid: removing a category from a chosen conditional bid remains feasible. A marginal below its bid price contradicts utility maximization; equality contradicts minimum-cardinality tie-breaking. The strict inequality therefore follows.

The marginal in this comparison is among those defining \(D_j\), because its conditioning set excludes \(j\). Thus every increase produces a price strictly below \(D_j\).

The stated \(C_j\) correctly counts the positive integer multiples of \(\varepsilon\) strictly below \(D_j\), including the cases \(D_j=0\) and integral \(D_j/\varepsilon\).

Every nonterminal round has positive mass of nonempty bids. Since there are finitely many categories, at least one newcomer set has positive mass and causes an increase. Consequently, the bound on updating rounds and finite termination are justified.

5. Exact simulation and running time

The partition argument is sound. Within each interval, type and bundle determine the same unique conditional bid. Each newcomer or incumbent prefix selection adds at most one boundary inside an existing interval. Simultaneous updates therefore add at most two boundaries per category, yielding the stated interval bound.

Exhaustive conditional-bid enumeration, price summation, and prefix selection fit the displayed running-time bound.

The arithmetic claim is also valid. Initial endpoints lie on the rational lattice generated by input masses and supplies. Prefix cuts preserve that lattice. A common denominator has binary length bounded by the total input length. Prices are integer multiples of the increment, with the additional bit length controlled by the logarithm of the update count.

This establishes an exact numerical-parameter-dependent simulation bound. It does not establish polynomial-time solvability in binary input length or a hardness classification.

6. Comparison with the cited discrete proof

The attribution is accurate. The cited rationality induction explicitly uses unchanged prices for items retained by the same incumbent. Its welfare proof explicitly uses allocation of every positive-price item. Both claims can be checked in [Sections 3.1–3.2 of the cited paper](https://www.cs.yale.edu/homes/cai/publication/smra/smra.pdf).

The terminal comparison inequality in the prover’s output correctly includes the increment term. Monotonicity gives its first inequality; comparison with the empty conditional bid gives its second. The almost-everywhere qualification matches the mass-based stopping rule.

Feedback and adjudication

No repair or additional mathematical clarification is required. The negative answers are fully established. The complexity field below is marked unresolved solely because the output does not classify the continuous problem’s complexity.

⟨structured verdict parsed — rendered above⟩