Answer: Yes. A single mechanism evaluable in polynomial time attains \(EFO_\kappa(\mu)\) exactly, hence guarantees the requested factor \(12.5\).
Theorem 6.4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn multi-unit environments, RSEM is a 12.5-approximation to the envy-free bench- mark EFO(2)(v). Notice that this mechanism can easily be generalized to other downward-closed environments. It remains incentive compatible for these environments because it is essentially an ironed virtual surplus optimizer on the set M, and furthermore, it is incentive compatible even if the permutation that assigns agents to the set system is fixed.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational population distribution \(\mu\) over a finite value set \(V\) and per-capita supply \(\kappa\), find an algorithm that outputs, for every reported population measure \(\nu\), an anonymous treatment schedule \(x_\nu(v),p_\nu(v)\) that is feasible and truthful for every infinitesimal agent, and maximizes revenue \(\sum_{v\in V}\mu_v p_\mu(v)\) relative to \(EFO_\kappa(\mu)\).
Let \(V\subseteq\mathbb Q_{\geq0}\) be a nonempty value domain of size \(m\), and let \(\kappa\in\mathbb Q\cap(0,1]\) be per-capita supply of a unit-demand service in an atomless population of total mass one.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length, including values and supply.
A single anonymous mechanism takes any rational reported probability measure \(\nu\) on \(V\) and returns treatments \((x_\nu(v),p_\nu(v))\) for every \(v\in V\), including absent types; these are service probabilities and expected payments.
For every \(\nu\), require \(0\leq x_\nu(v)\leq1\), \(p_\nu(v)\geq0\), \(\sum_v\nu_vx_\nu(v)\leq\kappa\), and individual rationality \(vx_\nu(v)-p_\nu(v)\geq0\).
An individual report does not change \(\nu\); truthfulness means \(vx_\nu(v)-p_\nu(v)\geq vx_\nu(w)-p_\nu(w)\) for every \(\nu\) and \(v,w\in V\). Indifference permits truthful reporting.
Define \(EFO_\kappa(\mu)\) as the maximum of \(\sum_v\mu_vp(v)\) over anonymous feasible, nonnegative-payment, individually rational treatments satisfying \(vx(v)-p(v)\geq vx(w)-p(w)\) for all positive-mass types \(v,w\).
Does a single mechanism, evaluable in time polynomial in \(m,\tau,L\), guarantee \(\sum_v\mu_vp_\mu(v)\geq EFO_\kappa(\mu)/12.5\) for every rational society \(\mu\) and supply \(\kappa\), or is this approximation guarantee unattainable in polynomial time?
For finite multi-unit populations, random sampling empirical Myerson is truthful and achieves expected revenue at least \(EFO^{(2)}(\mathbf v)/12.5\), where \(EFO^{(2)}\) replaces the highest value by the second-highest before optimizing envy-free revenue ([Devanur–Hartline–Yan](https://arxiv.org/pdf/1212.3741)).
In large economies, envy freedom and type measurability characterize robust approximate implementation under private values, excludability, and a convergent allocation space; this is an asymptotic implementation result, not the stated computational approximation guarantee ([Jackson–Kremer](https://web.stanford.edu/~jacksonm/envy.pdf)).
Yes. Under the stated definition of truthfulness, a single polynomial-time mechanism can attain the benchmark exactly: for every rational society \(\mu\),
\( \sum_{v\in V}\mu_vp_\mu(v)=EFO_\kappa(\mu). \)
Thus the requested approximation factor \(12.5\) is attainable. The essential premise is that an individual report leaves the reported measure unchanged.
We prove this by reducing the benchmark to mixtures of posted-price treatments and giving an explicit polynomial-time optimization algorithm.
Fix a reported probability measure \(\nu\). Write its positive-mass support in increasing order as
\( a_1<a_2<\cdots<a_t, \)
with masses \(b_i=\nu_{a_i}>0\), where \(\sum_{i=1}^t b_i=1\). Define the tail masses
\( Q_j=\sum_{i=j}^t b_i. \)
Consider any treatment feasible for the envy-free benchmark. On the support, denote its allocations and payments by \(x_i,p_i\), and its utilities by \(u_i=a_ix_i-p_i\).
For \(i<j\), the two envy-free inequalities imply
\( a_ix_i-p_i\geq a_ix_j-p_j,\qquad a_jx_j-p_j\geq a_jx_i-p_i. \)
Adding them gives \((a_j-a_i)(x_j-x_i)\geq0\). Because \(a_j>a_i\), allocations are nondecreasing:
\( 0\leq x_1\leq\cdots\leq x_t\leq1. \)
Set \(x_0=0\) and \(d_j=x_j-x_{j-1}\). Then
\( d_j\geq0,\qquad \sum_{j=1}^t d_j=x_t\leq1. \)
Individual rationality gives \(u_1\geq0\). For each \(i\geq2\), type \(a_i\)'s constraint against reporting \(a_{i-1}\) gives
\( u_i\geq u_{i-1}+(a_i-a_{i-1})x_{i-1}. \)
Iterating,
\( u_i\geq\sum_{h=1}^{i-1}(a_{h+1}-a_h)x_h. \)
Consequently, telescoping yields
\( p_i\leq a_ix_i-\sum_{h=1}^{i-1}(a_{h+1}-a_h)x_h =\sum_{j=1}^i a_jd_j. \)
Multiplying by masses and exchanging the finite sums establishes the revenue bound
\( \sum_{i=1}^t b_ip_i \leq\sum_{j=1}^t a_jQ_jd_j. \)
Likewise, the supply constraint becomes
\( \sum_{i=1}^t b_ix_i =\sum_{j=1}^t Q_jd_j \leq\kappa. \)
Therefore every benchmark treatment has revenue at most the optimum of the following linear program:
\( \text{maximize }\sum_{j=1}^t a_jQ_jd_j \quad\text{subject to}\quad d_j\geq0,\quad \sum_{j=1}^t d_j\leq1,\quad \sum_{j=1}^t Q_jd_j\leq\kappa. \)
For any feasible vector \(d\) in this program, define treatments for every \(v\in V\), including absent types, by
\( x_\nu(v)=\sum_{j=1}^t d_j\mathbf1_{\{v\geq a_j\}}, \qquad p_\nu(v)=\sum_{j=1}^t a_jd_j\mathbf1_{\{v\geq a_j\}}. \)
These are weighted mixtures of posted-price treatments.
Since all \(d_j,a_j\) are nonnegative and \(\sum_jd_j\leq1\), allocations lie in \([0,1]\) and payments are nonnegative. Truthful utility is
\( vx_\nu(v)-p_\nu(v) =\sum_{j=1}^t d_j\max\{v-a_j,0\}\geq0, \)
so individual rationality holds for all types.
For any true value \(v\) and report \(w\), each threshold satisfies
\( (v-a_j)\mathbf1_{\{v\geq a_j\}} \geq (v-a_j)\mathbf1_{\{w\geq a_j\}}. \)
Indeed, when \(v-a_j\) is positive, truthful reporting selects the positive contribution; when it is negative, truthful reporting avoids it; when it is zero, either choice gives zero. Multiplication by \(d_j\geq0\) and summation prove
\( vx_\nu(v)-p_\nu(v) \geq vx_\nu(w)-p_\nu(w). \)
This establishes truthfulness on the entire domain, including absent types.
Supply and revenue under \(\nu\) are respectively
\( \sum_{v\in V}\nu_vx_\nu(v)=\sum_{j=1}^t Q_jd_j\leq\kappa, \)
and
\( \sum_{v\in V}\nu_vp_\nu(v)=\sum_{j=1}^t a_jQ_jd_j. \)
Thus every feasible vector attains its linear-program objective through an admissible globally truthful treatment. Combined with the upper bound, this proves that the program's optimum is exactly \(EFO_\kappa(\nu)\).
We next solve the program explicitly.
Introduce a no-service option indexed by \(0\), with \(Q_0=R_0=0\). For \(j\geq1\), let \(R_j=a_jQ_j\). Set
\( \alpha_j=d_j\quad(j\geq1),\qquad \alpha_0=1-\sum_{j=1}^t d_j. \)
The optimization becomes
\( \text{maximize }\sum_{j=0}^t R_j\alpha_j \quad\text{subject to}\quad \alpha_j\geq0,\quad \sum_{j=0}^t\alpha_j=1,\quad \sum_{j=0}^tQ_j\alpha_j\leq\kappa. \)
Its feasible set is nonempty and compact, so an optimum exists. Choose an optimum having the smallest number of positive coordinates.
It has at most two positive coordinates. Otherwise, there is a nonzero vector \(h\), supported on its positive coordinates, satisfying
\( \sum_jh_j=0,\qquad \sum_jQ_jh_j=0, \)
because these are only two homogeneous linear equations in at least three unknowns. For sufficiently small \(\varepsilon>0\), both \(\alpha+\varepsilon h\) and \(\alpha-\varepsilon h\) remain feasible. Optimality therefore forces \(\sum_jR_jh_j=0\). Since \(h\) has both positive and negative coordinates, moving in its direction until the first coordinate reaches zero preserves feasibility and optimality while reducing support—a contradiction.
If it has two positive coordinates, its supply constraint is tight. If supply were slack, transferring a sufficiently small amount of weight in either direction between those two coordinates would remain feasible. Optimality would force their revenues to be equal. The option with smaller supply has supply no larger than their feasible weighted average, so using that option alone would be feasible and equally profitable, again contradicting minimal support.
The supply quantities are distinct: \(Q_1=1>Q_2>\cdots>Q_t>Q_0=0\), because every support mass is positive. Hence a two-option optimum has supplies strictly straddling \(\kappa\).
It follows that an optimum occurs among these explicit candidates:
\( \alpha_i=\frac{Q_j-\kappa}{Q_j-Q_i}, \qquad \alpha_j=\frac{\kappa-Q_i}{Q_j-Q_i}, \)
and giving revenue \(\alpha_iR_i+\alpha_jR_j\).
The no-service option is included, so this enumeration covers mixtures whose total weight on actual posted prices is less than one. It also covers singleton supports and zero-valued supports.
The mechanism uses the following single rule on every input \(\nu\):
There are at most \((t+1)^2\) candidates. Sorting requires a polynomial number of rational comparisons, and each candidate requires a constant number of rational arithmetic operations. The selected candidate has at most two active options, so returning all treatments requires only a constant number of operations per domain value.
For completeness, these are polynomial-time bit computations. The product of the input mass denominators has bit length at most their total encoded length. Using it as a common denominator computes every tail mass with polynomially many bits. Each candidate's weights and revenue then use a constant number of operations on these quantities, the input values, and \(\kappa\), so their bit lengths remain polynomial in \(L\). Exact comparisons and the output treatments consequently require polynomial bit complexity.
The algorithm therefore runs in time polynomial in \(m,t,L\), with \(t\) the actual support size. It never expands rational masses into individual agents.
The construction is one deterministic algorithm defined for every rational reported measure. For each fixed \(\nu\), it satisfies all incentive inequalities on \(V\). By the problem's premise, an individual's deviation changes only their report, leaving \(\nu\) fixed. These inequalities are therefore exactly the required truthfulness conditions, even though the selected prices depend on \(\nu\).
This differs from finite-agent mechanisms, where an individual's report changes the profile and incentive constraints connect different profiles, as discussed by [Devanur–Hartline–Yan](https://arxiv.org/pdf/1212.3741). The [Jackson–Kremer result](https://web.stanford.edu/~jacksonm/envy.pdf) concerns asymptotic robust approximate implementation; the explicit construction above establishes the computational guarantee directly.
At truthful input \(\mu\), the returned treatment achieves \(EFO_\kappa(\mu)\). Since this benchmark is nonnegative, it also achieves at least \(EFO_\kappa(\mu)/12.5\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes an exact polynomial-time mechanism under the truthfulness definition in USER_TASK. I found no major or minor mathematical gaps requiring repair.
Adding the two envy-free inequalities gives \((a_j-a_i)(x_j-x_i)\geq0\), so the support allocations are nondecreasing. Consequently, the increments \(d_j\) are nonnegative and satisfy \(\sum_jd_j\leq1\).
The adjacent incentive inequality has the correct direction:
\(u_i\geq u_{i-1}+(a_i-a_{i-1})x_{i-1}\).
Its iteration uses only \(u_1\geq0\), which individual rationality supplies.
The telescoping identity is correct: after substituting \(x_h=\sum_{j\leq h}d_j\), the coefficient of \(d_j\) in the payment bound is \(a_j\). The finite-sum exchanges therefore give precisely the stated revenue bound and supply constraint. Every admissible benchmark treatment yields a feasible vector for the proposed linear program.
The constructed allocations lie in \([0,1]\), and payments are nonnegative because \(a_j,d_j\geq0\). The displayed truthful utility formula establishes individual rationality for every \(v\in V\), including absent types.
The thresholdwise incentive inequality holds for each of the three cases \(v>a_j\), \(v<a_j\), and \(v=a_j\). In the equality case, both relevant utility contributions are zero, consistently with the task’s allowance of truthful reporting under indifference. Summing with nonnegative weights establishes all required incentive inequalities.
The support-weighted supply and revenue formulas are exact. Thus every feasible linear-program vector produces an admissible treatment attaining its objective. Together with the upper bound, this establishes equality with \(EFO_\kappa(\nu)\).
The transformed feasible set is a nonempty closed subset of the finite-dimensional probability simplex, hence compact. Its linear objective attains a maximum, and choosing an optimum with minimum support is well-defined.
With at least three positive coordinates, the stated two homogeneous equations admit a nonzero supported direction. Small movements in either direction preserve feasibility. Optimality forces zero objective change, and movement to the first vanishing coordinate preserves feasibility and reduces support. The contradiction is valid.
For a two-coordinate optimum with slack supply, small transfers in both directions are feasible, forcing equal revenues. Selecting the smaller-supply option alone then preserves feasibility and revenue, contradicting minimum support. Thus supply must bind.
Positive support masses imply strictly distinct tail supplies. A positive two-option mixture with binding supply therefore strictly straddles \(\kappa\). The displayed weights solve the normalization and supply equations, are positive, and yield the stated revenue.
Single options cover feasible endpoints, including cases where an option’s supply equals \(\kappa\). Including option \(0\) correctly represents unused mixture weight.
The enumeration also handles \(t=1\), zero values, \(\kappa=1\), and arbitrarily small positive rational supply. No division by zero occurs because paired supplies are distinct.
There are quadratically many candidates in the actual support size. The common-denominator argument bounds the encoding length of every tail mass polynomially in \(L\).
Each candidate uses only a constant number of rational operations on quantities with polynomial encoding length. Exact comparisons, selecting a maximum, and producing all \(m\) treatments consequently have polynomial bit complexity. The selected treatment has at most two active posted-price options, so output evaluation does not require expanding rational masses into agents.
Fixed tie-breaking makes the prescription a single algorithm defined for every rational reported measure. Because an individual deviation leaves \(\nu\) unchanged, the pointwise incentive inequalities already verified are exactly those required by USER_TASK. No incentive comparison across different reported measures is missing.
The output attains \(EFO_\kappa(\mu)\) exactly. Nonnegative payments ensure the benchmark is nonnegative, so the requested factor follows, including when the benchmark is zero.
Neither cited paper supplies a necessary step in the construction. The contextual distinction concerning finite-profile incentive constraints agrees with [Devanur–Hartline–Yan](https://arxiv.org/pdf/1212.3741), and the description of asymptotic implementation agrees with [Jackson–Kremer](https://web.stanford.edu/~jacksonm/envy.pdf). No unverified application of an external theorem is needed for the claimed computational result.
Actionable feedback: No additional mathematical clarification is needed. The exact guarantee, extension to absent types, and encoding-sensitive runtime are all established as written.
⟨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.