A certain state, known for its beautiful land and its tough regulations, faces a dilemma. In the spirit of strict liability, the people have decided that the government must pay owners for any zoning laws that reduce property values or forgo enforcement.

Suppose, for example, that you own a house in the woods, but have a strong desire to put up a fast food joint with an enormous parking lot. Your property value may go up. Your neighbors, on the other hand, might protest that the fast food development would cause their property values to decrease because of the resulting eyesore and pollution.

How does a state deal with such conflicting interests? This puzzle presents two alternative proposals and then proposes a challenge problem having to do with the fairer of the two.

Suppose a person P could prove a benefit of B dollars if she could develop. Suppose N, a neighbor of P, could prove that he would suffer a loss of L if P develops. "Neighbor" can be defined many ways, but for our purposes we will represent the neighborhood relationship by a graph. That is, nodes (property owners) in the graph may be connected to other nodes via edges, perhaps based on adjacency or line of site. Further, the graph is undirected, meaning that if A is a neighbor of B then B is also a neighbor of A.

If P develops, then P will have to pay each neighbor the value of that neighbor's loss. We can assume that P would not develop if she would have to pay out more than she would benefit.

Consider this figure:

Oregon Lore 1: Associated with each node (property) is a value for development. Suppose that the loss a neighbor N suffers due to the development of P is the benefit to development N gains divided by its number of neighbors. For example, F suffers a loss of 5 if one of A, C, or E develops. If one develops (say A), then F suffers a loss of 7.5 if either C or E develops.
Once a property develops, the owner is not allowed to object any further to development of any neighbor.

Let's start with the following rule that relates a property owner's losses directly to his or her benefits.

Personal Loss Rule:
Each property owner P's loss due to development by a neighbor is equal to P's benefit from his own development divided by the number of P's neighbors. Thus, the more P can claim as benefit from her own development, the more she can claim as a loss if others develop. In the figure above, E will lose 40 if F develops, whereas F will lose only 5 if E develops. On the other hand, if E develops, then F's losses will be redistributed to A and C (7.5 each). Finally, once a property owner P develops, then she can no longer complain if a neighbor N develops, so P's loss due to N's development goes to zero. This is called the No Tears proviso.

In the graph of the figure, E, D and A will develop first, then C and then F and B. Under the Personal Loss Rule, peripheral nodes or nodes receiving a lot of development benefit tend to develop first. It is quite hard to stop development once it starts.

Warm-Up 1: Again, to train your intuition, is there any assignment of benefits under the Personal Loss Rule that will prevent any development in this topology?

Solution to Warm-Up 1:
There are many solutions but here is one.


Oregon Lore 2: According to the Sprawl Rules, no development will occur in this situation. What happens if even one benefit changes?

The assigned values are: A = 20, B = 20, C = 30, D = 10, E = 10, and F = 30. (As Karven Lam of New York University has observed, if the benefit of each node equals the number of neighbors of that node, then this will be stable. All solutions are proportional to that one, I believe.)

Warm-Up 2: What happens if any of these benefits change?

Solution to Warm-Up 2:
Full development will occur. For example, if C were reduced to 29 in the solution to Warm-Up 1, then B, D and F would all develop and then so would the rest. That is, even if someone decreases his claimed benefit from developing then that person will eventually be able to develop!