Answer: Nonexistence can occupy an open set of positive Lebesgue measure. For fixed \(m=3\), equilibrium existence and exact equilibrium construction are polynomial-time solvable.
Theorem 5.1 — class: other
Fix \(J=\{1,2,3\}\), rational per-capita supplies \(q_j\in(0,1]\), type masses \(\mu_t>0\) summing to \(1\), and complete monotonically increasing rankings \(\succ_t\) over \(2^J\). For almost every budget vector \(b\in\mathbb{R}_{>0}^{|T|}\), can one compute positive prices \(p_j\) and assignment masses \(x_{t,S}\geq 0\) such that \(\sum_S x_{t,S}=\mu_t\), \(\sum_{t,S:j\in S}x_{t,S}=q_j\), and \(x_{t,S}>0\) only when \(S\) is a most-preferred bundle among those satisfying \(\sum_{j\in S}p_j\leq b_t\)?
Fix \(J=\{1,2,3\}\), with \(m=3\), and binary-rational supplies \(q_j\in(0,1]\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible rankings. Each type has an explicitly listed complete, transitive, weakly monotonically increasing preference relation \(\succeq_t\) over \(2^J\), including the empty bundle; indifferences are allowed.
Every individual of type \(t\) has the same per-capita budget \(b_t>0\). Money has no intrinsic value. Individuals consume subsets of \(J\), with at most one unit of each good.
An equilibrium consists of positive prices \(p_j\) and masses \(x_{t,S}\geq0\) satisfying \(\sum_{S\subseteq J}x_{t,S}=\mu_t\) and \(\sum_{t\in T}\sum_{S\ni j}x_{t,S}=q_j\) for every \(j\in J\).
Writing \(p(S)=\sum_{j\in S}p_j\), require \(x_{t,S}>0\) only if \(p(S)\leq b_t\) and \(S\succeq_t R\) for every \(R\subseteq J\) with \(p(R)\leq b_t\). Mass may split among indifferent optimal bundles; no tie-breaking rule is imposed.
For computation, budgets are positive binary rationals and \(L\) is the total input bit length; seek exact prices and assignment masses.
For every fixed society and supply vector, does equilibrium exist for Lebesgue-almost every \(b\in\mathbb{R}_{>0}^{\tau}\), or can nonexistence occupy a positive-measure set?
For rational budgets, can equilibrium existence be decided and an equilibrium computed whenever one exists in time polynomial in \(m,\tau,L\), or is deciding existence NP-hard?
Discrete: with three indivisible goods and any number of agents, equilibrium exists for almost all positive income vectors under monotonically increasing preferences, with an explicit construction ([Segal-Halevi](https://arxiv.org/html/1705.04212v6)).
Continuous nearby result: equilibrium existence is known for continuum economies with indivisible goods and quasilinear utility ([Azevedo, Weyl and White](https://knowledge.uchicago.edu/records/1btvv-6pd54)); that model gives money intrinsic utility. No result settling the exact fixed-budget model above was located.
Both questions can be settled:
The proofs below allow arbitrary splitting among indifferent optimal bundles.
A simple obstruction is that a single type with a strict ranking has a unique optimal bundle, so its aggregate consumption cannot equal fractional supplies. The following example goes further: the same society has equilibrium for an open set of budgets and nonexistence for another open set.
Take two types, denoted \(A\) and \(B\), with masses and supplies
\(\mu_A=\frac34,\qquad \mu_B=\frac14,\qquad (q_1,q_2,q_3)=\left(\frac12,\frac14,\frac14\right).\)
Type \(A\) ranks bundles solely by cardinality:
\(S\succeq_A R\quad\Longleftrightarrow\quad |S|\geq |R|.\)
Type \(B\) has the complete ranking
\(\{1,2,3\}\succ_B\{1,2\}\succ_B\{1,3\}\sim_B\{2,3\}\succ_B\{1\}\sim_B\{2\}\sim_B\{3\}\succ_B\varnothing.\)
These are distinct preference relations. Both strictly prefer every bundle to each proper subset, and both strictly prefer every larger-cardinality bundle to every smaller-cardinality bundle. All masses and supplies are positive dyadic rationals.
Fix positive prices and budgets. For each type \(t\in\{A,B\}\), define
\(k_t=\max\{|S|:S\subseteq J,\ p(S)\leq b_t\}.\)
The empty bundle is affordable, so this maximum exists and belongs to \(\{0,1,2,3\}\).
Every optimal affordable bundle for type \(t\) has cardinality \(k_t\): an affordable bundle of smaller cardinality is strictly worse than an affordable bundle attaining \(k_t\). Consequently, equilibrium assignments would satisfy
\(\sum_{S\subseteq J}|S|x_{t,S}=\mu_t k_t.\)
Summing market-clearing equations over the goods gives
\[ \text{ } \]
\(\frac34k_A+\frac14k_B=\sum_{j=1}^3q_j=1,\)
or equivalently \(3k_A+k_B=4\).
For integers \(k_A,k_B\in\{0,1,2,3\}\), the unique solution is \(k_A=k_B=1\): \(k_A=0\) would require \(k_B=4\), while \(k_A\geq2\) would require \(k_B<0\).
Thus every individual must receive a singleton in any equilibrium.
Assume an equilibrium exists. By the lemma, type \(A\)'s entire mass \(\frac34\) receives singletons.
Type \(A\) must receive positive masses of at least two distinct singleton goods. Otherwise, its mass would all consume one good \(j\), implying
\(q_j\geq\frac34,\)
contrary to \(\max_j q_j=\frac12\).
Choose distinct goods \(i,j\) whose singletons are assigned positive mass to type \(A\). Affordability implies
\(p_i\leq b_A,\qquad p_j\leq b_A.\)
Hence, if \(b_B\geq2b_A\),
\(p(\{i,j\})=p_i+p_j\leq2b_A\leq b_B.\)
Type \(B\) can therefore afford a pair, so \(k_B\geq2\). This contradicts the lemma. No equilibrium exists.
In particular, the open set
\(U=\{(b_A,b_B)\in\mathbb R_{>0}^2:b_B>2b_A\}\)
consists entirely of nonexistence instances. It has positive Lebesgue measure; for example, it contains the rectangle \((1,\frac54)\times(3,4)\).
Suppose
\(\max\{b_A,b_B\}<2\min\{b_A,b_B\}.\)
Set \(c=\min\{b_A,b_B\}\) and \(p_1=p_2=p_3=c\). Both types can afford every singleton, and neither can afford any pair. For both types, all singletons are therefore indifferent optimal bundles.
Assign
\(x_{t,\{j\}}=\mu_tq_j\)
for each type and good, and assign zero mass to every other bundle. Since \(\sum_jq_j=1\), each type receives its prescribed mass. Since \(\mu_A+\mu_B=1\), every good clears:
\(\sum_t x_{t,\{j\}}=(\mu_A+\mu_B)q_j=q_j.\)
This is an equilibrium. Thus nonexistence in the example is not an obstruction that persists for every budget vector.
Now consider any input satisfying the task's hypotheses, with rational budgets.
We use the standard rational linear-programming theorem: feasibility and optimization for rational linear programs are solvable in polynomial time in their encoding length, with exact rational feasible solutions and finite optima returned with polynomial encoding length. The programs below have explicitly polynomial encoding size.
Let \(B=\max_t b_t\).
In any equilibrium, each good \(j\) has positive supply. Its clearing equation therefore implies that some positively assigned bundle \(S\) contains \(j\). Positivity of prices and affordability yield
\(p_j\leq p(S)\leq b_t\leq B.\)
Thus it suffices to search prices satisfying \(0<p_j\leq B\).
Sort the distinct budget values as
\(0<v_1<\cdots<v_r=B,\qquad r\leq\tau.\)
Partition the positive real line into the following \(2r+1\) regions:
\((0,v_1),\ \{v_1\},\ (v_1,v_2),\ \{v_2\},\ \ldots,\ \{v_r\},\ (v_r,\infty).\)
For each of the seven nonempty bundles \(S\subseteq J\), choose a region for its price \(p(S)\). There are at most
\((2\tau+1)^7\)
such choices.
Each choice determines whether \(p(S)\leq b_t\), for every type and bundle. Indeed, no open region contains a budget value, while singleton regions explicitly record equality. The empty bundle is always affordable.
For a chosen tuple of regions, introduce variables \(p_1,p_2,p_3,\delta\), and maximize \(\delta\) subject to
\(0\leq\delta\leq1,\qquad \delta\leq p_j\leq B\quad(j\in J).\)
Add the following constraints for each nonempty bundle \(S\):
Reject the tuple if this linear program is infeasible or its optimum is zero.
This test is exact. A feasible solution with \(\delta>0\) gives positive prices satisfying every required strict inequality. Conversely, prices in the chosen regions with \(0<p_j\leq B\) have finitely many positive strict-inequality slacks. Choosing \(\delta>0\) no larger than these slacks, the prices, and \(1\), gives a feasible solution with positive objective.
The feasible set is compact because all four variables are bounded. Therefore, whenever feasible, its maximum is attained. Exact rational optimization distinguishes a positive optimum from zero.
For a surviving tuple, let \(\mathcal A_t\) be type \(t\)'s affordable bundles, and define its demand set by
\(\mathcal D_t=\{S\in\mathcal A_t:S\succeq_t R\text{ for every }R\in\mathcal A_t\}.\)
These sets are constant throughout the chosen price region. They can be computed directly from the explicitly listed preferences, using comparisons among only eight bundles.
Solve the rational linear feasibility problem
\(x_{t,S}\geq0\quad(S\in\mathcal D_t),\)
\(\sum_{S\in\mathcal D_t}x_{t,S}=\mu_t\quad(t\in T),\)
\(\sum_{t\in T}\sum_{\substack{S\in\mathcal D_t\\j\in S}}x_{t,S}=q_j\quad(j\in J).\)
Set all other assignment variables to zero. This program has at most \(8\tau\) variables and \(\tau+3\) equality constraints.
If feasible, return its assignment together with the prices found in Step 3. If every tuple is rejected or has an infeasible assignment program, report nonexistence.
Soundness. Returned prices are positive. The assignment program enforces type masses and market clearing. Every positively assigned bundle belongs to its type's demand set, so it is affordable and weakly preferred to every affordable alternative. Hence the returned objects form an equilibrium.
Completeness. Suppose an equilibrium exists. Its prices satisfy \(p_j\leq B\) by Step 1, and every nonempty bundle price belongs to exactly one enumerated region. That tuple passes Step 3. Its demand sets coincide with the equilibrium's demand sets, so the equilibrium assignment witnesses feasibility in Step 4. The algorithm therefore finds an equilibrium whenever one exists.
There are at most \((2\tau+1)^7\) tuples. For each tuple, the price program has four variables and a constant number of constraints; the assignment program has at most \(8\tau\) variables and polynomial encoding size. Sorting, preference comparisons, and exact rational linear programming all take polynomial time.
The total running time is therefore
\((2\tau+1)^7\operatorname{poly}(\tau,L),\)
which is polynomial for the stipulated \(m=3\). Both prices and assignment masses can be returned as exact rationals of polynomial bit length. No polynomial-time claim for unrestricted \(m\) is needed or asserted.
The counterexample concerns population masses and per-person bundle constraints. The finite-agent, three-item existence result in [Segal-Halevi](https://arxiv.org/html/1705.04212v6) consequently does not establish existence for this model. Likewise, [Azevedo, Weyl and White](https://knowledge.uchicago.edu/records/1btvv-6pd54) establish existence under quasilinear utility, a different demand model.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions correctly. The counterexample establishes positive-measure nonexistence for a fixed admissible society, and the algorithm decides existence and constructs an exact equilibrium in polynomial time for the stipulated \(m=3\). I found no substantive gaps or false steps.
The existence question asks whether almost-everywhere existence holds for every fixed society and supply vector. One admissible fixed society with a positive-measure set of nonexistence budgets disproves that assertion. The output supplies precisely such an example.
The computational claim is explicitly restricted to \(m=3\), as stipulated in USER_TASK. The output does not claim polynomial time when the number of goods varies.
The masses \(\mu_A=3/4\) and \(\mu_B=1/4\) are positive binary rationals summing to \(1\). The supplies \((1/2,1/4,1/4)\) satisfy all required restrictions.
Type \(A\)'s cardinality ordering is complete and transitive. Type \(B\)'s displayed ranking includes all eight bundles and defines a complete, transitive relation. Both relations strictly prefer larger cardinalities, so both satisfy weak monotonicity. They are distinct because type \(A\) is indifferent among all pairs, whereas type \(B\) strictly prefers \(\{1,2\}\) to the other pairs.
The introductory observation about a strict ranking is also valid: a strict complete ranking has exactly one optimal affordable bundle, forcing the whole mass of a single type to consume that bundle.
The empty bundle is affordable because budgets are positive, so each \(k_t\) is well-defined. Strict preference for greater cardinality implies that every optimal affordable bundle has cardinality \(k_t\). This argument permits indifferences within a cardinality class and does not impose tie-breaking.
Consequently, the total quantity consumed by type \(t\) is \(\mu_t k_t\), regardless of how its mass splits among optimal bundles. Summing market-clearing equations counts each assigned bundle once for each good it contains. Therefore the stated equation \(3k_A+k_B=4\) follows.
Its only solution with \(k_A,k_B\in\{0,1,2,3\}\) is \(k_A=k_B=1\). The exclusions of \(k_A=0\) and \(k_A\geq2\) are correct and exhaustive. Thus every positively assigned bundle must be a singleton.
Type \(A\)'s mass \(3/4\) cannot consume a single good exclusively, because every supply is at most \(1/2\). Nonnegative assignment masses therefore force positive consumption of at least two distinct singleton goods by type \(A\).
Their prices are each at most \(b_A\), so their pair costs at most \(2b_A\). Under the asserted budget inequality, that pair is affordable to type \(B\). This forces \(k_B\geq2\), contradicting the singleton lemma.
The argument covers equality \(b_B=2b_A\), since affordability uses a weak inequality. The open set \(b_B>2b_A\) is entirely contained in the nonexistence set. The displayed rectangle is indeed contained in it and has positive measure.
With \(c=\min\{b_A,b_B\}>0\), all singleton prices equal \(c\). Every singleton is affordable to both types, while every pair costs \(2c>\max\{b_A,b_B\}\). Triples are likewise unaffordable.
Both types are indifferent among all singletons and strictly prefer them to the empty bundle. Thus the proposed assignments use only optimal affordable bundles.
The assignment equations are correct: \(\sum_jq_j=1\) gives each type its required mass, and \(\mu_A+\mu_B=1\) gives each good its required supply. The close-budget condition defines a nonempty open set. This verifies the additional claim that the same society admits equilibria for other budgets.
Positive supply for every good ensures that some positively assigned bundle contains that good. Positive prices and affordability then imply \(p_j\leq B\). No equilibrium is excluded by this bound.
The \(2r+1\) regions partition all positive bundle prices, including equality with every distinct budget. Consequently, each region determines affordability for every type. There are seven nonempty bundles, yielding at most \((2\tau+1)^7\) tuples.
The enumeration may include incompatible bundle-price choices, but the subsequent price program tests their compatibility with additive prices.
A feasible solution with \(\delta>0\) satisfies positive prices and every prescribed open-region inequality strictly. Conversely, any prices belonging to the prescribed regions have finitely many positive strict-inequality slacks. A sufficiently small positive \(\delta\) satisfies all the displayed constraints.
The price program has a closed, bounded feasible set: \(p_j\in[0,B]\) and \(\delta\in[0,1]\). Thus a nonempty feasible set attains its maximum. Rejecting an infeasible program or a zero optimum is exactly the required test. Equality regions are retained without an inappropriate strictness requirement.
Affordability is constant within each tuple, so the demand sets are constant as well. Their definition exactly matches the task's optimality condition, including indifferences and the empty bundle.
The assignment program imposes precisely nonnegativity, type masses, and market clearing. Its variables allow arbitrary splitting among indifferent optimal bundles. Returning any successful price solution with any feasible assignment is valid because the demand sets depend only on the tuple.
Soundness and completeness both follow as written. In particular, completeness covers equilibria with real prices: the corresponding tuple passes the price test, and the original assignment witnesses assignment feasibility.
The stated rational linear-programming theorem supplies the needed feasibility and exact optimization guarantees. Its hypotheses are satisfied: all coefficients are rational, both programs have polynomial encoding length, and the price objective has a finite attained optimum.
The assignment program has at most \(8\tau\) variables. The price program has constant size apart from coefficient lengths. Polynomially many tuples and polynomial work per tuple give the claimed polynomial running time. Exact rational solutions of polynomial encoding length provide the requested prices and assignment masses.
The distinction drawn is correct. Segal-Halevi's model allocates a finite set of items by a partition among individual agents; its theorem does not directly establish existence for this population-mass model. [Segal-Halevi](https://arxiv.org/html/1705.04212v6)
The other cited result concerns a continuum economy with quasilinear utility, as its abstract explicitly states. It therefore addresses a different demand model. Neither external existence theorem is used as a premise of the counterexample or algorithm. [Azevedo, Weyl and White](https://knowledge.uchicago.edu/records/1btvv-6pd54)
No mathematical repair or additional clarification is needed.
⟨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.