You are currently browsing the category archive for the ‘Uncategorized’ category.

The other day, Andrew Postlewaite remarked that it is very hard to find a PhD economist whose academic ancestor thrice removed, was not a mathematician. Put differently, which PhD economists can trace their lineage back to Marshal, Keynes and perhaps even the Scottish master himself? An obvious problem is that it is unclear what it means for so&so to be one’s academic father. A strict definition might be thesis advisor. However, the PhD degree as we know it (some combination of study and research apprenticeship) is a relatively new thing. Arguably, the first modern PhD was granted by Yale in the early 1900s. Doctorate degrees were available in Germany prior to that. However, that degree was awarded upon submission of a body of work. There was no formal apprenticeship requirement. The UK did not introduce a doctorate degree until the early 1900s and that mimicked the German degree (and was introduced, apparently, to compete for US students who were flocking to Germany).

So, lets start at Yale with Irving Fisher. A celebrated economist, and justly so, at an institution that was the first to hand out PhD degrees. Fisher himself was a student of Josiah Willard Gibbs (mathematician and physicist, and, if you believe the mathematical genealogy project, descended from Poisson). What about Fisher’s descendants? Not a single of one of the laudatory pieces on Fisher here mention his students. Some digging uncovered James Harvey Rogers, who went on to become Sterling Professor of Economics at Yale and a panjandrum in the treasury. The university maintains an archive of his papers . Rogers also studied with Pareto. Rogers begat Walt Whitman Rostow. Rostow begat Everett Clyde Upshaw and that is where the line ends.

Lets try one more, Richard T. Ely, after whom the AEA has named one of its lecture series and credited as a founder of land economics. The Kirkus review of 1938 warmly endorses his biography, The Ground Under our Feet.’ Ely begat John R. Commons, W. A. Scott and E. A. Ross. Commons begat Edwin Witte,  the father of social security. Wikipedia credits Commons with influencing Gunnar Myrdal, Oliver Williamson and Herbert Simon, but influencing’ is not the same as thesis advisor. But, this line seems promising, however other duties intrude.

My former colleague Asher Wolinsky, once remarked that development economists had better hurry up lest the regions they studied became developed. From the March 2nd, 2014 edition of the NY Times, comes an announcement that the fateful day is upon us. The title of the piece is The End of the Developing World‘.

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.

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}$.

1. Let ${\rho_{ij}}$ is the resistance on link ${(i,j)}$.
2. ${c_i}$ unit cost of injecting current into node ${i}$.
3. ${v_i}$ marginal value of current consumed at node ${i}$.
4. ${d_i}$ amount of current consumed at node ${i}$.
5. ${s_i}$ amount of current injected at node ${i}$.
6. ${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.

In this, the second lecture, I focus on electricity markets. I’ll divide the summary of that lecture into two parts.

Until the 1980s electricity markets around the world operated as regulated monopolists. Generation (power plants) and distribution (the wires) were combined into a single entity. Beginning with Chile, a variety of Latin American countries started to privatize their electricity markets. So, imagine you were a bright young thing in the early 1980s, freshly baptised in the waters of Lake Michigan off Hyde Park. The General approaches you and says I want a free market in electricity, make it so (Quiero un mercado libre de la electricidad, que asi­ sea.) What would you reccomend?

Obviously, privatize the generators by selling them off, perhaps at auction (or given one’s pedigree, allocate them at random and allow the owners to trade among themeselves). What about the wire’s that carry electricity from one place to another. Tricky. Owner of the wire will have monopoly power, unless there are multiple parrallell wires. However, that would lead to inefficient duplication of resources. As a first pass, lets leave the wires in Government hands. Not obviously wrong. We do that with the road network. The Government owns and mainatins it and for a fee grants access to all.

So, competition to supply power but central control of the wires. Assuming an indifferent and benign authority controlling the wires, what will the market for generation look like? To fix ideas, consider a simple case. Two generators ${\{1, 2\}}$ and a customer ${3}$.

Generator has unlimited supply and a constant marginal cost of production of $20 a unit. Generator 2 has an unlimited supply and a constant marginal cost of production of$40 a unit. Customer 3 has a constant marginal value of ${V}$ upto 1500 units and zero thereafter. Assume ${U}$ to be sufficiently large to make all subsequent statements true. Initially there are only two wires, one from generator 1 to customer 3 and the other from generator 2 to customer 3. Suppose ${\{1,2,3\}}$ are all price takers. Then, the Walrasian price for this economy will be $20. For customer 3 this clearly a better outcome than unregulated monopoly, where the price would be ${U}$. What if the price taking assumption is not valid? An alternative model would be Bertrand competition between 1 and 2. So, the outcome would be a hairs breadth’ below$40. Worse than the Walrasian outcome but still better than unregulated monopoly. It would seem that deregulation would be a good idea and as the analysis above suggest, there is no necessity for a market to be designed. There is a catch. Is unregulated monopolist the right benchmark? Surely, a regulated monopolist would be better. Its not clear that one does better than the regulated monopolist.

Now lets add a wrinkle. Suppose the wire between 1 and 3 has capacity 600 units. There are two ways to think of this capacity constraint. The first is a capacity constraint on generator 1 that we have chosen to model as a constraint on the wire ${(1,3)}$. The second is that it is indeed a constraint on the wire ${(1,3)}$. The difference is not cosmetic as we shall see in a moment.

Suppose its a constraint on generator 1′s capacity. Then, under the price taking assumption, the Walrasian price in this economy will be $40. An alternative model of competition would be Bertrand-Edgeworth. In general equilibria are mixed, but whatever the mixture, the expected price per unit customer 3 will pay cannot exceed$40 a unit. In both cases, the outcome is better for customer 3 than unregulated monopolist.

Assume now the capacity constraint is on the wire instead. Under the price taking assumption, at a price of $20 unit, generator 1 is indifferent between supplying any non-negative amount. Generator 3′s supply correspondence is the empty set. However there is no way for supply to meet demand. Why is this? In the usal Walrasian set up each agent reports their supply and demand correspondence based on posted prices and their own information only. To obtain a sensible answer in this case, generator 1 must be aware of the capacity of the network into which its supply will be injected. As the next scenario we consider shows, this is not easy when it comes to electricity. Suppose there is now a link joining generator 1 and 2 with no capacity constraint. There is still a 600 unit capacity constraint on the link between 1 and 3. One might think, that in this scenario, customer 3 can receive all its demand from generator 1. It turns out that this is not possible because of the way electricity flows in networks. From the Fens of East Anglia comes a curious tale of a gift to Cambridge to endow a chair in honor of Stephen Hawking. The donor, Dennis Avery, put forward$6 million of which $2 million is to cover the costs of the Hawking chair. The balance is to be managed by charity, the Avery-Tsai foundation to, in the words of J. K. M. Sanders (Pro-Vice-Chancellor for Institutional Affairs), “……advance education and promote research in the science of cosmology at the University of Cambridge for the public benefit, and in particular to support the University in securing the best possible candidate as the Stephen W. Hawking Professor of Cosmology.” There are some unusual terms attached to the gift described below. Mr.Avery, however, passed away soon after the terms were negotiated. Renegotiation, now impossible, the University must decide whether to accept the gift as constructed or not at all. What makes the gift unusual? 1) Monies held by the foundation can be used to `top up’ the salary, so paying the individual an amount in excess of what the University might pay its top chair holders (which I believe is around 130K pounds). 2) The chair is to be housed in the Department of Applied Mathematics and Theoretical Physics (DAMTP). The gift requires DAMTP to certify each year to the Trustees that the base salary of the Hawking Professor is at least the average of other Professors in the Department. 3) The holder is subject to annual review and the monies from the foundation are contingent upon the outcome of that review. 4) It limits the tenure of the Professor to seven years, renewable for five and exceptionally for a further five. Let the fireworks begin. From the head of the DAMTP, P.H. Haynes and a supporter of the gift: “The unusual detailed arrangements surrounding this Professorship have rightly triggered significant debate amongst my Departmental colleagues and they have required detailed and robust discussion between Department, School, and the University.” Professor Goldstine of the DAMTP, responds with an objection to the circumvention of University rules with a delightful analogy to line integrals: “In the field of thermodynamics there is the concept of a ‘state function’, a quantity that is independent of the path by which a system is brought to a given point. This is one of those. It does not matter whether the payment goes through the University payroll or not if the University itself is signing off on the agreement and the funds are in its endowment. The choice of path certainly does not matter in the court of public opinion. How can the University contemplate an arrangement whose purpose is to circumvent its own rules?” He goes on to point out that it is inconceivable that a holder of the chair would accept a cut in pay upon expiration of the term. He is, by own admission rendered: “….almost speechless at Paragraph 9 of the deed, which asserts that the Department must certify each year to the Trustees that the base salary of the Hawking Professor is at least the average of other Professors in the Department. First, the requirement itself indicates a profound level of distrust of the Department’s operations. But second, how can it possibly be fair to tie one Professor’s salary to that of others? All their hard work over their career to date is used to define a starting point for his salary, independent of his qualifications. Moreover, if the Department chose to pay that minimum (which it might in light of other financial burdens), then the Stephen Hawking Professor would automatically get a raise if any other Professor did. This cannot be fair. I thought we strove to have a meritocracy in this University.” From an emeritus professor medieval history, G. R. Evans, clearly, a guardian of ancient rights: “….opening the doors to allowing outside bodies or donors to fund Professorships has led to the opening of further doors and only those with long constitutional memories may remember how it all began. I speak today just to put a reminder into the record, for this proposal has a constitutional context and if it is accepted, it will undoubtedly have constitutional consequences.” Dr. A. Pesci of the DAMTP opens with this gem: “This Chair looks to me like that pair of shoes at the Christmas sale. They looked beautiful and were half price. They were also two sizes too small and buying the matching dress would lead to bankruptcy. Hence, if one buys them, they would have to be left vacant, for if one wears them, they would cause enormous irreversible long-term damage.” The link to a full summary of the discussion can be found here. It is both interesting reading and amusing when compared with the earliest and best pamphlets on University politics that I know of: Microcosmographia Academica. I give one example from it: The Principle of the Dangerous Precedent is that you should not now do an admittedly right action for fear you, or your equally timid successors, should not have the courage to do right in some future case, which, ex hypothesi, is essentially different, but superficially resembles the present one. Every public action which is not customary, either is wrong, or, if it is right, is a dangerous precedent. It follows that nothing should ever be done for the first time. In 1961, Clarence Earl Gideon was charged with breaking and entering with intent to commit petty larceny. Appearing without counsel, Gideon invoked reverent authority: The United States Supreme Court says I am entitled to be represented by Counsel. Those words set in train a chain of events that confirmed, three years later, the right of indigent defendants in criminal proceedings, upon request, to have counsel appointed both during trial and on appeal. Qualified counsel, however, is scarce and there is an abundance of indigent defendants. Over the years the state has chosen to solve the problem of matching counsel to indigent defendant by fiat. Judge Posner in US vs Ely justifies this as follows: There are practical reasons for not giving indigent criminal defendants their choice of counsel. Appointed counsel are not paid at munificent rates under the Criminal Justice Act, 18 U.S.C. § 3006A(d); in the Central District of Illinois, in the most recent year for which data are available (1980), the average fee per case under the Act was only$426.31. Director of Adm. Off. of U.S. Cts., 1982 Ann.Rep. 511 (Exh. C-1). The best criminal lawyers who accept appointments therefore limit the amount of time they are willing to devote to this relatively unremunerative type of work; some criminal lawyers, indeed, only reluctantly agree to serve as appointed counsel, under pressure by district judges to whom they feel a sense of professional obligation. The services of the criminal defense bar cannot be auctioned to the highest bidder among the indigent accused — by definition, indigents are not bidders. But these services must be allocated somehow; indigent defendants cannot be allowed to paralyze the system by all flocking to one lawyer.

Time to sharpen pencils and put on the thinking cap. For a graduate student looking for a topic in market design, I cannot think of a more interesting question than how to match counsel to indigent defendants. One has: moral hazard (on the part of attorney), asymmetry of information (how does one distinguish between a good lawyer and a bad one), informed third parties with divided interests (Judges who appoint counsel, but may be more interested in a speedy trial than a vigorous defense), budget constraints (on the part of defendants) and competing objectives (speedy resolution vs. correct adjudication). For a description of the institution as it is currently structured and a proposal to revise it based on vouchers see Friedman and Schulhofer (yes Friedman fils).

In the analysis of combinatorial auctions two problems arise:

1. Surplus maximization: given prices for each item and a utility function over bundles of goods, find a bundle that maximizes the utility of a bundle less the price paid.
2. Welfare maximization: determine an allocation of goods to agents so as to maximize total welfare.

In general both problems are NP-hard and therefore a number of scholars have sought to identify conditions on preferences (i.e. ${u}$) that yield efficiently solvable instances of both problems. In this post I discuss a class preferences motivated by Cramton, Ausubel, McAfee and McMillan (1997) related to binary quadratic programs (BQP). A recent paper by Candogan, Ozdaglar and Parrilo (2013) prompted this two part post. I will say more about this paper in part 2. In this part I focus on surplus maximization.

Say that ${u}$ represents BQP preferences if

$\displaystyle u(S) = \sum_{i \in S}u_i + \sum_{i, j \in S}w_{ij}\,\, \forall S \subseteq M$

Interpret ${u_i}$ as the utility of consuming object ${i \in M}$ alone and ${w_{ij}}$ is the added benefit from consuming both ${i}$ and ${j }$ (if ${w_{ij} > 0}$), otherwise the disutility of doing so. The surplus maximization problem for BQP preferences is

$\displaystyle \max_{S \subseteq M} \sum_{i \in S}u_i + \sum_{i, j \in S}w_{ij} - \sum_{i \in S}p_i$

which can be rewritten as a binary quadratic program

$\displaystyle \max \sum_{i \in M}(u_i - p_i)x_i + \sum_{i \neq j}w_{ij}x_ix_j$

subject to

$\displaystyle x_i \in \{0,1\}\,\, \forall i \in M$

This problem is NP-hard as it encodes the independent set problem. To see why, let ${G = (V, E)}$ be a graph and let  ${w_{ij} = 0}$ if ${(i,j) \not \in E}$, ${u_i - p_i = 1}$ for all ${i \in M}$ and ${w_{ij} = -K}$ for all ${(i,j) \in E}$ where ${K }$ is a large positive number.

If ${w_{ij} \geq 0}$ for all ${i,j \in M}$ (pairs of goods are complements) there is a straightforward linearization of the surplus maximization problem:

$\displaystyle \max \sum_{i \in M}(u_i - p_i)x_i + \sum_{i \neq j}w_{ij}y_{ij}$

subject to

$\displaystyle y_{ij} \leq x_i\,\, \forall i,j \in M$

$\displaystyle y_{ij} \leq x_j\,\, \forall i,j \in M$

$\displaystyle 0 \leq y_{ij}, x_i \leq 1\,\, \forall i, j \in M$

Note that the constraint matrix is totally unimodular. Therefore, the surplus maximization problem can be solved as a linear program.

Thus, if ${w_{ij} > 0}$ for all ${i,j}$, surplus maximization is easy. With no restriction on the ${w_{ij}}$‘s, surplus maximization is NP-hard. Is there anything between these two extremes? Yes, Hansen and Simeone (1986) give us one case. To describe this case, we associate a graph with the ${w_{ij}}$‘s. One vertex for each ${i \in M}$ and for each ${(i,j)}$ such that ${w_{ij} \neq 0}$ an edge ${(i,j)}$. Call this graph ${G^w}$. Say that ${G^w}$ is sign balanced if it does not contain any cycle with an odd number of negative edges (${w_{ij} < 0}$). This implies that deleting all negative edges of ${G}$ disconnects it (say ${G =G_1\cup G_2}$), and ${\delta(G_1,G_2) }$ is the set of negative edges.

Consider the following linear relaxation of the surplus maximization problem:

$\displaystyle \max \sum_{i \in M}(u_i - p_i)x_i + \sum_{i \neq j}w_{ij}y_{ij}$

subject to

$\displaystyle y_{ij} \leq x_i\,\, \forall w_{ij} \geq 0$

$\displaystyle y_{ij} \leq x_j\,\, \forall w_{ij} \geq 0$

$\displaystyle y_{ij} \geq x_i + x_j -1\,\, \forall w_{ij} < 0$

$\displaystyle 0 \leq y_{ij}, x_i \leq 1\,\, \forall i,j$

If ${G^w}$ is sign balanced, Hansen and Simeone showed that the constraint matrix of this linear relaxation is totally unimodular. Therefore, the relaxation is exact. Here is a short argument that establishes integrality of the relaxation based on randomized rounding (due to Bertsimas, Teo and Vohra (1999)).

1. Let ${({\bar x}, {\bar y})}$ be an optimal solution to the relaxation.
2. Generate a single random number ${U}$ uniformly in ${[0,1]}$.
3. Round ${x_{i}}$ to 1 if ${i \in G_1}$ and ${{\bar x}_i \geq U}$, or ${i\in G_2}$ and ${{\bar x}_i \geq 1-U}$.

Since ${1-U}$ is also uniformly distributed in ${[0,1]}$, ${P(x_i =1) = {\bar x}_i}$. For ${i,j}$ both in ${ G_1}$ or both in ${G_2}$, ${P(x_i x_j=1) = \min \{{\bar x}_i,{\bar x}_j\}.}$ For ${i\in G_1}$ and ${j\in G_2}$,

$\displaystyle P(x_i x_j=1) = P(U\leq {\bar x}_i,1-U\leq {\bar x}_j) =[0, {\bar x}_i+{\bar x}_j-1]^+.$

At optimality, ${{\bar y}_{ij}= [{\bar x}_i, {\bar x}_j]^-}$ if ${w_{ij} \geq 0}$, ${{\bar y}_{ij}=[0, {\bar x}_i+{\bar x}_j-1]^+}$ if ${w_{ij} < 0}$. The expected objective function value of the random integral solution generated in this way is

$\displaystyle \sum_{i\neq j} w_{ij} E[x_i x_j] + \sum_i [u_i-p_i] x_i= \sum_{i,j} w_{ij} {\bar y}_{ij}+\sum_i [u_i-p_i] {\bar x}_i.$

Notice this is the optimal objective function value of the linear relaxation and this completes the argument.

In part 2 I turn to the welfare maximization question.

On his way to receive the Nobel, physicist Peter Higgs (of Higgs-Boson) was interviewed by the Grauniad. He said:

What should one make of this statement? Looking at Higgs’ description of his record at the time, it seems very clear that he would not have made it through the ranks now. Bad for Higgs. But is it bad for Science as some  have concluded? The article suggests so. But, there is a gap in logic. It implies, for example, that were Newton to have succumbed to the plague, Calculus and  the laws of motion would not be uncovered. This we know is false. The question of the best way to engineer a climate most conducive to research is not resolved by such reflections. It is not obvious that long periods of inactivity punctuated by bursts of magisterial insights is any better or worse than continued activity generating small insights that eventually cumulate into something larger.

Two public service announcements. The first about post-doc positions. The second about nominations for SIGecom dissertation awards.

Postdoc Positions

Penn’s newly-launched Warren Center for Network and Data Sciences seeks nominations for 2014 Warren Postdoctoral Fellowships. Warren Fellow candidates should have research interests in the subjects supported by the center, which include but are not limited to network science (including the study of social, technological, economic, organizational and biological networks, as well as underlying foundational areas such as graph theory, game theory, mechanism design) and data science (including machine learning, statistics, data privacy and security). The ideal candidate will have a strongly interdisciplinary research agenda with a demonstrated track record, and would be nominated by faculty affiliates of the Warren Center in two or more Penn departments who will act as hosts, advisors and collaborators of the candidate.

Warren Postdoctoral Fellows will receive generous and competitive stipends and research support, and will participate in a vibrant and community of Warren Center faculty affiliates, postdocs and students. We expect to fund multiple Warren Fellows for the 2014-15 academic year. Fellowships are for a one-year period, extendable to two by mutual agreement.

Dissertation Awards

SIGecom Doctoral Dissertation Award for dissertations defended in 2013. Nomination deadline end of February, 2014.

### Email Subscription

Join 102 other followers