Answer: The sharp uniform factor is \(\epsilon^*(m,\tau,Q)=1\) for \(\tau=1\), and \(\epsilon^*(m,\tau,Q)=0\) for \(\tau\ge2\), for every allowed \(m,Q\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatePDA is 1 k+1-Shapley fair for selling k items. Before proving the theorem, first notice that the Shapley contribution of a player is the expected marginal social wel- fare increase without any constraints on previous allocation. It is equivalent to keep a zero allocation 0N as the constraint, so that the Shapley contribution can also be written as: ϕi(θ′) = X B⊆V \{i} |B|!(|V | −|B| −1)! |V |! · SW∗(θ′, B ∪{i}, 0N) −SW∗(θ′, B, 0N) .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support distribution \(\mu\) over buyer valuation schedules and referral roles, a measurable block or graphon referral relation, and a specified supply scaling, determine the largest \(\epsilon\) achievable by a measurable allocation-and-transfer mechanism that is individually incentive compatible and individually rational, respects diffusion feasibility and supply, and gives each truthful buyer utility between \(\epsilon\phi_i\) and \(\phi_i\), where \(\phi_i\) is the buyer’s expected marginal welfare contribution under a random-priority ordering of the population.
A society is an atomless probability space partitioned into the \(\tau\) positive-mass type blocks specified by \(\mu\); their masses are binary rationals summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. The finite input has bit length \(L\).
Each type specifies a normalized valuation schedule on \(\{0,\ldots,m\}\), with nonnegative, nonincreasing rational marginal values, and a referral role. A symmetric binary block relation specifies actual neighbors, and a nonempty set of blocks consists of the seller's initial neighbors. Supply is a binary rational \(Q\in(0,m]\).
Buyers may report any normalized schedule with nonnegative, nonincreasing marginal values and suppress any measurable subset of their actual outgoing referrals, but cannot invent referrals. Reports and retained referral relations must be Borel measurable. A buyer is feasible precisely when reachable from the seller by a finite directed path of retained referrals.
A possibly randomized measurable direct mechanism assigns quantities \(q(x)\in\{0,\ldots,m\}\) and payments \(p(x)\in\mathbb R\), with finite expected utilities \(u(x)=\mathbb E[v_x(q(x))-p(x)]\). In every realization, \(\int q\,d\mu\le Q\); infeasible buyers receive zero quantity and payment, and feasible outcomes cannot depend on infeasible buyers' reports. Transfers of either sign are allowed; no revenue constraint is imposed.
Define the random-priority benchmark at any report profile as follows. Sample \(N\) buyers independently from \(\mu\), add a tagged buyer \(x\) and the seller, inherit the reported referrals, and use supply \(k_N=\lfloor(N+1)Q\rfloor\). For a coalition \(B\), let \(W_N(B)\) be maximum reported welfare under integer quantities bounded by \(m\), using only buyers reachable from the seller within \(B\); set \(W_N(B)=0\) when the seller is absent.
For a uniform permutation of these \(N+2\) agents, let \(B_x\) precede \(x\), and define \(\phi_x=\limsup_{N\to\infty}\mathbb E[W_N(B_x\cup\{x\})-W_N(B_x)]\), where expectation includes sampling and permutation. This fixes the per-buyer normalization of continuous marginal contribution.
Require dominant-strategy individual incentive compatibility for both valuation and referral reports, individual rationality, and \(\epsilon\phi_x\le u(x)\le\phi_x\) whenever \(x\) reports truthfully, for every admissible profile of other reports. A positive factor is infeasible if a required benchmark is infinite.
What is the sharp Shapley-fairness factor uniformly achievable in this continuous model as a function of \(m,\tau,Q\)? Can a positive factor be guaranteed, or must the worst-case factor be \(0\)?
For finite societies selling \(k\) homogeneous items, Permutation Diffusion Auction is individually incentive compatible, individually rational, and \(1/(k+1)\)-Shapley fair; one realization is computable in polynomial time. Its fairness bound is tight for that mechanism when \(k=1\). [Verified source](https://ojs.aaai.org/index.php/AAAI/article/download/38746/42708).
No result settling the specified continuous model was located in the literature search. Computational bounds should be expressed in \(m,\tau,L\) and any additional parameters.
Result and interpretation. Taking “uniformly achievable” to mean over all admissible societies with the specified parameters, the sharp factor is
\[ \epsilon^*(m,\tau,Q)= \begin{cases} 1,&\tau=1,\\ 0,&\tau\ge 2. \end{cases} \]
Here and below, a factor of \(0\) imposes \(0\le u(x)\le\phi_x\), including when \(\phi_x=+\infty\).
The obstruction for \(\tau\ge2\) uses the requirement that fairness hold for each truthful buyer against every admissible profile of other reports. It does not imply that every society with multiple types has factor \(0\): if every block consists of initial neighbors, the exact-fairness construction below applies.
1. An infinite benchmark when \(\tau\ge2\).
Construct a society consisting of one noninitial block \(B\), of mass \(b=1/2\), and \(\tau-1\) initial blocks \(A_1,\ldots,A_{\tau-1}\), whose positive dyadic masses sum to \(1/2\). The actual symmetric block relation connects each \(A_i\) to \(B\), with no other edges.
Give block \(B\) the valuation \(v_B(q)=q\). Give block \(A_i\) the valuation \(v_{A_i}(q)=(i-1)q\). These schedules satisfy all valuation hypotheses, and the schedules together with referral roles distinguish the \(\tau\) types.
Fix a buyer \(x\in A_1\). Thus \(x\) has zero valuation. Consider this report profile:
On an interval realization of the society, this is a Borel profile: singling out \(x\) changes a Borel relation on a singleton.
Represent the uniform permutation by independent uniform arrival times. Conditional on the tagged buyer’s arrival time being \(t\), the seller precedes \(x\) with probability \(t\). The number of sampled buyers belonging to \(B\) and preceding \(x\) is
\[ Z_N(t)\sim\operatorname{Binomial}(N,bt). \]
Before \(x\) arrives, block \(B\) is unreachable. All reachable buyers have reported zero valuation, so the predecessor coalition has welfare zero.
If the seller precedes \(x\), adding \(x\) makes every preceding sampled buyer in \(B\) reachable. Its resulting welfare is exactly
\[ \min\{mZ_N(t),k_N\}. \]
Consequently, the expected marginal contribution is
\[ M_N=\int_0^1 t\,\mathbb E\!\left[\min\{mZ_N(t),\lfloor(N+1)Q\rfloor\}\right]\,dt. \]
For each fixed \(t\), the binomial law of large numbers gives \(Z_N(t)/N\longrightarrow bt\) in probability. Since \(0\le mZ_N(t)/N\le m\), bounded convergence in expectation and then dominated convergence in \(t\) yield
\[ \lim_{N\to\infty}\frac{M_N}{N} =\int_0^1 t\min\{mbt,Q\}\,dt>0. \]
The last inequality follows from \(m,b,Q>0\). Therefore \(M_N\longrightarrow+\infty\), and
\[ \phi_x=+\infty. \]
This is a required benchmark for a truthful buyer. Every positive factor is therefore infeasible under the problem’s explicit convention concerning infinite benchmarks.
The mechanism assigning zero quantities and zero payments is individually incentive compatible, individually rational, and satisfies the factor-\(0\) bounds: welfare is monotone under coalition inclusion, so every benchmark is nonnegative. This proves the sharp uniform factor \(0\) for \(\tau\ge2\).
2. The benchmark when every buyer is an initial neighbor.
This includes every society with \(\tau=1\). Referrals then have no effect on feasibility, either in the full society or within a coalition containing the seller.
Write a buyer’s reported marginal values as
\[ a_1(y)\ge\cdots\ge a_m(y)\ge0, \]
and define aggregate marginal demand above price \(z\) by
\[ D(z)=\int\sum_{j=1}^m\mathbf 1_{\{a_j(y)>z\}}\,d\mu(y). \]
For the tagged buyer \(x\), put
\[ d_x(z)=\sum_{j=1}^m\mathbf 1_{\{a_j(x)>z\}}. \]
Changing one buyer’s report does not change \(D\), because a singleton has measure zero.
We first establish the benchmark formula
\[ \phi_x =\int_0^1 t\int_0^\infty d_x(z)\mathbf 1_{\{tD(z)<Q\}}\,dz\,dt. \tag{1} \]
Conditional on the tagged arrival time \(t\), let
\[ C_N(t,z)=\sum_{i=1}^N \mathbf 1_{\{U_i<t\}} \sum_{j=1}^m\mathbf 1_{\{a_j(Y_i)>z\}}. \]
Here the sampled buyers \(Y_i\) and their arrival times \(U_i\) are independent.
For any finite collection of nonincreasing marginal schedules, maximum welfare with capacity \(k\) is the sum of its \(k\) largest marginal values, or all marginal values if fewer are available. Such a selection can respect each buyer’s prefix constraint because its marginals are nonincreasing. The layer-cake identity therefore gives the tagged welfare increment, conditional on the seller preceding \(x\), as
\[ \Delta_N(t)= \int_0^\infty \left[ \min\{k_N,C_N(t,z)+d_x(z)\} -\min\{k_N,C_N(t,z)\} \right]dz. \]
For fixed \(t,z\), the summands defining \(C_N(t,z)\) are independent, identically distributed, and bounded by \(m\). Hence
\[ \frac{C_N(t,z)}N\longrightarrow tD(z) \]
almost surely.
Since \(k_N/N\longrightarrow Q\), the integrand defining \(\Delta_N(t)\) converges to \(d_x(z)\) when \(tD(z)<Q\), and to zero when \(tD(z)>Q\).
For each \(z\), the equality \(tD(z)=Q\) holds for at most one \(t\). Fubini’s theorem makes the exceptional set null in the product integration. Moreover, the integrand is bounded by \(d_x(z)\), whose integral is the finite number \(v_x(m)\). Dominated convergence, together with the probability \(t\) that the seller precedes \(x\), proves (1). Thus the benchmark’s limsup is an actual limit.
Integrating first over \(t\) also gives
\[ \phi_x= \frac12\int_0^\infty d_x(z)\min\left\{1,\frac{Q}{D(z)}\right\}^{\!2}\,dz, \tag{2} \]
where the minimum is defined to be \(1\) when \(D(z)=0\). In particular, \(\phi_x\le v_x(m)/2\), even when other buyers’ reported valuations are unbounded across the population.
3. Posted prices representing the benchmark.
For \(t\in(0,1)\), define
\[ c_t=\inf\{z\ge0:tD(z)\le Q\}. \]
The function \(D\) is nonincreasing and right-continuous. Also \(D(z)\longrightarrow0\): every reported schedule has finite marginal values, and its marginal count is bounded by \(m\). Consequently, \(c_t\) is finite and
\[ tD(c_t)\le Q. \tag{3} \]
Monotonicity gives \(D(z)>Q/t\) for \(z<c_t\), and \(D(z)\le Q/t\) for \(z>c_t\). The equality cases already excluded in deriving (1) therefore imply
\[ \phi_x=\int_0^1 tS_x(c_t)\,dt, \tag{4} \]
where
\[ S_x(c)=\max_{0\le q\le m}\{v_x(q)-cq\} =\sum_{j=1}^m(a_j(x)-c)_+. \]
The final equality follows directly by summing the nonincreasing marginal net values.
4. A measurable lottery satisfying supply in every realization.
Independent buyer lotteries would not by themselves establish realization-wise supply feasibility. The following correlated lottery does.
Fix a Borel measurable coordinate \(r:X\to[0,1]\) having a uniform distribution under \(\mu\). Such a coordinate exists on an atomless measurable probability space; see [Lemma A.1 on atomless probability spaces](https://www.math.uwaterloo.ca/~wang/files/e-book-final.pdf).
For fixed \(t\), let
\[ d_t(y)=\#\{j:a_j(y)>c_t\}, \qquad G_{t,d}=\{y:d_t(y)=d\}. \]
If \(M_{t,d}=\mu(G_{t,d})>0\), define, for \(y\in G_{t,d}\),
\[ R_t(y)= \frac{\mu\{z\in G_{t,d}:r(z)\le r(y)\}}{M_{t,d}}. \]
Set \(R_t(y)=0\) on classes of mass zero.
The conditional distribution of \(r\) on every positive-mass class is atomless, since \(\mu\{r=s\}=0\) for each \(s\). Its cumulative distribution function is continuous. The probability integral transform therefore shows that \(R_t\) is uniform within each such class.
Draw independent uniform random variables \(T\in(0,1)\) and \(U\in[0,1)\). Select buyer \(y\) when
\[ (R_T(y)+U)\bmod1<T. \]
A selected buyer receives \(d_T(y)\) units and pays \(c_Td_T(y)\). An unselected buyer receives and pays zero.
For every fixed realization \(T=t,U=u\), selection takes exactly a fraction \(t\) of the measure in each positive-mass demand class. Hence
\[ \int q\,d\mu =t\sum_{d=0}^m dM_{t,d} =tD(c_t) \le Q, \]
by (3). Classes of mass zero do not affect this integral.
All quantities are integers between \(0\) and \(m\). The outcome functions are Borel measurable: \(c_t\) is monotone in \(t\), the demand classes are jointly measurable, and their conditional cumulative distribution functions are measurable parameter integrals.
Crucially, every individual buyer, including one in a zero-mass class, is selected with conditional probability \(t\), because \(U\) is uniform.
5. Incentives, utilities, and sharpness.
Fix all other reports and a buyer \(x\). An individual deviation leaves \(D\) and all prices \(c_t\) unchanged.
Conditional on \(T=t\), a report inducing quantity \(d\) gives expected true utility
\[ t\bigl(v_x(d)-c_td\bigr). \]
Truthful reporting induces the number of strictly positive marginal net values. This quantity maximizes \(v_x(q)-c_tq\); marginal values equal to the price contribute zero. Truthful valuation reporting is therefore optimal conditional on every \(t\), and hence optimal in expectation.
Referral reports do not affect the mechanism. Since every buyer is an initial neighbor, their suppression cannot change feasibility. Thus truthful valuation and referral reporting is a dominant strategy.
For a truthful buyer, expected utility is, by (4),
\[ u(x)=\int_0^1 tS_x(c_t)\,dt=\phi_x. \]
It is nonnegative, establishing individual rationality and exact Shapley fairness.
Utilities are finite under every report. Indeed, \(c_t\le c_1<\infty\), so payments are bounded by \(mc_1\), and a buyer’s true value is bounded by \(v_x(m)\).
Finally, no uniform factor larger than \(1\) can satisfy the required upper bound whenever a benchmark is positive. For example, if all buyers have all \(m\) marginal values equal to \(1\), equation (2) gives
\[ \phi_x=\frac{Q^2}{2m}>0. \]
Thus the achieved factor \(1\) is sharp for \(\tau=1\).
6. Computational scope and the finite-auction result.
The impossibility witness uses dyadic masses, integer marginal values, and a finite block graph. Its finite society description has size polynomial in \(m,\tau\), and the encoding length of \(Q\). The suppressed-referral profile also has a finite description: all initial buyers except one named buyer suppress their referrals.
Arbitrary Borel report profiles have no specified finite encoding, so a runtime bound solely in \(m,\tau,L\) would not be justified. If a reported valuation profile is supplied as \(r\) constant pieces with rational masses and total description length \(L_{\mathrm{rep}}\), equation (2) computes a tagged benchmark exactly by sorting at most \(rm+m\) marginal values and integrating a rational step function. This takes \(O(rm\log(rm+m))\) comparisons and polynomial bit time in \(m,r,L_{\mathrm{rep}}\). In particular, the homogeneous truthful \(\tau=1\) profile has polynomial-time benchmark computation in \(m,L\).
The cited [finite PDA theorem](https://ojs.aaai.org/index.php/AAAI/article/download/38746/42708) gives factor \(1/(k+1)\). Under the present sampling normalization, \(k_N\) grows with \(N\), so that guarantee tends to zero. This alone would not prove impossibility; the infinite-benchmark construction above supplies the needed proof.
⟨structured verdict parsed — rendered above⟩
The claimed sharp factor is sound in substance, with two minor qualifications concerning Borel measurability and computational input length. I found no blocking mathematical error.
1. Scope and quantifiers.
The prover correctly interprets “uniformly achievable” as a guarantee over all admissible societies with fixed parameters. A single admissible counterexample therefore suffices to rule out a positive uniform factor when \(\tau\ge2\).
For \(\tau=1\), the nonempty set of initial-neighbor blocks necessarily contains the sole block. Thus every buyer is an initial neighbor, and the construction in Sections 2–5 covers the intended case.
2. Infinite-benchmark obstruction.
The society in Section 1 satisfies the relevant restrictions:
Before the tagged buyer arrives, no initial buyer in the predecessor coalition retains an outgoing referral to the noninitial block. Consequently, its positive-valued buyers are unreachable. Their retained outgoing referrals do not change this, because reachability is directed.
Conditional on tagged arrival time \(t\), the seller precedes the tagged buyer with probability \(t\), independently of the sampled buyers’ arrivals. Adding the truthful tagged buyer then makes precisely the preceding sampled buyers in the noninitial block reachable. The welfare increment is therefore correctly computed as \(\min\{mZ_N(t),k_N\}\).
The limiting calculation is valid. Bounded convergence in probability justifies convergence of the expectations after division by \(N\), and the integrands are uniformly bounded for the subsequent integration over \(t\). The limiting integral is strictly positive for every allowed \(m,Q\). Hence the unnormalized expected marginal contribution diverges, giving \(\phi_x=+\infty\).
This is a truthful tagged buyer against an admissible profile of other reports, exactly the quantifier required by the task. The explicit infinite-benchmark convention rules out every positive factor.
The zero-allocation, zero-payment mechanism supplies the matching factor-zero guarantee. Coalition welfare is nondecreasing under inclusion: existing reachable buyers and their feasible allocations remain available. Thus every benchmark is nonnegative. The prover explicitly states its convention for the otherwise indeterminate product of zero with an infinite benchmark; this is a natural interpretation of the factor-zero bounds.
3. Benchmark formula for initial neighbors.
The finite welfare calculation is correct. Selecting the largest marginal values can respect each buyer’s prefix constraint because marginal values are nonincreasing; ties can be ordered consistently with those prefixes.
The layer-cake expression for the tagged increment follows from this calculation. Conditional on the seller preceding the tagged buyer, the predecessor demand count satisfies the stated law of large numbers.
Away from \(tD(z)=Q\), the increment converges to the stated quantity: eventually the capacity either accommodates all tagged marginals above \(z\), or is already exhausted. For each \(z\), the exceptional equality occurs at most once in \(t\), since \(Q>0\). Fubini therefore makes the exceptional set null.
The dominating function is integrable because the tagged schedule has finitely many finite marginal values. This remains true even if other buyers’ reports are unbounded across the population. Consequently, formulas (1) and (2), including the assertion that the limsup is a limit, are justified.
4. Posted-price representation.
The properties of \(D\) used here are correct. Right-continuity follows from the strict marginal-value threshold and bounded convergence. Its convergence to zero follows from finite reported marginal values and the uniform bound of \(m\) on each buyer’s marginal count.
These properties justify finiteness of \(c_t\) and the capacity inequality \(tD(c_t)\le Q\). The distinction between strict and weak inequalities does not invalidate formula (4): the equality set was already shown to be null in the product integration.
The surplus expression is also correct, including ties at the posted price, whose net marginal contribution is zero.
5. Correlated lottery and measurability.
The conditional distribution of the fixed coordinate on every positive-mass demand class is atomless: each coordinate level set has zero measure in the entire society and hence in the class. The probability integral transform consequently gives the claimed uniform rank within each such class.
For every fixed realization, rotation by \(U\) selects a fraction \(t\) of each positive-mass class. The resulting supply calculation is exact. The finitely many zero-mass classes do not affect its integral.
For each individual buyer, including a buyer in a zero-mass class, rotation by uniform \(U\) gives selection probability \(t\). This correctly addresses the task’s pointwise fairness requirement.
There is one minor measurability qualification. The cited [Lemma A.1](https://www.math.uwaterloo.ca/~wang/files/e-book-final.pdf) establishes a uniform random variable measurable with respect to the probability space’s sigma algebra. It does not separately establish that this variable is Borel measurable relative to an unspecified topology. On the intended interpretation that atomlessness applies to the society’s Borel probability structure, the application is valid.
Minimum clarification: explicitly identify the relevant Borel sigma algebra and state that it is the atomless sigma algebra to which the lemma applies, or clarify why the selected coordinate has a Borel version. The subsequent parameter-integral measurability argument is routine under that interpretation.
6. Incentives, utility, and sharpness.
An individual report change leaves aggregate demand and prices unchanged because the individual has zero measure. Although it may change that buyer’s demand class and rank, the buyer’s conditional selection probability remains \(t\). Thus the conditional expected-utility expression used in Section 5 is correct.
Truthful reporting selects a surplus-maximizing quantity at each price. Price ties do not cause an incentive problem. Referral suppression cannot affect feasibility when every buyer is an initial neighbor. The mechanism is therefore dominant-strategy incentive compatible in the expected-utility sense specified by the task.
Formula (4) gives exact benchmark utility, establishing fairness and individual rationality. The bound \(c_t\le c_1<\infty\) correctly establishes finite utilities under every report.
The sharpness example also checks: with all marginal values equal to one, formula (2) gives \(\phi_x=Q^2/(2m)>0\), including the endpoint \(Q=m\). The required upper bound then excludes factors larger than one.
7. Computational claims and the finite-auction comparison.
The prover correctly declines to assign a finite-input runtime to arbitrary Borel profiles. Its sorting and rational-integration description for finitely represented profiles is substantively valid.
There is one minor input-length omission: “polynomial bit time in \(m,r,L_{\mathrm{rep}}\)” does not explicitly include the encoding length of \(Q\), or a separately supplied tagged schedule.
For example, keep \(m=r=1\) and the reported marginal value equal to one, but take \(Q=2^{-n}\). The exact benchmark is \(2^{-2n-1}\), whose ordinary rational encoding has length growing with \(n\). A bit-time bound cannot omit this input length.
Minimum clarification: include the original input length \(L\) and any separately encoded tagged schedule in the bound, or explicitly define \(L_{\mathrm{rep}}\) to include them.
The cited [finite PDA result](https://ojs.aaai.org/index.php/AAAI/article/download/38746/42708) supports the stated finite guarantee. The prover correctly observes that its vanishing sampled guarantee alone would not prove continuous impossibility.
The output establishes a sharp fairness result, rather than a complexity classification of the full continuous problem.
⟨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.