## Friday, May 1, 2015

### Utility maximization, matching and information equilibrium

Roger Farmer mentioned in a comment on his blog (that I discuss here) that he was using competitive search instead of Arrow-Debreu equilibrium -- that is to say search/matching theory (S/M) instead of utility maximization (UM) as a guiding principle. Matching is a somewhat weaker assumption than utility maximization (you end up at a point a little worse off than the utility maximum ... and there are invariably more points close to the utility maxima than there are utility maxima).

I thought this was a good context in which to present the idea of information equilibrium (IE) and non-ideal information transfer (NI). Let's use a concrete example; we'll say we have 11 people labeled by the numbers 2-12. Let's also say the distribution of utility D0 is given by the probability distribution of the roll of two dice:

That is to say person 7 has the highest utility (will pay the highest price for the widgets) and people 2 and 12 lave the lowest utility (have the lowest price they are willing to pay). You can also think of this as the distribution of demand in this example. Additionally, it is useful to think of person 2 and person 12 as effective producers of widgets and others as relative consumers of widgets.

What distribution of widgets W maximizes utility? W = D0. I'll illustrate this in the following graph for 20 widgets  (blue boxes):

That means for UM we have the condition W = D0  defining the allocation. You can also think of the blue boxes as representing the distribution of supply

How does this work for matching theory? Well, search costs enter into that model and we end up with some unfulfilled utility ... and for small search costs we have the condition W ≈ D0 for S/M. The distribution looks like this:

You in general have unmet supply (not all 20 widgets are allocated) with the matching approach -- this corresponds to e.g. unemployment in labor search models.

Information equilibrium represents a further weakening of the allocation condition to I(W) = I(D0), i.e. the information in the distribution of widgets/supply is equal to the information in the distribution of utility/demand. We can construct a distribution of widgets containing asymptotically the same information as D0 by rolling dice 20 times:

And finally we come to the least restrictive condition I(W) < I(D0) for non-ideal information transfer. The worst case (farthest from ideal) would be all 20 widgets belonging to person 2 or person 12 (i.e. the producers of widgets haven't sold anything -- a good analogy of a recession). A typical case (well, one generated randomly) would look like this :

With these examples, we have generated a hierarchy of the restrictiveness of the conditions -- in order of decreasing restrictiveness

1. Utility maximization (UM) with W = D0
2. Search/matching (S/M) with W ≈ D0
3. Information equilibrium (IE) with I(W) = I(D0)
4. Non-ideal information transfer (NI) with I(W) < I(D0)

In the limit of a large number of rolls over a long time, the condition I(W) = I(D0) is equivalent to W = D0, but for any finite example there exist more states where I(W) = I(D0) than states where W = D0.

A sequence of 20 rolls that fit with information equilibrium at each roll (each time step) are varied -- they are all sequences you can get from rolling dice 20 times. Here are 10 examples:

None of the above rolls are consistent with utility maximization at each time step (the 3rd one from the right comes close, though). The sequences consistent with utility maximization at each roll all begin with 7, 6, 8 ...  or 7, 8, 6 ... ; they represent less than 1.3% of all possible histories (the probability of rolling 7, 6, 8 or 7, 8, 6) while the IE-consistent rolls make up more than 98.7% of the possible histories.

However, the key point I wanted to make is that utility maximization and search/matching approaches represent special cases of the information theory approach. The history of transactions bringing the distributions W and D0 into 'equilibrium' (i.e. making W → D0) in the UM and S/M cases are contained in the sequences of transactions bringing W and D0 into information equilibrium.

Footnotes

 Ok, there are 21 boxes here. For those who counted, you have won this round!

 This also illustrates rational expectations if we consider the process by which widgets are assigned is via the rolling of dice -- the utility distribution is equal to the distribution of dice being rolled. No one expects an oversupply of 2's or a roll of 13, so the utility distribution matches the outcome.

 In reality, you'd need to look at a far larger number of widgets to really tell the difference between the ideal and non-ideal cases. The NI distribution is an improbable result of rolling 20 dice, but is not actually significant at the 5-sigma level, for example.

1. " Ok, there are 21 boxes here. For those who counted, you have won this round!" Haha... I did count, and was going to point that out.

Also, for the 2nd figure (i.e. "Matching") there are only 16 boxes. Does that mean the search itself 'cost' 4 boxes then?

You write:

"The sequences consistent with utility maximization at each roll all begin with 7, 6, 8 ... or 7, 8, 6"

Ok, so for each allocation, you're maximizing utility then. There's no first allocation that gives you more utility than to start with 7, and then to move onto either 6 or (equivalently) 8. What would the optimal 4th allocations look like? Back to 7 again, or do we start filling in 5 or 9? Is there a way (for us) to tell, or is there a hidden utility function you're using we're not privy too? What price will person 7 pay for his 2nd widget as compared to the price 5 will 5, 6, 8 or 9 will pay for their first?

"while the IE-consistent rolls make up more than 98.7% of the possible histories."

Here you lose me. If the dice are fair, I don't see why this isn't 100%.

" In reality, you'd need to look at a far larger number of widgets to really tell the difference between the ideal and non-ideal cases. The NI distribution is an improbable result of rolling 20 dice, but is not actually significant at the 5-sigma level, for example."

Same question: isn't NI just unfair dice?

Ah!... you're talking some kind of statistical test to see if the data is 'consistent' with a distribution, aren't you? So there's a chance that with even fair dice you'll find a sequence of 20 rolls for which this statistic indicates an result inconsistent with the distribution.

Shoot! You're always making me use my brain. It's not right. ;D

Great stuff! Fits right into my questions on more recent posts. BTW, I assume it's just an unfortunate accident that the boxes are not the same dimension vertically as one-unit on the y-axis?

1. 1. There is a lot more ambiguity in the filling pattern that maximizes utility as you add boxes. The result would depend on maximizing the overlap integral, but would have a left-right ambiguity.

2. I probably should have said "an additional 98.7%" (totaling 100%).

3. NI could probably be modeled as unfair dice, but may not be a true random variable and hence might not have a distribution from which it is drawn.

4. The probability for the dice rolls aren't whole numbers, but the results of dice rolls (boxes) are whole numbers. It would probably be better to normalize the result at each step of the way, but that is less illustrative.

2. 5. I wouldn't say the search cost 4 boxes; those left off are more like unemployed labor states.

Comments are welcome. Please see the Moderation and comment policy.

Also, try to avoid the use of dollar signs as they interfere with my setup of mathjax. I left it set up that way because I think this is funny for an economics blog. You can use € or £ instead.