Madras Manuscripts of Srinivasa Ramanujan (microfilmed)

 

manuscript book of ramanujan 1

manuscript book of ramanujan 2

 

Advertisement

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 e_i of money she possesses and for each good j the amount b_j of this good. In addition, we are given the utility functions of the buyers. Our critical assumption is that these functions are linear. Let u_ij denote the utility derived by i on obtaining a unit amount of good j. Thus if the buyer i is given x_ij units of good j, for 1 ≤ j ≤ n, then the happiness she derives is

∑_j=1ⁿu_ijx_ij —— (1)

Prices p₁, . . . , p_n 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 b_j is unit – by scaling the u_ij’s appropriately. The u_ij’s and e_i’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 x_ij’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∈Au_i^ei)^1/∑_ie_i —– (2)

then, the following objective function is equivalent:

max (∏_i∈Au_i^ei) —– (3)

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

maximize, ∑_i=1^n’e_ilogu_i

subject to

u_i = ∑_j=1ⁿu_ijx_ij ∀ i ∈ B

∑_i=1^n’ x_ij ≤ 1 ∀ j ∈ A

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

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

1. 1. ∀ j ∈ A : p_j ≥ 0
   2. ∀ j ∈ A : p_j > 0 ⇒ ∑_i∈A x_ij = 1
   3. ∀ i ∈ B, j ∈ A : u_ij/p_j ≤ ∑_j∈Au_ijx_ij/e_i
   4. ∀ i ∈ B, j ∈ A : x_ij > 0 ⇒ u_ij/p_j = ∑_j∈Au_ijx_ij/e_i

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 u_ij’s and e_i’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 u_ij > 0. By the third condition as stated above,

p_j ≥ e_iu_ij/∑_ju_ijx_ij > 0

By the second condition, ∑_i∈A x_ij = 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 : e_iu_ijx_ij/∑_j∈Au_ijx_ij = p_jx_ij

Summing over all j

∀ i ∈ B : e_i∑_j u_ijx_ij/∑_j∈Au_ijx_ij = p_jx_ij

⇒ ∀ i ∈ B : e_i = ∑_jp_jx_ij

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.

Blue Economy – Sagarmala Financial Engineering: Yet Another Dig. Skeletal Sketch of an Upcoming Talk in Somnath, Gujarat.

Authorized Share Capital in the case of Sagarmala happens to be INR 1000 crore, and is the number of stock units Sagarmala Development Company Limited (SDCL) has issued in its articles of incorporation. This ASC is open, in that share capital isn’t fully used, and there is ample room for future issuance of additional stock in order to raise capital quickly as and when a demand arises. SDCL can increase the authorized capital at anytime with shareholders’ approval and paying an additional fee to the RoC, Registrar of Companies. 

Capital Budgeting: Business determines and evaluates potential large expenditures/investments. Capital Budgeting is generally a long-term venture, and is a process that SDCL would use (and uses) to identify hat capital projects would create the biggest returns compared with the funds invested in the project. The system of ranking helps establish a potential return in the future, such that the SDCL management can choose where to invest first and most. Let us simply call it the first and most principle of budgeting. Blue Economy that instantiates itself via Sagarmala in India has options to choose from as regards its Capital Budgeting, viz. 

1. Throughput analysis – This defines the main motives behind a project, where all the costs are operating costs, and the main emphasis is on maximizing profits in passing through a bottleneck. The best example for Sagarmala speculatively thought out is the marking of Western Shipping Corridor for container traffic and posing a livelihood threat to traditional fishermen. Throughput is an alternative to the traditional cost accounting, but is neither accounting, not costing, since it is focused on cash flows. It does not allocate fixed costs to products and services sold or provided and treats direct labour as a fixed expense. Decisions made are based on three critical monetary variables: throughput, investment or inventory and operating expenses. Mathematically, this is defined as revenue minus totally variable expenses, the cost of raw materials or services incurred to produce the products sold or services delivred. T = R – TVE. 
2. Net Present Value (NPV) – this s the value of all future cash flows, either positive or negative over the entire life of an investment discounted to the present. NPV forms a part of an intrinsic valuation, and is employed for valuing business, investment security, capital project, new venture, cost reduction and almost anything involving cash flows. 

NPV = z₁/(1 + r) + z₂/(1 + r)² – X

      , where z₁ is the cash flow in time 1, z₂ is the cash flow in time 2, r is the discount       range, and X is the purchase price, or initial investment. NPV takes into account the timing of each cash flow that can result in a large impact on the present value of an investment. It is always better to have cash inflows sooner and cash outflows later. this is one spect where SDCL might encounter a bottleneck and thereby take recourse to throughput analysis. Importantly, NPV deliberates on revolving funds.  

3. Internal Rate of Return (IRR) – this is an interest rate at which NPV from all cash flows become zero. IRR qualifies attractiveness of an investment, whereby if IRR of a new project exceeds company’s required rate of return, then investment in that project is desirable, else project stands in need of a rejection. IRR escapes derivation analytically, and must be noted via mathematical trial and error. Interestingly, business spreadsheets are automated to perform these calculations. Mathematically, IRR is:

0 = P₀ + P₁/(1 + IRR) + P₂/(1 + IRR)² + …. + P_n/(1 + IRR)ⁿ

, where P₀, P₁,…, P_n are cash flows in periods of time 1, 2, …, n. 

 With a likelihood of venture capital and private equity expected in Sagarmala accompanied with multiple cash investments over the life-cycle of the project, IRR could come in handy for an IPO. 

     4. Discounted Cash Flow – this calculates the present value of an investment’s future            cash flows in order to arrive at  current fair value estimate for an investment. Mathematically, 

DCF =  CF₁/(1 + r) + CF₂/(1 + r)² + CF₃/(1 + r)³ + … + CF_n/(1 + r)ⁿ

, where CF_n are cash flows in respective n periods, and r is discount rate of return. 

DCF accounts for the fact that money received today can be invested today, while money we have to wait for cannot. DCF accounts for the time value of money and provides an estimate of what e should spend today to have an investment worth a certain amount of money at a specific point in the future. 

       5. Payback period – mathematically, this is defined as: 

Payback Period = Investment required/Annual Project Cash flow

This occurs the year plus a number of months before the cash flow turns positive. Though seemingly important, payback period does not consider the time value of investment/money, and is quite inept at handling projects with uneven cash flows. 

As a recap (and here, here, here)

Sagarmala is a 3-tier SPV structure

Private Players/PPPs OR EPCs/Turnkey – the latter are used for projects with high social impact or low IRR. 

Expenses incurred for project development will be treated as part of equity contribution by SDCL, or, in case SDCL does not have any equity, or expenses incurred are more than the stake of SDCL, SPV will defray SDCL. Divestment possibilities cannot be ruled out in order to recoup capital for future projects. 

Conjuncted: Integer Pivoting as a Polynomial-Time Algorithm

The Lemke-Howson Algorithm follows the edges of a polyhedron, which is implemented algebraically by pivoting as used by the simplex algorithm for solving a linear program. Let us see, if there is an efficient implementation that has no numerical errors by storing integers of arbitrary precision. The constraints defining the polyhedron are thereby represented as linear equations with nonnegative slack variables. For the polytopes P and Q in

P = {x ∈ R^M| x ≥ 0, B^⊤x ≤ 1},

Q = {y ∈ R^N |Ay ≤ 1, y ≥ 0}

these slack variables are nonnegative vectors s ∈ R^N and r ∈ R^M so that x ∈ P and y ∈ Q iff

B^⊤x + s = 1, r + Ay = 1 —– (1)

and

x ≥ 0, s ≥ 0, r ≥ 0, y ≥ 0 —— (2)

A binding inequality corresponds to a zero slack variable. The pair (x, y) is completely labeled iff x_ir_i = 0 ∀ i ∈ M and y_js_j = 0 ∀ j ∈ N, which by (2) can be written as the orthogonality condition

x^⊤r = 0, y^⊤s = 0

A basic solution to (1) is given by n basic (linearly independent) columns of B^⊤x + s = 1 and m basic columns of r + Ay = 1, where the nonbasic variables that correspond to the m respectively n other (nonbasic) columns are set to zero, so that the basic variables are uniquely determined. A basic feasible solution also fulfills (2), and defines a vertex x of P and y of Q. The labels of such a vertex are given by the respective nonbasic columns.

Pivoting is a change of the basis where a nonbasic variable enters and a basic variable leaves the set of basic variables, while preserving feasibility (2).

Integer pivoting always maintains an integer matrix (or “tableau”) of coefficients of a system of linear equations that is equivalent to the original system B^⊤x + s = 1, in the form

CB^⊤x + Cs = C1 —– (3)

In (3), C is the inverse of the basis matrix given by the basic columns of the original system, multiplied by the determinant of the basis matrix. The matrix C is given by the (integer) cofactors of the basis matrix; the cofactor of a matrix entry is the determinant of the matrix when the row and column of that element are deleted. When each entry has a bounded number of digits (by at most a factor of n log n compared to the original matrix entries), then integer pivoting is a polynomial-time algorithm. It is also superior to using fractions of integers or rational numbers because their cancelation requires greatest common divisor computations that take the bulk of computation time.

Lemke-Howson Algorithm – Symmetric Game with Symmetric Or NonSymmetric Equilibria. Note Quote.

Lemke-Howson Algorithm (LHA) function computes a sample mixed strategy Nash equilibrium in a bimatrix game. This function implements the Lemke-Howson complementary pivoting algorithm for solving Bimatrix Games, a variant of the Lemke algorithm for linear complementarity problems (LCPs). The LHA not only provides an elementary proof for the existence of equilibrium points, but also an efficient computational method for finding at least one equilibrium point. The LHA follows a path (called LH path) of vertex pairs (x, y) of P × Q, for the polytopes P and Q,

P = {x ∈ R^M| x ≥ 0, B^⊤x ≤ 1},

Q = {y ∈ R^N |Ay ≤ 1, y ≥ 0}

that starts at (0, 0) and ends at a Nash equilibrium. An LH path alternately follows edges of P and Q, keeping the vertex in the other polytope fixed. Because the game is nondegenerate, a vertex of P is given by m labels, and a vertex of Q is given by n labels. An edge of P is defined by m−1 labels.

For example, in the above figure, the edge defined by labels 1 and 3 joins the vertices 0 and c. Dropping a label l of a vertex x of P, say, means traversing the unique edge that has all the labels of x except for l. For example, dropping label 2 of the vertex 0 of P in the figure gives the edge, defined by labels 1 and 3, that joins 0 to vertex c. The endpoint of the edge has a new label, which is said to be picked up, for example, label 5 is picked up at vertex c.

The LHA starts from (0, 0) in P × Q. This is called the artificial equilibrium, which is a completely labeled vertex pair because every pure strategy has probability zero. It does not represent a Nash equilibrium of the game because the zero vector cannot be rescaled to a mixed strategy vector. An initial free choice of the LHA is a pure strategy k of a player (any label in M ∪ N ), called the missing label. Starting with (x, y) = (0, 0), label k is dropped. At the endpoint of the corresponding edge (of P if k ∈ M, of Q if k ∈ N), the new label that is picked up is duplicate because it was present in the other polytope. That duplicate label is then dropped in the other polytope, picking up a new label. If the newly picked label is the missing label, the algorithm terminates and has found a Nash equilibrium. Otherwise, the algorithm repeats by dropping the duplicate label in the other polytope, and continues in this fashion.

Input: Nondegenerate bimatrix game.

Output: One Nash equilibrium of the game.

Method: Choose k ∈ M ∪ N , called the missing label. Let (x, y) = (0, 0) ∈ P × Q. Drop label k (from x in P if k ∈ M, from y in Q if k ∈ N).

Loop: Call the new vertex pair (x, y). Let l be the label that is picked up. If l = k, terminate with Nash equilibrium (x, y) (rescaled as mixed strategy pair). Otherwise, drop l in the other polytope and repeat.

The LHA terminates, and finds a Nash equilibrium, because P × Q has only finitely many vertex pairs. The next vertex pair on the path is always unique. Hence, a given vertex pair cannot be revisited because that would provide an additional possibility to proceed in the first place.

What we seem to have done is describe the LH path for missing label k by means of alternating edges between two polytopes. In fact, it is a path on the product polytope P × Q, given by the set of pairs (x, y) of P × Q that are k-almost completely labeled, meaning that every label in M ∪ N − {k} appears as a label of either x or y. In the above figure for k = 2, the vertex pairs on the path are (0, 0), (c, 0), (c, p), (d, p), (d, q).

For a fixed missing label k, the k-almost completely labeled vertices and edges of the product polytope P × Q form a graph of degree 1 or 2. Clearly, such a graph consists of disjoints paths and cycles. The endpoints of the paths are completely labeled. They are the Nash equilibria of the game and the artificial equilibrium (0, 0).

Though, there is a corollary to the this, in that, a nondegenerate bimatrix game has an odd number of Nash equilibria. The LHA can start at any Nash equilibrium, not just the artificial equilibrium. In the figure with missing label 2, starting the algorithm at the Nash equilibrium (d, q) would just generate the known LH path backward to (0, 0). When started at the Nash equilibrium (a, s), the LH path for the missing label 2 gives the vertex pair (b, s), where label 5 is duplicate, and then the equilibrium (b, r). This path cannot go back to (0, 0) because the path leading to (0, 0) starts at (d, q). This gives the three Nash equilibria of the game as endpoints of the two LH paths for missing label 2. These three equilibria can also be found by the LHA by varying the missing label.

However, some Nash equilibria can remain elusive to the LHA. An example is the following symmetric 3 × 3 game with

A = B^⊤ =  

Every Nash equilibrium (x, y) of this game is symmetric, i.e., x = y, where x^⊤ is (0, 0, 1), (1/2, 1/4, 1/4), or (3/4, 1/4, 0). Only the first of these is found by the LHA, for any missing label; because the game is symmetric, it suffices to consider the missing labels 1, 2, 3. (A symmetric game remains unchanged when the players are exchanged; a symmetric game has always a symmetric equilibrium, but may also have nonsymmetric equilibria, which obviously come in pairs.)

Game’s Degeneracy Running Proportional to Polytope’s Redundancy.

For a given set of vertices V ⊆ R^K a Polytope P can be defined as the following set of points:

P = {∑_i=1^|V|λ_iv_i ∈ R^K | ∑_i=1^|V|λ_i = 1; λ_i ≥ 0; v_i ∈ V}

Polytope is an intersection of boundaries that separate the space into two distinct areas. If a polytope is to be defined as an intersection of half spaces, then for a matrix M ∈ R^mxn, and a vector b ∈ R^m, polytope P is defined as a set of points

P = {x ∈ Rⁿ | M_x ≤ b}

Switching over to a two-player game, (A, B) ∈ R^mxn2_>0, the row/column best response polytope P/Q is defined by:

P = {x ∈ R^m | x ≥ 0; xB ≤ 1}

Q = {y ∈ Rⁿ | Ay ≤ 1; y ≥ 0}

The polytope P, corresponds to the set of points with an upper bound on the utility of those points when considered as row strategies against which the column player plays.

An affine combination of points z₁,….z_k in some Euclidean space is of the form ∑_i=1^kλ_iz_i, where λ₁, …, λ_k are reals with ∑_i=1^kλ_i= 1. It is called a convex combination, if λ_i ≥ 0 ∀ i. A set of points is convex if it is closed under forming convex combinations. Given points are affinely independent if none of these points are an affine combination of the others. A convex set has dimension d iff it has d + 1, but no more, affinely independent points.

A polyhedron P in R^d is a set {z ∈ R^d | C_z ≤ q} for some matrix C and vector q. It is called full-dimensional if it has dimension d. It is called a polytope if it is bounded. A face of P is a set {z ∈ P | c^⊤z = q₀} for some c ∈ R^d, q₀ ∈ R, such that the inequality c^⊤z ≤ q₀ holds for all z in P. A vertex of P is the unique element of a zero-dimensional face of P. An edge of P is a one-dimensional face of P. A facet of a d-dimensional polyhedron P is a face of dimension d − 1. It can be shown that any nonempty face F of P can be obtained by turning some of the inequalities defining P into equalities, which are then called binding inequalities. That is, F = {z ∈ P | c_iz = q_i, i ∈ I}, where c_iz ≤ q_i for i ∈ I are some of the rows in C_z ≤ q. A facet is characterized by a single binding inequality which is irredundant; i.e., the inequality cannot be omitted without changing the polyhedron. A d-dimensional polyhedron P is called simple if no point belongs to more than d facets of P, which is true if there are no special dependencies between the facet-defining inequalities. The “best response polyhedron” of a player is the set of that player’s mixed strategies together with the “upper envelope” of expected payoffs (and any larger payoffs) to the other player.

Nondegeneracy of a bimatrix game (A, B) can be stated in terms of the polytopes P and Q as no point in P has more than m labels, and no point in Q has more than n labels. (If x ∈ P and x has support of size k and L is the set of labels of x, then |L ∩ M| = m − k, so |L| > m implies x has more than k best responses in L ∩ N. Then P and Q are simple polytopes, because a point of P, say, that is on more than m facets would have more than m labels. Even if P and Q are simple polytopes, the game can be degenerate if the description of a polytope is redundant in the sense that some inequality can be omitted, but nevertheless is sometimes binding. This occurs if a player has a pure strategy that is weakly dominated by or payoff equivalent to some other mixed strategy. Non-simple polytopes or redundant inequalities of this kind do not occur for “generic” payoffs; this illustrates the assumption of nondegeneracy from a geometric viewpoint. (A strictly dominated strategy may occur generically, but it defines a redundant inequality that is never binding, so this does not lead to a degenerate game.) Because the game is nondegenerate, only vertices of P can have m labels, and only vertices of Q can have n labels. Otherwise, a point of P with m labels that is not a vertex would be on a higher dimensional face, and a vertex of that face, which is a vertex of P, would have additional labels. Consequently, only vertices of P and Q have to be inspected as possible equilibrium strategies. Algorithmically, if the input is a nondegenerate bimatrix game, and output is an Nash equilibria of the game, then the method employed for each vertex x of P − {0}, and each vertex y of Q − {0}, if (x, y) is completely labeled, the output then is the Nash equilibrium (x · 1/1^⊤x, y · 1/1^⊤y).