Answer: For every fixed rational \(\epsilon\in(0,1)\), a relaxed envy-free allocation with welfare at least \(\operatorname{OPT}_{\mathrm{EF}}\) is computable in time polynomial in \(m,\tau,L\).
Theorem 3.8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a parameter ϵ ∈(0, 1), Auction 2 is a relaxed ϵB-envy-free and social-optimal auction. Moreover, the running time of the auction is O((n2m/ϵ)1/ϵ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite-support bidder types \(t=(v_t,B_t)\) with rational masses \(\mu_t\), position classes \(j=1,\ldots,m\) with qualities \(q_j\) and rational per-capita supplies \(\sigma_j\), and fixed \(\epsilon>0\), can one compute in time polynomial in \(m,\tau,L\) an allocation of mass \(\lambda_{t,j,p}\) to position class \(j\) at integer price \(p\), or to no position at price \(0\), such that each type’s masses sum to \(\mu_t\), each class’s assigned mass is at most \(\sigma_j\), and every assigned bundle satisfies \(0\le p\le \min(B_t,v_tq_j)\)? Require every bundle assigned to type \(t\) to satisfy \(v_tq_j-p\ge v_tq_k-r-\epsilon B_{\max}\) against every positive-mass bundle \((k,r)\) with \(r\le B_t-\epsilon B_{\max}\). The returned social welfare \(\sum_{t,j,p}\lambda_{t,j,p}v_tq_j\) must be at least the maximum welfare attainable in the same mass model under exact envy-freeness, where the comparison has no additive loss and applies whenever \(r\le B_t\). Each unit of mass receives one integral position or none; the population mass, not the bundles, is continuous.
A society is given by its support: the list of the \(\tau\) bidder types \(t=(v_t,B_t)\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Values and budgets are positive integers. There are \(m\ge1\) position classes with integer qualities \(q_1\ge\cdots\ge q_m>0\) and positive binary-rational per-capita supplies \(\sigma_j\). Let \(L\) be the total input bit length and \(B_{\max}=\max_t B_t\).
An allocation consists of nonnegative rational masses \(\lambda_{t,j,p}\), represented by their nonzero entries. Each individual receives one position at an integer payment, or the null bundle \((0,0)\), with \(q_0=0\). Require \(\sum_{j,p}\lambda_{t,j,p}=\mu_t\), \(\sum_{t,p}\lambda_{t,j,p}\le\sigma_j\) for \(j\ge1\), and \(0\le p\le\min\{B_t,v_tq_j\}\) whenever \(\lambda_{t,j,p}>0\).
For fixed rational \(\epsilon\in(0,1)\), call an allocation relaxed envy-free if every \(\lambda_{t,j,p}>0\) satisfies \(v_tq_j-p\ge v_tq_k-r-\epsilon B_{\max}\) against every bundle \((k,r)\) assigned positive total mass with \(r\le B_t-\epsilon B_{\max}\). Comparisons include bundles received by the same type and the null bundle when assigned; unassigned positions impose no comparisons.
Exact envy-freeness instead requires \(v_tq_j-p\ge v_tq_k-r\) whenever \(r\le B_t\). Let \(\operatorname{OPT}_{\mathrm{EF}}\) be the maximum welfare \(\sum_{t,j,p}\lambda_{t,j,p}v_tq_j\) among exact envy-free allocations in this same model. Envy is evaluated for each realized bundle, rather than for a type's average allocation or payment.
For every fixed \(\epsilon\in(0,1)\), can a relaxed envy-free allocation with welfare at least \(\operatorname{OPT}_{\mathrm{EF}}\) be computed in time polynomial in \(m,\tau,L\), with the polynomial allowed to depend on \(\epsilon\), or is obtaining this guarantee NP-hard for some fixed \(\epsilon\)?
For finite lists of bidders, Tang and Zhang establish a scheme polynomial in the bidder and position counts for fixed \(\epsilon\), with the same relaxed envy and welfare guarantees; they also establish a corresponding scheme for randomized allocations evaluated through expected clicks and payments. [Source](https://www.ijcai.org/Proceedings/15/Papers/098.pdf)
No result settling this support-encoded mass model was located in the literature search.
For every fixed rational \(\epsilon\in(0,1)\), the requested allocation can be computed in time polynomial in \(m,\tau,L\).
The key is to round payments down to a constant-size integer grid. Once payments lie on that grid, only the highest assigned quality at each price matters for envy comparisons. Those qualities can be enumerated, and the remaining allocation problem is a rational linear program.
Write \(B=B_{\max}\) and \(D=\epsilon B\). Define the positive integer grid spacing
\[
s=\lfloor D\rfloor+1
\]
and the price set
\[
P=\{0,s,2s,\ldots,s\lfloor B/s\rfloor\}.
\]
Here and below, displayed expressions use the same mathematical notation as inline expressions. In particular, the number of grid prices is \(K=|P|=\lfloor B/s\rfloor+1\). Since \(s>\epsilon B\), we have \(B/s<1/\epsilon\), and therefore
\[
K\le \lceil 1/\epsilon\rceil.
\]
For an integer payment \(p\), let \(\rho(p)=s\lfloor p/s\rfloor\). Then
\[
0\le p-\rho(p)\le s-1=\lfloor D\rfloor\le D.
\]
Lemma. Rounding every payment in an exact envy-free allocation from \(p\) to \(\rho(p)\) produces a relaxed envy-free allocation with unchanged welfare.
Proof. Preserve each assigned quality and mass, merging entries when their rounded payments coincide. Payments remain nonnegative integers. Because payments only decrease, budget feasibility and individual rationality remain valid. Type masses, supplies, and welfare are unchanged.
Consider any realized rounded bundle \((j,\rho(p))\) of type \(t\), and any globally assigned rounded bundle \((k,\rho(r))\) satisfying \(\rho(r)\le B_t-D\). Choose original positive-mass entries witnessing these rounded bundles. The rounding bound gives
\[
r\le \rho(r)+D\le B_t.
\]
Exact envy-freeness of the original allocation therefore implies \(v_tq_j-p\ge v_tq_k-r\). Consequently,
\[
v_tq_j-\rho(p)
\ge v_tq_j-p
\ge v_tq_k-r
\ge v_tq_k-\rho(r)-D.
\]
This is exactly the required relaxed envy inequality. The argument includes comparisons within a type and comparisons with the null bundle. \(\square\)
For a fixed price \(r\), every type prefers a larger quality at that price, because \(v_t>0\). Thus, if the largest quality assigned at price \(r\) is \(Q_r\), comparison against every bundle assigned at that price is equivalent to comparison against \((Q_r,r)\).
For each price \(p\in P\), enumerate one of these \(m+2\) choices:
There are at most \((m+2)^K\) enumerations. Repeated qualities can simply produce duplicate enumerations.
A chosen upper quality need not actually be assigned. Requiring comparisons against such a hypothetical bundle only strengthens the constraints used by the algorithm. The correctness proof below shows that one enumeration uses the actual largest qualities of the rounded optimal allocation.
Fix an enumeration. Call a triple \((t,j,p)\), with \(t\) a type, \(j\in\{0,\ldots,m\}\), and \(p\in P\), eligible when all the following conditions hold:
\[ v_tq_j-p\ge v_tQ_r-r-D. \]
Eligibility is determined by arithmetic on the input and the enumeration; it does not depend on allocation variables.
Introduce a nonnegative variable \(\lambda_{t,j,p}\) for each eligible triple. Solve the linear program that maximizes
\[
\sum_{\text{eligible }(t,j,p)}\lambda_{t,j,p}v_tq_j
\]
subject to the type-mass equations
\[
\sum_{\text{eligible }(t,j,p)}\lambda_{t,j,p}=\mu_t
\qquad\text{for every type }t,
\]
and the supply inequalities
\[
\sum_{\text{eligible }(t,j,p)}\lambda_{t,j,p}\le \sigma_j
\qquad\text{for every }j\in\{1,\ldots,m\}.
\]
Discard infeasible enumerations. Return an optimal solution from the feasible enumeration with largest objective value.
At least one enumeration is feasible: activate only price zero with upper quality zero, and assign every type its entire mass to the null bundle.
The linear-program constraints enforce type masses and supplies. Eligibility enforces integer payments, budget feasibility, individual rationality, and the restriction on the null bundle.
Now consider a positive entry \(\lambda_{t,j,p}\) and any globally assigned bundle \((k,r)\) with \(r\le B_t-D\). Since that bundle is assigned, price \(r\) is active and \(q_k\le Q_r\). Eligibility gives
\[
v_tq_j-p\ge v_tQ_r-r-D.
\]
Because \(v_t>0\), it follows that
\[
v_tq_j-p\ge v_tq_k-r-D.
\]
Thus every realized bundle satisfies every required comparison. This also covers bundles assigned to the same type and the null bundle when assigned.
First, the exact optimum is attained by a rational allocation. To see this, there are finitely many feasible integer-payment triples. For any subset of triples whose pairwise exact envy comparisons all hold, the mass and supply constraints define a bounded rational polytope, allowing some entries in the subset to have zero mass. Its allocations remain exact envy-free because deleting bundles removes comparisons. Every exact envy-free allocation belongs to one such polytope. Their finite union is nonempty, since it contains the all-null allocation, and each nonempty polytope has a rational welfare-maximizing vertex. Hence their maximum welfare is attained rationally.
Take an exact optimal allocation and apply the rounding lemma. Let \(\bar\lambda\) denote the resulting allocation. It is relaxed envy-free and has welfare \(\operatorname{OPT}_{\mathrm{EF}}\).
Choose the enumeration that makes a price active exactly when it occurs in \(\bar\lambda\), and, for each active price \(p\), sets \(Q_p\) to the largest quality actually assigned at that price.
Every positive entry of \(\bar\lambda\) is eligible:
Accordingly, \(\bar\lambda\) is feasible for this enumeration’s linear program. That program’s optimal welfare is at least \(\operatorname{OPT}_{\mathrm{EF}}\). The algorithm chooses the best enumeration, so its returned welfare is also at least \(\operatorname{OPT}_{\mathrm{EF}}\).
Each enumeration has at most \(\tau(m+1)K\) variables. Eligibility requires at most \(K\) comparisons per candidate triple. There are \(\tau\) mass equations and \(m\) supply inequalities.
All arithmetic has bit length polynomial in \(L\), with constants allowed to depend on the fixed rational \(\epsilon\). In particular, grid payments are at most \(B\), valuation products are input-integer products, and masses and supplies retain their input rational representations.
Polynomial-time rational linear programming yields an optimal rational solution of polynomial encoding length. The output lists at most \(\tau(m+1)K\) nonzero entries.
The total running time is therefore bounded by
\[
(m+2)^{\lceil1/\epsilon\rceil}
\operatorname{poly}(m,\tau,L),
\]
where the polynomial may depend on \(\epsilon\), as permitted.
This proof operates directly on support-encoded masses. It does not require expanding them into finite bidder lists or using the expected-click interpretation of randomized allocations in the [Tang–Zhang paper](https://www.ijcai.org/Proceedings/15/Papers/098.pdf).
⟨structured verdict parsed — rendered above⟩
The claimed polynomial-time result is correct. The proof addresses support-encoded rational masses and evaluates envy for each realized bundle, as required. I found no major or minor mathematical gaps.
With \(B=B_{\max}\), \(D=\epsilon B\), and \(s=\lfloor D\rfloor+1\), the spacing is a positive integer satisfying \(s>D\). Therefore \(B/s<1/\epsilon\), and the stated bound \(K=\lfloor B/s\rfloor+1\le\lceil1/\epsilon\rceil\) holds, including when \(1/\epsilon\) is an integer.
Every feasible payment is an integer between zero and \(B\), so its rounded payment belongs to \(P\). Integer division gives \(0\le p-\rho(p)\le s-1=\lfloor D\rfloor\le D\). These bounds remain valid when \(D<1\); in that case \(s=1\) and rounding changes no payments.
The lemma correctly handles the change in the affordability threshold.
For a rounded comparison bundle satisfying \(\rho(r)\le B_t-D\), its original payment satisfies \(r\le\rho(r)+D\le B_t\). Consequently, the original exact envy condition applies to the chosen original entries.
The displayed chain of inequalities is valid:
Together these establish the required relaxed inequality.
Merging entries does not introduce a problem: every positive merged entry has an original positive-mass witness, and exact envy-freeness applies to each such witness. Decreasing payments preserves budget feasibility and individual rationality. Qualities and masses remain unchanged, so supplies and welfare are preserved. The null bundle remains \((0,0)\).
At a fixed price \(r\), utility is increasing in quality because every \(v_t>0\). Affordability depends only on \(r\), not on quality. Thus comparison with the largest assigned quality at that price is equivalent to all comparisons at that price.
The enumeration includes every possible actual maximum: each assigned quality belongs to \(\{q_0,\ldots,q_m\}\). Its number of choices is at most \((m+2)^K\), and repeated qualities merely create duplicate cases.
Allowing an enumerated upper quality to remain unassigned only strengthens eligibility constraints. This cannot invalidate the soundness argument, and the completeness argument explicitly selects actual assigned maxima.
Eligibility correctly enforces:
The mass equations and supply inequalities are exactly the required allocation constraints. No supply constraint is needed for the null bundle.
Eligibility depends only on fixed input data and the enumeration, so filtering triples before forming the LP is valid.
The stated all-null enumeration is feasible. Whenever price zero meets the comparison threshold, its eligibility inequality is \(0\ge-D\); otherwise there is no comparison to check.
For any positive recipient entry and any actually assigned affordable comparison bundle \((k,r)\), eligibility supplies the comparison against \(Q_r\). Since \(q_k\le Q_r\) and \(v_t>0\), that inequality implies the required comparison against \(q_k\).
This argument applies to every positive recipient entry individually. It therefore covers comparisons within a type and does not substitute average utility for realized utility. Assigned null bundles are also included.
The attainment argument is valid.
There are finitely many feasible integer-payment triples. A subset satisfying all relevant exact envy comparisons defines a rational polytope through nonnegativity, mass equations, and supply inequalities. Each variable is bounded by its type’s mass, so the polytope is bounded.
Allowing some entries to become zero preserves exact envy-freeness: it removes recipient bundles or comparison bundles and introduces none. Conversely, the positive support of every exact envy-free allocation supplies one of the enumerated compatible subsets.
The finite union is nonempty because the all-null allocation is exact envy-free. A linear objective on each nonempty bounded rational polytope attains its maximum at a rational vertex. Hence a rational exact optimum exists.
This finite enumeration is used only to establish existence; the algorithm does not perform it.
Rounding an exact optimum gives a relaxed envy-free allocation with unchanged welfare.
For the enumeration using precisely its active prices and actual largest assigned qualities, every positive rounded entry is eligible. In particular, each comparison against \(Q_r\) corresponds to an actually assigned bundle, so relaxed envy-freeness supplies the required eligibility inequality.
The rounded optimum is therefore feasible for that LP. Its optimal objective is at least \(\operatorname{OPT}_{\mathrm{EF}}\), and selecting the best feasible enumeration preserves that guarantee.
For fixed rational \(\epsilon\), \(K\) is constant. Each enumeration has at most \(\tau(m+1)K\) variables, and its eligibility checks and constraints have polynomial size.
The quantities used in eligibility—grid payments, products of input integers, and rational thresholds involving fixed \(\epsilon\)—have polynomial bit length. The LP coefficients and right-hand sides likewise have polynomial encoding length.
The invoked rational linear-programming result applies: these are explicitly represented rational LPs, and every feasible LP is bounded. Polynomial-time LP algorithms can return an exact optimal rational solution of polynomial encoding length.
The enumeration count and output-entry count consequently give the stated polynomial running time and output representation.
None required. The argument establishes the requested guarantee directly in the support-encoded mass model.
⟨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.