Answer: The tight worst-case approximation factor is \(e/(e-1)\), independent of \(\lambda_{\max}/\lambda_{\min}\), and is achievable in polynomial time.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo budget-feasible proportion-representative mechanism obtains an approximation ratio better than Ω(α). In particular, it is worth stating that this lower bound also applies to the multiple group setting.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational group masses \(\lambda_j>0\) summing to \(1\), a finite rational cost domain \(K\), and truthful cost masses \(\mu_{j,c}\) summing to \(\lambda_j\), determine the tight worst-case approximation ratio for a computationally efficient truthful, individually rational, budget-feasible mechanism. The mechanism receives reported masses \(\nu_{j,b}\), assigns selection rates \(q_j(b;\nu)\) and expected per-person transfers \(p_j(b;\nu)\), and must satisfy \(\sum_{j,b}\nu_{j,b}p_j(b;\nu)\le B\) for every report measure, interpreted as exact aggregate expenditure over selected mass. For each infinitesimal agent of true cost \(c\), require \(p_j(c;\nu)-c q_j(c;\nu)\ge p_j(b;\nu)-c q_j(b;\nu)\) for every report \(b\), holding the other agents' mass fixed. Compare its truthful representation \(\min_j \sum_c\mu_{j,c}q_j(c;\mu)/\lambda_j\) with \(\mathrm{OPT}(\mu)=\max_{0\le y_{j,c}\le\mu_{j,c}}\min_j\sum_c y_{j,c}/\lambda_j\), subject to \(\sum_{j,c}c y_{j,c}\le B\). In particular, determine whether every such mechanism has a worst-case approximation lower bound of order \(\Omega(\lambda_{\max}/\lambda_{\min})\), or whether fractional selection beats it, with running time measured in \(m,\tau,L\).
There are \(m\ge1\) publicly known, disjoint groups in an atomless society, with positive binary rational masses \(\lambda_j\) summing to \(1\). Public inputs also include a positive binary rational budget \(B\) and a nonempty finite cost/report domain \(K\subset\mathbb Q_{>0}\).
A society is given by its support: the list of the \(\tau\) types \((j,c)\) with positive mass, each with its mass as a binary rational. Thus \(\tau\) is the support size, not the number of possible types. Truthful masses satisfy \(\mu_{j,c}\ge0\) and \(\sum_{c\in K}\mu_{j,c}=\lambda_j\); they are private.
An anonymous mechanism receives only reported masses \(\nu_{j,b}\ge0\), with \(\sum_{b\in K}\nu_{j,b}=\lambda_j\), and returns rational selection rates \(q_j(b;\nu)\in[0,1]\) and expected per-person transfers \(p_j(b;\nu)\ge0\), defined even for reports of zero mass. Require \(p_j(b;\nu)=0\) whenever \(q_j(b;\nu)=0\).
For every report measure, require exact aggregate expenditure \(\sum_{j,b}\nu_{j,b}p_j(b;\nu)\le B\). For every \(j,c,b,\nu\), require individual rationality \(p_j(c;\nu)-c q_j(c;\nu)\ge0\) and truthfulness \(p_j(c;\nu)-c q_j(c;\nu)\ge p_j(b;\nu)-c q_j(b;\nu)\). An individual's deviation has zero mass and leaves \(\nu\) unchanged; group membership cannot be misreported.
Define \(\mathrm{ALG}_M(\mu)=\min_j\lambda_j^{-1}\sum_{c\in K}\mu_{j,c}q_j(c;\mu)\) and \(\mathrm{OPT}(\mu)=\max\{\min_j\lambda_j^{-1}\sum_{c\in K}y_{j,c}:0\le y_{j,c}\le\mu_{j,c},\ \sum_{j,c}c y_{j,c}\le B\}\).
The approximation factor is \(\mathrm{OPT}/\mathrm{ALG}_M\), interpreted as \(+\infty\) when \(\mathrm{ALG}_M=0<\mathrm{OPT}\). Computational efficiency means polynomial time in \(m,\tau,|K|,L\), where \(\tau\) is the reported support size and \(L\) is the total binary input length.
What is the tight worst-case approximation factor achievable by such computationally efficient mechanisms over all admissible inputs? In particular, must every such mechanism incur an \(\Omega(\lambda_{\max}/\lambda_{\min})\) factor, where \(\lambda_{\max}=\max_j\lambda_j\) and \(\lambda_{\min}=\min_j\lambda_j\), or can fractional selection improve this dependence?
For finite agents with indivisible selection, an \(\Omega(n_{\max}/n_{\min})\) approximation lower bound is established; a polynomial-time mechanism achieves \(3+n_{\max}/n_{\min}\) when it selects at least one agent from every group ([discrete results](https://www.ijcai.org/proceedings/2021/0044.pdf)).
The expanded [journal version](https://www.sciencedirect.com/science/article/pii/S0004370223001212) also reports a matching discrete lower bound. No result settling precisely the atomless model above was located.
The tight worst-case approximation factor is \(\displaystyle \frac{e}{e-1}\approx 1.58198\), independent of \(\lambda_{\max}/\lambda_{\min}\).
A polynomial-time mechanism attains this guarantee. Conversely, every mechanism satisfying the stated incentive and budget constraints has worst-case factor at least \(\frac{e}{e-1}\), even for any fixed choice of group masses.
The argument uses the stipulated fact that an individual deviation leaves the reported measure unchanged. The cited discrete bounds concern indivisible selection and therefore do not establish a lower bound for this model. [IJCAI paper](https://www.ijcai.org/proceedings/2021/0044.pdf)
Write \(K=\{c_1,\ldots,c_h\}\), where \(0<c_1<\cdots<c_h\). Fix a reported measure \(\nu\) and a group, and abbreviate its menu by \(q_i,p_i\).
Adding the truthfulness inequalities for types \(c_i<c_k\) gives
\((c_k-c_i)(q_i-q_k)\ge 0.\)
Thus \(q_1\ge\cdots\ge q_h\). Set \(q_{h+1}=0\) and \(x_i=q_i-q_{i+1}\). Then
\(x_i\ge0,\qquad \sum_{i=1}^h x_i=q_1\le1,\qquad q_i=\sum_{k=i}^h x_k.\)
Truthfulness for type \(c_i\) against report \(c_{i+1}\) gives
\(p_i\ge p_{i+1}+c_i(q_i-q_{i+1}).\)
Together with individual rationality \(p_h\ge c_hq_h\), backward induction yields
\[p_i\ge \sum_{k=i}^h c_kx_k. \tag{1}\]
Conversely, for any nonnegative weights satisfying \(\sum_kx_k\le1\), the menu
\[q_i=\sum_{k=i}^h x_k,\qquad p_i=\sum_{k=i}^h c_kx_k \tag{2}\]
is truthful and individually rational. To see this, interpret weight \(x_k\) as offering price \(c_k\) and selecting precisely reports at most \(c_k\). For an individual of cost \(c\), participating in that offer contributes \(c_k-c\) to utility. Truthful reporting accepts every offer with nonnegative contribution and rejects every offer with negative contribution. Hence no alternative report improves utility.
Also, \(q_i=0\) forces every corresponding \(x_k=0\), so \(p_i=0\).
Consequently, every feasible truthful menu can be replaced by a mixture of posted prices preserving its selection rates and weakly decreasing every payment.
For every reported measure, define the normalized cumulative masses
\(f_{j,i}=\lambda_j^{-1}\sum_{k=1}^i\nu_{j,c_k}.\)
In particular, \(f_{j,h}=1\). Offering price \(c_i\) in group \(j\) selects fraction \(f_{j,i}\) and costs \(\lambda_jc_if_{j,i}\).
Solve the following linear program:
\(\text{maximize }t,\)
subject to
\(x_{j,i}\ge0,\qquad \sum_i x_{j,i}\le1\quad\text{for every }j,\)
\(\sum_i f_{j,i}x_{j,i}\ge t\quad\text{for every }j,\)
\[\sum_j\lambda_j\sum_i c_if_{j,i}x_{j,i}\le B,\qquad 0\le t\le1. \tag{3}\]
Return
\[q_j(c_k;\nu)=\sum_{i=k}^h x_{j,i},\qquad p_j(c_k;\nu)=\sum_{i=k}^h c_ix_{j,i}. \tag{4}\]
Section 1 proves truthfulness, individual rationality, and the required zero-payment property, including at reports of zero mass. The budget constraint in (3) is exactly the aggregate expenditure of (4).
Crucially, an individual's deviation leaves \(\nu\), and therefore the entire computed menu, unchanged.
For binary-rational reported masses, (3) is a rational linear program with \(mh+1\) variables and polynomially many constraints. Its coefficients have binary lengths polynomial in the input length. An exact rational optimal solution can therefore be computed in polynomial time in \(m,\tau,|K|,L\).
Moreover, this mechanism is pointwise optimal among feasible truthful mechanisms: applying (1) to any such mechanism produces feasible weights in (3), with the same selection rates and no greater expenditure.
Consider a normalized group of mass \(1\). Let its cumulative masses at the costs be \(f_i\), and let \(c(z)\), for \(0<z\le1\), be its nondecreasing cost quantile function.
Define
\(C(t)=\int_0^t c(z)\,dz.\)
This is the minimum actual cost of selecting fraction \(t\): any allocation selecting higher-cost mass while leaving lower-cost mass unselected can be improved by exchanging equal amounts of that mass.
Define the minimum posted-price-mixture expenditure for selecting exactly fraction \(s\):
\[T(s)=\min\left\{\sum_i c_if_ix_i:\ x_i\ge0,\ \sum_i x_i\le1,\ \sum_i f_ix_i=s\right\}. \tag{5}\]
Geometrically, \(T\) is the lower boundary of the convex hull of \((0,0)\) and the points \((f_i,c_if_i)\). It is finite and convex on \([0,1]\), and \(T(0)=0\).
Lemma. With \(\rho=1-e^{-1}\), for every \(0<t\le1\),
\[T(\rho t)<C(t). \tag{6}\]
Proof. Put \(s=\rho t\). Since all costs are positive, \(T(s)\ge c_1s>0\).
Because \(s\in(0,1)\), the finite convex polygon defining \(T\) has a supporting line at \(s\). Write it as
\(az-d,\qquad T(z)\ge az-d,\qquad T(s)=as-d.\)
Evaluating the supporting inequality at \(0\) gives \(d\ge0\). Since \(as-d=T(s)>0\), we also have \(a>0\) and \(d<as<at\).
Each threshold point satisfies
\(c_if_i\ge T(f_i)\ge af_i-d.\)
For any quantile \(z>0\), choose its cost index \(i\), so \(c(z)=c_i\) and \(f_i\ge z\). Therefore
\(c(z)\ge a-\frac{d}{f_i}\ge a-\frac{d}{z}.\)
Using positivity of costs,
\[c(z)\ge\max\left\{0,a-\frac{d}{z}\right\}. \tag{7}\]
If \(d=0\), integration gives \(C(t)\ge at>as=T(s)\).
Suppose \(d>0\), and set \(r=d/(at)\in(0,1)\). Integrating (7) gives
\[C(t)>\int_{d/a}^t\left(a-\frac{d}{z}\right)\,dz =at(1-r+r\log r). \tag{8}\]
The inequality is strict because the actual costs are positive on the nonempty interval \((0,d/a)\), where the lower bound in (7) is zero.
The function \(r\log r\) has derivative \(1+\log r\), second derivative \(1/r>0\), and minimum \(-e^{-1}\) at \(r=e^{-1}\). Hence
\(1-r+r\log r\ge \rho-r.\)
Combining this with (8),
\(C(t)>at(\rho-r)=as-d=T(s).\)
This proves (6). ∎
At a truthful society, let \(C_j,T_j\) denote the normalized functions from Section 3 for group \(j\), and write \(t^*=\mathrm{OPT}(\mu)\).
The cheapest way to obtain representation fraction \(t\) in every group costs
\(\sum_j\lambda_jC_j(t).\)
Indeed, selection beyond fraction \(t\) can be discarded, and the remaining selection can be replaced by the cheapest mass in its group. Therefore
\[\sum_j\lambda_jC_j(t^*)\le B. \tag{9}\]
Also, \(t^*>0\): selecting a sufficiently small common fraction uniformly across all types is feasible because \(B>0\) and \(K\) is finite.
Apply the lemma group by group:
\(\sum_j\lambda_jT_j(\rho t^*)<\sum_j\lambda_jC_j(t^*)\le B.\)
Thus posted-price mixtures selecting fraction \(\rho t^*\) in every group are feasible in (3). Its optimum consequently satisfies
\(\mathrm{ALG}_M(\mu)\ge \rho\,\mathrm{OPT}(\mu).\)
It follows that
\[\displaystyle \frac{\mathrm{OPT}(\mu)}{\mathrm{ALG}_M(\mu)} \le\frac1\rho=\frac{e}{e-1}. \tag{10}\]
The mechanism computes the rational LP optimum; it does not need to represent \(e\) or \(\rho\).
Arbitrary real report measures. If “every report measure” includes masses without finite binary encodings, a rational-output extension also exists. The strict budget slack above and continuity of the finite convex functions \(T_j\) permit a common fraction slightly greater than \(\rho t^*\). Scale its weights down slightly, retaining representation greater than \(\rho t^*\), to make every weight-sum constraint strict. Sufficiently close nonnegative rational weights then preserve these strict inequalities and budget feasibility. Define the extension by choosing the first suitable rational tuple in a fixed enumeration. Section 1 still proves all incentive properties. Polynomial-time computation applies to the binary-encoded inputs specified in the question.
Fix any admissible group masses \(\lambda_1,\ldots,\lambda_m\). We construct a sequence of finite rational societies with those same masses.
Let \(n\) run through powers of two with \(n\ge4\), and put
\(r_n=\frac{\lfloor n/e\rfloor}{n},\qquad c_i=\max\left\{\frac1n,\ 1-\frac{r_n}{i/n}\right\}, \quad i=1,\ldots,n.\)
These are positive rational costs. Let \(K_n\) contain their distinct values. In each group, assign mass \(\lambda_j/n\) to each listed index, aggregating indices with identical costs.
Define
\(\overline c_n=\frac1n\sum_{i=1}^n c_i,\qquad B_n=\frac{\lceil n\overline c_n\rceil}{n}.\)
The group masses, type masses, and budget are valid binary-rational inputs. Selecting everybody costs \(\overline c_n\le B_n\), so
\[\mathrm{OPT}=1. \tag{11}\]
For any threshold cost \(c\in K_n\), let \(i\) be the last index with \(c_i=c\). Its normalized cumulative mass is \(f=i/n\), and the construction gives
\[cf=c_i(i/n)\ge i/n-r_n=f-r_n. \tag{12}\]
Now consider any truthful mechanism on this society. By Section 1, in group \(j\) its allocation has threshold weights \(x_{j,k}\ge0\) with \(\sum_kx_{j,k}\le1\), and its expenditure is at least the corresponding posted-price-mixture expenditure.
Write \(A_j\) for its selected fraction in group \(j\). From (12), its group expenditure is at least
\(\lambda_j\sum_k(f_k-r_n)x_{j,k} =\lambda_j\left(A_j-r_n\sum_kx_{j,k}\right) \ge\lambda_j(A_j-r_n).\)
Summing, using \(\sum_j\lambda_j=1\), and applying budget feasibility gives
\(B_n\ge\sum_j\lambda_jA_j-r_n \ge\min_j A_j-r_n.\)
Consequently, every truthful mechanism satisfies
\[\mathrm{ALG}_M\le B_n+r_n. \tag{13}\]
It remains to compute the limit. Define
\(g_r(z)=\max\{0,1-r/z\}\quad(z>0),\qquad g_r(0)=0.\)
This function is nondecreasing and bounded by \(1\). Its right-endpoint Riemann sum differs from its integral by at most \(1/n\). Replacing \(g_{r_n}(i/n)\) by \(c_i\) increases each summand by at most \(1/n\); rounding the budget adds less than another \(1/n\). Thus
\(\int_0^1g_{r_n}(z)\,dz \le B_n \le\int_0^1g_{r_n}(z)\,dz+\frac3n.\)
The integral is
\(\int_0^1g_r(z)\,dz =\int_r^1(1-r/z)\,dz =1-r+r\log r.\)
Since \(r_n\to e^{-1}\),
\[B_n+r_n\longrightarrow 1-e^{-1}=\rho. \tag{14}\]
Combining (11)–(14), every mechanism has approximation factor at least \(1/(B_n+r_n)\) on these instances, with the usual infinite-factor interpretation if its selection is zero. These lower bounds converge to \(1/\rho=e/(e-1)\).
Therefore no smaller uniform approximation factor is possible, regardless of computational efficiency.
The exact uniform worst-case factor is \(\frac{e}{e-1}\). Fractional selection under the stated zero-mass deviation model removes the dependence on \(\lambda_{\max}/\lambda_{\min}\) entirely.
⟨structured verdict parsed — rendered above⟩
The output resolves the task. The upper bound and matching lower bound are correct, and the polynomial-time mechanism meets the stated incentive, budget, and rational-output requirements. I found no major or minor issues requiring repair.
The tight factor is understood as a worst-case supremum over admissible inputs. The lower-bound sequence approaches the claimed constant; attaining equality on a finite instance is unnecessary.
The monotonicity argument is correct. Adding the two incentive inequalities for \(c_i<c_k\) gives the displayed inequality and hence \(q_i\ge q_k\). Therefore the weights \(x_i=q_i-q_{i+1}\) are nonnegative, sum to at most \(1\), and reproduce all selection rates.
The payment lower bound is correct. The adjacent incentive inequality has the stated direction:
\[
p_i\ge p_{i+1}+c_i(q_i-q_{i+1}).
\]
Together with \(p_h\ge c_hq_h\), its backward iteration gives equation (1), including the endpoint \(i=h\).
The converse construction satisfies every required incentive inequality. For each threshold offer, truthful reporting includes all offers whose utility contribution is positive and excludes those whose contribution is negative. An offer at the individual's exact cost contributes zero, so ties cause no problem. A different report cannot increase the sum of these contributions.
This argument applies to every cost in \(K\), including reports with zero mass. Nonnegative weights also ensure nonnegative payments. If \(q_i=0\), every weight entering its payment is zero, establishing the required zero-payment condition.
Consequently, the claimed replacement preserves selection rates and weakly decreases payments. It does not assume that transfers in the original mechanism already have the posted-price form.
The LP correctly describes feasible mixtures. The coefficient \(f_{j,i}\) is the selected fraction under threshold \(c_i\), and \(\lambda_jc_if_{j,i}\) is its aggregate expenditure. Thus the representation constraints and budget constraint have the correct normalization.
The returned menus satisfy the mechanism requirements. Section 1 applies separately to every group. Summing the returned payments against reported masses gives exactly the LP expenditure. The stipulated zero-mass deviation leaves the report measure unchanged, so menu dependence on the reported measure introduces no additional incentive condition.
The invocation of polynomial-time rational linear programming is valid. The relevant hypotheses hold:
An exact rational optimum therefore exists and can be computed in polynomial time. The rational output menus inherit polynomial encoding length. Using all \(m|K|\) potential reports is consistent with the requested polynomial dependence on \(m,\tau,|K|,L\); the argument never substitutes the number of possible types for the reported support size.
Pointwise optimality on encoded inputs follows. Applying equation (1) to any competing feasible truthful menu produces feasible LP weights with identical selection rates and no greater expenditure. Its achieved minimum representation is therefore bounded by the LP optimum.
The definitions of \(C\) and \(T\) are valid. The cost-quantile integral describes the cheapest fractional selection. Zero-mass cost levels do not affect that integral.
The feasible weights in equation (5), together with unused weight assigned to \((0,0)\), give precisely the stated convex hull. Since \(f_h=1\), every selection fraction in \([0,1]\) is feasible. Thus \(T\) is finite and convex on the stated interval, with \(T(0)=0\).
The supporting-line argument has the required domain conditions. For \(s=\rho t\), one has \(0<s<1\), including when \(t=1\). A supporting line exists at this interior point. Evaluating it at zero yields \(d\ge0\). Positivity of \(T(s)\) then yields \(a>0\) and \(d<as<at\).
The quantile bound has the correct direction. A cost index belonging to quantile \(z>0\) has \(f_i\ge z>0\). Since \(d\ge0\), this justifies the inequality involving the two denominators. No division by a zero cumulative mass occurs.
Both integration cases are correct.
The integral evaluates correctly to \(at(1-r+r\log r)\). The derivative, second derivative, and minimum of \(r\log r\) are also correct. Their substitution gives the claimed strict inequality \(T(\rho t)<C(t)\).
This establishes the lemma for every stated \(0<t\le1\).
The benchmark comparison is correct. Achieving representation fraction \(t\) in each group has minimum actual expenditure \(\sum_j\lambda_jC_j(t)\). Discarding excess selection and replacing the remainder by cheapest available mass are valid fractional operations.
The benchmark optimum exists because its finite-dimensional feasible set is compact. Its positivity follows from the positive budget, finite cost domain, and positive group masses.
Applying the lemma to every group therefore supplies feasible mixtures at fraction \(\rho t^*\), with strict aggregate budget slack. The LP optimum achieves at least that representation. Equation (10) follows, and its denominator is positive.
Rational outputs do not require representing the irrational constant. The mechanism returns the rational LP optimum. The comparison with \(\rho t^*\) is solely part of its analysis.
The extension to arbitrary real reports is adequate. Reading \(t^*\) in that paragraph as the benchmark for the report measure under consideration, strict budget slack and continuity permit a slightly larger common selection fraction. Slight scaling makes all weight-sum constraints strict while retaining representation above the target. Nonnegative rational approximation then preserves the strict representation and feasibility inequalities.
The resulting rational weights give rational selection rates and transfers because \(K\) consists of rational costs. The enumeration defines a menu for each such report measure. No polynomial-time claim is made for inputs without finite binary encodings.
The extension need not retain exact pointwise LP optimality; it retains the approximation guarantee required by the task.
The constructed instances are admissible. For every power of two \(n\ge4\), \(r_n\) is positive and less than \(1\). The costs are positive rationals and form a nondecreasing sequence. Aggregating repeated costs therefore produces a valid finite domain and support.
The masses \(\lambda_j/n\) remain binary rational when the original group masses are binary rational. Aggregation preserves this property and the prescribed group totals. The rounded budget is positive and binary rational.
The benchmark equals \(1\). Full selection costs \(\overline c_n\), since the group masses sum to \(1\). The budget is at least this quantity, while representation cannot exceed \(1\).
Equation (12) is correct, including repeated costs. Taking the last index with a given cost gives its actual cumulative mass. Multiplying the defining cost inequality by this mass gives the displayed threshold-expenditure bound.
The expenditure lower bound applies to every feasible truthful mechanism. Section 1 supplies threshold weights for its allocation and a lower bound on its payments. Because \(r_n\ge0\) and each group's weight sum is at most \(1\), the displayed inequality involving \(A_j-r_n\) has the correct direction.
Summing against the group masses and using their sum of \(1\) gives equation (13). No computational restriction is used.
The approximation of the integral and its limit are correct. The nondecreasing function \(g_{r_n}\) has right-endpoint Riemann-sum error at most \(1/n\). Replacing its sampled values by \(c_i\) adds at most \(1/n\) to the average, and budget rounding adds less than \(1/n\). The resulting \(3/n\) bound is valid.
The integral evaluates to \(1-r+r\log r\). Substituting the limit \(r_n\to e^{-1}\) gives \(B_n+r_n\to1-e^{-1}\).
Thus every mechanism has worst-case factor at least the claimed constant. The argument works for each fixed admissible vector of group masses, since only the domains, within-group distributions, and budgets vary along the sequence.
The proof establishes a universal polynomial-time approximation factor and a matching lower bound against all mechanisms satisfying the specified constraints. Consequently, the claimed dependence on \(\lambda_{\max}/\lambda_{\min}\) is unnecessary in this atomless model.
The cited discrete paper uses indivisible selection indicators, so its lower bound does not establish a lower bound for the present fractional model. This contextual statement is consistent with its [mechanism definition](https://www.ijcai.org/proceedings/2021/0044.pdf).
No additional lemma, corrected computation, or clarification is needed to make the submitted argument verifiable.
⟨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.