Explicit Payments for Obviously Strategyproof Mechanisms

There is a defensible positive case, but it is narrower than for a paper containing an explicit complexity classification. This paper has no named theorem saying that one of its problems is NP-hard, in P, W[1]-hard, or FPT. Its NP-hardness statement about single-minded auctions is an uncatalogued claim in the introduction, attributed to [19]. The best available anchors are therefore its named algorithmic results on explicit payments, OSP recognition, and subsidy bounds.

The most convincing anchor is Theorem 5.1, proved in this paper. It states that Algorithm 1 for single-minded combinatorial auctions requires subsidies of at most
\[ n v_2-(n-1)v_\ell-v_{\ell-1}. \]

A natural continuous mirror is Mass-Greedy-OSP-Subsidy. An instance contains a finite item set \(U\), a finite family of demanded bundles \(\mathcal R\subseteq 2^U\), valuation levels \(D=\{v_1>\cdots>v_\ell\}\), a rational distribution
\[ \mu\in\Delta_{\mathcal R\times D}, \]
and a deterministic tie-breaking rule. A complete bidder type is \(\theta=(R,D,v)\): the desired bundle, valuation domain, and realized value. The mass \(\mu_{R,v}\) is the fraction of bidders with that type. The intended regime is \(N\gg\tau\), with \(N\mu_{R,v}\) bidders of each type and \(\tau=|\operatorname{supp}(\mu)|\) small.

The allocation remains binary at the individual level. A bidder either receives the whole bundle \(R\) or receives nothing; no bidder receives a fractional bundle. The aggregate decision variable is \(x_{R,v}\), the mass of type-\((R,v)\) bidders accepted by the greedy rule. To make the high-multiplicity regime operational, one can let the \(N\)-th finite realization contain \(Nq_j\) interchangeable copies of item \(j\), for a fixed rational capacity vector \(q\). This models many repeated markets, advertising slots, cloud-resource units, or procurement opportunities. It is still the same single-minded allocation problem, with discrete bundles and binary individual outcomes.

The mass-greedy rule orders types by
\[ \Phi(R,v)=\frac{v}{\sqrt{|R|}}, \]
asks values from high to low, and accepts as much of a type’s mass as the remaining capacities permit. A payment variable \(p_{\theta,h}\) is a net transfer to one bidder of type \(\theta\) at history \(h\). Using the paper’s auction convention, utility is
\[ u=v a+p, \]
where \(a\in\{0,1\}\) denotes winning. The continuous problem is:

Find per-type, per-history transfers \(p_{\theta,h}\) making the mass-greedy implementation obviously strategyproof and individually rational, with losing bidders charged nothing, while minimizing the maximum mass-weighted external subsidy
\[ > S_\infty(\mu)= > \max_h\left(\sum_{\theta}\mu_\theta p_{\theta,h}\right)_+. > \]

OSP is imposed through the paper’s worst-truthful-versus-best-deviation inequalities, applied to every finite \(N\)-replica and then passed to the type-level limit. This avoids the vacuity that would arise if a literally nonatomic bidder had zero influence on the outcome.

The finite theorem suggests the normalized asymptotic target
\[ \limsup_{N\to\infty}\frac{S_N}{N}\le v_2-v_\ell. \]
Theorem 5.2, also proved here, supplies a useful boundary case: under a sufficiently strong separation of the efficiency ratios, the same greedy mechanism needs no subsidy at all. Thus the continuous problem asks not merely whether a mass version exists, but how subsidy density depends on the support geometry of \(\mu\).

I would expect the fixed-\(\tau\), finite-level, type-explicit version to be Class A: OSP and IR constraints become linear inequalities over type-level payment variables, and the number of repeated agents disappears. With unrestricted bundle systems and unbounded \(m\), however, the packing structure remains and hardness is likely to transfer from the underlying combinatorial auction. This is exactly the sort of instance-regime split the programme is meant to expose.

The second anchor is Proposition 3.1, proved in this paper. It gives explicit payments for agents queried in reverse-greedy order. For a profile or type-level history in outcome class \(k\), the payment has the form
\[ p(b)=\vartheta_b(k)f^k+ \sum_{j=0}^{k-1} \bigl(\vartheta_b(j)-\vartheta_b(j+1)\bigr)f^j. \]

Its continuous mirror is Reverse-Greedy Mass Payment Computation. The instance consists of a finite support \(\Theta\), a distribution \(\mu\), a finite outcome-level set \(f^0,\ldots,f^r\), and an explicitly represented reverse-greedy implementation tree. Each node records the type threshold queried and each leaf records the binary or ordered outcome received by the corresponding mass block.

The decision variable is a payment density \(p_{\theta,h}\), identical for all agents of type \(\theta\) reaching history \(h\). The task is to output an OSP payment schedule, certify individual rationality, and, when all agents are reverse-greedy, certify budget balance. The aggregate quantity is simply
\[ \sum_{\theta}\mu_\theta p_{\theta,h} \]
at each compatible leaf. The continuous problem is therefore a genuine high-multiplicity version of the paper’s problem: repeated agents do not receive a new preference model, and bundles or services remain discrete; only the payment table and its aggregate financial consequences are represented by type masses.

This one should be Class A whenever the reverse-greedy tree is given at the type level. Proposition 3.1 is already an explicit finite formula, so the computation is linear in the number of type-history pairs. The interesting further question is whether the thresholds \(\vartheta_b(j)\) can themselves be computed efficiently from a succinct allocation rule rather than from an explicit tree. That is where a real separation or pricing problem could appear.

The third anchor is Corollary 4.2, stated in this paper and obtained from the cited Theorem 2.3 of [14] together with the payment results proved here. It says, for binary outcomes, that a mechanism is OSP exactly when its tree is, or can be transformed to, a two-way greedy implementation with interleaving and the payments are those in equations (1) and (2).

Its continuous mirror is Mass-Two-Way-OSP Recognition and Payment Design. An instance contains a finite type distribution \(\mu\), a binary allocation rule \(f\) over a finite type-level mechanism tree, and the allowed interleaving operations. The question is whether there exists a type-level payment density \(p_{\theta,h}\) such that the mass mechanism is OSP. If yes, the solution must output the transformed two-way greedy tree, the payment density, and the minimum subsidy subject to IR and budget balance whenever those are compatible.

For an explicitly represented type-level tree, I expect Class A: the interleaving conditions and payment equations can be checked directly, and the mass distribution only weights the resulting transfers. The more ambitious version in which the tree must be synthesized from a succinct allocation rule may be Class C. Its difficulty would come from finding the correct extensive-form decomposition, not from population multiplicity. That distinction is itself valuable: the continuous mirror would show exactly which part of OSP mechanism design is simplified by high multiplicity and which part is not.

These mirrors cover the paper’s single-minded greedy auction result, its reverse-greedy payment construction, and its binary OSP characterization. They do not claim to cover every three-way or split-and-greedy payment formula, and they do not treat the cited NP-hardness of welfare approximation as a theorem proved in this paper.

The weakest point is that OSP is fundamentally an individual, extensive-form notion. A naive nonatomic population makes every individual non-pivotal, so OSP can become vacuous. The mirror must therefore use a robust finite-replica interpretation or a carefully defined mass-block implementation. A second weakness is supply: with a fixed number of indivisible items and \(N\to\infty\), the winning fraction tends to zero. Scaling supply with population gives a more useful market regime, but an opponent could argue that this changes the original auction. I think the case survives because repeated bundles, repeated slots, and repeated service opportunities are natural high-multiplicity environments, and the individual allocation, valuation, greedy ordering, and OSP constraints remain those of the paper.

So my positive verdict is: the paper supports a credible continuous mirror, strongest for its explicit reverse-greedy payments and for subsidy density in large markets of repeated single-minded bidders. It does not itself establish a continuous complexity result; it supplies the structural mechanism results from which such a continuization programme could be built.