Answer: Polynomial-time exactly solvable: an admissible mechanism attains \(R(M)=\mathrm{OPT}\), so \(c=1\).
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet I = (F, S, B) be an instance with multi-parameter, unit-demand agents and S being a matroid or simpler feasibility constraint. Then, there exists a polynomial time computable mechanism for bI that is budget feasible and DSIC for I and obtains a constant fraction of the revenue of the optimal budget-feasible mechanism for I.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of private value vectors and public budgets with rational population masses \(\mu_t\), a finite service set \(J\), and per-capita total supply \(q\), does a \(\mathrm{poly}(|J|,\tau,L)\)-time algorithm output an anonymous direct-revelation mechanism with indivisible service lotteries and feasible mass rationing that is DSIC, ex-post IR, budget-feasible, and earns a fixed constant fraction of optimal expected revenue per capita? Require supply feasibility at every report-mass profile and evaluate revenue under the truthful type distribution \(\mu\).
A society is nonatomic and has total mass \(1\). It is given by its support: \(\tau\) types \(t=(v_t,B_t)\) with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Values and public budgets are nonnegative binary rationals. Conditional on each public budget, the value coordinates are independent.
There are \(m=|J|\geq1\) service kinds. Agents are unit-demand; receiving service \(j\) gives value \(v_{tj}\), and receiving nothing gives value \(0\). The binary-rational supply \(q\in[0,1]\) bounds total served mass, with no separate capacity for a service kind. Let \(L\) be the total input bit length.
For each public budget \(b\), let \(T_b=\{t:B_t=b\}\) and \(\beta_b=\sum_{t\in T_b}\mu_t\). An agent with budget \(b\) may report any value vector in \(T_b\); budgets cannot be misreported. A report-mass profile is any \(\rho\geq0\) satisfying \(\sum_{r\in T_b}\rho_r=\beta_b\) for every \(b\).
An anonymous direct mechanism assigns each report \(r\), at each profile \(\rho\), a lottery over receiving one indivisible service or nothing, jointly with a realized payment \(P\). Identical reports with identical public budgets receive identical lotteries. Include the option to receive nothing and pay nothing.
Let \(x_{rj}(\rho)\) be the probability of service \(j\). Mass rationing must implement these probabilities while serving total mass at most \(q\) in every realization, at every report-mass profile; in particular, \(\sum_r\rho_r\sum_jx_{rj}(\rho)\leq q\).
Payments are nonnegative and never exceed the public budget. Ex-post IR requires \(P\leq v_{rj}\) whenever truthful report \(r\) receives \(j\), and \(P=0\) when it receives nothing. Utility is expected realized value minus payment, and is \(-\infty\) if a payment exceeds the true budget.
DSIC requires, for every \(\rho\) and every \(t,r\in T_b\), that type \(t\) weakly prefers its truthful lottery to report \(r\)'s lottery. A single nonatomic agent's deviation leaves \(\rho\) unchanged; lotteries for zero-mass reports must also be defined. Truthful reporting may be selected when utilities tie.
Revenue is \(R(M)=\sum_t\mu_t\mathbb E[P\mid t,\rho=\mu]\). Let \(\mathrm{OPT}\) be its supremum over all anonymous DSIC, ex-post IR, budget-feasible mechanisms satisfying the same reporting and supply requirements.
Does there exist an absolute constant \(c>0\) and an algorithm running in \(\mathrm{poly}(m,\tau,L)\) time that outputs such a mechanism with \(R(M)\geq c\,\mathrm{OPT}\), or is obtaining any fixed positive constant fraction NP-hard? The output mechanism must have a finite description evaluable in polynomial time in these parameters and the bit length of a rational report-mass profile.
For finite societies with independent unit-demand value coordinates, public budgets, and matroid feasibility, a polynomial-time computable DSIC constant-factor revenue approximation is stated in [Chawla–Malec–Malekian](https://arxiv.org/abs/1103.6280).
[Richter](https://www.sciencedirect.com/science/article/abs/pii/S0899825619300193) characterizes optimal revenue mechanisms for a continuum with a divisible good and without unit-demand. This does not settle the indivisible-service problem above; no result for this precise formulation was located.
The problem is exactly solvable in polynomial time. There is an algorithm producing an admissible mechanism with \(R(M)=\mathrm{OPT}\), so one may take \(c=1\).
The proof uses the explicitly listed support and the stipulated nonatomic deviation model. It does not require conditional independence of the value coordinates.
Write \(T\) for the listed support and define \(a_{tj}=\min\{B_t,v_{tj}\}\).
For each \(t\in T\) and \(j\in J\), introduce variables:
Consider the linear program maximizing
\(\displaystyle V=\sum_{t\in T}\mu_t\sum_{j\in J}z_{tj}\)
subject to the following constraints.
For every \(t\in T\),
\(\displaystyle x_{tj}\geq0,\qquad \sum_{j\in J}x_{tj}\leq1.\)
For every \(t\in T\) and \(j\in J\),
\(\displaystyle 0\leq z_{tj}\leq a_{tj}x_{tj}.\)
For every public budget \(b\) and every \(t,r\in T_b\),
\(\displaystyle \sum_{j\in J}v_{tj}x_{tj}-\sum_{j\in J}z_{tj}\ \geq\ \sum_{j\in J}v_{tj}x_{rj}-\sum_{j\in J}z_{rj}.\)
Finally,
\(\displaystyle \sum_{t\in T}\mu_t\sum_{j\in J}x_{tj}\leq q.\)
The zero vector is feasible. The feasible region is closed and bounded: every allocation variable lies in \([0,1]\), and every payment variable lies in \([0,a_{tj}]\). Thus an optimal solution \((x^*,z^*)\) exists. Denote its objective value by \(V^*\).
Take any admissible mechanism and examine its lotteries at the truthful profile \(\rho=\mu\). Set
\(\displaystyle x_{tj}=\Pr(t\text{ receives }j),\qquad z_{tj}=\mathbb E[P\,\mathbf 1_{\{t\text{ receives }j\}}].\)
Unit demand gives the allocation constraints. Nonnegative payments, budget feasibility, and truthful ex-post IR give
\(\displaystyle 0\leq z_{tj}\leq \min\{B_t,v_{tj}\}\Pr(t\text{ receives }j)=a_{tj}x_{tj}.\)
Because receiving nothing entails zero payment, the expected payment for report \(t\) is \(\sum_jz_{tj}\).
For a deviation from \(t\) to \(r\in T_b\), every realized payment remains within the true budget \(b\). Consequently, expected utility from that deviation is exactly
\(\displaystyle \sum_jv_{tj}x_{rj}-\sum_jz_{rj}.\)
The DSIC requirements therefore imply the LP incentive inequalities. Realization-wise supply feasibility implies the LP supply constraint by taking expectations.
The LP objective equals the mechanism’s revenue. Hence
\(\displaystyle \mathrm{OPT}\leq V^*.\)
Define conditional service prices by
\(\displaystyle p_{rj}=\frac{z^*_{rj}}{x^*_{rj}}\quad\text{if }x^*_{rj}>0,\)
and set \(p_{rj}=0\) when \(x^*_{rj}=0\). The LP constraints ensure
\(\displaystyle 0\leq p_{rj}\leq\min\{B_r,v_{rj}\}.\)
Let \(s_r=\sum_jx^*_{rj}\). At any admissible report-mass profile \(\rho\), define
\(\displaystyle D(\rho)=\sum_r\rho_rs_r.\)
Set \(\alpha(\rho)=1\) when \(D(\rho)\leq q\), and set \(\alpha(\rho)=q/D(\rho)\) otherwise. The second branch has a positive denominator, so this also defines the rule when \(q=0\).
For report \(r\), prescribe the following lottery:
Also provide the outside option of receiving nothing and paying nothing.
These probabilities are nonnegative and sum to one.
Whenever truthful report \(r\) receives service \(j\), its payment satisfies \(p_{rj}\leq B_r\) and \(p_{rj}\leq v_{rj}\). Receiving nothing costs zero. Thus the required payment restrictions hold at every profile.
Fix any profile \(\rho\), budget \(b\), and types \(t,r\in T_b\). Expected utility of type \(t\) from report \(r\) is
\(\displaystyle U_t(r;\rho)=\alpha(\rho)\left(\sum_jv_{tj}x^*_{rj}-\sum_jz^*_{rj}\right).\)
Here we used \(x^*_{rj}p_{rj}=z^*_{rj}\), including when \(x^*_{rj}=0\).
The LP incentive inequality, multiplied by the common nonnegative factor \(\alpha(\rho)\), gives
\(\displaystyle U_t(t;\rho)\geq U_t(r;\rho).\)
Under the stipulated nonatomic deviation model, a single agent’s deviation leaves \(\rho\), and therefore \(\alpha(\rho)\), unchanged. This proves exactly the required DSIC condition.
Truthful utility is nonnegative because each \(z^*_{tj}\leq v_{tj}x^*_{tj}\). Thus truthful reporting also weakly dominates the outside option.
All formulas apply to every listed report, whether or not its current mass is positive.
Writing \(w_{rj}=\alpha(\rho)x^*_{rj}\), the prescribed total served mass is
\(\displaystyle \sum_r\rho_r\sum_jw_{rj}=\alpha(\rho)D(\rho)\leq q.\)
We next implement this bound in every realization.
The following construction implements any prescribed probabilities \(w_{rj}\geq0\) with \(\sum_jw_{rj}\leq1\), while allocating exactly mass \(\rho_rw_{rj}\) to service \(j\) within each report class.
For every positive-mass report class \(A_r\), choose a normalized coordinate \(u_r:A_r\to[0,1)\) whose pushforward of the class’s normalized mass is Lebesgue measure. Such a coordinate exists for every finite nonatomic measure space: the nonatomic divisibility theorem permits repeated equal bisections, and the resulting binary partition labels give a uniform coordinate. Its hypotheses hold because restricting the society’s nonatomic measure to \(A_r\) preserves nonatomicity.
For a zero-mass report class, assign coordinate zero to its agents, if any.
Partition \([0,1)\) into consecutive half-open service intervals \(I_{rj}\) of lengths \(w_{rj}\), followed by a no-service interval of length \(1-\sum_jw_{rj}\). Draw one common uniform shift \(U\in[0,1)\). Give an agent in class \(r\) service \(j\) precisely when
\(\displaystyle (u_r+U)\bmod1\in I_{rj}.\)
Charge \(p_{rj}\) upon receiving service \(j\), and zero otherwise.
For each fixed agent, translation of a uniform shift is uniform. Thus its service probability is exactly \(w_{rj}\), regardless of its coordinate. Identical reports therefore receive identical lotteries.
For each fixed shift, translation preserves Lebesgue measure. The mass receiving service \(j\) in class \(r\) is consequently exactly \(\rho_rw_{rj}\). Summing across report classes and services proves that, in every realization, total served mass is at most \(q\).
Zero-mass classes contribute no served mass but still have the prescribed lotteries. The population coordinates only correlate allocations; they do not affect any agent’s marginal lottery.
The LP has \(2\tau m\) variables and \(O(\tau m+\tau^2)\) constraints. Its coefficients are rational, and its total encoding length is polynomial in \(m,\tau,L\).
We use the standard rational linear-programming theorem: an explicitly represented rational LP can be solved exactly in time polynomial in its encoding length; a bounded nonempty rational polytope has an optimal rational solution of polynomial encoding length. Polynomial LP algorithms and the vertex-size bounds underlying exact optimization are described in [MIT’s linear-programming notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
The theorem applies here because the LP is explicit, rational, nonempty, and bounded. Hence \((x^*,z^*)\) and the conditional prices \(p_{rj}\) have polynomial encoding length and are computable in polynomial time.
The output consists of these tables, the scaling formula, and the cyclic rationing rule. Given a rational profile \(\rho\), evaluating \(D(\rho)\), \(\alpha(\rho)\), all service probabilities, and all interval endpoints takes polynomial time in \(m,\tau,L\) and the profile’s bit length.
There is also a finite randomization implementation at every rational profile. Let \(K\) be the product of the denominators of the rational probabilities \(w_{rj}\), and write \(n_{rj}=Kw_{rj}\). The bit length of \(K\) is polynomial; its numerical magnitude need not be polynomial.
Partition each report class into cells labeled by \(\lfloor Ku_r\rfloor\). These cells each have mass \(\rho_r/K\). Draw a common integer \(H\) uniformly from \(\{0,\ldots,K-1\}\), and cyclically shift cell labels by \(H\). Assign consecutive blocks of \(n_{rj}\) shifted labels to service \(j\).
Every agent visits every shifted label with equal probability, giving probability \(n_{rj}/K=w_{rj}\) for service \(j\). In every realization, exactly \(n_{rj}\) cells receive that service, giving mass \(\rho_rw_{rj}\).
Computing this rationing description, and evaluating its label rule given \(H\), uses polynomial time and polynomial-length integers. It requires no enumeration of the \(K\) shifts or cells. At irrational profiles, the continuous-shift construction defines the mechanism and proves feasibility.
The LP supply constraint gives \(D(\mu)\leq q\), so \(\alpha(\mu)=1\). Therefore the constructed mechanism earns
\(\displaystyle R(M)=\sum_t\mu_t\sum_jx^*_{tj}p_{tj}=\sum_t\mu_t\sum_jz^*_{tj}=V^*.\)
The mechanism is admissible at every report-mass profile. Combining its revenue with the earlier upper bound yields
\(\displaystyle V^*=R(M)\leq\mathrm{OPT}\leq V^*.\)
Thus the supremum is attained, and exact optimization—and hence any fixed positive constant approximation up to \(c=1\)—is polynomial-time solvable for the formulation in the question.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes exact polynomial-time optimization under the task’s natural interpretation: the evaluator computes report lotteries from a report-mass profile, while nonatomic rationing implements those lotteries. There is one minor technical omission in the coordinate construction. I found no false central step or gap requiring new mathematics.
The variables distinguish allocation probabilities from payments attributable to each service. At the truthful profile, ex-post IR and budget feasibility imply \(0\leq z_{tj}\leq \min\{B_t,v_{tj}\}x_{tj}\). Payment upon receiving nothing is zero, so total expected payment is exactly \(\sum_j z_{tj}\).
For \(t,r\in T_b\), payments in report \(r\)’s lottery cannot exceed type \(t\)’s budget: both reports have public budget \(b\). Thus the stated deviation utility is correct, including deviations whose realized payment exceeds the deviator’s value. Ex-post IR is required for truthful reports; it does not prohibit such deviations.
The incentive inequalities therefore follow from the stipulated DSIC definition. Taking expectations of realization-wise supply feasibility gives the LP supply inequality. The objective equals truthful revenue, establishing \(\mathrm{OPT}\leq V^*\).
Nonemptiness, closedness, and boundedness are correctly established. In particular, all values and budgets are finite rationals, so the payment bounds are finite.
When \(x^*_{rj}=0\), the LP forces \(z^*_{rj}=0\). Consequently, the identity \(x^*_{rj}p_{rj}=z^*_{rj}\) holds in both branches of the price definition.
For positive allocation probabilities, division gives \(0\leq p_{rj}\leq \min\{B_r,v_{rj}\}\). Replacing conditional payment randomness by these deterministic conditional prices preserves the expected utilities used by the LP and satisfies the required realized-payment restrictions.
Since \(0\leq s_r\leq1\) and report masses sum to one, \(0\leq D(\rho)\leq1\). The scaling factor is well-defined and belongs to \([0,1]\).
The edge cases are handled correctly:
At a fixed profile, every report’s utility is multiplied by the same nonnegative factor. A single agent’s deviation leaves that profile unchanged by explicit assumption in the task. Multiplying the LP incentive inequalities by \(\alpha(\rho)\) therefore establishes precisely the required DSIC inequalities.
Truthful utility is nonnegative term by term, so the outside option creates no additional incentive constraint. Zero-mass reports retain defined lotteries and participate in the same inequalities.
Restricting a nonatomic finite measure to a measurable positive-mass report class preserves nonatomicity. Repeated equal bisections support the asserted existence of a measurable uniform coordinate. The proof implicitly uses the standard measurable interpretation of report classes.
Once the stated coordinate \(u_r:A_r\to[0,1)\) exists, both required conclusions follow:
These are separate statements, and the proof correctly establishes both. Summing the latter quantities yields realization-wise supply feasibility. The common shift creates correlations without altering identical reports’ marginal lotteries, which is the anonymity condition specified in the task.
Zero-mass classes cause no difficulty: their agents can have the prescribed marginal lotteries while contributing zero served mass.
Minor issue: The stated binary-partition justification does not address exceptional binary labels corresponding to the endpoint \(1\). A direct binary-label construction naturally takes values in \([0,1]\), whereas the proof requires \([0,1)\). Because lotteries must be defined for every agent, an almost-everywhere statement alone is insufficient.
Minimum clarification: Specify how exceptional endpoint labels are handled, and confirm that the resulting coordinate is defined everywhere, remains measurable, and has the claimed pushforward distribution. This is a routine measure-theoretic clarification, not a substantive obstruction.
There are \(2\tau m\) variables. The incentive constraints number \(\sum_b|T_b|^2\leq\tau^2\); the remaining constraints number \(O(\tau m)\). All coefficients have polynomial total encoding length.
The rational-LP theorem is stated sufficiently precisely for this application: an explicit rational LP is solvable in polynomial time, and a nonempty bounded rational polytope has a polynomial-length rational optimum. Its hypotheses are satisfied, including potentially lower-dimensional feasible regions. The cited [MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial LP algorithms, polynomial vertex encoding bounds, and recovery of exact optima.
Taking ratios to form conditional prices preserves polynomial bit length. At a rational profile, the sums, scaling factor, probabilities, and interval endpoints likewise have polynomial bit length and are computable by polynomially many rational arithmetic operations.
The denominator-product argument is correct: the bit length of \(K\) is bounded by the sum of the denominator bit lengths. Numerical enumeration of its potentially many cells or shifts is unnecessary. Conditional on the class labels, the finite cyclic rule has exactly the claimed probabilities and realized masses.
The computational scope should be read precisely. The proof establishes polynomial evaluation of report lotteries and their rationing specification. It does not establish an algorithm for constructing coordinates on an arbitrary separately supplied measure space, or for computing an arbitrary agent’s real coordinate. The task supplies support data and asks for evaluation at rational report-mass profiles; it supplies no such additional computational input. Under that natural interpretation, this distinction does not invalidate the result.
At the truthful profile, LP feasibility gives \(D(\mu)\leq q\), hence \(\alpha(\mu)=1\). The constructed mechanism’s revenue is therefore exactly \(V^*\).
Combined with the previously established upper bound, this yields \(R(M)=\mathrm{OPT}=V^*\). The argument consequently establishes attainment of the supremum and the requested approximation with \(c=1\).
Conditional independence is unused. This is consistent: proving the claim for a larger class of explicitly represented supports also proves it for the restricted class in the task.
⟨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.