Answer: Exact optimization and the decision problem are polynomial-time solvable; for \(m=1\), an exact algorithm uses \(O(\tau^2L^2)\) bit operations. Feasibility holds exactly when \(\kappa\le\max_i v_iS_i\). A threshold is optimal exactly when \(\kappa\le v_1\), or an index \(i\ge2\) satisfies \(a_i=\kappa\), \(a_j<a_i\) for every \(j<i\), and \(B_i\le U_i\), with the quantities defined above.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximate2 agents case: If f is log-concave, then the serial cost sharing mechanism maximizes the expected number of consumers. If f is log-concave and welfare-concave, then the serial cost sharing mechanism maximizes the expected social welfare. 3 agents case: If f is log-concave and nonincreasing, then the serial cost sharing mechanism maximizes the expected number of consumers.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an excludable project, finite valuation types \(0\le v_1<\dots<v_\tau\le1\), rational masses \(\mu_j\) summing to \(1\), and per-capita cost \(\kappa>0\), maximize served mass \(\sum_j\mu_jx_j\) over service fractions \(x_j\in[0,1]\) and average payments \(p_j\ge0\), subject to \(v_jx_j-p_j\ge v_jx_k-p_k\) for all \(j,k\), \(v_jx_j-p_j\ge0\), and \(\sum_j\mu_jp_j=\kappa\) (report infeasibility if necessary). Characterize when the threshold rule serving all types above \(t\), none below \(t\), and a fraction at \(v_j=t\) when needed, with served agents paying \(t\), attains the optimum.
A society is given by its support: the list of \(\tau\ge1\) valuation types with positive binary-rational masses \(\mu_j\), where \(\sum_j\mu_j=1\); \(\tau\) is the support size, not the number of possible types. There is one excludable, nonrivalrous project, so \(m=1\). Valuations \(0\le v_1<\cdots<v_\tau\le1\) and the fixed per-capita construction cost \(\kappa>0\) are binary rationals. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A menu assigns each reported support type a service fraction \(x_j\in[0,1]\) and an average payment \(p_j\ge0\). Fractions are admission probabilities, and utility is evaluated in expectation; reports range over the support, with truthful reporting required only to be weakly optimal.
Maximize \(\sum_j\mu_jx_j\), subject to \(v_jx_j-p_j\ge v_jx_k-p_k\) for every \(j,k\), \(v_jx_j-p_j\ge0\) for every \(j\), and \(\sum_j\mu_jp_j=\kappa\). Report infeasibility if no construction-financing menu exists.
A threshold menu has \(t\in[0,1]\), assigns \(x_j=1\) when \(v_j>t\), \(x_j=0\) when \(v_j<t\), permits \(x_j\in[0,1]\) when \(v_j=t\), and sets \(p_j=tx_j\); it must satisfy the same financing equality.
Is exact served-mass maximization polynomial-time solvable, or is its decision version with a binary-rational served-mass target \(q\in[0,1]\) NP-hard?
For which feasible inputs does some threshold menu attain the optimum?
For finite agents with i.i.d. valuations and a differentiable density on \([0,1]\), equal sharing by the largest willing coalition maximizes expected participation for two agents under log-concavity, and for three agents under log-concavity and a nonincreasing density. The comparison class assigns each coalition nonnegative shares summing to construction cost, weakly decreasing as the coalition expands, and selects its largest willing coalition. [Wang et al.](https://ifmas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p1380.pdf)
No result settling this exact finite-support mass-menu problem was located in the literature search.
Exact served-mass maximization is polynomial-time solvable. For \(m=1\), an exact algorithm uses \(O(\tau^2L^2)\) bit operations and either reports infeasibility or returns an optimal rational menu.
Threshold menus are not always optimal. Below is a necessary-and-sufficient criterion for threshold optimality, expressed entirely in the input data.
Define the tail masses and tail revenues by
\(S_i=\sum_{j=i}^{\tau}\mu_j,\qquad a_i=v_iS_i,\qquad A=\max_{1\le i\le\tau}a_i.\)
Thus \(S_1=1\), and the strict positivity of the masses gives \(S_1>S_2>\cdots>S_\tau>0\).
Lemma 1. Every incentive-compatible menu has a monotone allocation:
\(0\le x_1\le\cdots\le x_\tau\le1.\)
For such an allocation, put \(x_0=0\) and \(y_i=x_i-x_{i-1}\). The componentwise largest payments compatible with incentive compatibility and individual rationality are
\(\overline p_j=\sum_{i=1}^{j}v_i y_i.\)
These payments are nonnegative, and their total revenue is
\(R(y)=\sum_{j=1}^{\tau}\mu_j\overline p_j=\sum_{i=1}^{\tau}a_i y_i.\)
The served mass is
\(s(y)=\sum_{j=1}^{\tau}\mu_jx_j=\sum_{i=1}^{\tau}S_i y_i.\)
Proof. Adding the incentive constraints for types \(j\) and \(k\) gives
\((v_j-v_k)(x_j-x_k)\ge0.\)
Because valuations are strictly ordered, allocations are monotone.
Individual rationality gives \(p_1\le v_1x_1\). The incentive constraint preventing type \(j\) from reporting \(j-1\) gives
\(p_j-p_{j-1}\le v_j(x_j-x_{j-1}).\)
Telescoping proves \(p_j\le\overline p_j\).
Conversely, the proposed payments satisfy individual rationality because
\(\overline p_j=\sum_{i=1}^{j}v_i y_i\le v_j\sum_{i=1}^{j}y_i=v_jx_j.\)
For \(j>k\),
\(v_k(x_j-x_k)\le\overline p_j-\overline p_k=\sum_{i=k+1}^{j}v_i y_i\le v_j(x_j-x_k).\)
The right inequality prevents type \(j\) from reporting \(k\), and the left inequality prevents type \(k\) from reporting \(j\). Thus all incentive constraints hold. Nonnegativity follows from \(v_i,y_i\ge0\). Finally, interchanging finite sums gives the revenue and served-mass identities. \(\square\)
Proposition 2. A construction-financing menu exists if and only if \(\kappa\le A\).
Proof. Every feasible menu satisfies
\(\kappa=\sum_j\mu_jp_j\le R(y)=\sum_i a_i y_i\le A,\)
where the last inequality uses \(\sum_i y_i=x_\tau\le1\).
Conversely, suppose \(\kappa\le A\), and choose \(h\) with \(a_h=A\). Since \(\kappa>0\), necessarily \(A>0\). Set \(y_h=\kappa/A\) and all other increments to zero. Lemma 1 supplies an admissible menu with revenue exactly \(\kappa\). \(\square\)
If \(\kappa\le v_1\), the optimal served mass is \(1\): take \(x_j=1\) and \(p_j=\kappa\) for every type. Incentive compatibility holds because all reports have the same outcome; individual rationality follows from \(v_j\ge v_1\ge\kappa\).
It remains to consider
\(v_1<\kappa\le A.\)
Consider the following auxiliary optimization problem:
maximize \(s(y)=\sum_i S_i y_i\), subject to
\(y_i\ge0,\qquad \sum_i y_i\le1,\qquad R(y)=\sum_i a_i y_i\ge\kappa.\)
Every financing menu supplies a feasible point of this problem, so its optimum is initially only an upper bound.
Lemma 3. Every optimum of the auxiliary problem satisfies
\(R(y)=\kappa,\qquad \sum_i y_i=1.\)
Consequently, its optimum equals the optimal served mass of the original menu problem.
Proof. The feasible region is nonempty and compact, so an optimum exists. Let \(e_1\) denote the vector whose first coordinate is \(1\) and whose other coordinates are zero. It has revenue \(v_1\) and served mass \(1\).
Suppose a feasible \(y\) has \(R(y)>\kappa\). Define
\(\theta=\frac{\kappa-v_1}{R(y)-v_1},\qquad y'=\theta y+(1-\theta)e_1.\)
Then \(0<\theta<1\), and \(R(y')=\kappa\). Moreover, \(s(y)<1\): equality would force every \(x_j=1\), since every mass is positive, and hence would force \(y=e_1\) and \(R(y)=v_1<\kappa\). Therefore
\(s(y')=\theta s(y)+(1-\theta)>s(y).\)
Thus an optimum cannot have revenue strictly above \(\kappa\).
Now suppose \(c=\sum_i y_i<1\). Replacing \(y\) by \(y+(1-c)e_1\) preserves all auxiliary constraints: revenue increases by the nonnegative quantity \((1-c)v_1\). Served mass increases by \(1-c>0\). Thus an optimum must have \(c=1\).
At an auxiliary optimum, Lemma 1 supplies admissible payments with revenue \(R(y)=\kappa\). This attains the auxiliary upper bound in the original problem. \(\square\)
This establishes a useful stronger statement: when \(\kappa>v_1\), every optimal financing menu has
\(x_\tau=1,\qquad R(y)=\kappa,\qquad p_j=\overline p_j\text{ for every }j.\)
Indeed, its allocation must also optimize the auxiliary problem. Furthermore, \(p_j\le\overline p_j\), and equality of their weighted sums, together with \(\mu_j>0\), forces equality coordinatewise.
There is an optimal increment vector with at most two positive coordinates.
To prove this without invoking linear-programming algorithms, choose an optimum with the smallest number of positive coordinates. If it has at least three, there is a nonzero vector \(d\), supported on those coordinates, satisfying
\(\sum_i d_i=0,\qquad \sum_i a_i d_i=0.\)
Small perturbations in either direction preserve nonnegativity and both equalities. If \(\sum_i S_i d_i\ne0\), one direction improves the objective, a contradiction. Otherwise, move along \(d\) until a positive coordinate becomes zero. This preserves optimality and contradicts minimality of the support.
If two positive coordinates have equal revenues, retaining only the one with larger \(S_i\) weakly improves the objective and reduces the support. Hence a two-coordinate optimum can be chosen with distinct revenues.
It follows that, for \(v_1<\kappa\le A\), the optimum \(V(\kappa)\) is the maximum of the following candidates:
This candidate set is nonempty: \(a_1=v_1<\kappa\), while some \(a_k\ge\kappa\).
For a maximizing pair, take
\(y_i=\frac{a_k-\kappa}{a_k-a_i},\qquad y_k=\frac{\kappa-a_i}{a_k-a_i},\)
with all other coordinates zero. Recover the optimal menu using
\(x_j=\sum_{\ell\le j}y_\ell,\qquad p_j=\sum_{\ell\le j}v_\ell y_\ell.\)
Geometrically, \(V(\kappa)\) is the greatest second coordinate among convex combinations of the points \((a_i,S_i)\) whose first coordinate is \(\kappa\).
Assume the input is feasible.
If \(\kappa\le v_1\), a threshold menu is optimal: choose \(t=\kappa\) and serve everyone, including the whole atom at \(v_1\) if \(t=v_1\).
For the remaining case \(\kappa>v_1\), define the following test for an index \(i\ge2\).
First require
\(a_i=\kappa,\qquad a_j<a_i\text{ for every }j<i.\)
When this holds, define
\(\displaystyle B_i=\max_{j<i}\frac{S_j-S_i}{a_i-a_j},\)
and
\(\displaystyle U_i=\min_{\substack{j>i\\a_j>a_i}}\frac{S_i-S_j}{a_j-a_i},\)
where \(U_i=+\infty\) if its indexing set is empty.
Theorem 4. Some threshold menu attains the optimum if and only if either:
In the second case, an optimal threshold is \(t=v_i\), serving every type \(j\ge i\) fully and excluding every type \(j<i\).
Suppose \(\kappa>v_1\) and a threshold menu is optimal. The stronger statement following Lemma 3 applies.
If the threshold equals no support valuation, its nonempty served set is a full tail beginning at some \(i\), with \(t<v_i\). Its actual revenue is \(tS_i\), while its maximal revenue is \(v_iS_i>tS_i\). This contradicts \(R(y)=\kappa\).
Now suppose \(t=v_i\), and let \(\alpha=x_i\).
If \(i<\tau\), the nonzero allocation increments are \(y_i=\alpha\) and \(y_{i+1}=1-\alpha\). Its actual and maximal revenues differ by
\(\displaystyle R(y)-\kappa=(1-\alpha)(v_{i+1}-v_i)S_{i+1}.\)
Strictly increasing valuations and positive tail masses imply that this difference vanishes only when \(\alpha=1\).
If \(i=\tau\), optimality requires \(x_\tau=1\), again giving \(\alpha=1\).
Thus an optimal threshold must serve a whole tail at price \(v_i\), and consequently must satisfy \(\kappa=a_i\).
Suppose the full tail beginning at \(i\) is optimal.
If some \(j<i\) has \(a_j\ge a_i=\kappa\), then \(e_j\) is feasible for the auxiliary problem and serves \(S_j>S_i\), contradicting optimality. Hence every earlier revenue is strictly smaller.
Suppose now that \(B_i>U_i\). Then \(U_i\) is finite, and there are indices \(j<i<k\), with \(a_j<a_i<a_k\), such that
\(\displaystyle \frac{S_j-S_i}{a_i-a_j}>\frac{S_i-S_k}{a_k-a_i}.\)
Put \(D_j=a_i-a_j>0\) and \(D_k=a_k-a_i>0\). The convex combination assigning weights \(D_k/(D_j+D_k)\) and \(D_j/(D_j+D_k)\) to \(e_j\) and \(e_k\), respectively, has revenue \(a_i\). Its served mass exceeds \(S_i\) by
\(\displaystyle \frac{D_jD_k}{D_j+D_k}\left(\frac{S_j-S_i}{D_j}-\frac{S_i-S_k}{D_k}\right)>0.\)
This contradicts optimality. Therefore \(B_i\le U_i\).
Suppose the stated requirements hold. Choose a finite \(\lambda\) satisfying \(B_i\le\lambda\le U_i\); choosing \(\lambda=B_i\) suffices. Since \(i\ge2\), \(B_i>0\).
For every \(j\),
\(S_j+\lambda a_j\le S_i+\lambda a_i.\)
For \(j<i\), this is precisely the lower-bound condition defining \(B_i\). For \(j>i\) with \(a_j>a_i\), it follows from the upper-bound condition defining \(U_i\). For \(j>i\) with \(a_j\le a_i\), it follows from \(S_j<S_i\) and \(\lambda\ge0\).
Write \(C=S_i+\lambda a_i>0\). Every feasible auxiliary allocation satisfies
\(\displaystyle s(y)+\lambda R(y)=\sum_j y_j(S_j+\lambda a_j)\le C\sum_jy_j\le C.\)
Since \(R(y)\ge\kappa=a_i\), this gives
\(s(y)\le C-\lambda R(y)\le C-\lambda a_i=S_i.\)
The full tail beginning at \(i\) attains \(S_i\) and finances construction exactly. It is therefore optimal. \(\square\)
Take
\(\displaystyle (v_1,v_2,v_3)=\left(0,\frac12,1\right),\qquad (\mu_1,\mu_2,\mu_3)=\left(\frac12,\frac14,\frac14\right),\qquad \kappa=\frac18.\)
Then
\(\displaystyle (S_1,S_2,S_3)=\left(1,\frac12,\frac14\right),\qquad (a_1,a_2,a_3)=\left(0,\frac14,\frac14\right).\)
The menu
\(\displaystyle (x_1,x_2,x_3)=\left(\frac12,1,1\right),\qquad (p_1,p_2,p_3)=\left(0,\frac14,\frac14\right)\)
is admissible by Lemma 1, raises \(\kappa=1/8\), and serves mass \(3/4\).
It is optimal because \(S_i+2a_i\le1\) for every \(i\). Hence every feasible menu satisfies
\(s(y)+2R(y)\le1,\qquad s(y)\le1-2\kappa=\frac34.\)
The best threshold serves only mass \(1/2\). Specifically:
Thus the optimum is strictly larger than every threshold menu’s served mass.
Compute the tail masses and revenues, test \(\kappa\le A\), and then enumerate the singleton and pair candidates. This uses \(O(\tau^2)\) rational arithmetic operations. The threshold criterion requires at most another \(O(\tau^2)\) operations.
All intermediate numbers can be represented with \(O(L)\) bits. For example, tail masses can use the product of the input mass denominators as a common denominator; its bit length is at most \(O(L)\). Each candidate and comparison subsequently involves only a constant number of arithmetic operations on such numbers. Using elementary integer arithmetic gives \(O(\tau^2L^2)\) bit operations for the stipulated \(m=1\). The output menu also has polynomial encoding length.
For the decision problem, compare the computed optimum with \(q\) by exact rational arithmetic. Therefore the decision problem belongs to \(\mathrm{P}\); NP-hardness under polynomial-time many-one reductions would imply \(\mathrm{P}=\mathrm{NP}\).
The finite-agent model in [Wang et al.](https://ifmas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p1380.pdf) imposes financing at each profile where construction occurs. Here financing is an equality of support-weighted average payments. The proof above addresses the stated mass-menu model directly and requires no density or log-concavity hypothesis.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions correctly. The optimization algorithm, feasibility test, and necessary-and-sufficient threshold criterion are rigorous. I found no major or minor mathematical issues.
The argument uses the stated support size \(\tau\), positive masses, strictly increasing valuations, admission probabilities, expected utility, weak incentive compatibility, nonnegative payments, and the support-weighted financing equality.
It does not replace the support by a larger type space or impose financing separately at realized valuation profiles. All conclusions concern the stipulated case \(m=1\).
Adding the two incentive constraints correctly gives
\[
(v_j-v_k)(x_j-x_k)\ge0.
\]
Strict ordering of valuations therefore implies monotone allocations.
With \(x_0=0\), the increments satisfy \(y_i\ge0\) and \(\sum_i y_i=x_\tau\le1\). Individual rationality for type \(1\), followed by the adjacent downward-report constraints, gives the claimed componentwise bound
\[
p_j\le\sum_{i=1}^j v_i y_i.
\]
The proposed maximal payments simultaneously satisfy individual rationality and every incentive constraint. The displayed inequalities for \(j>k\) establish both reporting directions; equality is permitted under the task’s weak-optimality requirement. Nonnegativity also follows directly.
The revenue and served-mass identities correctly result from interchanging finite sums. No assumption about a continuous type domain is used.
The necessity argument correctly bounds actual revenue by maximal revenue and then by \(A\), using nonnegative increments and \(\sum_i y_i\le1\).
For sufficiency, the allocation with its sole increment equal to \(\kappa/A\) is admissible because feasibility of the inequality and \(\kappa>0\) imply \(A>0\) and \(0<\kappa/A\le1\). Its maximal payments raise exactly \(\kappa\).
Consequently, the stated feasibility characterization is exact, including the case \(A=0\), which is necessarily infeasible.
The constant menu has identical outcomes across reports, nonnegative payments, individual rationality, and revenue exactly \(\kappa\). Its served mass is \(1\), the universal upper bound.
The corresponding threshold construction is valid. When \(\kappa=v_1\), full admission of the tied atom is expressly permitted.
The auxiliary problem is a valid upper bound: every financing menu has maximal revenue at least its actual revenue \(\kappa\).
The feasible region is nonempty by Proposition 2 and compact. In the regime \(v_1<\kappa\), the interpolation parameter satisfies \(0<\theta<1\), and interpolation with \(e_1\) preserves nonnegativity and the allocation bound while setting revenue to \(\kappa\).
The strict objective improvement is justified. Served mass \(1\) would force every allocation to equal \(1\), because all masses are positive; this would force the increment vector to be \(e_1\), whose revenue is insufficient in this regime.
The second improvement argument also holds when \(v_1=0\): adding the missing increment at coordinate \(1\) strictly increases served mass and never decreases revenue.
Thus every auxiliary optimum has revenue exactly \(\kappa\) and total increment \(1\). Lemma 1 then supplies payments attaining the auxiliary objective with exact financing. The equality of the original and auxiliary optimum follows.
The subsequent stronger statement about every optimal financing menu is also justified: its allocation must attain the auxiliary optimum, and equality of weighted revenues forces componentwise equality of actual and maximal payments because every mass is strictly positive.
The minimal-support argument is valid. With at least three positive coordinates, the two homogeneous equalities admit a nonzero supported direction. Sufficiently small perturbations in both directions preserve nonnegativity.
A nonzero objective derivative would contradict optimality. Otherwise, moving to the boundary preserves both equalities and the objective while reducing support. The direction has both positive and negative coordinates because its coordinate sum is zero, so the stated boundary move is available.
Equal-revenue coordinates can correctly be consolidated into the coordinate with larger tail mass. Hence the singleton and distinct-revenue pair candidates exhaust some optimal solution.
The pair weights, objective formula, and reconstructed menu are correct. The candidate set is nonempty: either some revenue equals \(\kappa\), or the revenue \(a_1=v_1<\kappa\) can be paired with a revenue strictly exceeding \(\kappa\).
For an optimal threshold whose price equals no support valuation, positive financing ensures a nonempty served tail. Its price is strictly below the first served valuation, so actual revenue is strictly below maximal revenue. This contradicts Lemma 3.
When \(t=v_i\) and \(i<\tau\), the increment representation and revenue difference
\[
R(y)-\kappa=(1-\alpha)(v_{i+1}-v_i)S_{i+1}
\]
are correct. Strict valuation ordering and positive masses force \(\alpha=1\). At \(i=\tau\), the requirement \(x_\tau=1\) gives the same conclusion.
Thus the necessary condition \(\kappa=a_i\) is established. In the regime \(\kappa>v_1\), such an index cannot be \(1\).
An earlier index with revenue at least \(a_i=\kappa\) supplies an auxiliary-feasible allocation with strictly larger served mass. Hence the strict earlier-revenue requirements are necessary.
If \(B_i>U_i\), finiteness of the indexing sets ensures that the displayed violating indices exist. The proposed convex-combination weights sum to \(1\), are positive, and give revenue exactly \(a_i\).
Rechecking the served-mass difference confirms the displayed expression and its positive sign. This contradicts optimality, proving necessity of \(B_i\le U_i\).
The earlier-revenue requirements make all denominators defining \(B_i\) positive. Since \(i\ge2\), its indexing set is nonempty and \(B_i>0\).
Choosing \(\lambda=B_i\) works even when \(U_i=+\infty\). The three cases considered in the proof correctly establish the supporting inequality for every index.
The bound using \(C\sum_j y_j\le C\) is valid because \(C>0\). The final use of \(R(y)\ge\kappa\) has the correct inequality direction because \(\lambda\ge0\).
The full tail at price \(v_i\) attains the bound and finances exactly. The characterization therefore covers every feasible input.
The stated tails and revenues are correct. The proposed menu has increments \((1/2,1/2,0)\), so its payments agree with Lemma 1. Its revenue is \(1/8\) and its served mass is \(3/4\).
The inequalities \(S_i+2a_i\le1\), together with total increment at most \(1\) and maximal revenue at least \(\kappa\), correctly certify optimality.
The threshold case analysis covers the entire permitted price interval. Its financing calculations are correct, including the tied atoms at prices \(1/2\) and \(1\). The best threshold served mass is indeed \(1/2\).
Candidate enumeration and threshold testing require \(O(\tau^2)\) rational operations. The common-denominator explanation supports \(O(L)\)-bit tail quantities. Each candidate and comparison uses only a constant number of operations on such quantities.
The reconstructed optimal menu has at most two nonzero increments, so its cumulative allocation and payment entries also have polynomial encoding length. Elementary exact arithmetic supports the claimed \(O(\tau^2L^2)\) bit-operation bound for \(m=1\). Comparing the optimum with the input target adds only polynomial work.
The boundary cases are covered: \(\tau=1\), \(v_1=0\), \(A=0\), \(\kappa=v_1\), \(\kappa=A\), equal tail revenues, and an empty indexing set for \(U_i\).
The distinction from the cited finite-agent model is accurate: that paper requires payments to sum to construction cost whenever the project is built. No theorem from it is needed by this proof. [Wang et al., model description](https://ifmas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p1380.pdf)
No repair or additional mathematical clarification 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.