Answer: Yes. A deterministic polynomial-time mechanism achieves welfare exactly \(\mathrm{OPT}\) for every truthful-value profile and every invitation profile, with individual rationality and dominant-strategy truthfulness in joint individual value-and-invitation deviations.
Theorem 5.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateNet- √ k-APM is √ k-EF, IR, SP, but not WBB. Regarding IP-MON allocation, we propose the Network Single-minded Auction (NSA) mechanism, which combines a non-trivial extension of Algorithm 2, presented in Algo- rithm 3, along with the payment scheme introduced in Theo- rem 4.4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\) items, rational per-capita supplies \(q_j\), and a finite directed block network whose blocks have rational masses \(\mu_t\), values \(v_t\), desired bundles \(S_t\), and referral roles, does a polynomial-time mass extension of Net-\(\sqrt{k}\)-APM achieve welfare at least \(1/\sqrt{k}\) of the feasible mass-allocation optimum while remaining individually rational and dominant-strategy truthful in each bidder’s value and invitation choices? Each individual can invite an adjacent block, activating its positive mass; each served individual receives a whole desired bundle, and the mechanism may serve a fraction of each block. No budget-balance guarantee is required.
Let \(m=k\geq1\) be the number of item kinds, with binary-rational per-capita supplies \(q_j\geq0\). A society is given by its support: the list of its \(\tau\) positive-mass types, each with binary-rational mass \(\mu_t>0\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible bundles or referral roles.
Each type occupies an atomless block and has a public nonempty desired bundle \(S_t\subseteq\{1,\ldots,m\}\), a private binary-rational value \(v_t\geq0\), and an outgoing-neighbor set in a finite directed block network with seller \(s\). An individual values exactly \(S_t\) at \(v_t\), and every other bundle at zero; bundles and block memberships cannot be misreported.
The seller activates its outgoing-neighbor blocks. Each active individual can invite any subset of their block's outgoing neighbors; one invitation activates the entire target block, recursively. Activation is the least closure of these invitations, including invitations from single individuals of zero mass. Inactive individuals receive nothing and pay zero, and their reports cannot affect the outcome.
Give individuals fixed public labels within their blocks. A deterministic mechanism selects measurable subsets of individuals, giving each selected individual their whole desired bundle, and specifies signed per-individual payments. If \(x_t\) is the served mass of type \(t\), feasibility means \(0\leq x_t\leq\mu_t\), \(x_t=0\) for inactive types, and \(\sum_{t:j\in S_t}x_t\leq q_j\) for every item kind \(j\).
Define \(\mathrm{OPT}\) as the maximum of \(\sum_t v_t x_t\) over these feasible mass allocations for the currently active population. Individual utility is \(v_i a_i-p_i\), where \(a_i\in\{0,1\}\) indicates service. Individual rationality requires nonnegative utility at a truthful value for every invitation subset; dominant-strategy truthfulness requires truthful value and inviting every outgoing neighbor to weakly dominate every joint value-and-invitation deviation, fixing everyone else's reports.
For computation, allow finite report partitions into \(r\) public-label intervals with rational endpoints and finitely many explicitly recorded singleton exceptions \(e\); singleton reports and invitation events remain observable despite having zero mass. Let \(L\) be the total binary input length. Require a finite allocation/payment representation whose construction and pointwise evaluation take polynomial time in \(m,\tau,|E|,L,r,e\); any tie-breaking must use a fixed public order.
Target. Does a polynomial-time mass analogue achieve welfare at least \(\mathrm{OPT}/\sqrt{k}\) on every truthful-value profile, for every invitation profile, while satisfying individual rationality and dominant-strategy truthfulness in individual values and invitations, with no budget-balance requirement?
Nearest known results. For finite bidders and one copy of each item, Net-\(\sqrt{k}\)-APM achieves this welfare ratio, individual rationality, and invitation-and-value strategyproofness, while potentially running a deficit. [Discrete approximation result](https://arxiv.org/html/2507.14472v1).
No result settling this exact atomless, individual-to-block activation formulation was located in the literature search.
Yes. In fact, the stated mass model admits a deterministic polynomial-time mechanism achieving welfare exactly \(\mathrm{OPT}\).
The construction uses optimal mass allocations, individual posted prices, and a rebate for inviting every outgoing neighbor. The proof treats each individual as the strategic agent; it does not assume that a whole positive-mass block reports jointly.
Identify block \(t\) with the public-label interval \([0,1)\), carrying measure \(\mu_t\) times Lebesgue measure. Fix public orders on blocks and item kinds, and use increasing label order within each block.
Write \(\widehat v_i\) for individual \(i\)'s reported value and \(R_i\subseteq N_t\) for her reported invitation set, where \(N_t\) is her block’s public outgoing-neighbor set.
Construct the reported block graph by including an edge from \(t\) to \(u\) whenever some individual in block \(t\) invites \(u\). In particular, singleton invitation events contribute edges. Include the seller’s outgoing edges. The active blocks are precisely those reachable from the seller in this graph: reachability implements the required least activation closure.
We will use the following observation.
Activation observation. Fix everyone else’s reports. An individual’s activity status is independent of her own value and invitation reports.
Indeed, her invitations can change only edges leaving her block \(t\). Reachability of \(t\) does not depend on edges leaving \(t\): any path reaching \(t\) can be shortened to a simple path, which reaches \(t\) before using any outgoing edge of \(t\). If \(t\) is unreachable, changing its outgoing edges cannot change any reachable block.
Consequently, an inactive individual’s reports have no effect on the active population. All subsequent calculations use only active blocks’ reports.
For mass calculations, replace each active block’s bid function by its canonical interval step function equal to it almost everywhere. Merge adjacent intervals with equal bids and use a fixed half-open endpoint convention. Singleton bid exceptions do not enter this step function; their actual bids remain available for pointwise allocation.
This canonical function is unchanged by changing one individual’s value report.
Index its positive-length intervals across active blocks by \(h\). Let:
Solve the rational linear program
\( \displaystyle W=\max_x\left\{\sum_h b_hx_h: 0\leq x_h\leq\nu_h,\quad \sum_{h:j\in S_h}x_h\leq q_j\ \text{for every }j \right\}. \)
Its feasible set is nonempty because \(x=0\) is feasible, and compact because every coordinate has a finite upper bound. Hence an optimum exists. Select an optimum canonically by successively maximizing its coordinates in public block-and-label order, while preserving the optimal objective and previously selected coordinates.
The dual is
\( \displaystyle \min_{y,z}\left\{ \sum_jq_jy_j+\sum_h\nu_hz_h: y_j\geq0,\ z_h\geq0,\quad \sum_{j\in S_h}y_j+z_h\geq b_h\ \text{for every }h \right\}. \)
It is feasible, for example with \(y=0\) and \(z_h=b_h\). Strong linear-programming duality therefore supplies a dual optimum of value \(W\).
Define \(B=\max_h b_h\), taking \(B=0\) when there are no active intervals. There is a dual optimum satisfying
\( 0\leq y_j\leq B,\qquad 0\leq z_h\leq B. \)
To verify this, start with any dual optimum and cap every coordinate at \(B\). Every constraint has right-hand side at most \(B\). If a coordinate appearing in a constraint was capped, its new contribution alone is \(B\), so that constraint remains satisfied. Otherwise its left-hand side is unchanged. All objective coefficients are nonnegative, so capping cannot increase the objective. By weak duality, the capped solution remains optimal.
Among bounded dual optima, select \(y\) by successive lexicographic minimization in the fixed public item order. This uniquely determines the item-price vector. Define block \(t\)’s posted bundle price by
\( \displaystyle c_t=\sum_{j\in S_t}y_j. \)
Thus \(0\leq c_t\leq kB\).
Price independence. Fix an individual’s invitations and everyone else’s reports. Changing only that individual’s value report leaves the active blocks, canonical interval step functions, linear programs, and canonical prices unchanged.
This is exact independence, since one individual has zero mass.
We first establish the relation between bids and prices.
For primal and dual optima, their objective difference is
\( \displaystyle 0= \sum_j y_j\left(q_j-\sum_{h:j\in S_h}x_h\right) +\sum_hz_h(\nu_h-x_h) +\sum_hx_h(c_{t(h)}+z_h-b_h). \)
Every summand is nonnegative by primal and dual feasibility. Therefore:
For each canonical interval \(h=[\ell_h,u_h)\), select its initial label segment of mass \(x_h\), namely
\( \displaystyle D_h=\left[\ell_h,\ \ell_h+\frac{x_h}{\mu_{t(h)}}\right). \)
Let \(D\) be the union of these segments. Their endpoints are rational.
The actual service rule for every active individual \(i\) in block \(t\), including every singleton exception, is
\( \displaystyle a_i= \begin{cases} 1,&\widehat v_i>c_t,\\ 0,&\widehat v_i<c_t,\\ \mathbf 1_{\{i\in D\}},&\widehat v_i=c_t. \end{cases} \)
An inactive individual receives nothing.
On each canonical interval, this rule agrees almost everywhere with membership in \(D_h\), by the three conclusions above. Hence its served mass on that interval is exactly \(x_h\). Exceptional point allocations do not change any mass constraint.
The allocation is consequently measurable and feasible on every admissible report profile. Each served individual receives her whole desired bundle.
For an active individual \(i\) in block \(t\), define
\( \displaystyle p_i=a_ic_t-c_t\,\mathbf 1_{\{R_i=N_t\}}. \)
Thus inviting every outgoing neighbor earns a rebate equal to the posted bundle price:
Inactive individuals pay zero.
If \(N_t\) is empty, its only invitation subset is the full set, so the rebate applies.
Fix arbitrary reports of everyone else and any invitation subset for individual \(i\). Suppose she reports her true value \(v_i\).
If active, her utility is
\( \displaystyle u_i=a_i(v_i-c_t)+c_t\,\mathbf 1_{\{R_i=N_t\}}. \)
Under the truthful service rule,
\( \displaystyle a_i(v_i-c_t)=\max\{v_i-c_t,0\}. \)
This identity holds also at equality, regardless of label tie-breaking. Both terms in the utility expression are nonnegative. Therefore individual rationality holds at a truthful value for every invitation subset.
An inactive individual has utility zero.
Fix all reports of everyone except individual \(i\), whose true value is \(v_i\).
By the activation observation, either she is inactive under every invitation action or active under every invitation action. In the inactive case, every action gives utility zero. Consider the active case.
Let \(c_t^{F}\) be her bundle price when she invites every outgoing neighbor. At a truthful value, her utility is
\( \displaystyle u_i^{F} =c_t^{F}+\max\{v_i-c_t^{F},0\} =\max\{v_i,c_t^{F}\} \geq v_i. \)
Changing only her value report leaves \(c_t^{F}\) unchanged, by price independence. Any such deviation produces a service indicator \(a\in\{0,1\}\) and utility
\( \displaystyle a(v_i-c_t^{F})+c_t^{F} \leq \max\{v_i,c_t^{F}\} =u_i^{F}. \)
Thus no value deviation with full invitations is profitable.
The deviation may change the active population, allocation, and price. Nevertheless, it receives no rebate. If its price is \(c_t^{R}\geq0\) and its service indicator is \(a\), its utility is
\( \displaystyle u_i^{R}=a(v_i-c_t^{R})\leq v_i. \)
Indeed, an unserved individual gets zero, while a served individual gets at most \(v_i\). This inequality holds for every deviating value report.
Combining the inequalities gives
\( \displaystyle u_i^{F}\geq v_i\geq u_i^{R}. \)
Therefore truthful value reporting together with full invitations weakly dominates every joint value-and-invitation deviation.
Consider any truthful-value profile and any invitation profile. Within each active type \(t\), the bid is \(v_t\) everywhere. The mass linear program is therefore precisely the program defining \(\mathrm{OPT}\), possibly with redundant interval subdivisions.
The pointwise implementation has exactly the optimal served masses, since its finite exceptional set has zero mass. Consequently,
\( \displaystyle \sum_t v_tx_t=\mathrm{OPT}. \)
Because \(k\geq1\) and \(\mathrm{OPT}\geq0\), this establishes the requested bound
\( \displaystyle \sum_t v_tx_t\geq\frac{\mathrm{OPT}}{\sqrt{k}}. \)
The finite report representation gives polynomially many canonical intervals and explicitly recorded singleton events.
Activation is graph reachability, including singleton invitation edges. Canonical bid intervals are constructed by scanning and merging the reported intervals. Their masses are rational with polynomial encoding length.
The primal and bounded dual have polynomially many variables and constraints and rational coefficients of polynomial encoding length. We use the standard theorem that rational linear programs admit exact polynomial-time optimization; see [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239).
The canonical choices require only polynomially many additional coordinate optimizations. These successively expose faces of the original rational polytopes. Each coordinate optimum is attained at an original vertex, whose encoding length is polynomial by the determinant bounds for rational linear systems. Thus the added equality constraints retain polynomial encoding length.
The prices and allocation cutoffs consequently have polynomial encoding length. Overlaying the input report intervals with the allocation cutoffs produces a polynomial-size allocation/payment representation; singleton exceptions are evaluated separately. Under the stipulated public-label representation, pointwise evaluation requires interval comparisons, bid-price comparison, checking whether the invitation set is full, and evaluating the displayed payment formula.
Hence construction and evaluation meet the requested polynomial bound in \(m,\tau,|E|,L,r,e\).
No budget-balance assertion is needed: the rebates are permitted signed payments. The proof retains singleton reports pointwise and singleton invitations in activation, while using their zero mass only in the supply and welfare calculations.
⟨structured verdict parsed — rendered above⟩
The prover’s claimed resolution is correct under the public-label interval representation stipulated in the task. The mechanism establishes exact optimal welfare, individual rationality, and dominant-strategy truthfulness against joint individual value-and-invitation deviations. I found no major or minor mathematical issues requiring repair.
The reported graph correctly includes an invitation edge whenever at least one individual sends that invitation, including singleton events. Reachability from the seller therefore implements the specified least activation closure.
The activation observation is valid. An individual changes only edges leaving her own block. Whether that block is reachable cannot depend on those edges: a simple path reaching the block does not first leave it. If the block is unreachable, changing its outgoing edges cannot change the reachable population.
Consequently, inactive individuals’ reports cannot affect the active population. Because subsequent optimization uses only active blocks’ reports, they cannot affect allocation or payments either.
Removing finitely many singleton bid exceptions does not change interval masses or mass objectives. Merging adjacent intervals with equal bids and fixing the endpoint convention makes the canonical step function independent of a change at one individual.
Holding invitations fixed, changing one individual’s value therefore leaves activation, canonical mass data, and the price-selection program unchanged. This is the exact independence needed for the value-incentive argument.
The prover also preserves singleton bids for pointwise service and singleton invitations for activation. It does not incorrectly discard their observable effects.
The primal correctly represents feasible mass service: each interval has an upper bound equal to its mass, and each selected individual consumes one unit of every item in her desired bundle.
The primal is feasible and compact. The displayed dual has the correct objective, signs, and constraints. Its proposed feasible point is valid for nonnegative admissible bids. Thus the hypotheses for finite-dimensional linear-programming strong duality are satisfied.
The bounded-dual argument is correct. Capping a coordinate at \(B\) preserves any affected constraint because that coordinate alone then contributes \(B\), while every right-hand side is at most \(B\). Nonnegative objective coefficients ensure the objective cannot increase; weak duality ensures the capped optimum remains optimal.
Lexicographic minimization over bounded dual optima is well-defined and uniquely determines the item-price vector. The claimed bounds \(0\leq c_t\leq kB\) follow because every desired bundle contains at most \(k\) items.
Re-expanding the displayed primal–dual objective difference gives exactly the dual objective minus the primal objective. Each displayed summand is nonnegative.
The stated consequences are correct:
Under the stated label measure, the initial segment \(D_h\) has mass \(x_h\), and its endpoint lies within its canonical interval because \(0\leq x_h\leq\nu_h\).
The actual threshold rule agrees almost everywhere with the selected segments. Singleton exceptions can change individual service but cannot change served masses or supply consumption. The allocation is consequently measurable and feasible, including when supplies or bids are zero.
Substituting the payment formula into utility gives the displayed expression correctly.
At a truthful value, the threshold rule yields
\(a_i(v_i-c_t)=\max\{v_i-c_t,0\}\).
This remains true at equality regardless of tie-breaking.
Both the threshold surplus and the full-invitation rebate are nonnegative. Individual rationality therefore holds for every invitation subset and arbitrary admissible reports of other individuals. Inactive individuals receive utility zero.
An empty outgoing-neighbor set is handled correctly: its only invitation subset qualifies as full invitations.
The proof fixes everyone else’s reports, as required, and correctly separates the possible deviations.
Under truthful value reporting and full invitations, utility is
\(\max\{v_i,c_t^F\}\geq v_i\).
If a deviation retains full invitations, value-report independence fixes the price. Every possible resulting service indicator gives utility at most \(\max\{v_i,c_t^F\}\).
If a deviation withholds an invitation, it receives no rebate. Its utility is either zero or \(v_i-c_t^R\), hence at most \(v_i\), because \(v_i\geq0\) and \(c_t^R\geq0\). This bound does not require prices or activation to remain unchanged.
These comparisons cover every joint deviation. The inactive case is also covered because activity is independent of the individual’s own action.
On every truthful-value profile, each active type’s mass bid equals its true type value. The interval LP therefore has exactly the feasible allocations and objective defining \(\mathrm{OPT}\), up to redundant subdivision.
Pointwise exceptions have zero mass, so the implementation preserves the LP’s optimal welfare. This conclusion holds for every invitation profile; it does not assume that invitations are full.
Since \(k\geq1\) and \(\mathrm{OPT}\geq0\), exact optimality implies the required approximation bound. The case \(\mathrm{OPT}=0\) causes no difficulty.
The rational-LP result invoked is applicable: the programs have rational coefficients, polynomial dimensions, and polynomial coefficient encoding lengths, and their required optima exist. The cited reference is correctly identified as Khachiyan’s *Polynomial algorithms in linear programming*. [Publication record](https://www.mathnet.ru/eng/zvmmf5239)
The successive coordinate optimizations preserve faces of the original feasible polytopes. Their optimum coordinate values can be taken from original vertices, so the determinant-based encoding bound avoids an uncontrolled accumulation of bit lengths.
Interval masses, prices, and allocation cutoffs therefore have polynomial encoding length. Division by \(\mu_t\) is legitimate because every block mass is strictly positive. Overlaying finitely many report intervals and allocation cutoffs gives a polynomial-size representation; singleton exceptions remain explicitly evaluable.
The no-active-block case is covered by the stated convention \(B=0\). Zero supplies and zero bids do not invalidate feasibility, duality, or the construction.
The argument needs no budget-balance property, and the task explicitly permits signed payments. The rebates are therefore admissible. No additional clarification or missing mathematical lemma is needed to verify the claimed result.
⟨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.