Where Does Convexity Come From?

I sometimes find it useful to distinguish between 'forwards' and 'backwards' orientations in mathematics. Given some object or family X, we can (in the 'forwards' direction) see what the existence of X entails--what kind of X there are, what more complex objects we can build out of X, etc.

In the backwards direction, we try to tell an 'origin story' about X. What is the question for which X is the answer? What is the process of which X is the result? There's usually no unique answer, and working in this direction gives a measure of creative freedom.

One important subset of backwards-focused activity is finding 'variational characterizations' of concepts. This means looking for maximization (or minimization) processes underlying the formation of the objects X. So, e.g., spheres at first sight seem like the most boring objects in geometry--they're easy to describe, they look the same from every direction, etc.--but the fact that they enclose volume with maximal efficiency is profound, and leads quickly to even deeper math when you look at double bubbles, tilings of space, and so on. Nature often 'tries' to minimize certain potential functions, and social agents try to maximize various perceived benefits, so whatever your area of interest, variational characterization may be an important way of making sense of observed patterns.

Here's a simple example. Why should we study convexity? I'll give a variational characterization from an economic perspective, which gives an origin story for a broad class of convex functions.

***

Peggy and Otto are friends, with different attitudes about nutrition. Peggy thinks it's all about the protein; Otto is buzzed over Omega-3 oils. (They read different magazines.)
In the first flush of enthusiasm for their new health ideas, protein and Omega-3's are the only food variables they care about.

This raises an issue whenever they buy food together: who gets what part of the food item? Ideally, they'd separate out the two key ingredients in a centrifuge, but for now, food items should be assumed to have, in each region, local 'densities' of the two nutrients that are nonseparable. The best the friends can do is break the food into tiny bits, estimate the protein and Omega-3 in each, and use this information to decide on an allocation.

We're not sure what's 'fair', exactly, but we can describe the 'frontier' of best possible trade-offs between Peggy and Otto's perceived benefits. Given a food item, define a function f(x) to be the maximum amount of Omega-3 that can be consumed by Otto, subject to the constraint that Peggy gets at least an x amount of protein.

Then f maps nonnegative reals to nonnegative reals. Moreover, it's convex down on the region where it's positive, that is, its underside is a convex body:



Why? Intuitively, we arrange the crumbs of the food item in increasing order of their protein-to-Omega-3 content ratio. As we begin giving Peggy more and more protein, we initially can do it most 'cost-effectively' by feeding her the crumbs for which this ratio is highest, but as we go on we are forced to give up more and more Omega-3 for each marginal unit of protein.

I leave it to hard-core readers to fill in details about exactly when this logic can be made rigorous; I have in mind continuous additive set measures over a compact set, and by 'maximum' I mean 'supremum'. However, I regard this result as 'morally true' (a phrase I adopted from Prof. Thomas Hunter at Swarthmore), that is, true with 'reasonable' assumptions and relatively robust to changes in the model.

What's more, the converse is also true: given any such function f(x) (nonnegative-to-nonnegative, convex down on its bounded support), I can make you a food item such that f(x) represents the set of optimal trade-offs between protein and Omega-3's.
($19.95 shipping and handling. Warning: product may taste like a soggy brick.)

So there you have it: a variational characterization of convexity, a 'recipe' if you will, with additive measures and optimization as the basic ingredients. Since many results in theoretical economics assume convexity of various types, recipes like this one (which is not new, but amounts to folklore as far as I can tell) are an important part of the 'pre-theory' of the discipline, motivating and making plausible such assumptions. Challenges to the use of these assumptions, then, should critically engage the pre-theory, for instance, by identifying cases, in both production and consumption of goods, where interaction between inputs makes additivity unrealistic. In the case at hand, of course, we know that the two friends are both wrong--nutritional 'value' is not an additive function of food consumed, as e.g. fats and protein are both necessary. (It's not even clear that nutrition should be considered a real-valued function, since there are multiple health/fitness goals one might be interested in.)

***

I'll end with a question to the readers: I am interested in the origin stories of probability distributions, and have from time to time skimmed over the literature regarding the trendiest distributions of them all, the power laws. I know there are a multitude of settings that give rise to them. So which ones should I study, and from which references?
I have no single criterion in mind, but am receptive to any of the following: rigor, interest, plausibility, generality, simplicity. I am also interested in critical analyses of the apparent power-law 'gold rush' in complexity studies. Thanks!

Out of My Depth

You are in a pitch-black room. But don't be alarmed.

Someone is pouring liquid at a slow, uniform speed into a thin, transparent vessel; it is pooling at the bottom. The fluid itself is dark, but when in direct contact with the atmosphere it glows purple. So what you see is precisely the evolving shape of the fluid's surface. It seems that you stand to learn something: the shape of the inside of the vessel will be gradually revealed in cross-sections.

But wait--this seems to rely on the assumption that the vessel itself is not moving. Suppose, instead, that the vessel is almost perfectly weightless, and may roll as the heavy liquid's center of gravity shifts.

Can you reconstruct the vessel's shape in this case?

I'm curious to know, but probably underequipped to solve this question, which was the result of a momentary hallucination during a long concert. There are some potential messy issues with cusps, and questions of whether the vessel is open at the top, etc., to which I advise that one assumes whatever makes the problem interesting or tractable.

Money Colliding at High Speeds

Are there any gamers among my vast readership? Here is a simple auction-based card game I once toyed with; I'm curious what others think, and how it might be souped up for greater replay value.

For two or three players. Each receives all 13 cards in a suit, which they hold privately; the remaining suit (diamonds) is shuffled and put face down. On each round, a diamond card is flipped face up; players simultaneously submit a 'bid' card from their suit. The highest bid gets the diamond (ties can be handled in one of several ways, suit yourselves), and all bid cards used get discarded.

To score when all diamonds have been auctioned: each player gets m points for the m of diamonds, 11 for the jack, etc.

This game can reach a maniacal level of second-guessing--exciting, but perhaps too little in the way of underlying strategy and calculation. It is easy to show that no deterministic strategy is 'undominated' (i.e. there is always a victorious counter-strategy); but I don't see that any simple randomized strategy is undominated either.

Suggestions? Pointers to successful auction games already on the market? I'd look into them myself, but then half of my attraction to the auction genre is that I'm a cheapskate.

Math and MarketThink

I recently stumbled upon a book that made me really happy. It's called 'No One Makes You Shop At Wal-Mart: The Surprising Deceptions of Individual Choice', by Tom Slee (who has a very nice blog going as well, called Whimsley). This is a clearly written, engaging treatment of classic game-theoretic situations as encountered in consumer decision-making. It outlines what I think are some of the simplest and most powerful ways to challenge the thesis that consumers can reliably 'vote with their dollars' to promote the goods, services, social structures, and way of life that they most value.

I say 'challenge', not 'refute'. Slee takes a patient approach, showing readers how to construct simple economic models and reason about their consequences. The models, in fact, are deliberately oversimplified in order to isolate patterns and identify their potential recurrence in a variety of situations.

Slee's title example is a schematic fable of the rise of big outlet stores on the fringes of town: Wal-Mart comes in, underprices the smaller and economically interdependent downtown stores; consumers, who value access to a vibrant downtown, nevertheless 'selfishly' shop at Wal-Mart when it suits them, relying the patronage of others (upon which they 'free-ride') will keep downtown afloat. Downtown declines, and consumers are (potentially) all made worse off as a result.

This little story alone is (as Slee recognizes) hardly an indictment of Wal-Mart. But it is an internally consistent model that is no more schematic than the implicit model of commerce (which Slee calls 'MarketThink') underlying much economic discourse. It puts failure of 'market democracy' on the table as a thinkable, plausible outcome; as such it can shift the terms of debate and orient more empirically-grounded investigation.

As I see it, unregulated free markets, and crude forms of MarketThink, have at least two serious weaknesses:
1) they fail to adequately address concerns about equity and the welfare of the worst-off;
2) they fail to give adequate provision of public goods (like clean air and water, nature, community development, etc.), and they overproduce public 'bads' (like traffic), with similar potential problems involving fashion goods, network goods, and other goods proeducing 'externalities' of various types.

The claims of the disadvantaged upon public conscience and policy in the US have, on the whole, come a long way in the past century; but as no objective measure of human welfare has been widely accepted, their foothold within economic theory remains tenuous. GDP, 'consumer surplus', and other measurable constructs--generally biased towards markets and equity-insensitive--serve as dominant proxies for human welfare. Problem 1) poses a serious challenge, in discourse as well as on the ground.

On the other hand, problem 2) (which is Slee's focus) has (to an extent not realized by many people) long been recognized and taken seriously by economic theorists. The 'Welfare Theorems' inspired by the writings of Adam Smith, which undergird the general confidence in markets by neoclassical economic theorists, explicitly assume away the possibility of goods whose production and consumption directly affect anyone except buyer and seller. (They also make a certain technical assumption, involving convexity, that is meaningfully restrictive and worth pondering--another post, maybe.) Economists have acknowledged real-world violations of these assumptions, and proposed various remedies (often market-based), at least since Pigou in the '30s. Game theory has expanded and clarified these debates (as Slee shows, while also showing how little in the way of 'hard math' is really involved to make the basic points).

Still, the Welfare Theorems form the 'core message' of most introductory econ texts I have perused or studied from, and the Invisible Hand is the most pervasive idea (often implicit) in popular discussions of markets. Further, I believe that many critics of market absolutism have, in their suspicion of economics, insufficiently tapped the Prisoner's Dilemma and related ideas of game theory, which combine

-simplicity;
-generality;
-memorability;

-establishment credentials and currency within the discourse of economics, without being dependent either on the crudest assumptions (e.g. "money's all that matters") popularly and incorrectly attributed to that field, or on assumptions and concepts foreign to it;

-considerable integrity and truth.

This is not to say game theory doesn't have shortcomings--it does. Nor is it to say that game theory points the way to any clear solutions to the dilemmas it diagnoses, or that any rival to market liberalism can definitively solve them. Again, Slee's book doesn't aim to describe a master theory, or match theory to observation, or save the world. Instead it illustrates that mathematics can help us think (and argue) about social reality without laying claim to full knowledge, denying the world's complexity, or suppressing and devaluing the unmeasurable. This alone is enough to make me hope 'No One Makes You Shop At Wal-Mart' gets widely read.

Math for Little People

I'm 22. There's a part of me that's asking: "Why haven't you proved any great theorems yet?" But I can't beat myself up too much over this--with Republicans in the White House, and with so much HBO magic happening lately, the odds are stacked against me.

But there's a different kind of math anxiety creeping up: one of these days, I might have kids. Those kids are going to be curious about the world around them, and they're going to look to me for answers--at least when their mother isn't around.

For the most part, I'll be happy to fend them off with a mix of idle speculation and propaganda. But... what if they ask why honeycombs have six sides?

What if they want to know why scooting towards the middle of the see-saw makes you go up? What if they ask why the rubber chain-links on the swing don't ever come apart, if they're not 'connected'? Could I in good conscience give sloppy answers to questions I know involve beautiful math?

I know the Feds wouldn't come and take them away; I know the kids won't be too disappointed; I know their appetite for rigorous proof will come slowly, if at all. But could I live with myself? No, I've got to get a better grasp of the 'basic facts' of life in our spatial world before I help bring someone new along, if only for my own sake.

But what are these? It's up for grabs, but here's the category I've had in mind mostly: qualitative features of structures, arrangements, and movement, observable by 'medium-sized' agents like children, and generated by/consistent with a naive 'block-world' understanding of matter and physical law (not referring to the AI environment of that name, but in a similar spirit). This is the conceptual space in which I've lived most of my life (and thought about discrete math and computer science), and if it's good enough for me it's good enough for my kids. Molecules and lightning bolts I won't sweat so much, but Block World I want to get right.

So then... how to pick out, think about, and explain its most important facts?

Some of them are, I think, topological, as I've alluded with the swing example. But kids won't swallow homotopy theory any more than they'll eat lima beans, even if I can still remember it by then. Anyways, there's a potential save here: Block World is basically discrete, so the space of 'topological' deformations of objects is much smaller and more well-behaved (I've already posted on discretization in topology).

A good place to start would be the Jordan Curve Theorem, famed for its difficulty in spite of its surface obviousness: what could be clearer than the fact that a non-self-intersecting loop in the plane divides the plane into two components, 'inside' and 'outside'?

As one discrete formulation, consider the loop as a path on the grid, where each step in any direction is of even length. Then it appears that the inside is path-connected, also by grid paths (without the even-length restriction), and separated from the outside. For example:



I think this problem is excellent fodder for thought, and I would encourage anyone who's been scared away by the Theorem in the past to work on it in this friendlier setting.

No hints, though--would your kids respect you?

(Clarification for concerned parties: there are no children on the horizon; I do believe in responsible parenting; and I don't get HBO, although I do swear by Curb Your Enthusiasm.)

Assignment Testing and PCPs

Would anyone like to improve their understanding of the PCP Theorem? This is, in my opinion, the most amazing result in all of computer science, and with the recent work of Irit Dinur its proof should be within reach of a much larger audience. However, there is still considerable complexity involved.

I recently finished writing an expository paper called Building Assignment Testers that presents one key step in Dinur's proof, the step which is most algebraic and most indebted to previous PCP constructions. In my paper I state the PCP Theorem, build and analyze 'assignment testers', and explain why this step is also sufficient to give a weaker version of the PCP Theorem, in which the proof string supplied by the prover is not required to be polynomially bounded.

Several good references are available already, but in the paper I explain why I hope my work represents an expository advance. Essentially, I aim to make clearer how assignment testing can be viewed as a natural composition of simple statistical tests, and how these tests can be first analyzed in isolation, then combined by a general lemma.

For anyone who saw and enjoyed my talk on Property Testing, or read the Powerpoint, Assignment Testers are an important and very interesting application of the testing paradigm--a natural next step for study.

Enjoy the paper! Of course, I welcome questions and comments.