Ezra Klein, one among the chattering classes recently posted a summary of graduation speech given by Thomas Sargent to Berkeley economics undergraduates in 2007. Sargent prefaced his remarks with these words:

I will economize on words.

Lets see how well he succeeded:

Economics is organized common sense. Here is a short list of valuable lessons that our beautiful subject teaches.

1. Many things that are desirable are not feasible.

2. Individuals and communities face trade-offs.

3. Other people have more information about their abilities, their efforts, and their preferences than you do.

4. Everyone responds to incentives, including people you want to help. That is why social safety nets don’t always end up working as intended.


Everything after the comma is superfluous. Why emphasize the bit about people you want to help? Why choose to emphasize the business of safety nets? He could just as well have said: That is why markets don’t always end up working as intended.


5. There are tradeoffs between equality and efficiency.


Redundant given items 1 and 2 above. It also implies a commonly accepted definition of equality and efficiency.


6. In an equilibrium of a game or an economy, people are satisfied with their choices. That is why it is difficult for well meaning outsiders to change things for better or worse.


Wrong. Within the constraints of the game they may be satisfied with the outcome. It does not follow they are satisfied with the game they were obliged to play.


7. In the future, you too will respond to incentives. That is why there are some promises that you’d like to make but can’t. No one will believe those promises because they know that later it will not be in your interest to deliver. The lesson here is this: before you make a promise, think about whether you will want to keep it if and when your circumstances change.
This is how you earn a reputation.


He garbled this one by confusing the desire to make promises and whether they are credible. Here is an edit with fewer words.


Promises about tomorrow are easy to make, but because you will respond to incentives in the future they are hard to keep. Its even harder to convince others that you will keep them. Before you make a promise, think about whether you will want to keep it if and when your circumstances change. This is how you earn a reputation.


8. Governments and voters respond to incentives too. That is why governments sometimes default on loans and other promises that they have made.


Redundant given item 4 above.


9. It is feasible for one generation to shift costs to subsequent ones. That is what national government debts and the U.S. social security system do (but not the social security system of Singapore).


Item in brackets clearly redundant, but what is a bully pulpit for unless one get one’s licks in!


10. When a government spends, its citizens eventually pay, either today or tomorrow, either through explicit taxes or implicit ones like inflation.

11. Most people want other people to pay for public goods and government transfers (especially transfers to themselves).

12. Because market prices aggregate traders’ information, it is difficult to forecast stock prices and interest rates and exchange rates.


Rests on a supposition that some might find arguable. Conclusion might still follow. Perhaps, a simple `you can’t beat the market without an unfair advantage’ might suffice. 

Now compare with Yoram Baumann’s translation of Mankiw’s ten principles of economics:

#1. Choices are bad.
#2. Choices are really bad.
#3. People are stupid.
#4. People aren’t that stupid.
#5. Trade can make everyone worse off.
#6. Governments are stupid.
#7. Governments aren’t that stupid.
#8. Blah blah blah.
#9. Blah blah blah.
#10. Blah blah blah.

On many campuses one will find notices offering modest sums to undergraduates to participate in experiments. When the experimenter does not attract sufficiently many subjects to participate at the posted rate, does she raise it? Do undergraduates make counter offers? If not, why not?  An interesting contrast is medical research where there has arisen a class of human professional guinea pigs. They have a jobzine and the anthropologist Roberto Abadie has book on the subject. Prices paid to healthy subjects to participate in  trials vary and increase with the potential hazards. The jobzine I mention earlier provides ratings of various research organizations who carry out such studies. A number of questions come to mind immediately: how are prices determined, are subjects in a position to offer informed consent, should such contracts be forbidden and does relying on such subjects induce a selection bias?

In the March 23rd edition of the NY Times Mankiw proposes a `do no harm’ test for policy makers:

…when people have voluntarily agreed upon an economic arrangement to their mutual benefit, that arrangement should be respected.

There is a qualifier for negative externalities, and he goes on to say:

As a result, when a policy is complex , hard to evaluate and disruptive of private transactions, there is good reason to be skeptical of it.

Minimum wage legislation is offered as an example of a policy that fails the do no harm test.

The association with the Hippocratic oath gives it an immediate appeal. I think the test to be more Panglossian (or should I say Leibnizian) than Hippocratic.

There is an immediate `heart strings’ argument against the test, because indentured servitude passes the `do no harm’ test. However, indentured servitude contracts are illegal in many jurisdictions ( repugnant contracts?). This argument raises only more questions, like why would we rule out such contracts? I want to focus instead on two other aspects of the `do no harm’ principle contained in the words `voluntarily’ and `benefit’. What is voluntary and benefit compared to what?

To fix ideas imagine two parties, who if they work together and expend equal effort can jointly produce a good worth $1. How should they split the surplus produced? How will they split the surplus produced? An immediate answer to the `should’ question is 50-50. A deeper answer would suggest that they each receive their marginal product (or added value) of $1, but this impossible without an injection of money from the outside. There is no immediate answer to the `will’ question as it will depend on the outside options of each of the agents and their relative patience. Suppose for example, the outside option of each party is $0, one agent is infinitely patient and the other has a high discount rate. It isn’t hard to construct a model of bargaining where the lions share of the gains from trade go to the patient agent. Thus, what `will’ happen will be very different from what `should’ happen. What `will’ happen depends on the relative patience and outside options of the agents at the time of bargaining. In my extreme example of a very impatient agent, one might ask why is it that one agent is so impatient? Is the patient agent exploiting the impatience of the other agent coercion?

When parties negotiate to their mutual benefit, it is to their benefit relative to the status quo. When the status quo presents one agent an outside option that is untenable, say starvation, is bargaining voluntary, even if the other agent is not directly threatening starvation? The difficulty with the `do no harm’ principle in policy matters is the assumption that the status quo does less harm than a change in it would. This is not clear to me at all. Let me illustrate this  with two examples to be found in any standard microeconomic text book.

Assuming a perfectly competitive market, imposing a minimum wage constraint above the equilibrium wage would reduce total welfare. What if the labor market were not perfectly competitive? In particular, suppose it was a monopsony employer constrained to offer the same wage to everyone employed. Then, imposing a minimum wage above the monopsonist’s optimal wage would increase total welfare.

The abstract of a 2005 paper by Itti and Baldi begins with these words:

The concept of surprise is central to sensory processing, adaptation, learning, and attention. Yet, no widely-accepted mathematical theory currently exists to quantitatively characterize surprise elicited by a stimulus or event, for observers that range from single neurons to complex natural or engineered systems. We describe a formal Bayesian definition of surprise that is the only consistent formulation under minimal axiomatic assumptions.

They propose that surprise be measured by the Kullback-Liebler divergence between the prior and the posterior. As with many good ideas, Itti and Baldi are not the first to propose this. C. L. Martin and G. Meeden did so in 1984 in an unpublished paper entitled: `The distance between the prior and the posterior distributions as a measure of surprise.’ Itti and Baldi go further and provide experimental support that this notion of surprise comports with human notions of surprise. Recently, Ely, Frankel and Kamenica in Economics, have also considered the issue of surprise, focusing instead on how best to release information so as to maximize interest.

Surprise now being defined, one might go on to define novelty, interestingness, beauty and humor. Indeed, Jurgen Schmidhuber has done just that (and more). A paper on the optimal design of jokes cannot be far behind. Odd as this may seem, it is a part of a venerable tradition. Kant defined humor as the sudden transformation of a strained expectation into nothing. Birkhoff himself wrote an entire treatise on Aesthetic Measure (see the review by Garabedian). But, I digress.

Returning to the subject of surprise, the Kulback-Liebler divergence is not the first measure of surprise or even the most wide spread. I think that prize goes to the venerable p-value. Orthodox Bayesians, those who tremble in the sight of measure zero events, look in horror upon the p-value because it does not require one to articulate a model of the alternative. Even they would own, I think, to the convenience of having to avoid listing all alternative models and carefully evaluating them. Indeed I. J. Good  writing in 1981 notes the following:

The evolutionary value of surprise is that it causes us to check our assumptions. Hence if an experiment gives rise to a surprising result given some null hypothesis H it might cause us to wonder whether H is true even in the absence of a vague alternative to H.

Good, by the way, described himself as a cross between Bayesian and Frequentist, called a Doogian. One can tell from this label that he had an irrepressible sense of humor. Born Isadore Guldak Joseph of a Polish family in London, he changed his name to Ian Jack Good, close enough one supposes. At Bletchley park he and Turing came up with the scheme that eventually broke the German Navy’s enigma code. This led to the Good-Turing estimator. Imagine a sequence so symbols chosen from a finite alphabet. How would one estimate the probability of observing a letter from the alphabet that has not yet appeared in the sequence thus far? But, I digress.

Warren Weaver was, I think, the first to propose a measure of surpirse. Weaver is most well known as a popularizer of Science. Some may recall him as the Weaver on the slim volume by Shannon and Weaver on the Mathematical Theory of Communication. Well before that, Weaver played an important role at the Rockefeller foundation, where he used their resources to provide fellowships to many promising scholars and jump start molecular biology. The following is from page 238 of my edition Jonas’ book `The Circuit Riders’:

Given the unreliability of such sources, the conscientious philanthropoid has no choice but to become a circuit rider. To do it right, a circuit rider must be more than a scientifically literate ‘tape recorder on legs.’ In order to win the confidence of their informants, circuit riders for Weaver’s Division of Natural Sciences were called upon the offer a high level of ‘intellectual companionship – without becoming ‘too chummy’ with people whose work they had, ultimately, to judge.

But, I digress.

To define Weaver’s notion, suppose a discrete random variable X that takes values in the set \{1, 2, \ldots, m\}. Let p_i be the probability that X = i. The surprise index of outcome k is \frac{\sum_i i p^2_i}{p_k}. Good himself jumped into the fray with some generalizations of Weaver’s index. Here is one \frac{[\sum_iip_i^t]^{1/t}}{p_k}. Others involve the use of logs, leading to measures that are related to notions of entropy as well probability scoring rules. Good also proposed axioms that a good measure to satisfy, but I cannot recall if anyone followed up to derive axiomatic characterizations.

G. L. S. Shackle, who would count as one of the earliest decision theorists, also got into the act. Shackle departed from subjective probability and proposed to order degrees of beliefs by their potential degrees of surprise. Shackle also proposed, I think, that an action be judged interesting by its best possible payoff and its potential for surprise. Shackle, has already passed beyond the ken of men. One can get a sense of his style and vigor from the following response to an invitation to write a piece on Rational Expectations:

Rational expectations’ remains for me a sort of monster living in a cave. I have never ventured into the cave to see what he is like, but I am always uneasily aware that he may come out and eat me. If you will allow me to stir the cauldron of mixed metaphors with a real flourish, I shall suggest that ‘rational expectations’ is neo-classical theory clutching at the last straw. Observable circumstances offer us suggestions as to what may be the sequel of this act or that one. How can we know what invisible circumstances may take effect in time-to come, of which no hint can now be gained? I take it that ‘rational expectations’ assumes that we can work out what will happen as a consequence of this or that course of action. I should rather say that at most we can hope to set bounds to what can happen, at best and at worst, within a stated length of time from ‘the present’, and can invent an endless diversity of possibilities lying between them. I fear that for your purpose I am a broken reed.

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.

Penn state runs auctions to license its intellectual property. For each license on the block there is a brief description of what the relevant technology is and an opening bid which I interpret as a reserve price. It also notes whether the license is exclusive or not. Thus, the license is sold for a single upfront fee. No royalties or other form of contingent payment. As far as I can tell the design is an open ascending auction.

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‘.

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!

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.

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.

Join 103 other followers


Get every new post delivered to your Inbox.

Join 103 other followers

%d bloggers like this: