allocation problem

The tea room is a wonderful thing. You sit and work with a cup of Constant Comment, and interesting people drift in and out and talk about interesting things. A filter-feeder lifestyle, with math taking the place of tasty plankton.

One example: on Friday there was a talk about the allocation problem with submodular utility functions. It's an economic question: given a group of people with different desires (utility functions) and a set of items they can receive, how can you allocate the resources to maximize everyone's happiness? To make life simpler, they assumed that the utility functions were submodular, that is,
w(A) + w(B) <= w(A \cup B) + w(A \cap B). This translates to decreasing marginal value, or risk aversion.

They set up a random rounding procedure that, in polynomial time, can take a given allocation and improve it until it is some fraction r of the value of the feasible solution for that instance of the problem; also, r > 1 - 1/e.

The most obvious way to set up an allocation is to allow each player to choose a "tentative set," and then resolve disputes between players who claim the same item by giving it to whoever can get the most utility from it. This winds up giving exactly a bound of 1 - 1/e, which Vondrak improves on with more sophisticated random rounding methods.

He ran through it fast, so I missed quite a few of the details; I'll have to read the paper through when (and if!) I have time. The amazing thing is that everything looks elementary.

I'm pretty blown away. It seems to me that a lot of the hard problems in the world (energy consumption comes to mind first) are essentially questions of allocating resources to people with different priorities. People call it "policy" and not math, but these guys just showed that in a specific kind of model you can always get better than 63% of the best solution.