Equilibrium Market Prices are Unique – Convexity and Concavity Utility Functions on a Linear Case. Note Quote + Didactics.


Consider a market consisting of a set B of buyers and a set A of divisible goods. Assume |A| = n and |B| = n′. We are given for each buyer i the amount ei of money she possesses and for each good j the amount bj of this good. In addition, we are given the utility functions of the buyers. Our critical assumption is that these functions are linear. Let uij denote the utility derived by i on obtaining a unit amount of good j. Thus if the buyer i is given xij units of good j, for 1 ≤ j ≤ n, then the happiness she derives is

j=1nuijxij —— (1)

Prices p1, . . . , pn of the goods are said to be market clearing prices if, after each buyer is assigned an optimal basket of goods relative to these prices, there is no surplus or deficiency of any of the goods. So, is it possible to compute such prices in polynomial time?

First observe that without loss of generality, we may assume that each bj is unit – by scaling the uij’s appropriately. The uij’s and ei’s are in general rational; by scaling appropriately, they may be assumed to be integral. By making the mild assumption that each good has a potential buyer, i.e., a buyer who derives nonzero utility from this good. Under this assumption, market clearing prices do exist.

It turns out that equilibrium allocations for Fisher’s linear case are captured as optimal solutions to a remarkable convex program, the Eisenberg–Gale convex program.

A convex program whose optimal solution is an equilibrium allocation must have as constraints the packing constraints on the xij’s. Furthermore, its objective function, which attempts to maximize utilities derived, should satisfy the following:

  1. If the utilities of any buyer are scaled by a constant, the optimal allocation remains unchanged.
  2. If the money of a buyer b is split among two new buyers whose utility functions are the same as that of b then sum of the optimal allocations of the new buyers should be an optimal allocation for b.

The money weighted geometric mean of buyers’ utilities satisfies both these conditions:

max (∏i∈Auiei)1/∑iei —– (2)

then, the following objective function is equivalent:

max (∏i∈Auiei) —– (3)

Its log is used in the Eisenberg–Gale convex program:

maximize, ∑i=1n’eilogui

subject to

ui = ∑j=1nuijxij ∀ i ∈ B

i=1n’ xij ≤ 1 ∀ j ∈ A

xij ≥ 0 ∀ i ∈ B, j ∈ A —– (4)

where xij is the amount of good j allocated to buyer i. Interpret Lagrangian variables, say pj’s, corresponding to the second set of conditions as prices of goods. Optimal solutions to xij’s and pj’s must satisfy the following:

    1. ∀ j ∈ A : p≥ 0
    2. ∀ j ∈ A : p> 0 ⇒ ∑i∈A xij = 1
    3. ∀ i ∈ B, j ∈ A : uij/pj ≤ ∑j∈Auijxij/ei
    4. ∀ i ∈ B, j ∈ A : xij > 0 ⇒ uij/pj = ∑j∈Auijxij/ei

From these conditions, one can derive that an optimal solution to convex program (4) must satisfy the market clearing conditions.

For the linear case of Fisher’s model:

  1. If each good has a potential buyer, equilibrium exists.
  2. The set of equilibrium allocations is convex.
  3. Equilibrium utilities and prices are unique.
  4. If all uij’s and ei’s are rational, then equilibrium allocations and prices are also rational. Moreover, they can be written using polynomially many bits in the length of the instance.

Corresponding to good j there is a buyer i such that uij > 0. By the third condition as stated above,

pj ≥ eiuij/∑juijxij > 0

By the second condition, ∑i∈A xij = 1, implying that prices of all goods are positive and all goods are fully sold. The third and fourth conditions imply that if buyer i gets good j then j must be among the goods that give buyer i maximum utility per unit money spent at current prices. Hence each buyer gets only a bundle consisting of her most desired goods, i.e., an optimal bundle.

The fourth condition is equivalent to

∀ i ∈ B, j ∈ A : eiuijxij/∑j∈Auijxij = pjxij

Summing over all j

∀ i ∈ B : eij uijxij/∑j∈Auijxij = pjxij

⇒ ∀ i ∈ B : ei = ∑jpjxij

Hence the money of each buyer is fully spent completing the proof that market equilibrium exists. Since each equilibrium allocation is an optimal solution to the Eisenberg-Gale convex program, the set of equilibrium allocations must form a convex set. Since log is a strictly concave function, if there is more than one equilibrium, the utility derived by each buyer must be the same in all equilibria. This fact, together with the fourth condition, gives that the equilibrium prices are unique.

Coarse Philosophies of Coarse Embeddabilities: Metric Space Conjectures Act Algorithmically On Manifolds – Thought of the Day 145.0


A coarse structure on a set X is defined to be a collection of subsets of X × X, called the controlled sets or entourages for the coarse structure, which satisfy some simple axioms. The most important of these states that if E and F are controlled then so is

E ◦ F := {(x, z) : ∃y, (x, y) ∈ E, (y, z) ∈ F}

Consider the metric spaces Zn and Rn. Their small-scale structure, their topology is entirely different, but on the large scale they resemble each other closely: any geometric configuration in Rn can be approximated by one in Zn, to within a uniformly bounded error. We think of such spaces as “coarsely equivalent”. The other axioms require that the diagonal should be a controlled set, and that subsets, transposes, and (finite) unions of controlled sets should be controlled. It is accurate to say that a coarse structure is the large-scale counterpart of a uniformity than of a topology.

Coarse structures and coarse spaces enjoy a philosophical advantage over coarse metric spaces, in that, all left invariant bounded geometry metrics on a countable group induce the same metric coarse structure which is therefore transparently uniquely determined by the group. On the other hand, the absence of a natural gauge complicates the notion of a coarse family, while it is natural to speak of sets of uniform size in different metric spaces it is not possible to do so in different coarse spaces without imposing additional structure.

Mikhail Leonidovich Gromov introduced the notion of coarse embedding for metric spaces. Let X and Y be metric spaces.

A map f : X → Y is said to be a coarse embedding if ∃ nondecreasing functions ρ1 and ρ2 from R+ = [0, ∞) to R such that

  • ρ1(d(x,y)) ≤ d(f(x),f(y)) ≤ ρ2(d(x,y)) ∀ x, y ∈ X.
  • limr→∞ ρi(r) = +∞ (i=1, 2).

Intuitively, coarse embeddability of a metric space X into Y means that we can draw a picture of X in Y which reflects the large scale geometry of X. In early 90’s, Gromov suggested that coarse embeddability of a discrete group into Hilbert space or some Banach spaces should be relevant to solving the Novikov conjecture. The connection between large scale geometry and differential topology and differential geometry, such as the Novikov conjecture, is built by index theory. Recall that an elliptic differential operator D on a compact manifold M is Fredholm in the sense that the kernel and cokernel of D are finite dimensional. The Fredholm index of D, which is defined by

index(D) = dim(kerD) − dim(cokerD),

has the following fundamental properties:

(1) it is an obstruction to invertibility of D;

(2) it is invariant under homotopy equivalence.

The celebrated Atiyah-Singer index theorem computes the Fredholm index of elliptic differential operators on compact manifolds and has important applications. However, an elliptic differential operator on a noncompact manifold is in general not Fredholm in the usual sense, but Fredholm in a generalized sense. The generalized Fredholm index for such an operator is called the higher index. In particular, on a general noncompact complete Riemannian manifold M, John Roe (Coarse Cohomology and Index Theory on Complete Riemannian Manifolds) introduced a higher index theory for elliptic differential operators on M.

The coarse Baum-Connes conjecture is an algorithm to compute the higher index of an elliptic differential operator on noncompact complete Riemannian manifolds. By the descent principal, the coarse Baum-Connes conjecture implies the Novikov higher signature conjecture. Guoliang Yu has proved the coarse Baum-Connes conjecture for bounded geometry metric spaces which are coarsely embeddable into Hilbert space. The metric spaces which admit coarse embeddings into Hilbert space are a large class, including e.g. all amenable groups and hyperbolic groups. In general, however, there are counterexamples to the coarse Baum-Connes conjecture. A notorious one is expander graphs. On the other hand, the coarse Novikov conjecture (i.e. the injectivity part of the coarse Baum-Connes conjecture) is an algorithm of determining non-vanishing of the higher index. Kasparov-Yu have proved the coarse Novikov conjecture for spaces which admit coarse embeddings into a uniformly convex Banach space.

Fréchet Spaces and Presheave Morphisms.



A topological vector space V is both a topological space and a vector space such that the vector space operations are continuous. A topological vector space is locally convex if its topology admits a basis consisting of convex sets (a set A is convex if (1 – t) + ty ∈ A ∀ x, y ∈ A and t ∈ [0, 1].

We say that a locally convex topological vector space is a Fréchet space if its topology is induced by a translation-invariant metric d and the space is complete with respect to d, that is, all the Cauchy sequences are convergent.

A seminorm on a vector space V is a real-valued function p such that ∀ x, y ∈ V and scalars a we have:

(1) p(x + y) ≤ p(x) + p(y),

(2) p(ax) = |a|p(x),

(3) p(x) ≥ 0.

The difference between the norm and the seminorm comes from the last property: we do not ask that if x ≠ 0, then p(x) > 0, as we would do for a norm.

If {pi}{i∈N} is a countable family of seminorms on a topological vector space V, separating points, i.e. if x ≠ 0, there is an i with pi(x) ≠ 0, then ∃ a translation-invariant metric d inducing the topology, defined in terms of the {pi}:

d(x, y) = ∑i=1 1/2i pi(x – y)/(1 + pi(x – y))

The following characterizes Fréchet spaces, giving an effective method to construct them using seminorms.

A topological vector space V is a Fréchet space iff it satisfies the following three properties:

  • it is complete as a topological vector space;
  • it is a Hausdorff space;
  • its topology is induced by a countable family of seminorms {pi}{i∈N}, i.e., U ⊂ V is open iff for every u ∈ U ∃ K ≥ 0 and ε > 0 such that {v|pk(u – v) < ε ∀ k ≤ K} ⊂ U.

We say that a sequence (xn) in V converges to x in the Fréchet space topology defined by a family of seminorms iff it converges to x with respect to each of the given seminorms. In other words, xn → x, iff pi(xn – x) → 0 for each i.

Two families of seminorms defined on the locally convex vector space V are said to be equivalent if they induce the same topology on V.

To construct a Fréchet space, one typically starts with a locally convex topological vector space V and defines a countable family of seminorms pk on V inducing its topology and such that:

  1. if x ∈ V and pk(x) = 0 ∀ k ≥ 0, then x = 0 (separation property);
  2. if (xn) is a sequence in V which is Cauchy with respect to each seminorm, then ∃ x ∈ V such that (xn) converges to x with respect to each seminorm (completeness property).

The topology induced by these seminorms turns V into a Fréchet space; property (1) ensures that it is Hausdorff, while the property (2) guarantees that it is complete. A translation-invariant complete metric inducing the topology on V can then be defined as above.

The most important example of Fréchet space, is the vector space C(U), the space of smooth functions on the open set U ⊆ Rn or more generally the vector space C(M), where M is a differentiable manifold.

For each open set U ⊆ Rn (or U ⊂ M), for each K ⊂ U compact and for each multi-index I , we define

||ƒ||K,I := supx∈K |(∂|I|/∂xI (ƒ)) (x)|, ƒ ∈ C(U)

Each ||.||K,I defines a seminorm. The family of seminorms obtained by considering all of the multi-indices I and the (countable number of) compact subsets K covering U satisfies the properties (1) and (1) detailed above, hence makes C(U) into a Fréchet space. The sets of the form

|ƒ ∈ C(U)| ||ƒ – g||K,I < ε

with fixed g ∈ C(U), K ⊆ U compact, and multi-index I are open sets and together with their finite intersections form a basis for the topology.

All these constructions and results can be generalized to smooth manifolds. Let M be a smooth manifold and let U be an open subset of M. If K is a compact subset of U and D is a differential operator over U, then

pK,D(ƒ) := supx∈K|D(ƒ)|

is a seminorm. The family of all the seminorms  pK,D with K and D varying among all compact subsets and differential operators respectively is a separating family of seminorms endowing CM(U) with the structure of a complete locally convex vector space. Moreover there exists an equivalent countable family of seminorms, hence CM(U) is a Fréchet space. Let indeed {Vj} be a countable open cover of U by open coordinate subsets, and let, for each j, {Kj,i} be a countable family of compact subsets of Vj such that ∪i Kj,i = Vj. We have the countable family of seminorms

pK,I := supx∈K |(∂|I|/∂xI (ƒ)) (x)|, K ∈  {Kj,i}

inducing the topology. CM(U) is also an algebra: the product of two smooth functions being a smooth function.

A Fréchet space V is said to be a Fréchet algebra if its topology can be defined by a countable family of submultiplicative seminorms, i.e., a countable family {qi)i∈N of seminorms satisfying

qi(ƒg) ≤qi (ƒ) qi(g) ∀ i ∈ N

Let F be a sheaf of real vector spaces over a manifold M. F is a Fréchet sheaf if:

(1)  for each open set U ⊆ M, F(U) is a Fréchet space;

(2)  for each open set U ⊆ M and for each open cover {Ui} of U, the topology of F(U) is the initial topology with respect to the restriction maps F(U) → F(Ui), that is, the coarsest topology making the restriction morphisms continuous.

As a consequence, we have the restriction map F(U) → F(V) (V ⊆ U) as continuous. A morphism of sheaves ψ: F → F’ is said to be continuous if the map F(U) → F'(U) is open for each open subset U ⊆ M.

Organic and the Orgiastic. Cartography of Ground and Groundlessness in Deleuze and Heidegger. Thought of the Day 43.0


In his last hermeneutical Erörterung of Leibniz, The Principle of Ground, Heidegger traces back metaphysics to its epochal destiny in the twofold or duplicity (Zwiefalt) of Being and Thought and thus follows the ground in its self-ungrounding (zugrundegehen). Since the foundation of thought is also the foundation of Being, reason and ground are not equal but belong together (zusammenhören) in the Same as the ungrounded yet historical horizon of the metaphysical destiny of Being: On the one hand we say: Being and ground: the Same. On the other hand we say: Being: the abyss (Ab-Grund). What is important is to think the univocity (Einsinnigkeit) of both Sätze, those Sätze that are no longer Sätze. In Difference and Repetition, similarly, Deleuze tells us that sufficient reason is twisted into the groundless. He confirms that the Fold (Pli) is the differenciator of difference engulfed in groundlessness, always folding, unfolding, refolding: to ground is always to bend, to curve and recurve. He thus concludes:

Sufficient reason or ground is strangely bent: on the one hand, it leans towards what it grounds, towards the forms of representation; on the other hand, it turns and plunges into a groundless beyond the ground which resists all forms and cannot be represented.

Despite the fundamental similarity of their conclusions, however, our short overview of Deleuze’s transformation of the Principle of Sufficient Reason has already indicated that his argumentation is very different from Heideggerian hermeneutics. To ground, Deleuze agrees, is always to ground representation. But we should distinguish between two kinds of representation: organic or finite representation and orgiastic or infinite representation. What unites the classicisms of Kant, Descartes and Aristotle is that representation retains organic form as its principle and the finite as its element. Here the logical principle of identity always precedes ontology, such that the ground as element of difference remains undetermined and in itself. It is only with Hegel and Leibniz that representation discovers the ground as its principle and the infinite as its element. It is precisely the Principle of Sufficient Reason that enables thought to determine difference in itself. The ground is like a single and unique total moment, simultaneously the moment of the evanescence and production of difference, of disappearance and appearance. What the attempts at rendering representation infinite reveal, therefore, is that the ground has not only an Apollinian, orderly side, but also a hidden Dionysian, orgiastic side. Representation discovers within itself the limits of the organized; tumult, restlessness and passion underneath apparent calm. It rediscovers monstrosity.

The question then is how to evaluate this ambiguity that is essential to the ground. For Heidegger, the Zwiefalt is either naively interpreted from the perspective of its concave side, following the path of the history of Western thought as the belonging together of Being and thought in a common ground; or it is meditated from its convex side, excavating it from the history of the forgetting of Being the decline of the Fold (Wegfall der Zwiefalt, Vorenthalt der Zwiefalt) as the pivotal point of the Open in its unfolding and following the path that leads from the ground to the abyss. Instead of this all or nothing approach, Deleuze takes up the question in a Nietzschean, i.e. genealogical fashion. The attempt to represent difference in itself cannot be disconnected from its malediction, i.e. the moral representation of groundlessness as a completely undifferentiated abyss. As Bergson already observed, representational reason poses the problem of the ground in terms of the alternative between order and chaos. This goes in particular for the kind of representational reason that seeks to represent the irrepresentable: Representation, especially when it becomes infinite, is imbued with a presentiment of groundlessness. Because it has become infinite in order to include difference within itself, however, it represents groundlessness as a completely undifferentiated abyss, a universal lack of difference, an indifferent black nothingness. Indeed, if Deleuze is so hostile to Hegel, it is because the latter embodies like no other the ultimate illusion inseparable from the Principle of Sufficient Reason insofar as it grounds representation, namely that groundlessness should lack differences, when in fact it swarms with them.

Some content on this page was disabled on May 4, 2020 as a result of a DMCA takedown notice from Columbia University Press. You can learn more about the DMCA here: