Monthly Archive

You are currently browsing the monthly archive for February 2014.

The Political Economy of Robots

February 17, 2014 in political economy, science fiction | Tags: Elysium, Political Economy, Robots, utopia/dystopia | by rvohra | 4 comments

In the movie Elysium, the 1%, set up a gated community in space to separate themselves from the proles. Why only one Elysium? On earth, there is still a teeming mass of humanity that needs goods and services. Fertile ground for another 1% arise to meet these needs and eventually build another Elysium. Perhaps there is no property rights regime on Earth that encourages investment etc. Not the case in the movie because there is a police force, legal and parole system apparently administered by Robots. Furthermore, the robots are controlled by the 1% off site. Why do the 1% need to maintain control of the denizens of Earth? Elysium appears to be completely self-sustaining. No resources are apparently needed by it from the Earth. The only visible operation run by Elysium on earth is a company that manufactures robots. The head man is an Elysium expatriate but everyone else working at the factory is a denizen of Earth. Is Earth a banana republic to which Elysium outsources production? No, contradicts the self-sustaining assumption earlier. In short, the economics of the world envisioned in the movie make no sense. It used to be that scientific plausibility was a constraint on science fiction (otherwise its fantasy or magical realism for snobs). I’d add another criteria, economic plausibility. Utopias (or dystopias) must be economically plausible. With these words, can I lay claim to have started to a new branch of literary criticism: the economic analysis of utopian/dystopian fiction?

Back to the subject of this post. Pay attention to the robots in the movie. They have the agility and dexterity of humans. They are stronger. They can even detect sarcasm. Given this, its unclear why human are needed to work in the robot factory. Robots could be used to repair robots and produce new ones. What should such a world look like? Well I need only one `universal’ robot to begin with to produce and maintain robots for other tasks: farming, medical care, construction etc. Trade would become unnecessary for most goods and services. The only scarce resource would be the materials needed to produce and maintain robots (metals, rare earths etc.). Profits would accrue to the individuals who owned these resources. These individuals might trade among themselves, but would have no reason to trade with anyone outside this group. So, a small group of individuals would maintain large armies of robots to meet their needs and maintain their property rights over the inputs to robot production. Everyone else is surplus to needs. Thats a movie I would go to the cinema to see!

An Instance of Price Discrimination

February 12, 2014 in Uncategorized | Tags: price discrimination | by rvohra | 2 comments

From the New York Times comes a straightforward example of 3rd degree price discrimination. Prices of certain luxury vehicles are much higher in China than in the U.S. For example, the Porsche Cayenne, has a base price of $150,000 in China but $50,000 in the U.S. Price discrimination invites arbitrage, and the invitation in this case is so generous, that many people have accepted. Curiously, some of those who have accepted have been arrested, charged and fined for mail fraud and violations of customs laws.

Manufacturers have restrictions in their contracts with dealers to prohibit this sort of arbitrage, in part this is because cars produced for sale in one country will not be comply with extant regulation in another country. Interestingly, it is illegal for anyone other than the original equipment manufacturer to export NEW cars overseas. USED cars are an entirely different matter. US customs believes that if I buy a new car, and then drive it straight to the port to ship to China, it remains a new car. On the other hand, if I drive it home, it is used. Subsequent cases will turn upon the question of makes a car new vs. used?

As an aside, Ken Sparks, spokesman for BMW North America, defended the Governments vigorous pursuit of the arbitrageurs with these words:

Illegal exports deny legitimate customers here in the U.S. the popular vehicles, which are in high demand.

I can only imagine the pain of being denied a BMW. Perhaps, they could better show their concern by giving away the car for free.

Combinatorial Auctions and Binary Quadratic Valuations (Postscript)

February 10, 2014 in Auctions, Mechanism design, Operations research | by rvohra | 1 comment

In an earlier pair of posts I discussed a class of combinatorial auctions when agents have binary quadratic valuations. To formulate the problem of finding a welfare maximizing allocation let ${x^k_j = 1}$ if object ${j \in M}$ is given to agent ${k \in N}$ and zero otherwise. Denote the utility of agent ${k \in N}$ from consuming bundle ${S \subseteq M}$ by

$\displaystyle u_k(S) = \sum_{i \in S}u^k_i + \sum_{i, j \in S}w^k_{ij}.$

The problem of maximizing total welfare is

$\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{i \neq j}w^k_{ij}x^k_ix^k_j$

subject to

$\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M$

$\displaystyle x^k_i \in \{0,1\}\,\, \forall i \in M, k \in N$

I remarked that Candogan, Ozdaglar and Parrilo (2013) identified a solvable instance of the welfare maximization problem. They impose two conditions. The first is called sign consistency. For each ${i,j \in M}$ , the sign of ${w^k_{ij} }$ and ${w^r_{ij}}$ for any ${k, r \in N}$ is the same. Furthermore, this applies to all pairs ${i, j \in M}$ .

Let ${G^w}$ be a graph with vertex set ${M}$ and for any ${i,j \in M}$ such that ${w^k_{ij} \neq 0}$ introduce an edge ${(i,j)}$ . Because of the sign consistency condition we can label the edges of ${G^w}$ as being positive or negative depending on the sign of ${w^k_{ij}}$ . Let ${E^+ = \{(i,j): w^k_{ij} \geq 0\}}$ and ${E^- = \{(i,j): w^k_{ij} < 0\}}$ . The second condition is that ${G^w}$ be a tree.

The following is the relaxation that they consider:

$\displaystyle \max \sum_{k \in N}\sum_{i \in M}u^k_ix^k_i + \sum_{k \in N}\sum_{(i,j) \in E^+ \cup E^-}w^k_{ij}z^k_{ij}$

subject to

$\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in M$

$\displaystyle z^k_{ij} \leq x^k_i, x^k_j\,\, \forall k \in N, (i,j) \in E^+$

$\displaystyle z^k_{ij} \geq x^k_i + x^k_j - 1\,\, \forall k \in N, (i,j) \in E^-$

$\displaystyle x^k_i, z^k_{ij} \in \{0,1\}\,\, \forall i \in M, k \in N$

Denote by ${P}$ the polyhedron of feasible solutions to the last program. I give a new proof of the fact that the extreme points of ${P}$ are integral. My thanks to Ozan Candogan for (1) patiently going through a number of failed proofs and (2) being kind enough not to say :“why the bleep don’t you just read the proof we have.”

Let ${{\cal C}}$ be the maximal connected components of ${G^w}$ after deletion of the edges in ${E^-}$ (call this ${G^+}$ ). The proof will be by induction on ${|{\cal C}|}$ . The case ${|{\cal C}| = 1}$ follows from total unimodularity. I prove this later.

Suppose ${|{\cal C}| > 1}$ . Let ${({\bar z}, {\bar x})}$ be an optimal solution to our linear program. We can choose ${({\bar z}, {\bar x})}$ to be an extreme point of ${P}$ . As ${G^w}$ is a tree, there must exist a ${C \in {\cal C}}$ incident to exactly one negative edge, say ${(p,q)}$ . Denote by ${P'}$ the polyhedron ${P}$ restricted to just the vertices of ${C}$ and by ${Q}$ the polyhedron ${P}$ restricted to just the vertices in the complement of ${C}$ . By the induction hypothesis, both ${P'}$ and ${Q}$ are integral polyhedrons. Each extreme point of ${P'}$ ( ${Q}$ ) assigns a vertex of ${C}$ (the complement of ${C}$ ) to a particular agent. Let ${X_1, X_2, \ldots, X_a}$ be the set of extreme points of ${P'}$ . If in extreme point ${X_r}$ , vertex ${p}$ is assigned to agent ${k}$ we write ${X_{rk} = 1}$ and zero otherwise. Similarly with the extreme points ${Y_1, Y_2, \ldots, Y_b}$ of ${Q}$ . Thus, ${Y_{rk} = 1}$ is ${Y_r}$ assigns vertex ${q}$ to agent ${k}$ . Let ${v(X_{r})}$ be the objective function value of the assignment ${X_r}$ , similarly with ${v(Y_{rk})}$ .

Now ${({\bar z}, {\bar x})}$ restricted to ${P'}$ can be expressed as ${\sum_r\lambda_{r}X_{r}}$ . Similarly, ${({\bar z}, {\bar x})}$ restricted to ${Q}$ can be expressed as ${\sum_r\mu_{r}Y_{r}}$ . We can now reformulate our linear program as follows:

$\displaystyle \max \sum_r\lambda_{r}v(X_{r}) + \sum_r\mu_{r}v(Y_{r}) -\sum_{k \in N} |w^k_{pq}|y^k_{pq}$

subject to

$\displaystyle -\sum_r\lambda_{rk} = -1$

$\displaystyle -\sum_r\mu_{rk} = -1$

$\displaystyle \sum_{r: X_{rk} = 1}\lambda_{r}X_{r} + \sum_{r: Y_{rk} = 1}\mu_{r}Y_{r} \leq y^k_{pq} + 1\,\, \forall k \in N$

$\displaystyle \lambda_{r}, \mu_{r}, y^k_{pq} \geq 0\,\, \forall r, k$

The constraint matrix of this last program is totally unimodular. This follows from the fact that each variable appears in at most two constraints with coefficients of opposite sign and absolute value 1 (this is because ${X_{rk}}$ and ${X_{rk'}}$ cannot both be 1, similarly with the ${Y}$ ‘s). Total unimodularity implies that the last program has integral optimal solution and we are done. In fact, I believe the argument can be easily modified to to the case where in ${G^w}$ every cycle must contain a positive even number of negative edges.

Return to the case ${|{\cal C}| = 1}$ . Consider the polyhedron ${P}$ restricted to just one ${C \in {\cal C}}$ . It will have the form:

$\displaystyle \sum_{k \in N}x^k_i \leq 1\,\, \forall i \in C$

$\displaystyle z^k_{ij} \leq x^k_i, x^k_j\,\, \forall k \in N, (i,j) \in E^+ \cap C$

$\displaystyle x^k_i, z^k_{ij} \in \{0,1\}\,\, \forall i \in C, k \in N$

Notice the absence of negative edges. To establish total unimodularity we use the Ghouila-Houri (GH) theorem. Fix any subset, ${S}$ , of rows/constraints. The goal is to partition them into two sets ${L}$ and ${R}$ so that column by column the difference in the sum of the non-zero entries in ${L}$ and and the sum of the nonzero entries in ${R}$ differ by at most one.

Observe that the rows associated with constraints ${\sum_{k \in N}x^k_i \leq 1}$ are disjoint, so we are free to partition them in any way we like. Fix a partition of these rows. We must show to partition the remaining rows to satisfy the GH theorem. If ${y^k_{ij} - x^k_i \leq 0}$ is present in ${S}$ but ${y^k_{ij} -x^k_j \leq 0}$ is absent (or vice-versa), we are free to assign the row associated with ${y^k_{ij} - x^k_i \leq 0}$ in any way to satisfy the GH theorem. The difficulty will arise when both ${y^k_{ij}}$ , ${x^k_i}$ and ${x^k_j}$ are present in ${S}$ . To ensure that the GH theorem is satisfied we may have to ensure that the rows associated with ${y^k_{ij} - x^k_i \leq 0}$ and ${y^k_{ij} -x^k_j \leq 0}$ be separated.

When ${S}$ is the set of all constraints we show how to find a partition that satisfies the GH theorem. We build this partition by sequentially assigning rows to ${L}$ and ${R}$ making sure that after each assignment the conditions of the GH theorem are satisfied for the rows that have been assigned. It will be clear that this procedure can also be applied when only a subset of constraints are present (indeed, satisfying the GH theorem will be easier in this case).

Fix an agent ${k \in N}$ . The following procedure will be repeated for each agent in turn. Pick an arbitrary vertex in ${C}$ (which is a tree) to be a root and direct all edges `away’ from the root (when ${S}$ is a subset of the constraints we delete from ${C}$ any edge ${(i,j)}$ in which at most one from the pair ${y^k_{ij} - x^k_i \leq 0}$ and ${y^k_{ij} -x^k_j \leq 0}$ appears in ${S}$ ) . Label the root ${L}$ . Label all its neighbors ${R}$ , label the neighbors of the neighbors ${L}$ and so on. If vertex ${i \in C}$ was labeled ${L}$ assign the row ${\sum_{k \in N}x^k_i \leq 1}$ to the set ${L}$ otherwise to the row ${R}$ . This produces a partition of the constraints of the form ${\sum_{k \in N}x^k_i \leq 1}$ satisfying GH.

Initially, all leaves and edges of ${C}$ are unmarked. Trace out a path from the root to one of the leaves of ${C}$ and mark that leaf. Each unmarked directed edge ${(i,j)}$ on this path corresponds to the pair ${y^k_{ij} - x^k_i \leq 0}$ and ${y^k_{ij} -x^k_j \leq 0}$ . Assign ${y^k_{ij} - x^k_i \leq 0}$ to the same set that is the label of ${i}$ . Assign ${y^k_{ij} - x^k_j \leq 0}$ to the same set that is the label of vertex ${j}$ . Notice that in making this assignment the conditions of the GH theorem continues to satisfied. Mark the edge ${(i,j)}$ . If we repeat this procedure again with another path from the root to an unmarked leaf, we will violate the GH theorem. To see why suppose the tree contains edge ${(i,j)}$ as well as ${(i,t)}$ . Suppose ${i}$ was labeled ${L}$ on the first iteration and ${(i,j)}$ was marked. This means ${y^k_{ij} - x^k_{i} \leq 0}$ was assigned to ${L}$ . Subsequently ${y^k_{it} - x^k_i \leq 0}$ will also be assigned to ${L}$ which will produce a partition that violates the GH theorem. We can avoid this problem by flipping the labels on all the vertices before repeating the path tracing procedure.

Market Design Class (Lecture # 2 Part 2)

February 2, 2014 in Auctions, market design, Mechanism design, Operations research, Uncategorized | by rvohra | Comments closed

What is the institutional detail that makes electricity special? Its in the physics that I will summarize with a model of DC current in a resistive network. Note that other sources, like Wikipedia give other reasons, for why electricity is special:

Electricity is by its nature difficult to store and has to be available on demand. Consequently, unlike other products, it is not possible, under normal operating conditions, to keep it in stock, ration it or have customers queue for it. Furthermore, demand and supply vary continuously. There is therefore a physical requirement for a controlling agency, the transmission system operator, to coordinate the dispatch of generating units to meet the expected demand of the system across the transmission grid.

I’m skeptical. To see why, replace electricity by air travel.

Let ${V}$ be the set of vertices and ${E^*}$ the set of edges a the network. It will be convenient in what follows to assign (arbitrarily) an orientation to each edge in ${E^*}$ . Let ${E}$ be the set of directed arcs that result. Hence, ${(i,j) \in E}$ mens that the edge ${(i,j)}$ is directed from ${i}$ to ${j}$ . Notice, if ${(i,j) \in E}$ , then ${(i,j) \not \in E}$ .

Associated with each ${(i,j) \in E}$ is a number ${x_{ij}}$ that we interpret as a flow of electricity. If ${x_{ij} > 0}$ we interpret this to be a flow from ${i}$ to ${j}$ . If ${x_{ij} < 0}$ we interpret this as a flow from ${j}$ to ${i}$ .

Let ${\rho_{ij}}$ is the resistance on link ${(i,j)}$ .
${c_i}$ unit cost of injecting current into node ${i}$ .
${v_i}$ marginal value of current consumed at node ${i}$ .
${d_i}$ amount of current consumed at node ${i}$ .
${s_i}$ amount of current injected at node ${i}$ .
${K_{ij}}$ capacity of link ${(i,j)}$ .

Current must satisfy two conditions. The first is conservation of flow at each node:

$\displaystyle s_i + \sum_{k: (k,i) \in E}x_{ji} = \sum_{j: (i,j) \in E}x_{ij} + d_i\,\, \forall i \in V$

The second is Ohm’s law. There exist node potentials ${\{\phi_i\}_{i \in V}}$ such that

$\displaystyle \rho_{ij}x_{ij} = \phi_i - \phi_j\,\, \forall (i,j) \in E.$

Using this systems equations one can derive the school boy rules for computing the resistance of a network (add them in series, add the reciprocals in parallel). At the end of this post is a digression that shows how to formulate the problem of finding a flow that satisfies Ohm’s law as an optimization problem. Its not relevant for the economics, but charming nonetheless.

At each node ${i \in V}$ there is a power supplier with constant marginal cost of production of ${c_i}$ upto ${S_i}$ units. At each ${i \in V}$ there is a consumer with constant marginal value of ${v_i}$ upto ${D_i}$ units. A natural optimization problem to consider is

$\displaystyle \max \sum_{i \in V}[v_id_i - c_is_i]$

subject to

$\displaystyle \sum_{j: (i,j) \in E}x_{ij} -\sum_{j: (j,i) \in E}x_{ji} - s_i + d_i= 0\,\, \forall i \in V$

$\displaystyle \rho_{ij}x_{ij} = \mu_i - \mu_j\,\, \forall (i,j) \in E$

$\displaystyle -K_{ij} \leq x_{ij} \leq K_{ij}\,\, \forall (i,j) \in E$

$\displaystyle 0 \leq s_i \leq S_i\,\, \forall i \in V$

$\displaystyle 0 \leq d_i \leq D_i\,\, \forall i \in V$

This is the problem of finding a flow that maximizes surplus.

Let ${{\cal C}}$ be the set of cycles in ${(V, E^*)}$ . Observe that each ${C \in {\cal C}}$ corresponds to a cycle in ${(V, E)}$ if we ignore the orientation of the edges. For each cycle ${C \in {\cal C}}$ , let ${C^+}$ denote the edges in ${E}$ that are traversed in accordance with their orientation. Let ${C^-}$ be the set of edges in ${C}$ that are traversed in the opposing orientation.

We can project out the ${\phi}$ variables and reformulate as

$\displaystyle \max \sum_{i \in V}[v_id_i - c_is_i]$

subject to

$\displaystyle \sum_{j: (i,j) \in E}x_{ij} -\sum_{j: (j,i) \in E}x_{ji} - s_i + d_i= 0\,\, \forall i \in V$

$\displaystyle \sum_{(i,j) \in C^+}\rho_{ij}x_{ij} - \sum_{(i,j) \in C^-}\rho_{ij}x_{ij} = 0\,\, \forall \,\, C \in {\cal C}$

$\displaystyle -K_{ij} \leq x_{ij} \leq K_{ij}\,\, \forall (i,j) \in E$

$\displaystyle 0 \leq s_i \leq S_i\,\, \forall i \in V$

$\displaystyle 0 \leq d_i \leq D_i\,\, \forall i \in V$

Recall the scenario we ended with in part 1. Let ${V = \{1, 2, 3\}}$ , ${E = \{(1,3), (1,2), (2,3)\}}$ and in addition suppose ${\rho_{ij} =1}$ for all ${(i,j)}$ . Only ${(1,3)}$ has a capacity constraint of 600. Let ${D_1 = D_2 = 0}$ and ${S_3 = 0}$ . Also ${c_1 = 20}$ and ${c_2 = 40}$ and each have unlimited capacity. At node 3, the marginal value is ${V > 40}$ upto 1500 units and zero thereafter. The optimization problem is

$\displaystyle \max Vd_3 - 20s_1 - 40 s_2$

subject to

$\displaystyle x_{12} + x_{13} - s_1 = 0$

$\displaystyle x_{23} - s_2 - x_{12} = 0$

$\displaystyle d_3 - x_{13} - x_{23} = 0$

$\displaystyle x_{13} - x_{23} - x_{12} = 0$

$\displaystyle -600 \leq x_{13} \leq 600$

$\displaystyle 0 \leq d_3 \leq 1500$

Notice, for every unit of flow sent along ${(1,3)}$ , half a unit of flow must be sent along ${(1,2)}$ and ${(2,3)}$ as well to satisfy the cycle flow constraint.

The solution to this problem is ${x_{13} = 600}$ , ${x_{12} = -300}$ , ${x_{23} = 900}$ , ${s_1 = 300}$ , ${s_2 = 1200}$ and ${d_3 = 1500}$ . What is remarkable about this not all of customer 3’s demand is met by the lowest cost producer even though that producer has unlimited capacity. Why is this? The intuitive solution would have been send 600 units along ${(1,3)}$ and 900 units along ${(1,2) \rightarrow (2,3)}$ . This flow violates the cycle constraint.

In this example, when generator 1 injects electricity into the network to serve customer 3’s demand, a positive amount of that electricity must flow along every path from 1 to 3 in specific proportions. The same is true for generator 2. Thus, generator 1 is unable to supply all of customer 3’s demands. However, to accommodate generator 2, it must actually reduce its flow! Hence, customer 3 cannot contract with generators 1 and 2 independently to supply power. The shared infrastructure requires that they co-ordinate what they inject into the system. This need for coordination is the argument for a clearing house not just to manage the network but to match supply with demand. This is the argument for why electricity markets must be designed.

The externalities caused by electricity flows is not a proof that a clearing house is needed. After all, we know that if we price the externalities properly we should be able to implement the efficient outcome. Let us examine what prices might be needed by looking at the dual to the surplus maximization problem.

Let ${y_i}$ be the dual variable associated with the flow balance constraint. Let ${\lambda_C}$ be associated with the cycle constraints. Let ${\nu_i}$ and ${\theta_i}$ be associated with link capacity constraints. Let ${\mu_i}$ and ${\sigma_i}$ be associated with the remaining tow constraints. These can be interpreted as the profit of supplier ${i}$ and the surplus of customer ${i}$ respectively. For completeness the dual would be:

$\displaystyle \min \sum_{(i,j) \in E}[\nu_{ij} + \theta_{ij}]K_{ij} + \sum_{i \in V}[S_i \mu_i + D_i \sigma_i]$

subject to

$\displaystyle -\theta_{ij} + \nu_{ij} + \rho_{ij}\sum_{C^+ \ni (i,j)}\lambda_C - \rho_{ij}\sum_{C^- \ni (i,j)}\lambda_C + y_i - y_j = 0\,\, \forall (i,j) \in E$

$\displaystyle \mu_i - y_i \geq -c_i\,\, \forall i \in V$

$\displaystyle \sigma_i + y_i \geq v_i\,\, \forall i \in V$

$\displaystyle \nu_{ij}, \theta_{ij}, \mu_i, \sigma_i \geq 0\,\, \forall i \in V,\,\,\forall (i,j) \in E$

Now ${y_i}$ has a natural interpretation as a price to be paid for consumption at node ${i}$ for supply injected at node ${i}$ . ${\mu_i}$ and ${\nu_i}$ can be interpreted as the price of capacity. However, ${\lambda_C}$ is trickier, price for flow around a cycle? It would seem that one would have to assign ownership of each link as well as ownership of cycles in order to have a market to generate these prices.

Monthly Archive

The Political Economy of Robots

An Instance of Price Discrimination

Combinatorial Auctions and Binary Quadratic Valuations (Postscript)

Market Design Class (Lecture # 2 Part 2)

Email Subscription

Entries by:

Recent Posts

Recent Comments

Blogroll

Archives

Meta