Answer: Yes. A deterministic truthful mechanism computable in polynomial time achieves \(\mathrm{OPT}\) exactly, and therefore at least \(\mathrm{OPT}/(m+1)\), with polynomial-time individual allocation and payment evaluation.
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe mechanism with (m + 1)-Apx-MUCA as the allocation algorithm and the associated critical value pay- ment scheme is (m + 1)-approximation truthful mechanism for multi unit combinatorial auctions with m types of goods. Single Minded Bidders Some of our techniques apply to the more general model of Single Minded Bidders of Lehmann, O’Callaghan, & Shoham. In this section we shortly mention which tech- niques do generalize and how.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) resource types, per-capita supplies \(b\in\mathbb{Q}_{\ge 0}^m\), and an atomless population with a finite-support distribution \(\mu\) over reported types \((q,v)\in\mathbb{Z}_{\ge 0}^m\times\mathbb{Q}_{\ge 0}\), compute a truthful mechanism assigning each individual either their whole requested bundle or nothing, subject to \(\sum_t q_i^t x_t\le b_i\) for every resource \(i\), that maximizes reported welfare \(\sum_t v^t x_t\). Here \(x_t\in[0,\mu_t]\) is the mass served from type \(t\), demand vectors are known or verifiable, and truthfulness is evaluated against an individual’s unilateral value-report deviation.
Let \(m\ge1\), with per-capita supplies \(b\in\mathbb Q_{\ge0}^m\). A society of total mass \(1\) is given by its support: the list of \(\tau\) types \((q^t,v^t)\in\mathbb Z_{\ge0}^m\times\mathbb Q_{\ge0}\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total binary input length.
Each individual has a known or verifiable demand vector and a privately known value. Service supplies the whole requested bundle; otherwise the individual receives nothing. Utilities are quasi-linear, and unserved individuals pay zero; require nonnegative payments and individual rationality at truthful reports.
Represent each type's atomless mass by an interval with immutable public individual identities. A deterministic mechanism specifies finitely described measurable allocation and payment rules, including their response to every unilateral nonnegative rational value report, even one outside the support. Such a deviation preserves the individual's identity and demand and leaves the aggregate distribution unchanged. Truthfulness means dominant-strategy truthfulness for each individual, with utility ties permitted.
Writing \(x_t\in[0,\mu_t]\) for the mass served from type \(t\), feasibility requires \(\sum_{t=1}^{\tau}q_i^t x_t\le b_i\) for every resource \(i\). Define \(\mathrm{OPT}\) as the maximum of \(\sum_{t=1}^{\tau}v^t x_t\) over these feasible masses, without incentive constraints.
Does this model admit a truthful mechanism computable in time polynomial in \(m,\tau,L\), with polynomial-time individual allocation and payment evaluation in the query bit length, that always achieves welfare at least \(\mathrm{OPT}/(m+1)\), or is such a polynomial-time approximation impossible?
For finitely many known single-minded bidders, a polynomial-time deterministic truthful mechanism achieves an \((m+1)\)-approximation for multi-unit combinatorial auctions. [Mu’alem–Nisan](https://cdn.aaai.org/AAAI/2002/AAAI02-058.pdf)
No result settling this precise atomless mechanism problem was identified in the literature search.
Yes. The model admits a deterministic truthful mechanism computable in polynomial time that achieves \(\mathrm{OPT}\) exactly. Consequently, it satisfies the requested \((m+1)\)-approximation.
The construction uses optimal LP resource prices and public identities to ration individuals whose reported values equal their bundle prices. Truthfulness relies on the stipulated zero mass of every individual and the permission of utility ties.
Consider the primal linear program
\(\displaystyle \max \sum_{t=1}^{\tau}v^t x_t,\qquad \sum_{t=1}^{\tau}q_i^t x_t\le b_i\ \ (i=1,\ldots,m),\qquad 0\le x_t\le\mu_t\ \ (t=1,\ldots,\tau).\)
Its optimum is precisely \(\mathrm{OPT}\). The feasible region is nonempty because it contains the zero vector, and compact because every variable lies in a bounded interval.
Introducing dual variables \(p_i\ge0\) for resource constraints and \(z_t\ge0\) for upper bounds gives the dual
\(\displaystyle \min \sum_{i=1}^{m}b_i p_i+\sum_{t=1}^{\tau}\mu_t z_t,\qquad \sum_{i=1}^{m}q_i^t p_i+z_t\ge v^t\ \ (t=1,\ldots,\tau).\)
The dual is feasible: take \(p_i=0\) and \(z_t=v^t\). Strong LP duality therefore supplies optimal primal and dual solutions \(x^*\) and \((p^*,z^*)\) with equal objective values.
Define the bundle price
\(\displaystyle c_t=\sum_{i=1}^{m}q_i^t p_i^*.\)
These prices satisfy two crucial implications:
For completeness, both follow directly from the duality gap identity:
\(\displaystyle 0=\sum_{i=1}^{m}p_i^*\left(b_i-\sum_{t=1}^{\tau}q_i^t x_t^*\right)+\sum_{t=1}^{\tau}z_t^*(\mu_t-x_t^*)+\sum_{t=1}^{\tau}x_t^*(c_t+z_t^*-v^t).\)
Every summand is nonnegative by primal and dual feasibility, so every summand vanishes.
If \(v^t>c_t\), dual feasibility gives \(z_t^*\ge v^t-c_t>0\). Hence \(z_t^*(\mu_t-x_t^*)=0\) forces \(x_t^*=\mu_t\).
If \(v^t<c_t\), then \(c_t+z_t^*-v^t>0\). Hence \(x_t^*(c_t+z_t^*-v^t)=0\) forces \(x_t^*=0\).
Thus partial service can occur only at equality \(v^t=c_t\).
Represent the interval for type \(t\) as \([0,\mu_t)\), with local identity coordinate \(s\). The pair \((t,s)\) is immutable: changing a report does not move the individual into another interval.
Compute \(x^*\) and \(p^*\) from the positive-mass reported profile. Use a fixed deterministic LP algorithm and fixed input ordering. Reports made by individual identities as null exceptions do not enter this aggregate computation.
For the individual with identity \((t,s)\), whose fixed demand is \(q^t\), and every report \(r\in\mathbb Q_{\ge0}\), define service by
\(\displaystyle a_t(s,r)= \begin{cases} 1,&r>c_t,\\ 1,&r=c_t\text{ and }s<x_t^*,\\ 0,&\text{otherwise}. \end{cases}\)
Define the payment by
\(\displaystyle P_t(s,r)=c_t\,a_t(s,r).\)
A served individual receives the whole bundle \(q^t\). An unserved individual receives nothing and pays zero. Since \(p^*\ge0\) and \(q^t\ge0\), every payment is nonnegative.
The rule is defined even when \(r\) does not occur in the support. In particular, an off-support report is evaluated using the same identity, demand, bundle price, and identity cutoff.
The allocation and payment functions are measurable: their definitions use rational value thresholds and interval cutoffs.
At truthful reports, each interval has served mass exactly \(x_t^*\):
Consequently, resource consumption is
\(\displaystyle \sum_{t=1}^{\tau}q_i^t x_t^*\le b_i\)
for every resource \(i\), and welfare is
\(\displaystyle \sum_{t=1}^{\tau}v^t x_t^*=\mathrm{OPT}.\)
A unilateral report changes outcomes at at most one identity. A singleton has zero mass, so such a change leaves every aggregate resource integral unchanged. Feasibility therefore also holds after every unilateral deviation, including an off-support deviation.
Fix an individual and fix the reports of all other individuals. The positive-mass reported profile is independent of this individual's report, because the individual has zero mass. Thus the computed LP solutions, bundle price, and identity cutoff are identical under every report by this individual.
Write \(c\) for the fixed bundle price and \(h\in\{0,1\}\) for the fixed decision at equality. The individual faces the following menu:
Let \(w\in\mathbb Q_{\ge0}\) be the individual's true value. Their utility from reporting \(r\) is
\(\displaystyle U_w(r)=(w-c)a(r).\)
There are three cases.
If \(w>c\): truthful reporting obtains service and utility \(w-c>0\). Every other report gives either that same utility or zero.
If \(w<c\): truthful reporting obtains no service and utility zero. Every report obtaining service gives utility \(w-c<0\); every other report gives zero.
If \(w=c\): every report gives utility zero, regardless of service.
Therefore
\(\displaystyle U_w(w)\ge U_w(r)\qquad\text{for every }r\in\mathbb Q_{\ge0}.\)
This argument fixes arbitrary other reports in the model; it does not require them to be truthful. Truthful reporting is consequently a dominant strategy.
Truthful individual rationality also follows: truthful service occurs only when \(w\ge c\), and otherwise the individual pays zero.
The standard rational-LP theorem provides deterministic algorithms that return exact optimal rational solutions, with polynomial encoding length, in time polynomial in the input encoding length. Exact optimization includes lower-dimensional feasible regions. See the treatment of polynomial solvability in [Nemirovski’s optimization notes, Section 8.4](https://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2020.pdf).
Here the primal has \(\tau\) variables and \(m+2\tau\) inequalities. The dual has \(m+\tau\) variables and a polynomial-size rational description. The feasibility and bounded-optimum hypotheses were checked in Section 1. Thus both optimal solutions can be computed exactly in time polynomial in \(m,\tau,L\).
Store, for each immutable interval label \(t\), the rational cutoff \(x_t^*\) and rational bundle price \(c_t\). This table has polynomial encoding length.
For a finitely encoded rational identity coordinate \(s\) and rational report \(r\), evaluation requires only comparisons of \(r\) with \(c_t\), and, at equality, of \(s\) with \(x_t^*\). Exact rational comparisons take polynomial time in the table size and query bit length. The interval formulas themselves define the rule for every real identity coordinate.
The essential case is an individual rejected at an equality \(v^t=c_t\). Overreporting makes that individual served, but the payment remains \(c_t=v^t\), so utility remains zero.
For example, take one resource, demand \(q^1=1\), value \(v^1=1\), mass \(\mu_1=1\), and supply \(b_1=1/2\). An optimal solution has \(x_1^*=1/2\) and price \(c_1=1\). Half the interval receives service and pays one. A rejected individual can overreport and receive service, but gains no utility; the additional singleton service consumes zero aggregate supply.
Hence the construction satisfies the specified weak dominant-strategy truthfulness while attaining exact optimal welfare.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed exact optimum under the task’s finite-support, atomless model. I found no false mathematical step or major gap. There is one minor clarification concerning the encoding of identity queries.
The primal correctly represents the benchmark \(\mathrm{OPT}\): allocation variables are served masses, the resource constraints are exactly those in the task, and the bounds enforce available type masses.
The feasible set contains the zero vector and is compact. Its linear objective therefore attains a finite maximum.
The stated dual is correct. In particular, upper bounds require the nonnegative variables \(z_t\), and the resulting dual constraints are \(c_t+z_t\ge v^t\). The proposed feasible dual point \(p=0,\ z_t=v^t\) satisfies every constraint.
The application of strong LP duality is valid: the primal is feasible with a finite optimum, and the dual is feasible. Optimal primal and dual solutions exist and have equal objective values. No strict feasibility or positive resource supply is required.
Assessment: Correct.
The displayed duality-gap identity expands to the dual objective minus the primal objective. Every term has the asserted nonnegative sign:
Equality of objective values consequently forces each term to vanish.
For \(v^t>c_t\), dual feasibility implies \(z_t>0\), so the upper-bound slack must vanish. For \(v^t<c_t\), the dual-constraint slack is strictly positive, so \(x_t^*=0\).
The statement that partial service can occur only at equality is correct. It does not assert that equality necessarily entails partial service.
Assessment: Correct, including strict inequalities and endpoint allocations.
The allocation rule specifies an outcome for every allowed rational report. Demand and identity remain fixed, and neither the bundle price nor the identity cutoff depends on the individual’s report.
Payments are nonnegative because both demand coordinates and resource prices are nonnegative. Unserved individuals pay zero.
The threshold and prefix sets are measurable. The formula also specifies outcomes at irrational identity coordinates, even though the computational claim is separately made for rational coordinates.
At a unilateral deviation, ignoring the deviator in aggregate computation is justified by the task’s explicit stipulation that such a deviation leaves the aggregate distribution unchanged.
Assessment: Correct on the stipulated input and deviation domain.
The phrase “arbitrary other reports in the model” should be read within that domain. The output does not supply an algorithm for arbitrary report distributions with infinite support; the task does not require polynomial processing of such inputs.
The three cases correctly reproduce \(x_t^*\) at truthful reports:
Thus truthful resource use equals the feasible primal resource use, and truthful welfare equals \(\mathrm{OPT}\).
A unilateral deviation changes allocation at only one identity. A singleton is measurable and has zero mass, so every resource integral remains unchanged. This verifies feasibility after every required unilateral deviation, including reports outside the support.
Assessment: Correct. Serving an additional singleton does not violate the task’s aggregate feasibility definition.
With other reports fixed, the individual’s zero mass keeps the aggregate LP input unchanged. Determinism therefore keeps the selected optimal solutions and cutoff unchanged as well.
The stated utility formula is correct. Each case establishes the required comparison against every nonnegative rational report:
The equality case is particularly important: a rejected individual can obtain service by overreporting, but cannot obtain strictly greater utility. This is consistent with the task’s permission of utility ties.
Truthful individual rationality follows from the same case analysis.
Assessment: Correct. The proof establishes weak dominant-strategy truthfulness, as requested.
The rational-LP theorem invoked is applicable: a feasible rational LP with finite optimum admits exact optimal rational solutions computable in polynomial bit complexity. The cited treatment addresses rational LP optimization through primal–dual feasibility and exact solution recovery, including polynomial bit complexity. [Ben-Tal–Nemirovski, Section 8.4](https://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2020.pdf)
The stated program dimensions are correct. Both descriptions have polynomial input length. The dual optimum is finite: its objective is nonnegative and it has the finite feasible objective supplied in Section 1.
Exact rational solutions have polynomial encoding length. Computing each \(c_t\) from those solutions and storing all prices and cutoffs preserves polynomial encoding length.
For rational identity coordinates and rational reports, the indicated comparisons take polynomial time in the stored description and query length.
Minor issue: The task does not explicitly specify how identity coordinates are encoded. Section 5 adopts rational coordinates for computational queries while defining the mechanism mathematically for every real coordinate. This is a natural computational interpretation, but it should be stated explicitly as the query convention. It does not undermine the allocation, truthfulness, or welfare argument.
Minimum clarification: Specify that individual evaluation queries encode the interval label and a rational local identity coordinate in binary.
The example is consistent: the served mass is \(1/2\), the bundle price is \(1\), and a rejected individual with true value \(1\) obtains zero utility whether rejected or served at that price.
The output resolves the requested approximation question with the stronger exact-welfare guarantee. No hardness conclusion is established or needed. The only identified issue is the minor query-encoding clarification.
⟨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.