Answer: Yes. A polynomial-time construction with polynomial-size explicit representation achieves \(\operatorname{OPT}(\sigma)\) at every state, and therefore a \(2\)-approximation.
Theorem 1 — class: algorithmic
Given a finite type set \(T\), rational masses \(\mu_t\), and rational piecewise-polynomial valuations \(V_t(b,\sigma)\) satisfying the paper’s monotonicity and SOS conditions on finite replications, can one construct in time polynomial in \(\tau=|T|\) and the input length finite piecewise-rational descriptions of allocation and payment intensities \(a_t(b,\sigma)\) and \(p_t(b,\sigma)\)? Here \(b\in\{0,1\}\) is the tagged agent’s signal and \(\sigma_t\in[0,\mu_t]\) is the mass of other type-\(t\) agents with signal \(1\); intensities may grow as a signal group’s mass approaches zero. For every state \(\sigma\), require feasibility \(\sum_{t,b}\mu_{t,b}a_t(b,\sigma)\leq 1\), ex-post IC and IR using the same other-agent state under a deviation, and welfare \(\sum_{t,b}\mu_{t,b}a_t(b,\sigma)V_t(b,\sigma)\geq\tfrac12\max_{t,b:\mu_{t,b}>0}V_t(b,\sigma)\), where \(\mu_{t,1}=\sigma_t\) and \(\mu_{t,0}=\mu_t-\sigma_t\).
Consider a single-item auction, so \(m=1\). A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each type has a publicly known valuation \(V_t:\{0,1\}\times D\to\mathbb R_{\geq0}\), where \(D=\prod_u[0,\mu_u]\); the first argument is its private binary signal, and \(\sigma\in D\) records other agents’ masses with signal \(1\). Values are weakly increasing in every mass coordinate and satisfy \(V_t(1,\sigma)>V_t(0,\sigma)\).
The SOS promise means the following: for every positive integer \(N\) with all \(N\mu_u\) integral, form disjoint groups \(E_{N,u}\) of \(N\mu_u\) bidders. For each \(i\in E_{N,t}\), the set function \(v_i(S)=V_t(\mathbf1_{i\in S},(|(S\setminus\{i\})\cap E_{N,u}|/N)_{u\in T})\) is monotone and submodular on \(\bigcup_uE_{N,u}\).
Input valuations are piecewise polynomial on explicitly listed semialgebraic partitions of \(D\). Cells use Boolean formulas of rational polynomial sign conditions; polynomials use sparse monomial lists with binary coefficients and exponents. Let \(L\) be the total input bit length; these conditions are promises.
Seek allocation intensities \(a_t(b,\sigma)\geq0\) and expected payment intensities \(p_t(b,\sigma)\in\mathbb R\), described by explicit finite partitions of the same kind with rational functions on cells. Denominators must be nonzero on their cells, including boundary cells. Intensities are finite at every state but may be unbounded near a vanishing signal group.
A single agent’s report leaves \(\sigma\) unchanged. Ex-post IC and IR require, for every \(t,\sigma,b,c\), \(a_t(b,\sigma)V_t(b,\sigma)-p_t(b,\sigma)\geq a_t(c,\sigma)V_t(b,\sigma)-p_t(c,\sigma)\) and \(a_t(b,\sigma)V_t(b,\sigma)-p_t(b,\sigma)\geq0\), including counterfactual reports into zero-mass groups.
Write \(\mu_{t,1}=\sigma_t\) and \(\mu_{t,0}=\mu_t-\sigma_t\). At every real state \(\sigma\in D\), require \(\sum_{t,b}\mu_{t,b}a_t(b,\sigma)\leq1\) and \(\sum_{t,b}\mu_{t,b}a_t(b,\sigma)V_t(b,\sigma)\geq\tfrac12\max_{t,b:\mu_{t,b}>0}V_t(b,\sigma)\); zero-mass groups contribute zero.
Can such an ex-post IC-IR mechanism achieving a \(2\)-approximation at every state be constructed for every promised input in time polynomial in \(m,\tau,L\), including its explicit output description?
For finitely many bidders with binary signals and SOS values, a randomized ex-post IC-IR \(2\)-approximation exists; its construction is polynomial in the explicit valuation-table input size. [Amer–Talgam-Cohen](https://arxiv.org/pdf/2107.08806)
No result settling this precise mass model and explicit representation requirement was located.
Yes. Under the stated convention that an individual report leaves \(\sigma\) unchanged, a polynomial-time construction achieves exact optimal welfare at every state. The SOS promise is unnecessary for this construction.
The two features that make this possible are the unchanged-state IC condition and the permission for intensities to grow without bound near a vanishing signal group. All intensities below are nevertheless finite at every state.
Fix a type \(t\) and a state \(\sigma\). Write \(v_b=V_t(b,\sigma)\), so \(v_1>v_0\).
Adding the two IC inequalities gives
\[ (a_1-a_0)(v_1-v_0)\geq 0. \]
Consequently, IC requires \(a_1\geq a_0\). Conversely, any nonnegative allocations satisfying this inequality admit the payments
\[ p_0=a_0v_0,\qquad p_1=a_1v_0. \]
To verify this directly:
Thus truthful reporting maximizes utility, and truthful utility is nonnegative. This verification also applies to reports into zero-mass groups.
It therefore suffices to construct allocations satisfying \(a_t(1,\sigma)\geq a_t(0,\sigma)\).
Order the types as \(1,\ldots,\tau\). Define
\[ W_t(\sigma)= \begin{cases} V_t(0,\sigma),&\sigma_t=0,\\ V_t(1,\sigma),&\sigma_t>0. \end{cases} \]
This is the maximum value among the present signal groups of type \(t\):
Hence, writing \(\operatorname{OPT}(\sigma)\) for the benchmark in the question,
\[ \operatorname{OPT}(\sigma)=\max_{t\in T}W_t(\sigma). \]
Let \(w(\sigma)\) be the smallest index attaining this maximum.
For every type \(t\neq w(\sigma)\), set both allocation and payment intensities to zero.
For the winning type \(t=w(\sigma)\), use the following rules.
If \(\sigma_t>0\), set
\[ a_t(0,\sigma)=0,\qquad a_t(1,\sigma)=\frac{1}{\sigma_t}, \]
\[ p_t(0,\sigma)=0,\qquad p_t(1,\sigma)=\frac{V_t(0,\sigma)}{\sigma_t}. \]
If \(\sigma_t=0\), set
\[ a_t(0,\sigma)=a_t(1,\sigma)=\frac{1}{\mu_t}, \]
\[ p_t(0,\sigma)=p_t(1,\sigma)=\frac{V_t(0,\sigma)}{\mu_t}. \]
In every case, allocations are nonnegative, \(a_t(1,\sigma)\geq a_t(0,\sigma)\), and \(p_t(b,\sigma)=a_t(b,\sigma)V_t(0,\sigma)\). Section 1 therefore proves ex-post IC and IR for every type, state, and counterfactual report.
If the winning type satisfies \(\sigma_t>0\), its signal-\(1\) group consumes total allocation
\[ \mu_{t,1}a_t(1,\sigma) =\sigma_t\frac{1}{\sigma_t}=1. \]
Every other present group receives zero allocation. Welfare is therefore
\[ V_t(1,\sigma)=W_t(\sigma)=\operatorname{OPT}(\sigma). \]
If the winning type satisfies \(\sigma_t=0\), its signal-\(0\) group consumes total allocation
\[ \mu_{t,0}a_t(0,\sigma) =\mu_t\frac{1}{\mu_t}=1. \]
Its counterfactual signal-\(1\) group has zero mass and contributes zero. Welfare is
\[ V_t(0,\sigma)=W_t(\sigma)=\operatorname{OPT}(\sigma). \]
Thus feasibility holds with equality, and the mechanism achieves exact welfare at every real state.
All intensities are finite: the denominator \(\sigma_t\) is used only where \(\sigma_t>0\), and \(\mu_t>0\) by hypothesis.
The remaining issue is representing the winner regions and payments without enumerating all combinations of input cells.
For each \(t,b\), write the supplied piecewise-polynomial description as cells \(F_{tbj}\) with polynomial values \(P_{tbj}\). All formulas below are interpreted on \(D\).
A piecewise description of \(W_t\) consists of the branches
\[ F_{t0j}\land(\sigma_t=0), \quad\text{with polynomial }P_{t0j}, \]
and
\[ F_{t1j}\land(\sigma_t>0), \quad\text{with polynomial }P_{t1j}. \]
Denote these branches by \((G_{ti},Q_{ti})\). They are disjoint and cover \(D\).
For distinct types \(t,u\) and either comparison relation \(\bowtie\in\{>,\geq\}\), define the Boolean formula
\[ \mathsf C_{tu}^{\bowtie} = \bigvee_{i,j} \left( G_{ti}\land G_{uj}\land (Q_{ti}-Q_{uj}\bowtie 0) \right). \]
At each state, exactly one branch for each type applies. Therefore this formula holds exactly when \(W_t(\sigma)\bowtie W_u(\sigma)\).
The region where type \(t\) wins is consequently described by
\[ \mathsf R_t = \left(\bigwedge_{u<t}\mathsf C_{tu}^{>}\right) \land \left(\bigwedge_{u>t}\mathsf C_{tu}^{\geq}\right). \]
The strict comparisons against smaller indices implement the specified tie-breaking. The regions \(\mathsf R_t\) are disjoint and cover \(D\).
For each input cell \(F_{t0j}\), output the two case formulas
\[ \mathsf R_t\land F_{t0j}\land(\sigma_t=0), \]
\[ \mathsf R_t\land F_{t0j}\land(\sigma_t>0). \]
These cases are mutually disjoint and cover \(D\). Empty cases impose no conditions and can be retained as vacuous branches in the formula-based description; their nonempty realizations form the partition.
On the first case, specify the winning type’s allocations as \(1/\mu_t\) and its payments as \(P_{t0j}/\mu_t\). On the second case, specify its allocations as \(0,1/\sigma_t\) and its payments as \(0,P_{t0j}/\sigma_t\). All other types’ outputs are zero.
Every output is thus a rational function on its cell. Every denominator is nonzero throughout its cell, including its included boundary points.
Let \(K\) be the total number of branches used to describe all the \(W_t\). The explicit input encoding gives \(K=O(L)\).
Across all ordered type pairs, the comparison formulas contain at most \(K^2\) branch-pair disjuncts. Each disjunct copies input formulas and compares a difference of two input polynomials. Sparse subtraction has polynomial bit complexity: it merges the monomial lists, retains binary exponents, and performs rational coefficient arithmetic of polynomial bit length.
There are at most twice as many output cases as input cells for the signal-\(0\) valuations. Expanding all copied formulas, and listing all allocation and payment functions on every case, therefore still uses polynomially many bits and polynomial construction time in \(\tau,L\).
The construction performs only symbolic operations. It does not require evaluating polynomial signs at arbitrary real states or testing semialgebraic feasibility.
The stated mass model admits a polynomial-time, explicitly represented ex-post IC-IR mechanism achieving exact optimal welfare, and hence the requested \(2\)-approximation. Its IC proof is pointwise because an individual report leaves \(\sigma\) unchanged.
⟨structured verdict parsed — rendered above⟩
The construction is mathematically sound under the stated unchanged-state IC condition. It achieves exact optimal welfare, and its explicit description has polynomial size. The only minor ambiguity concerns whether the output encoding permits empty cell formulas.
Fixing \(t,\sigma\), adding the two truthful-report inequalities indeed gives
\[
(a_1-a_0)(v_1-v_0)\geq 0.
\]
Since the task promises \(v_1>v_0\), this implies \(a_1\geq a_0\).
For the proposed payments \(p_b=a_bv_0\), a true signal-\(0\) bidder receives utility zero under either report. A true signal-\(1\) bidder receives utility \(a_b(v_1-v_0)\) when reporting \(b\). Nonnegative allocations and \(a_1\geq a_0\) therefore establish both IC and IR.
This argument checks all four combinations of true signal and report. It also covers zero-mass groups: the task requires the inequalities pointwise, and none of these calculations requires the reporting group to have positive mass.
The definition of \(W_t\) is correct. When \(\sigma_t=0\), the signal-\(0\) group has mass \(\mu_t>0\), while the signal-\(1\) group is absent. When \(\sigma_t>0\), the signal-\(1\) group is present and has strictly greater value than signal \(0\), whether or not signal \(0\) is also present.
Consequently,
\[
\operatorname{OPT}(\sigma)=\max_t W_t(\sigma).
\]
The maximum exists because the support is finite and nonempty. Selecting its smallest-index maximizer is well-defined, including at ties.
Nonwinning types have zero allocations and payments, so their IC and IR inequalities hold.
For a winning type with \(\sigma_t>0\), the allocations satisfy
\[
a_t(1,\sigma)=1/\sigma_t\geq a_t(0,\sigma)=0.
\]
For a winning type with \(\sigma_t=0\), both allocations equal \(1/\mu_t\). In both cases, the payments have precisely the form verified in step 1.
Thus the allocation rule’s dependence on the winning region causes no IC problem: an individual report leaves \(\sigma\), and hence the winning region, unchanged by assumption.
When the winning type has \(\sigma_t>0\), its signal-\(1\) group consumes allocation \(\sigma_t/\sigma_t=1\), and all other present groups consume zero. Welfare equals \(V_t(1,\sigma)=\operatorname{OPT}(\sigma)\).
When \(\sigma_t=0\), its signal-\(0\) group consumes allocation \(\mu_t/\mu_t=1\). The positive counterfactual signal-\(1\) intensity contributes zero because that group has zero mass. Welfare equals \(V_t(0,\sigma)=\operatorname{OPT}(\sigma)\).
The other endpoint, \(\sigma_t=\mu_t\), is covered by the positive-\(\sigma_t\) branch. Every denominator is nonzero wherever used. Values and intensities are finite at every state; possible divergence as \(\sigma_t\) approaches zero is expressly permitted.
These calculations establish exact welfare, which implies the requested approximation. No SOS property is used or needed for this argument.
The branches describing each \(W_t\) are disjoint and exhaustive because the input cells form partitions and the conditions \(\sigma_t=0\) and \(\sigma_t>0\) partition its allowed coordinate range.
At any state, exactly one branch for each compared type applies. Thus each comparison formula correctly tests the corresponding values of \(W_t\) and \(W_u\).
The winning-region formula requires strict superiority over smaller indices and weak superiority over larger indices. This correctly implements the stated tie-breaking and makes the winning regions disjoint and exhaustive.
Refining each winning region by the winning type’s signal-\(0\) input cells supplies the polynomial needed for its payments. The resulting nonempty cases form a common partition for all outputs, with the claimed rational functions.
Minor issue: The write-up retains empty case formulas. Under the usual set-theoretic definition, a partition contains only nonempty sets. The task does not explicitly specify whether its encoding accepts empty guards. The minimum clarification is to state that formula-based output descriptions permit vacuous branches, with their nonempty realizations constituting the partition. The formulas already establish disjointness and coverage; no mathematical argument is missing here.
The number \(K\) of branches is bounded by the explicit input length. Across ordered type pairs, the number of branch-pair disjuncts is at most \(K^2\). Copying input formulas introduces only polynomial growth.
Sparse polynomial subtraction preserves polynomial description size: the number of monomials cannot exceed the combined input counts, exponent encodings remain binary, and subtracting rational coefficients has polynomial bit complexity.
There are only polynomially many output cases. Repeating the expanded winning-region formulas and listing all types’ outputs on each case multiplies polynomial bounds by polynomial factors. Consequently, the explicit output and its construction remain polynomial in \(\tau,L\), with \(m=1\).
No sign evaluation or semialgebraic feasibility test is needed, subject to the empty-guard convention above.
The requested construction is established in substance. The only requested clarification concerns the syntax of the explicit partition representation.
⟨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.