d4-conf-sagt-2010-0002 (d4-conf-sagt-2010-0002)

Given \(n\) divisible goods of unit supply and two cohort types \(r\in\{1,2\}\), with rational masses \(\lambda_r>0\) summing to \(1\), common linear utilities \(u_r\), and per-person budgets \(b_r\), each cohort’s shared authority submits one nonzero utility report. Its aggregate budget is \(M_r=\lambda_r b_r\), and its payoff is its total true utility under the paper’s Fisher-market rules and equilibrium-allocation payoff selection. Describe all pure Nash equilibrium report pairs, with their prices and induced allocations.

A society is given by its support: the list of its \(\tau=2\) types with positive binary-rational masses \(\lambda_r\), where \(\lambda_1+\lambda_2=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) divisible goods, each of unit supply. Type \(r\) has strictly positive rational linear utility coefficients \(u_{rj}\) and a positive rational per-person budget \(b_r\). Its authority controls aggregate budget \(M_r=\lambda_rb_r\) and reports \(s_r\in\mathbb R_{\geq0}^{m}\) with \(\sum_j s_{rj}=1\).
For reports \(s=(s_1,s_2)\), let \(p(s)\) and \(\mathcal X(s)\) be the prices and aggregate equilibrium allocations of the linear Fisher market with reported utilities \(s_r\) and budgets \(M_r\), requiring full allocation of every good, including zero-price goods, and full budget expenditure. Thus \(\sum_jp_j=M_1+M_2\).
For aggregate allocation \(x\), set \(U_r(x)=\sum_j u_{rj}x_{rj}\). Select allocations in \(\mathcal A(s)=\operatorname*{arg\,max}_{x\in\mathcal X(s)}U_1(x)U_2(x)\), and define authority payoff \(P_r(s)=U_r(x)\) for a selected allocation; all maximizers have the same payoff vector. Retain every maximizing allocation when describing outcomes.
Only authorities may deviate, changing their entire cohort's report. Let \(L\) denote the total binary input length, including any queried rational reports; state running times in \(m,\tau,L\).

What is the exact set of pure Nash equilibrium report pairs, their prices, and their selected aggregate allocations?
Is membership in this set, for a given rational report pair, decidable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For two individual buyers, all normalized pure Nash equilibria are symmetric and admit an exact characterization by at most \(2m-1\) convex polyhedral regions. [Verified characterization](https://arxiv.org/abs/1002.4832v3).
No separate characterization or complexity result for this precise cohort-authority formulation was located.

The equilibrium set has an exact polyhedral characterization, and membership is decidable in polynomial time. Cohort masses enter only through the aggregate budgets \(M_r=\lambda_rb_r\).

The aggregation produces exactly two strategic Fisher buyers, with true utilities \(u_r\), budgets \(M_r\), and the stated allocation selector. The cited paper uses the same product-of-true-utilities selector. [Adsul et al., Section 2](https://arxiv.org/pdf/1002.4832). The proof below also handles zero report coordinates explicitly.

1. Exact characterization. Define
\[ \]
\(B=M_1+M_2\), \(a=M_1/B\), and \(a_2=1-a=M_2/B\). Thus \(0<a<1\).

Relabel the goods so that
\[ \]
\(u_{11}/u_{21}\geq u_{12}/u_{22}\geq\cdots\geq u_{1m}/u_{2m}\),
breaking ties arbitrarily. For \(q\in\mathbb R^m\), write \(Q_k=\sum_{j=1}^kq_j\), with \(Q_0=0\).

All regions below include the constraints \(q_j\geq0\) and \(\sum_jq_j=1\).

For each \(k\in\{1,\ldots,m\}\), define the closed convex polyhedron \(\mathcal B_k\) by

• \(Q_{k-1}\leq a\leq Q_k\);
• \(u_{1i}q_j\geq u_{1j}q_i\) for every \(i\leq k\leq j\);
• \(u_{2i}q_j\leq u_{2j}q_i\) for every \(i\leq k\leq j\).

For each \(k\in\{1,\ldots,m-1\}\), define the closed convex polyhedron \(\mathcal C_k\) by

• \(Q_k=a\);
• \(u_{1i}q_j\geq u_{1j}q_i\) for every \(i\leq k<j\);
• \(u_{2i}q_j\leq u_{2j}q_i\) for every \(i\leq k<j\).

Set
\[ \]
\(\mathcal Q=\bigcup_{k=1}^m\mathcal B_k\;\cup\;\bigcup_{k=1}^{m-1}\mathcal C_k\).

The complete set of pure Nash equilibrium report pairs is
\[ \]
\(\{(q,q):q\in\mathcal Q\}\).

Every \(q\in\mathcal Q\) is strictly positive. Its equilibrium prices are
\[ \]
\(p_j=Bq_j\).

Here is the complete allocation description. Define the canonical allocation to authority \(1\) by
\[ \]
\(z_j=\min\{1,\max\{0,(a-Q_{j-1})/q_j\}\}\),
and let
\[ \]
\(V_1=\sum_ju_{1j}z_j,\qquad V_2=\sum_ju_{2j}(1-z_j)\).

All selected aggregate allocations, without discarding ties, are precisely
\[ \]
\(\mathcal A(q,q)=\{(x,\mathbf1-x):0\leq x_j\leq1,\ \sum_jq_jx_j=a,\ \sum_ju_{1j}x_j=V_1,\ \sum_ju_{2j}(1-x_j)=V_2\}\).

The remainder proves these claims.

2. Market conditions and a universal deviation bound. At any report profile and equilibrium allocation, there are constants \(c_r>0\) such that
\[ \]
\(p_j\geq c_rs_{rj},\qquad x_{rj}>0\Longrightarrow p_j=c_rs_{rj}\).

These are the linear Fisher optimality conditions. A positive reported coefficient cannot have zero price, because then the buyer’s budget-constrained demand problem would be unbounded. A zero-price good therefore has zero reported coefficient for both buyers; allocating it preserves these conditions.

Fix one authority, with budget \(M\), true coefficients \(u_j>0\), and budget fraction \(\alpha=M/B\). Fix the other authority’s normalized report \(t\), allowing zeros. Define the fractional-knapsack value
\[ \]
\(W(u,t,\alpha)=\max\{\sum_ju_jy_j:0\leq y_j\leq1,\ \sum_jt_jy_j\leq\alpha\}\).

Consider any unilateral report and any resulting equilibrium allocation \(x\) to the deviating authority. The other authority’s optimality conditions give \(p_j\geq ct_j\), with equality wherever it receives a positive quantity. Consequently,
\[ \]
\(B-M=c\sum_jt_j(1-x_j)=c(1-T),\qquad M=\sum_jp_jx_j\geq cT\),
where \(T=\sum_jt_jx_j\).

Combining these equalities and inequalities gives \(T\leq M/B=\alpha\). Therefore every unilateral deviation satisfies
\[ \]
\(\sum_ju_jx_j\leq W(u,t,\alpha)\).

This bound applies to every equilibrium allocation, hence also to the selected allocation.

3. The bound is the exact supremum over deviations. Let \(S=\sum_ju_j\). For \(\varepsilon>0\), report the normalization of
\[ \]
\(v_j=t_j+\varepsilon u_j\).
Scaling a report by a positive constant does not change its demand, so we can work with \(v\) directly.

Take any equilibrium allocation \(x\) under this deviation. All prices are positive because \(v_j>0\). There are constants \(c,d>0\) satisfying
\[ \]
\(p_j\geq cv_j,\qquad p_j\geq dt_j\),
with equality in the first inequality when \(x_j>0\), and in the second when \(x_j<1\).

Write \(T=\sum_jt_jx_j\) and \(V=\sum_ju_jx_j\). Full expenditure gives
\[ \]
\(M=c(T+\varepsilon V)\).
Summing \(p_j\geq cv_j\) gives \(B\geq c(1+\varepsilon S)\). Hence
\[ \]
\(T+\varepsilon V\geq\alpha(1+\varepsilon S)\),
and, since \(V\leq S\),
\[ \]
\(\alpha-\varepsilon S\leq T\leq\alpha\).

We next show that \(x\) maximizes true utility under knapsack capacity \(T\). The other authority spends a positive budget, so it receives some good \(k\) with \(t_k>0\). Thus
\[ \]
\(dt_k=p_k\geq c(t_k+\varepsilon u_k)\),
which implies \(d/c>1\). Put \(\theta=(d/c-1)/\varepsilon>0\).

The optimality conditions imply
\[ \]
\(x_j>0\Longrightarrow u_j\geq\theta t_j,\qquad x_j<1\Longrightarrow u_j\leq\theta t_j\).

For any \(y\in[0,1]^m\), these inequalities give, coordinate by coordinate,
\[ \]
\((u_j-\theta t_j)(y_j-x_j)\leq0\).
If additionally \(t\cdot y\leq T=t\cdot x\), summing yields \(u\cdot y\leq u\cdot x\).

Let \(y^\star\) attain \(W=W(u,t,\alpha)\). The vector \((T/\alpha)y^\star\) is feasible for capacity \(T\), so
\[ \]
\(V\geq(T/\alpha)W\geq W-\varepsilon SW/\alpha\geq W-\varepsilon S^2/\alpha\).

This estimate holds for every equilibrium allocation under the deviation. Taking \(\varepsilon\) arbitrarily small proves
\[ \]
\(\sup_{\text{unilateral reports}}P=W(u,t,\alpha)\).

Consequently, a profile is a Nash equilibrium exactly when each authority already receives its corresponding knapsack value against the other report.

4. Every Nash equilibrium has identical, strictly positive reports. First observe two properties of any optimizer in the definition of \(W(u,t,\alpha)\):

• Every coordinate with \(t_j=0\) equals \(1\), because \(u_j>0\).
• The budget constraint is tight. Otherwise, because \(\alpha<1=\sum_jt_j\), some coordinate with \(t_j>0\) is below \(1\); increasing it slightly improves utility.

Now suppose \(s=(s_1,s_2)\) is a Nash equilibrium, and let \((x,\mathbf1-x)\) be selected. Section 3 and budget tightness imply
\[ \]
\(s_2\cdot x=a,\qquad s_1\cdot(\mathbf1-x)=a_2\).

For authority \(2\), full expenditure therefore gives
\[ \]
\(M_2=c_2s_2\cdot(\mathbf1-x)=c_2a_2\),
so \(c_2=B\). Since \(p_j\geq Bs_{2j}\) and both sides sum to \(B\), equality holds coordinatewise: \(p=Bs_2\).

The same argument for authority \(1\) gives \(p=Bs_1\). Thus
\[ \]
\(s_1=s_2=q=p/B\).

If \(q_j=0\), both authorities’ knapsack optimizers must receive the entire good \(j\). That contradicts full allocation with unit supply. Hence \(q_j>0\) for every good.

Conversely, at a symmetric positive report \((q,q)\), the prices are \(Bq\), and the equilibrium allocations are exactly
\[ \]
\(\{(x,\mathbf1-x):x\in[0,1]^m,\ q\cdot x=a\}\).

Indeed, these allocations exhaust both budgets and all supplies, and every good has the same reported utility per unit of expenditure.

Such a profile is a Nash equilibrium if and only if some equilibrium allocation simultaneously attains both authorities’ knapsack maxima. If such an allocation exists, its product equals the product of the two individual maxima. Every product maximizer must then attain both maxima, since both are positive. Section 3 excludes any profitable deviation.

This also proves that the selection rule cannot conceal a non-equilibrium profile by choosing a favorable allocation.

5. Simultaneous optimality and the polyhedral regions. For positive \(q\), a feasible allocation \(x\), with \(q\cdot x=a\), simultaneously maximizes both authorities’ utilities exactly when
\[ \]
\[x_i>0,\ x_j<1\Longrightarrow \frac{u_{1i}}{q_i}\geq\frac{u_{1j}}{q_j}\quad\text{and}\quad\frac{u_{2i}}{q_i}\leq\frac{u_{2j}}{q_j}. \tag{*}\]

For necessity, transfer a sufficiently small amount of expenditure between goods \(i\) and \(j\). Violating the first inequality improves authority \(1\)’s utility; violating the second improves authority \(2\)’s utility.

For sufficiency for authority \(1\), choose a positive threshold between
\[ \]
\(\max_{x_j<1}u_{1j}/q_j\quad\text{and}\quad\min_{x_i>0}u_{1i}/q_i\).
Both indexing sets are nonempty because \(0<a<1\). Condition \((*)\) makes this interval nonempty. The same coordinatewise threshold argument used in Section 3 proves global knapsack optimality. Applying it to \(\mathbf1-x\) proves optimality for authority \(2\).

We now justify the canonical allocation. Suppose a simultaneously optimal allocation has an inversion: \(i<j\), \(x_i<1\), and \(x_j>0\). Condition \((*)\) gives
\[ \]
\(\frac{u_{1j}}{q_j}\geq\frac{u_{1i}}{q_i},\qquad \frac{u_{2j}}{q_j}\leq\frac{u_{2i}}{q_i}\).
Together with the chosen ordering \(u_{1i}/u_{2i}\geq u_{1j}/u_{2j}\), these force equality in both displayed inequalities.

We may therefore transfer expenditure from good \(j\) to good \(i\), preserving both true utilities and the budget, until \(x_i=1\) or \(x_j=0\). Processing goods in increasing order eliminates all inversions after finitely many such transfers. The resulting allocation is exactly \(z\): a prefix assigned to authority \(1\), then at most one shared good, then a suffix assigned to authority \(2\).

If \(z\) has a genuinely shared good \(k\), condition \((*)\) gives the inequalities of \(\mathcal B_k\). If it has no shared good, its cutoff \(k\) satisfies \(Q_k=a\), and \((*)\) gives the inequalities of \(\mathcal C_k\). Thus every Nash equilibrium belongs to the claimed union.

For the converse, first check that each region forces positivity.

• In \(\mathcal B_k\), if \(q_k=0\), the first family of inequalities with \(j=k\) forces every \(q_i=0\) for \(i\leq k\); the second family with \(i=k\) forces every \(q_j=0\) for \(j\geq k\). This contradicts \(\sum_jq_j=1\). With \(q_k>0\), the remaining inequalities force every coordinate positive.
• In \(\mathcal C_k\), a zero coordinate in the prefix forces the entire suffix to be zero, contradicting its mass \(1-a>0\). A zero coordinate in the suffix similarly contradicts prefix mass \(a>0\).

For \(q\in\mathcal B_k\), the canonical allocation has
\[ \]
\(z_i=1\ (i<k),\qquad z_k=(a-Q_{k-1})/q_k,\qquad z_j=0\ (j>k)\).
The region inequalities imply every comparison required by \((*)\), including when \(z_k\) is an endpoint. For \(q\in\mathcal C_k\), the canonical allocation is the prefix–suffix split, and the same conclusion follows.

Hence every point in the union yields a Nash equilibrium. This completes the polyhedral characterization.

6. Why the allocation description retains every maximizer. At an equilibrium report, \(z\) simultaneously attains the individual maxima \(V_1,V_2\). Every market allocation has utilities at most these values. Because \(V_1,V_2>0\), its product equals the maximum \(V_1V_2\) exactly when both utility equalities hold.

Therefore the allocation polytope in Section 1 is precisely \(\mathcal A(q,q)\). It includes all possible reallocations among tied goods that preserve the maximizing payoff vector.

More generally, the selector is well-defined even at boundary reports: the equilibrium-allocation set is compact and convex, and positive budgets with strictly positive true coefficients make both true utilities positive. Strict concavity of \(\log U_1+\log U_2\) in the utility vector implies that all product maximizers have the same payoff vector.

7. Polynomial-time membership and outcome computation. For a queried rational report pair:

• Check nonnegativity and normalization.
• Reject if \(s_1\neq s_2\), or if their common report \(q\) has a zero coordinate.
• Compute \(M_1,M_2,B,a\), and sort the goods by \(u_{1j}/u_{2j}\).
• Construct the canonical allocation \(z\) by cumulative sums.
• Check \((*)\) for every pair with \(z_i>0\) and \(z_j<1\).

Acceptance is equivalent to Nash equilibrium membership. On acceptance, compute \(p=Bq\), \(V_1,V_2\), and output the allocation polytope above.

Sorting requires \(O(m\log m)\) rational comparisons; the final test requires \(O(m^2)\). Exact rational arithmetic has polynomial bit complexity in the total input length \(L\). Thus the running time is
\[ \]
\(O(\tau m^2\operatorname{poly}(L))\), with \(\tau=2\).

The full region description has \(O(m^3)\) inequalities and can be generated in \(O(\tau m^3\operatorname{poly}(L))\) time. The selected-allocation polytope for an accepted query has \(m\) variables, box constraints, and three affine equalities.

For \(m=1\), the characterization reduces to the unique report pair \(((1),(1))\), price \(B\), and allocation \((a,1-a)\).

⟨structured verdict parsed — rendered above⟩

Assessment

The target is resolved in substance, with one minor expositional gap. The proof establishes the exact equilibrium reports, prices, and all selected allocations, together with polynomial-time membership. I found no false central step or missing argument requiring new mathematics.

The minor gap concerns the supplementary assertion that the equilibrium-allocation set is compact and convex at arbitrary boundary reports. Those properties are asserted without justification. The task already stipulates that the selector gives a unique payoff vector, so this omission does not undermine the main characterization.

Step-by-step verification

1. Aggregation and the cited model

The reduction to two strategic buyers is valid under the task’s definitions. Each authority controls precisely one report and aggregate budget \(M_r=\lambda_rb_r\), and its payoff uses aggregate utility \(U_r\). No additional strategic agents arise from the cohort masses.

The attribution concerning the selector is correct: Section 2, equation (1), of the cited paper selects an equilibrium allocation maximizing the product of true utilities. Its strategy space allows nonnegative, nonzero utility reports; positive rescaling explains the normalization used here. The paper subsequently assumes positive report coordinates for its main analysis, so the prover’s explicit boundary argument is relevant. [Adsul et al., Sections 2–3](https://arxiv.org/pdf/1002.4832)

The prover does not rely on the paper’s characterization to establish the proposed regions; Sections 2–5 supply a separate argument.

2. Universal deviation bound

The stated optimality conditions have the correct direction:

\[ p_j\geq c_rs_{rj}, \]

with equality on goods received in positive quantity. Normalization ensures each reported utility vector is nonzero. A positive reported coefficient at zero price would indeed make unconstrained budget-feasible demand unbounded. A good with zero price therefore has zero reported coefficient for both buyers.

For the fixed opponent report \(t\), the expenditure identities are valid even when some coordinates vanish. Equality is needed only where the opponent receives a positive amount. Consequently,

\[ B-M=c(1-T),\qquad M\geq cT \]

implies \(T\leq M/B\). The deviator’s allocation also satisfies the box constraints required by the knapsack problem.

Thus the bound by \(W(u,t,\alpha)\) applies to every equilibrium allocation, including every allocation selected by the product rule.

3. Exact supremum over deviations

The perturbation \(v=t+\varepsilon u\) is strictly positive and becomes an admissible report after normalization. Working with its unnormalized form is legitimate because positive scaling preserves demand.

The expenditure calculation and price summation correctly yield

\[ T+\varepsilon V\geq\alpha(1+\varepsilon S). \]

Together with \(V\leq S\) and the previous upper bound, this gives the stated estimate

\[ \alpha-\varepsilon S\leq T\leq\alpha. \]

The opponent’s positive expenditure ensures it receives some good with positive \(t_k\). The displayed inequality on that good establishes \(d/c>1\), so the threshold \(\theta\) is positive.

Both threshold implications have the correct signs. Their coordinatewise consequence proves that the resulting allocation maximizes true utility at capacity \(T\).

The scaled vector \((T/\alpha)y^\star\) is feasible: \(0\leq T/\alpha\leq1\), and its expenditure is at most \(T\). The approximation estimate

\[ V\geq W-\varepsilon S^2/\alpha \]

is therefore valid.

Crucially, this estimate holds for every equilibrium allocation under the perturbed report. Selection ambiguity cannot defeat the argument.

The passage from a supremum to the Nash condition is sound. If the current payoff is strictly below \(W\), a sufficiently small positive perturbation supplies a strictly profitable deviation. Attainment of the supremum by a report is unnecessary.

4. Symmetry and strict positivity

Both properties asserted for knapsack optimizers are correct:

• A zero-cost coordinate must be fully assigned because its true coefficient is positive.
• Capacity must be exhausted because \(\alpha<1\), leaving a positive-cost coordinate available whenever expenditure is below capacity.

At a Nash equilibrium, the selected allocations attain the knapsack bounds. Hence the two report-weighted expenditure equalities follow.

The derivation \(c_2=B\) is valid because \(a_2>0\). Coordinatewise domination \(p_j\geq Bs_{2j}\), together with equal total sums, forces equality in every coordinate. The corresponding argument for buyer 1 proves symmetry.

A zero coordinate in the common report would require both buyers to receive the whole corresponding good. This contradicts unit supply. Thus equilibrium reports are strictly positive.

For symmetric positive reports, the claimed prices and allocation set satisfy demand optimality, expenditure, and full allocation. The simultaneous-maxima criterion is also correct: both maxima are positive, and every feasible utility is bounded by its respective maximum. Product maximization therefore selects simultaneous maximizers whenever they exist.

5. Simultaneous optimality and the regions

Condition \((*)\) is correctly oriented for both buyers.

Its necessity follows from feasible expenditure transfers. Its sufficiency uses the stated threshold argument. The relevant indexing sets are nonempty because \(0<a<1\) and every \(q_j>0\). Applying the criterion to the complementary allocation gives buyer 2’s optimality.

The inversion argument is valid. The two inequalities obtained from \((*)\), combined with the ordering by \(u_{1j}/u_{2j}\), force equality in both utility-per-price comparisons. Consequently, the proposed transfers preserve both true utilities and expenditure.

The finite prefix-processing argument is sufficiently specified: transfers fill the current earlier good or empty a later good, and completed earlier coordinates need not be disturbed. Its endpoint is the canonical allocation.

The two cutoff cases are exhaustive:

• A genuinely shared good produces the required \(\mathcal B_k\) comparisons.
• An unshared cutoff satisfies \(Q_k=a\) and produces the \(\mathcal C_k\) comparisons.

The positivity checks for both region families are correct. Once positivity is established, their inequalities imply all comparisons required by \((*)\). The endpoint cases in \(\mathcal B_k\) introduce additional comparisons but do not invalidate sufficiency.

The claim is a union of at most \(2m-1\) regions; neither disjointness nor nonemptiness of every region is required.

6. All selected allocations

At an equilibrium report, the canonical allocation attains both individual maxima \(V_1,V_2\). Since both are positive, a market allocation maximizes the product exactly when it attains both utility equalities.

The displayed allocation polytope therefore retains every maximizing allocation, including ties. It does not impose the canonical prefix structure on all selected allocations.

Minor issue: The subsequent discussion of arbitrary boundary reports asserts compactness and convexity of the equilibrium-allocation set without explaining or citing those properties for the stated zero-price convention. Strict concavity establishes payoff-vector uniqueness once those properties are available; it does not establish them itself.

Minimum clarification: Supply a justification or precise reference covering nonnegative normalized reports and mandatory full allocation of zero-price goods. This concerns the supplementary well-definedness claim, not the established equilibrium characterization.

7. Complexity and edge cases

The membership algorithm implements the proved equivalences:

• Validate the reports.
• Require symmetry and positivity.
• Sort the true-utility ratios.
• Compute the canonical allocation.
• Check simultaneous optimality.

The comparison counts are correct. Rational sorting, cumulative sums, divisions by positive rational coordinates, and cross-multiplied comparisons all have polynomial bit complexity in \(L\). The stated bound \(O(\tau m^2\operatorname{poly}(L))\) is valid with \(\tau=2\).

The full region description has \(O(m^3)\) inequalities. The selected-allocation description uses \(m\) variables and three affine equalities; possible redundancy among these equalities is harmless.

For \(m=1\), normalization forces the unique report pair, and expenditure determines the stated allocation. This edge case is handled correctly.

⟨structured verdict parsed — rendered above⟩