Answer: A polynomial-time ex-post IC and IR direct mechanism achieves exact welfare optimality, hence the requested \(3.31543\)-approximation.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor agents with SOS valuations, there is a polynomial time, ex-post IC & IR mechanism that gives 3.31543-approximation to the optimal welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational finite-support society \(\mu\) over bidder classes \(k\) and finite signals \(s\), with nonnegative monotone anonymous values \(V_k(z;\nu)\) satisfying measure-SOS, can one compute in time polynomial in the support size, type descriptions, and input bit length a direct rate mechanism \(a_k(r;\nu),p_k(r;\nu)\) such that, for every background society \(\nu\), class \(k\), true signal \(z\), and report \(r\), truthful utility satisfies \(a_k(z;\nu)V_k(z;\nu)-p_k(z;\nu)\ge a_k(r;\nu)V_k(z;\nu)-p_k(r;\nu)\) and is nonnegative, feasibility satisfies \(\sum_{k,r}\nu_{k,r}a_k(r;\nu)\le 1\), and welfare satisfies \(\sum_{k,s}\mu_{k,s}a_k(s;\mu)V_k(s;\mu)\ge \max_{(k,s):\mu_{k,s}>0}V_k(s;\mu)/3.31543\)? The allocation and payment rates are the high-multiplicity normalization of per-agent probabilities and payments, with utilities scaled by the same factor.
An atomless population has total mass \(1\), public roles \(r\in\{1,\ldots,m\}\), and private signals in explicitly listed finite sets \(S_r\subseteq\mathbb Q_{\ge0}\) containing \(0\). Let \(K=\sum_r|S_r|\). Each agent can receive either zero or one identical unit; supply is a fixed rational density \(\rho>0\).
A society is given by its support: the list of the \(\tau\) types \(t=(r,s)\) with positive mass \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Reported distributions \(\nu\) preserve public role masses.
Public valuations \(V_r(s;\nu)\) are nonnegative, strictly increasing in \(s\), and exactly evaluable as binary rationals; let \(C\) bound evaluation cost and \(L\) denote input bit length.
Distributional monotonicity and SOS mean the following: for every finite list of roles \(r_j\) and positive rational weights \(w_j\) summing to \(1\) with the prescribed role masses, the lift \(F(z)=V_r(z_0;\sum_{j=1}^Nw_j\delta_{(r_j,z_j)})\), where \(\delta_t\) is unit mass at type \(t\), is weakly increasing in every coordinate and satisfies \(F(z'_{-i},b)-F(z'_{-i},a)\le F(z_{-i},b)-F(z_{-i},a)\) whenever \(z'_{-i}\ge z_{-i}\) coordinatewise and \(b\ge a\), for every coordinate \(i\), including \(0\).
A direct mechanism specifies allocation probabilities \(x_r(a;\nu)\in[0,1]\) and expected payments \(p_r(a;\nu)\in\mathbb R\) for every permissible report, including types absent from the support. A unilateral report changes neither the agent's public role nor the aggregate \(\nu\).
Ex-post IC requires \(x_r(s;\nu)V_r(s;\nu)-p_r(s;\nu)\ge x_r(a;\nu)V_r(s;\nu)-p_r(a;\nu)\) for every \(r,s,a,\nu\); ex-post IR requires the truthful utility to be nonnegative. Both use expectations over mechanism randomness.
Feasibility requires an implementation by measurable sets of recipients of mass at most \(\rho\) in every realization, with the stated individual allocation probabilities. At truth, \(y_t=x_r(s;\mu)\), and \(\mathrm{OPT}_\rho(\mu)=\max\{\sum_t\mu_ty_tV_r(s;\mu):0\le y_t\le1,\ \sum_t\mu_ty_t\le\rho\}\).
Can an ex-post IC and IR direct mechanism be constructed and evaluated in time polynomial in \(m,\tau,K,L,C\), guaranteeing \(\sum_t\mu_tx_r(s;\mu)V_r(s;\mu)\ge\mathrm{OPT}_\rho(\mu)/3.31543\) for every admissible society, or is this approximation guarantee unattainable in polynomial time?
For finite single-item auctions with public SOS valuations, a polynomial-time ex-post IC and IR mechanism achieves a \(3.31543\)-approximation ([source](https://arxiv.org/pdf/2210.06507)).
For binary signals, a tight \(2\)-approximation exists in the discrete model ([source](https://arxiv.org/abs/2107.08806)). No result settling the specified atomless model was located.
The guarantee is attainable in polynomial time. In fact, the specified atomless model admits a welfare-optimal ex-post IC and IR mechanism.
The decisive premise is that a unilateral report leaves the aggregate distribution \(\nu\) unchanged. Thus an agent cannot change a price computed from \(\nu\). Distributional monotonicity and SOS are unnecessary for this construction.
Fix a reported distribution \(\nu\). Write its positive-mass support as \(T_\nu\), and define \(v_t=V_r(s;\nu)\) for \(t=(r,s)\).
If \(\rho\geq1\), allocate to every agent and charge zero. This is feasible, IC, IR, and optimal because all valuations are nonnegative.
Henceforth suppose \(0<\rho<1\). Sort the supported types in nonincreasing order of \(v_t\). Let \(c\) be the value of the first type at which cumulative mass reaches or exceeds \(\rho\). Define
\(H=\sum_{t\in T_\nu:\,v_t>c}\nu_t,\qquad B=\sum_{t\in T_\nu:\,v_t=c}\nu_t,\qquad q=\dfrac{\rho-H}{B}.\)
The choice of \(c\) implies \(H<\rho\leq H+B\). Consequently, \(B>0\) and \(0<q\leq1\).
For every permissible report, including reports absent from \(T_\nu\), set
\(x_r(a;\nu)= \begin{cases} 1,&V_r(a;\nu)>c,\\ q,&V_r(a;\nu)=c,\\ 0,&V_r(a;\nu)<c, \end{cases} \qquad p_r(a;\nu)=c\,x_r(a;\nu).\)
The same cutoff and tie probability apply to all roles. The expected allocated mass is exactly
\(\sum_{t\in T_\nu}\nu_t x_t=H+qB=\rho.\)
Fix any \(\nu\), role \(r\), true signal \(s\), and alternative report \(a\). Put \(v=V_r(s;\nu)\).
By the stipulated atomless deviation rule, reporting \(a\) leaves \(\nu\), and hence \(c\) and \(q\), unchanged. The agent’s expected utility from report \(a\) is therefore
\(x_r(a;\nu)v-p_r(a;\nu)=x_r(a;\nu)(v-c).\)
There are three cases.
Thus truthful reporting weakly dominates every alternative report, and truthful utility is nonnegative. This proves ex-post IC and IR for every permissible report and every \(\nu\).
In particular, absent reports cause no difficulty: their allocations and payments are explicitly defined by the same price rule.
We now prove the required implementation by measurable recipient sets.
Let \((A,\mathcal A,\lambda)\) be the atomless population space, with \(\lambda(A)=1\). At the reported profile, let \(A_>\) and \(A_=\) be the measurable sets of agents whose reported valuations exceed and equal \(c\), respectively. Their masses are \(H\) and \(B\).
We use the standard atomless divisibility theorem: if a finite measure is atomless, every measurable set of mass \(b\) has a measurable subset of any prescribed mass in \([0,b]\). The restriction of \(\lambda\) to \(A_=\) satisfies these hypotheses.
Repeatedly bisecting \(A_=\) into equal-mass measurable subsets produces a measurable function \(h:A_=\to[0,1)\) with uniform pushforward under normalized measure. Explicitly, the successive binary partition labels define the binary digits of \(h\); every dyadic interval of length \(2^{-n}\) has preimage mass \(B2^{-n}\), which determines the uniform distribution. Exceptional binary-expansion points form a null set and can be assigned arbitrary values.
Draw \(U\) uniformly from \([0,1)\), and choose the recipient set
\(R_U=A_>\ \cup\ \{i\in A_=:(h(i)+U)\bmod1<q\}.\)
For every fixed realization \(U=u\), rotation preserves uniform measure, so
\(\lambda(R_u)=H+qB=\rho.\)
For every individual \(i\in A_=\), the random variable \((h(i)+U)\bmod1\) is uniform. Hence that individual receives a unit with probability \(q\). Agents in \(A_>\) receive with probability \(1\), and all remaining agents receive with probability \(0\).
Charge each recipient \(c\) and each nonrecipient zero. Expected payments are exactly \(c\,x_r(a;\nu)\).
This implements the stated probabilities and payments while respecting supply in every realization.
For rational input, the lottery also has a compact finite description. Write \(q=u/d\) with integers \(0<u\leq d\). Draw \(J\) uniformly from \(\{0,\ldots,d-1\}\), and select a tied agent precisely when
\((\lfloor d\,h(i)\rfloor+J)\bmod d<u.\)
Each realization selects \(u\) equal-mass cells, and each individual is selected for exactly \(u\) of the \(d\) possible shifts. Thus the same feasibility and marginal-probability conclusions hold.
Evaluate the mechanism at truth, \(\nu=\mu\). Write \(v_t=V_r(s;\mu)\) and \(x_t=x_r(s;\mu)\).
Let \(z\) be any feasible allocation in the optimization defining \(\mathrm{OPT}_\rho(\mu)\). Then
\(\sum_t\mu_t(x_t-z_t)v_t = \sum_t\mu_t(x_t-z_t)(v_t-c) + c\left(\rho-\sum_t\mu_tz_t\right).\)
Every term on the right is nonnegative:
Therefore the mechanism’s welfare is at least that of every feasible \(z\). Its own allocation is feasible, so
\(\sum_t\mu_t x_r(s;\mu)V_r(s;\mu)=\mathrm{OPT}_\rho(\mu).\)
The requested approximation follows immediately.
On an explicitly encoded rational distribution:
At the given society, this requires at most \(K\) valuation evaluations and sorting \(\tau\) supported values. Rational comparisons, sums, and divisions have polynomial bit complexity: their operand lengths are polynomially bounded by the input length, the number of types, and the lengths of the exactly evaluated valuations. In the usual bit-cost model, those output lengths are bounded by the evaluation cost \(C\).
Consequently, construction and evaluation take time polynomial in \(m,\tau,K,L,C\). The mechanism is specified by one algorithm for all reported distributions; it requires no enumeration of possible distributions or individual agents.
In the cited finite-auction model, a bidder’s deviation changes the signal profile that determines valuations and allocations. [Lu, Sun, and Zhou’s formulation](https://arxiv.org/pdf/2210.06507) explicitly compares allocations at different signal profiles.
Here, the task explicitly fixes \(\nu\) during a unilateral deviation. That permits an endogenous market-clearing price to remain fixed throughout each agent’s IC comparison. The proof above establishes optimality directly under that premise.
⟨structured verdict parsed — rendered above⟩
The argument resolves the assigned task. Under the stipulated rule that a unilateral report leaves the aggregate distribution unchanged, the proposed mechanism is ex-post IC, ex-post IR, feasible in every realization, and exactly welfare-optimal. Its allocation and expected-payment rules have polynomial construction and evaluation cost. No major or minor issues were found.
For \(\rho\geq1\), allocating to everyone is feasible because total population mass is \(1\). Zero payments give IC and IR, and nonnegative valuations establish optimality.
For \(0<\rho<1\), the supported masses sum to \(1\), so the cutoff type exists. Choosing the first sorted type whose cumulative mass reaches \(\rho\) correctly gives
\[
H<\rho\leq H+B.
\]
Consequently, \(B>0\) and \(0<q\leq1\); the division defining \(q\) is valid.
Ties do not create ambiguity: \(H\) and \(B\) include all supported types strictly above and exactly at the cutoff, respectively. The allocation and payment formulas explicitly cover all permissible reports, including absent types and roles with zero reported mass.
The crucial hypothesis is explicitly supplied by the task: an individual’s report leaves \(\nu\) unchanged. Therefore both \(c\) and \(q\) remain fixed in every incentive comparison.
The utility calculation
\[
x_r(a;\nu)V_r(s;\nu)-p_r(a;\nu)
=x_r(a;\nu)(v-c)
\]
is correct. Each of the three cases establishes the required inequality for every alternative report:
Truthful utility is nonnegative throughout. These arguments also cover absent truthful types, \(c=0\), and \(q=1\). No distributional monotonicity or SOS assumption is used or needed.
The invoked divisibility theorem is stated with the needed hypotheses: a finite atomless measure admits measurable subsets of every intermediate mass. Restricting the population measure to the measurable tied set preserves atomlessness, and \(B>0\) permits normalization.
Repeated equal-mass bisection supplies the claimed measurable uniform coordinate. The dyadic-cell masses are consistent, and the binary-expansion exceptions have measure zero. Assigning arbitrary values on those exceptions preserves the uniform pushforward.
For each fixed rotation \(u\), the selected tied set is measurable and has mass \(qB\). Thus every realization has recipient mass
\[
H+qB=\rho.
\]
Separately, for every individual—including individuals in exceptional null sets—the random rotation gives allocation probability \(q\). The proof therefore establishes individual marginals, rather than only an almost-everywhere statement.
The rational finite lottery also checks out: its \(d\) cells each have mass \(B/d\), each shift selects exactly \(u\) cells, and each individual is selected under exactly \(u\) shifts. Recipient payments have the stated expectations.
The displayed welfare identity is correct because the constructed allocation uses total mass \(\rho\). Every summand has the asserted sign: above the cutoff, both factors are nonnegative; below it, both are nonpositive; at it, the product vanishes.
The remaining term is nonnegative because \(c\geq0\) and the competing allocation is feasible. Hence the constructed allocation weakly outperforms every feasible allocation in the task’s optimization problem. Its own feasibility establishes equality with \(\mathrm{OPT}_\rho(\mu)\), including cases with zero valuations.
On the rationally encoded society, supported valuation evaluations, sorting, rational arithmetic, and evaluation of all \(K\) permissible reports require polynomial time. In the stated bit-cost model, evaluation cost \(C\) bounds the lengths of explicitly returned rational valuations. Sums, products, and divisions in the construction retain polynomial bit length.
Other rational reported distributions can have support larger than \(\tau\), but their support is at most \(K\), which is already an allowed complexity parameter.
The continuum implementation is an existence argument, not an algorithm enumerating recipients. This matches the task’s feasibility requirement, which asks for an implementation by measurable recipient sets. The polynomial algorithm specifies and evaluates the direct mechanism’s allocation probabilities and expected payments.
The cited paper’s ex-post IC definition compares allocations and payments at signal profiles differing in the deviating bidder’s coordinate. The prover’s description of that distinction is accurate. See Definition 2 in [Lu, Sun, and Zhou](https://arxiv.org/pdf/2210.06507). The present proof relies on the different deviation rule expressly imposed by the task.
No additional clarification or repair is required.
⟨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.