d4-conf-sagt-2015-0021 (d4-conf-sagt-2015-0021)

Given \(m\) resources, \(\tau\) valuation types with public rational masses \(\mu_t>0\) summing to \(1\), per-capita supplies \(h_j\), and normalized, monotone, subadditive valuations \(v_t:[0,1]^m\to\mathbb{R}_{\ge 0}\) privately held by the type parties, determine the nondeterministic communication complexity of producing a feasible \((2-\varepsilon)\)-approximation to \(\mathrm{OPT}\). A feasible plan consists of a probability distribution \(\pi_t\) over bundles for each type, with welfare \(\sum_t\mu_t\int v_t(x)\,d\pi_t(x)\) and resource use \(\sum_t\mu_t\int x_j\,d\pi_t(x)\le h_j\) for every resource \(j\).

A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. There are \(m\ge1\) resources with public binary-rational per-capita supplies \(h_j\in(0,1]\); \(L\) is the total public input bit length.
Each type is represented by one party privately holding a Borel-measurable valuation \(v_t:[0,1]^m\to\mathbb R_{\ge0}\), with finite values, \(v_t(0)=0\), and coordinatewise monotonicity. Subadditivity means \(v_t(x+y)\le v_t(x)+v_t(y)\) whenever \(x,y,x+y\in[0,1]^m\); continuity is not assumed.
A plan assigns each type a Borel probability measure \(\pi_t\) on bundles. Its welfare is \(W(\pi)=\sum_t\mu_t\int v_t(x)\,d\pi_t(x)\), and feasibility means \(\sum_t\mu_t\int x_j\,d\pi_t(x)\le h_j\) for every \(j\). Define \(\mathrm{OPT}=\sup_{\pi\text{ feasible}}W(\pi)\).
Use nondeterministic bit communication on a shared blackboard, with unrestricted local computation and free access to each party's own valuation. Certificates and the output count toward communication; an output explicitly lists finitely supported lotteries with binary-rational probabilities and bundle coordinates. Complexity parameters are \(m,\tau,L\), and \(\varepsilon\).

For each fixed \(\varepsilon\in(0,1)\), what is the worst-case nondeterministic communication complexity of producing a feasible plan with \(W(\pi)\ge\mathrm{OPT}/(2-\varepsilon)\)? Does communication polynomial in \(m,\tau,L\) suffice, or is communication exponential in \(m\) necessary?

For finitely many agents receiving deterministic bundles under unit aggregate supplies, a \((2-\varepsilon)\)-approximation requires exponential communication, even nondeterministically. [Source](https://arxiv.org/pdf/1507.07011). The [published version](https://www.researchgate.net/publication/306925842_On_the_Efficiency_of_the_Proportional_Allocation_Mechanism_for_Divisible_Resources) retains this result. No result settling the mass-and-lottery problem was found in the searches conducted.

Conclusion

As stated, the worst-case communication is unbounded even when \(m=1\), \(\tau=2\), and \(L\) is constant. Thus neither a polynomial bound nor an exponential bound in the listed parameters suffices.

This follows from the absence of a parameter controlling private valuation scales. To address the substantive mass-and-lottery question beyond that obstruction, I also prove that polynomial nondeterministic communication suffices under the additional normalization \(v_t(\mathbf 1)=1\) for every supported type. That result accommodates discontinuities and even does not require subadditivity.

1. An unbounded lower bound for the stated model

Write \(\alpha=2-\varepsilon\), so \(1<\alpha<2\).

Use the fixed public instance
\[ \]
\(m=1,\qquad \tau=2,\qquad \mu_1=\mu_2=\tfrac12,\qquad h_1=\tfrac12.\)

For positive numbers \(a,b\), give the parties the valuations
\(v_1(x)=ax\) and \(v_2(x)=bx\). These valuations are finite, continuous, monotone, normalized at zero, and additive, hence subadditive.

For an output plan, define \(z_t=\int x\,d\pi_t(x)\). Feasibility is equivalent to
\(z_1+z_2\le 1\), and its welfare is
\(W=\tfrac12(az_1+bz_2)\).
Consequently,
\(\mathrm{OPT}=\tfrac12\max\{a,b\}\): the upper bound follows from feasibility, and assigning bundle \(1\) to a type with the larger slope achieves it.

The transcript property

A sound nondeterministic protocol must satisfy two conditions:

• On every input, some certificate leads to acceptance and a valid approximate output.
• Every accepting execution produces a valid approximate output.

Fix a complete accepting transcript, including its certificate and output. The pairs of private inputs compatible with it form a rectangle. Indeed, once the transcript is fixed, each party’s messages and acceptance decisions depend only on that party’s private input. Therefore, if the same transcript accepts on \((a,a)\) and \((b,b)\), it also accepts on \((a,b)\) and \((b,a)\), with the same output.

This remains true with arbitrary local computation and additional local nondeterministic choices: compatibility with the fixed transcript is still a separate condition on each party.

An infinite family requiring distinct transcripts

Choose an integer \(r>0\) such that
\(2^r>\alpha/(2-\alpha)\),
and put
\(a_n=2^{-rn}\) for \(n=1,2,\ldots\).

These slopes are positive dyadic rationals. In particular, this argument even restricts every valuation to take values in \([0,1]\).

Suppose a protocol has a finite worst-case communication bound \(C\). There are only finitely many complete transcripts of at most \(C\) bits. Choose one accepting transcript for every diagonal input \((a_n,a_n)\). Two distinct diagonal inputs must share a transcript.

Let their slopes be \(A>b\). The shared transcript also accepts on both \((A,b)\) and \((b,A)\). Let \(z_1,z_2\) be the means of its common output. Approximation on the two crossed inputs requires
\(Az_1+bz_2\ge A/\alpha\)
and
\(bz_1+Az_2\ge A/\alpha\).

Adding these inequalities and using feasibility gives
\((A+b)(z_1+z_2)\ge 2A/\alpha\),
and hence
\(1+b/A\ge 2/\alpha\).

But the construction gives
\(A/b\ge 2^r>\alpha/(2-\alpha)\).
Equivalently,
\(1+b/A<1+(2-\alpha)/\alpha=2/\alpha\),
a contradiction.

Thus no finite \(C\) exists. The public input is fixed throughout, so no finite function of \(m,\tau,L,\varepsilon\) bounds the worst-case communication.

This is not caused by discontinuities or by irrational output requirements. The example uses linear valuations with dyadic slopes. The missing parameter is private valuation scale or representation length.

2. The substantive lottery case under public normalization

The preceding obstruction should not be mistaken for an exponential lower bound arising from the number of resources. Here is a positive result for a natural, explicitly stronger model.

Proven claim. Suppose additionally that \(v_t(\mathbf 1)=1\) for every type. For each fixed \(\varepsilon\in(0,1)\), a feasible \((2-\varepsilon)\)-approximation has a nondeterministic certificate and explicit output of polynomial length in \(m,\tau,L\).

Individual normalization changes relative welfare weights, so this is an additional hypothesis, not a without-loss-of-generality transformation.

2.1. A finite grid approximates arbitrary lotteries

Fix a rational number \(a\) with
\(1<a<2-\varepsilon\).
Choose a positive dyadic number \(\rho\) satisfying
\(\rho\le\min\{1/16,(a-1)/8\}\).

These choices ensure
\((1+\rho)^2/(1-2\rho)\le a\).
To verify this, put \(d=a-1\in(0,1)\). The difference between the right and left sides after clearing the positive denominator is
\(a(1-2\rho)-(1+\rho)^2 =d-4\rho-2d\rho-\rho^2\).
Since \(\rho\le d/8\), this is at least
\(d-6\rho-\rho^2 \ge d/4-d^2/64>0\).

Let \(H=\min_j h_j>0\). Choose a dyadic grid spacing \(\delta=2^{-k}\le\rho H\), and define
\(G=\{0,\delta,2\delta,\ldots,1\}^m\).

For a bundle \(x\), let \(R(x)\) round every coordinate upward to the next grid point. This is a Borel map, and
\(R(x)\ge x\) and \(R(x)_j\le x_j+\delta\).

Given any feasible plan, replace each lottery by its image under \(R\), then retain that lottery with probability \(1/(1+\rho)\) and otherwise assign zero. Its aggregate consumption of resource \(j\) is at most
\((h_j+\delta)/(1+\rho)\le h_j\).
Monotonicity and \(v_t(0)=0\) show that its welfare is at least the original welfare divided by \(1+\rho\).

Let \(P\) be the optimal welfare among feasible lotteries supported on \(G\). Taking the supremum over the original feasible plans gives
\(\mathrm{OPT}\le(1+\rho)P\).

No continuity or attainment of the original supremum was used. Also,
\(H\le P\le1\).
For the lower bound, give every type the full bundle with probability \(H\), and zero otherwise. For the upper bound, monotonicity and normalization give \(v_t(x)\le1\).

2.2. The finite linear program and its dual

Use variables \(\lambda_{t,g}\), denoting the probability that type \(t\) receives grid bundle \(g\). The finite linear program maximizes
\(\sum_{t,g}\mu_t\lambda_{t,g}v_t(g)\)
subject to
\(\sum_g\lambda_{t,g}=1\),
\(\sum_{t,g}\mu_t\lambda_{t,g}g_j\le h_j\),
and \(\lambda_{t,g}\ge0\).

Its feasible set is nonempty and compact, so it has an optimum at a vertex.

Such a vertex has at most
\(K=\tau+m\)
positive variables. Indeed, if there were more, the corresponding columns in the matrix of the \(\tau\) probability equations and \(m\) resource expressions would be linearly dependent. A sufficiently small perturbation in both signs along that dependence would preserve all those expressions and nonnegativity, contradicting extremality.

The dual has variables \(p_j\ge0\) and \(u_t\), with constraints
\(u_t+p\cdot g\ge v_t(g)\)
for every \(t,g\), and objective
\(D=\sum_t\mu_tu_t+\sum_jh_jp_j\).

The constraint for \(g=0\) implies \(u_t\ge0\). The choice \(u_t=1\), \(p_j=0\) is dual feasible. Finite-dimensional linear-programming duality therefore supplies optimal dual variables with \(D=P\le1\). Their nonnegativity implies
\(u_t\le1/\mu_t\) and \(p_j\le1/h_j\).

These bounds are crucial: their logarithms are controlled by the public input length.

2.3. Short dyadic output and certificate

Choose public dyadic numbers \(\eta,e>0\) such that
\(K\eta\le\rho H\)
and
\((m+1)e\le\rho H\).

Start with an optimal sparse primal solution. Round every positive probability downward to a multiple of \(\eta\), then assign each type’s missing probability to zero.

This preserves feasibility because every resource consumption weakly decreases. The resulting output has at most \(K+\tau=m+2\tau\) atoms, with dyadic coordinates and probabilities. Since \(v_t(g)\le1\), its welfare \(W\) satisfies
\(W\ge P-K\eta\ge P-\rho H\).

For each type, let \(M_t\) be its expected value in this output, and include the dyadic number
\(b_t=e\lfloor M_t/e\rfloor\)
in the certificate. Define the publicly computable lower bound
\(B=\sum_t\mu_tb_t\).
Then
\(B\ge W-e\ge P-2\rho H\ge(1-2\rho)P\).

Finally, round the optimal dual variables upward to multiples of \(e\). The rounded variables remain dual feasible, and their objective satisfies
\(D\le P+(m+1)e\le P+\rho H\le(1+\rho)P\).

2.4. Verification and soundness

The certificate contains the output lotteries, \(p,u\), and the numbers \(b_t\).

Each party checks:

• Its claimed bound satisfies \(b_t\le\int v_t\,d\pi_t\).
• For every grid bundle \(g\), it satisfies \(v_t(g)\le u_t+p\cdot g\).

The grid may be enormous, but these checks are local and finite; local computation is unrestricted.

The parties also check the rational probabilities, public feasibility, nonnegative dual variables, and the public inequality
\((1+\rho)D\le aB\).

For any accepting certificate, the local dual inequalities bound every feasible grid plan by \(D\). Thus
\(\mathrm{OPT}\le(1+\rho)P\le(1+\rho)D\le aB\le aW\).
Therefore the accepted output meets the requested approximation.

For the constructed certificate, acceptance follows from
\((1+\rho)D/B\le(1+\rho)^2/(1-2\rho)\le a\).
This establishes completeness as well as soundness.

2.5. Communication length

Positive public masses and supplies have logarithmic reciprocals bounded by \(O(L)\). Consequently:

• Grid coordinates have \(O(L+\log(1/\rho))\) bits.
• Output probabilities have \(O(L+\log(m+\tau)+\log(1/\rho))\) bits.
• Rounded prices, dual constants, and value bounds have polynomial bit length.
• There are at most \(m+2\tau\) output atoms and \(m+2\tau\) additional numerical certificate entries.

For fixed \(\varepsilon\), the total communication is therefore
\(O_\varepsilon((m+\tau)(m+1)(L+\log(m+\tau)))\).

3. Relation to the supplied lower bound

The cited paper’s Lemma 10 concerns deterministic allocations to finitely many agents under aggregate supply constraints. Its reduction uses the fact that two agents cannot both receive more than half of the same resource. That restriction does not hold for the separate lotteries constrained only by aggregate expectations here. [Christodoulou, Sgouritsa, and Tang, Lemma 10](https://arxiv.org/pdf/1507.07011)

The normalized theorem above establishes a polynomial certificate for the mass-and-lottery problem directly. For the exact stated model, however, the unrestricted private scales already make worst-case communication unbounded.

⟨structured verdict parsed — rendered above⟩

The stated-model lower bound is correct: worst-case nondeterministic bit communication is unbounded already for fixed \(m=1\), \(\tau=2\), and constant public input length. The additional normalized theorem is also sound in substance, with one minor omission concerning the bit lengths of the chosen dyadic parameters.

There are no major mathematical gaps.

1. Fixed public instance and optimum

The instance satisfies all public restrictions: both masses are positive, their sum is \(1\), and the supply is positive. The linear valuations satisfy every stated valuation requirement, including subadditivity.

For any lotteries, their means lie in \([0,1]\). The displayed feasibility and welfare formulas are correct:
\[ z_1+z_2\le 1,\qquad W=\tfrac12(az_1+bz_2). \]
Consequently,
\[ W\le\tfrac12\max\{a,b\}(z_1+z_2)\le\tfrac12\max\{a,b\}. \]
The described deterministic allocation attains this bound. Thus the asserted optimum is exact, without any attainment issue.

2. Transcript rectangle property

The rectangle argument is valid in the specified shared-blackboard bit model. Fixing the entire certificate, transcript, and output makes compatibility a separate condition on each party’s private input. Combining compatible private inputs therefore preserves the same accepting transcript and output.

Additional private nondeterministic choices do not invalidate this reasoning: witnesses for each party’s compatibility can be selected separately. Soundness is essential here, and the prover explicitly states the necessary universal condition on accepting executions.

Because certificates and outputs count toward communication, a finite worst-case bit bound permits only finitely many complete transcripts. The pigeonhole argument therefore applies.

3. Infinite family and crossed-input contradiction

For fixed \(\alpha=2-\varepsilon\in(1,2)\), the required integer \(r\) exists. Every slope \(a_n=2^{-rn}\) is strictly positive and dyadic. The example also genuinely has values in \([0,1]\); it does not exploit unbounded valuation magnitudes or zero valuations.

Two distinct selected diagonal inputs sharing a transcript yield crossed inputs with the same output. The approximation inequalities on those crossed inputs are exactly
\[ Az_1+bz_2\ge A/\alpha,\qquad bz_1+Az_2\ge A/\alpha. \]
Adding them and using feasibility gives
\[ 2A/\alpha\le(A+b)(z_1+z_2)\le A+b. \]
Hence \(1+b/A\ge2/\alpha\).

The separation condition implies
\[ b/A<(2-\alpha)/\alpha, \]
which gives the strict opposite inequality. The contradiction is valid.

This establishes the claimed absence of any finite uniform communication bound in the listed parameters. It does not merely establish an exponential lower bound. The decreasing positive scales are allowed by the task as written; this is not an unintended degenerate interpretation.

4. Grid approximation under normalization

The supplementary theorem explicitly adds \(v_t(\mathbf1)=1\), and correctly acknowledges that this changes the model.

The rounding map is Borel measurable, maps into the finite grid, and satisfies the stated coordinate bounds. Since masses sum to \(1\), rounding increases aggregate consumption in each coordinate by at most \(\delta\). Mixing the rounded lottery with zero using retention probability \(1/(1+\rho)\) therefore restores feasibility.

Monotonicity and \(v_t(0)=0\) establish the welfare bound. Taking the supremum is legitimate even without attainment:
\[ \mathrm{OPT}\le(1+\rho)P. \]
Normalization and monotonicity bound all values by \(1\). The full-bundle lottery with probability \(H\) is feasible, so \(H\le P\le1\) is correct.

The constant calculation is also correct. With \(d=a-1\in(0,1)\),
\[ a(1-2\rho)-(1+\rho)^2 =d-4\rho-2d\rho-\rho^2 \ge d/4-d^2/64>0. \]
All denominators used subsequently are positive.

5. Finite linear program, sparsity, and duality

The finite primal feasible set is nonempty and compact. Its real-valued objective coefficients cause no difficulty for finite-dimensional linear programming.

The vertex support bound is correct. A dependence among more than \(\tau+m\) positive columns yields a nonzero perturbation preserving all probability equations and resource expressions. A sufficiently small perturbation in either direction preserves nonnegativity, contradicting extremality.

The displayed dual has the correct scaling by the masses. The zero-bundle constraint forces \(u_t\ge0\). Both primal and dual feasibility, together with finite primal optimum, justify the invoked finite-dimensional strong duality and existence of an optimal dual solution.

Since all objective terms are nonnegative,
\[ u_t\le1/\mu_t,\qquad p_j\le1/h_j \]
follow as claimed.

6. Rounding and certificate verification

Rounding positive probabilities downward and assigning the deficit to zero preserves probability normalization and feasibility. The support-size bound remains valid, including when zero was already present.

The welfare loss is at most \(K\eta\). Rounding the expected values downward loses at most \(e\) after weighting by masses. Thus
\[ B\ge P-2\rho H\ge(1-2\rho)P>0. \]

Rounding nonnegative dual variables upward preserves every dual constraint. Its objective increase is at most
\[ e\sum_t\mu_t+e\sum_jh_j\le(m+1)e. \]
Therefore the claimed bound on \(D\) is correct.

For arbitrary accepting certificates, the locally verified grid inequalities supply the dual upper bound, and the verified value bounds give \(B\le W\). The complete soundness chain
\[ \mathrm{OPT}\le(1+\rho)P\le(1+\rho)D\le aB\le aW \]
is valid. Since \(a<2-\varepsilon\), this meets the requested approximation.

Completeness follows from the proved bounds on \(B\) and \(D\). Exhaustive grid checking is finite and incurs no communication cost under unrestricted local computation.

7. Minor issue: parameter choices and communication length

Where: Sections 2.1, 2.3, and 2.5.

Issue: The inequalities prescribing \(\delta\), \(\eta\), and \(e\) only give upper bounds on their sizes. Arbitrarily small dyadic choices satisfy those inequalities while having arbitrarily long encodings. Thus the communication estimate does not follow from those inequalities alone.

Minimum clarification needed: Specify that these public dyadic parameters are chosen with the asserted bounded bit lengths, and record the corresponding bounds. This is a routine parameter-selection clarification, requiring no new mathematical argument.

With that clarification, the atom counts and numerical-entry counts support the displayed polynomial communication estimate. The estimate is for fixed \(\varepsilon\), as claimed.

8. Relation to the cited result

The source check confirms that Lemma 10 concerns allocations under unit aggregate supplies and that its reduction explicitly uses the exclusion of two agents each receiving more than half of the same resource. The prover accurately identifies why that exclusion does not automatically apply to separate lotteries constrained only in expectation. [Christodoulou, Sgouritsa, and Tang, Lemma 10](https://arxiv.org/pdf/1507.07011)

This observation explains why the cited reduction cannot simply be transferred; it is not used as a substitute for the direct proofs above.

The exact stated model is resolved by the unbounded communication lower bound. The normalized theorem is supplementary and does not turn the original model into a polynomial-versus-exponential split.

⟨structured verdict parsed — rendered above⟩