Answer: \(\lambda(m,\tau,L)=1\) in the anonymous support-profile interpretation specified above.
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is a constant $c > 0$ such that, for any polytime TIE transformation $\calt$, there is an algorithm $\alg$ and problem instance $\Feas$ such that $\frac{approx_\Feas(\alg)}{approx_\Feas(\calt(\alg))} \geq n^c$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of service-relevant value types \(\Theta\), rational type masses \(\mu\), an anonymous feasible correspondence \(\mathcal F(\mu)\) over type-level service probabilities, and black-box access to an algorithm \(\mathcal A\) returning feasible allocations on reported mass profiles, determine the optimal worst-case welfare-loss factor \(\lambda(\tau,L)\) achievable by a polynomial-\((\tau,L)\)-query transformation that preserves feasibility and makes a tagged agent’s expected service nondecreasing in its reported value at every fixed background mass profile. Welfare is \(W_\mu(x)=\sum_{\theta\in\Theta}\mu_\theta\theta x_\theta\), with each unit of mass receiving either a whole unit of service or none.
Let \(\Theta\subset\mathbb Q_{>0}\) be a finite report domain with \(m=|\Theta|\ge2\). A society is atomless, of total mass \(1\), and is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total encoding length of the domain and mass profile.
Fix an unknown, nonempty family of measurable binary service outcomes on this society, independent of reports and invariant under measure-preserving relabelings of agents. No downward-closure assumption is imposed.
For each reported mass profile \(\mu\), let \(\mathcal F(\mu)\subseteq[0,1]^\Theta\) consist of the type-level service probabilities attainable by lotteries over these outcomes, treating agents with the same report symmetrically. Each individual receives a whole unit of service or none; fractional coordinates represent probabilities. Coordinates of zero-mass types impose no feasibility restriction.
An oracle \(\mathcal A\) returns feasible rational probability vectors on rational reported mass profiles, possibly randomly, with polynomially bounded reply length. A transformation knows the domain and welfare objective but has no description of the feasibility constraint or access to a feasibility oracle; it may query \(\mathcal A\) adaptively at other profiles.
A tagged agent has zero mass, so changing its report leaves the background profile \(\mu\) fixed. Its service probability when reporting \(\theta\) is the coordinate \(x_\theta(\mu)\), including at absent types. Require \(\mathbb E[x_\theta(\mu)]\le\mathbb E[x_{\theta'}(\mu)]\) whenever \(\theta<\theta'\), at every background profile, and feasibility on every execution.
Define \(W_\mu(x)=\sum_{\theta\in\Theta}\mu_\theta\theta x_\theta\) and \(\operatorname{OPT}(\mu)=\sup_{x\in\mathcal F(\mu)}W_\mu(x)\). Let \(\mathcal P_{\tau,L}\) contain the rational profiles with support size at most \(\tau\) and encoding length at most \(L\), and set \(r_{\tau,L}(\mathcal B)=\inf_{\mu\in\mathcal P_{\tau,L}}\mathbb E[W_\mu(\mathcal B(\mu))]/\operatorname{OPT}(\mu)\), assigning ratio \(1\) when the optimum is zero.
Transformations must work uniformly for every such feasibility constraint and oracle, in polynomial time and with polynomially many queries in \(m,\tau,L\); query encodings must also have polynomial length.
What is the optimal worst-case loss factor \(\lambda(m,\tau,L)\in[1,\infty]\) achievable by these transformations, with the guarantee \(r_{\tau,L}(\mathcal T(\mathcal A))\ge r_{\tau,L}(\mathcal A)/\lambda(m,\tau,L)\) for every admissible oracle and constraint?
For finite societies with \(n\) agents, every polynomial-time feasibility-oblivious truthful-in-expectation transformation can lose a factor \(n^c\) in worst-case approximation ratio for some constant \(c>0\); the construction uses nonbinary allocation amounts. [Source](https://pages.cs.wisc.edu/~shuchi/papers/black-box.pdf)
No result settling this exact atomless, anonymous, support-input model was located in the literature search.
Result and interpretation. In the intended anonymous support-input model, the optimal loss factor is \(\lambda(m,\tau,L)=1\). A transformation can make every returned probability vector monotone while weakly increasing its welfare.
We use the usual support-profile interpretation of an atomless society: represent agents by the Lebesgue unit interval, with report classes occupying intervals of the specified masses. Equivalently, equal-mass pieces can be interchanged by measure-preserving relabelings. This specifies the interpretation of anonymity used below.
Feasibility-preserving pooling. Fix a rational profile \(\mu\) and a feasible vector \(x\in\mathcal F(\mu)\). Let \(B\) be a nonempty collection of positive-mass report classes, and write \(M_B=\sum_{\theta\in B}\mu_\theta\). Define a new vector by
\(\displaystyle y_\theta=\frac{\sum_{\eta\in B}\mu_\eta x_\eta}{M_B}\quad\text{for }\theta\in B,\)
and leave all other positive-mass coordinates unchanged. Then \(y\) is feasible.
To prove this, choose an integer \(N\) such that every \(N\mu_\theta\) is an integer. Represent each report class as a union of cells of measure \(1/N\). The classes in \(B\) collectively contain \(K=NM_B\) cells.
Take a lottery witnessing feasibility of \(x\). Independently choose uniformly one of the \(K\) cyclic permutations of these cells, preserving the relative position within each cell and fixing agents outside their union. Apply this measure-preserving relabeling to the sampled outcome. Every resulting outcome belongs to the original family, by its relabeling invariance and independence from reports.
For any agent in this union, the preimages under the \(K\) permutations visit each cell once. The original service marginal is \(x_\theta\) on every cell belonging to report class \(\theta\), in the type-probability sense of symmetry. Consequently, the new service marginal is
\(\displaystyle \frac{1}{K}\sum_{\theta\in B}(N\mu_\theta)x_\theta =\frac{\sum_{\theta\in B}\mu_\theta x_\theta}{M_B}.\)
Outside the union, marginals are unchanged. This proves feasibility of \(y\). In particular, every realized service outcome remains binary and admissible; no downward-closure property is used.
The possibly large integer \(N\) is only an existence witness. The transformation need not construct or enumerate these permutations because its output is a probability vector.
The transformation. Order the positive-mass types as \(\theta_1<\cdots<\theta_t\), where \(t\le\tau\), and put \(w_j=\mu_{\theta_j}>0\).
Query \(\mathcal A\) once at the actual profile \(\mu\), obtaining a feasible vector \(x\). Start with singleton blocks of the ordered support. For each block \(B\), maintain its mass and probability:
\(\displaystyle M_B=\sum_{j\in B}w_j,\qquad p_B=\frac{\sum_{j\in B}w_jx_{\theta_j}}{M_B}.\)
Whenever two adjacent blocks \(B,C\) satisfy \(p_B>p_C\), merge them and give the merged block the probability
\(\displaystyle p_{B\cup C}=\frac{M_Bp_B+M_Cp_C}{M_B+M_C}.\)
Each merge reduces the number of blocks, so there are at most \(t-1\) merges. Continue until no adjacent inversion remains. Assign every positive-mass type its final block probability.
Complete the absent coordinates as follows: below the smallest positive-mass type, assign probability \(0\); elsewhere, assign the probability of the largest positive-mass type weakly below that coordinate. These coordinates impose no feasibility restriction by the problem’s premise.
Feasibility and monotonicity. The initial vector is feasible. Each merge is precisely the pooling operation proved feasible above, applied to the current vector. Thus feasibility holds after every merge and for the final output, for every realization of the oracle’s randomness.
At termination, consecutive block probabilities are nondecreasing. Hence probabilities are nondecreasing across the positive-mass types. The specified completion of absent coordinates preserves this ordering throughout \(\Theta\).
Therefore, on every execution,
\(\displaystyle y_\theta(\mu)\le y_{\theta'}(\mu)\quad\text{whenever }\theta<\theta'.\)
Taking expectations gives the required tagged-agent monotonicity. This argument applies separately at every background profile, as required by the zero-mass tagged-agent model.
Welfare improvement. Consider a merge of adjacent blocks \(B,C\), with \(B\) preceding \(C\). Define their mass-weighted mean types by
\(\displaystyle v_B=\frac{\sum_{j\in B}w_j\theta_j}{M_B},\qquad v_C=\frac{\sum_{j\in C}w_j\theta_j}{M_C}.\)
Every type in \(B\) is smaller than every type in \(C\), so \(v_B<v_C\). Before merging, these blocks contribute \(M_Bv_Bp_B+M_Cv_Cp_C\) to welfare. After merging, they contribute
\(\displaystyle (M_Bv_B+M_Cv_C)\frac{M_Bp_B+M_Cp_C}{M_B+M_C}.\)
Subtracting the former expression from the latter gives
\(\displaystyle \frac{M_BM_C}{M_B+M_C}(p_B-p_C)(v_C-v_B)>0,\)
because a merge occurs only when \(p_B>p_C\). All other contributions remain unchanged. Thus every merge increases welfare, and absent coordinates have zero welfare weight. Consequently,
\(\displaystyle W_\mu\bigl(\mathcal T(\mathcal A)(\mu)\bigr)\ge W_\mu\bigl(\mathcal A(\mu)\bigr)\)
for every oracle realization.
Polynomial complexity. The transformation makes exactly one oracle query, whose encoding is the input profile itself. Sorting and a direct implementation of the merging procedure use polynomially many rational arithmetic operations.
For bit complexity, maintain each block’s mass \(M_B\) and service mass \(S_B=\sum_{j\in B}w_jx_{\theta_j}\), calculating \(p_B=S_B/M_B\). Every maintained quantity is a sum, product, or quotient of input and oracle-reply rationals. A common denominator for all original weights and weighted probabilities has bit length bounded by the sum of their denominator bit lengths. Thus every block quantity and output coordinate has polynomial encoding length. Since the oracle reply length is polynomially bounded, the complete transformation runs in polynomial time in \(m,\tau,L\).
Optimal loss factor. Taking expectations in the welfare inequality gives, at every profile with positive optimum,
\(\displaystyle \frac{\mathbb E[W_\mu(\mathcal T(\mathcal A)(\mu))]}{\operatorname{OPT}(\mu)} \ge \frac{\mathbb E[W_\mu(\mathcal A(\mu))]}{\operatorname{OPT}(\mu)}.\)
At profiles with zero optimum, both ratios are assigned \(1\). Taking infima over \(\mathcal P_{\tau,L}\) therefore yields
\(\displaystyle r_{\tau,L}(\mathcal T(\mathcal A))\ge r_{\tau,L}(\mathcal A).\)
Thus loss factor \(1\) is achievable uniformly for every admissible constraint and oracle. Since the stipulated range of loss factors starts at \(1\), it is optimal.
The cited finite-society lower bound does not contradict this conclusion: its welfare constructions use feasibility constraints asymmetric across agents. Here relabeling invariance permits pooling, and the tagged agent’s report change leaves the background profile fixed. [Chawla–Immorlica–Lucier, “On the Limits of Black-Box Reductions in Mechanism Design,” p. 3](https://pages.cs.wisc.edu/~shuchi/papers/black-box.pdf)
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed loss factor \(\lambda(m,\tau,L)=1\) under its explicitly stated Lebesgue support-profile interpretation. The pooling argument, welfare calculation, monotonicity guarantee, and polynomial complexity bound are sound. There is one minor clarification concerning the underlying atomless probability space.
The prover explicitly represents the society by the Lebesgue unit interval, partitioned into report classes of the prescribed masses. This is the natural interpretation of the support-input model: the input specifies masses and types, without additional structure distinguishing agents.
Minor issue: Atomlessness alone, for an arbitrary probability space, does not imply that the space is isomorphic to the Lebesgue interval or that arbitrary equal-mass pieces can be interchanged by measure-preserving automorphisms. The prover’s opening paragraph therefore specifies a natural interpretation rather than deriving it from atomlessness alone.
Minimum clarification: State that the intended society is a standard atomless probability space, understood up to null sets, or explicitly adopt the Lebesgue support-profile convention as part of the model. Under the intended reading prescribed by USER_TASK, this is a minor scope clarification.
The pooling argument is valid under that interpretation.
\[ \frac{1}{K}\sum_{\theta\in B}N\mu_\theta x_\theta = \frac{\sum_{\theta\in B}\mu_\theta x_\theta}{M_B}. \]
This establishes membership of the pooled vector in \(\mathcal F(\mu)\), without requiring downward closure. The witness lottery need not be supplied by the oracle: the transformation is required to return a feasible probability vector, and the construction proves that such a lottery exists.
The potentially enormous \(N\) causes no computational problem because the transformation does not construct the witness.
Every block has positive mass, so all divisions are defined. Starting from singleton blocks, adjacent merges preserve contiguity and keep the current probability constant within each block.
Each merge reduces the block count by one. Consequently, there are at most \(t-1\) merges. A direct implementation that scans for adjacent inversions has polynomial running time.
When no adjacent inversion remains, the block probabilities form a nondecreasing sequence. This gives the required ordering on the positive-mass support. The argument also covers \(t=1\), when no merge is necessary.
The absent-coordinate completion is well-defined because total mass is \(1\), so the support is nonempty.
Assigning \(0\) below the smallest support type and otherwise copying the largest support type below the coordinate preserves monotonicity, including gaps within the support and coordinates above its maximum. All probabilities remain in \([0,1]\).
The task explicitly exempts zero-mass coordinates from feasibility restrictions, so these assignments preserve feasibility.
The output is monotone on every execution. Taking expectations therefore gives the required inequalities. Because a tagged report change leaves \(\mu\) fixed, no additional consistency argument between different background profiles is needed.
The displayed subtraction is correct. For a merged pair, the welfare difference is
\[
\frac{M_BM_C}{M_B+M_C}(p_B-p_C)(v_C-v_B).
\]
All masses are positive. Contiguity and strict ordering of the support types imply \(v_B<v_C\). The merge condition gives \(p_B>p_C\). Thus every actual merge strictly increases welfare.
With no merges, welfare is unchanged. Absent coordinates carry zero welfare weight. The resulting pointwise welfare inequality is therefore valid.
The transformation makes one query at the input profile, satisfying both the query-count and query-encoding requirements.
Maintaining block masses and service masses as sums of the original rational quantities avoids uncontrolled growth from recursively nested expressions. Products of denominators have bit length equal to the sum of their bit lengths; numerators and subsequent ratios likewise have polynomial length. Rational comparisons, additions, divisions, and sorting can consequently be performed in polynomial time given the stipulated polynomial reply-length bound.
No feasibility description or feasibility-oracle access is used.
For positive optimum, division preserves the pointwise welfare inequality. Expectations exist because all coordinates lie in \([0,1]\) and the domain is finite.
An attained optimum is unnecessary: the argument only uses the numerical supremum in the denominator. At zero optimum, the task assigns both ratios \(1\).
Taking infima over the same profile class preserves the inequality, proving
\[
r_{\tau,L}(\mathcal T(\mathcal A))\geq r_{\tau,L}(\mathcal A).
\]
Since the allowed loss factors start at \(1\), establishing achievability of \(1\) establishes optimality.
The comparison is accurate. The cited paper explicitly describes its constructions as using feasibility constraints asymmetric across agents; its welfare construction also uses nonbinary allocation amounts. This supports the claim that its lower bound does not contradict the present argument. No theorem from that paper is needed for the pooling proof. [Chawla–Immorlica–Lucier, PDF page 3 and Section 3.1](https://pages.cs.wisc.edu/~shuchi/papers/black-box.pdf)
⟨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.