Submodular Functions in Generalized Matching Markets and Game Theory
A set function (a function mapping a set to a value) is said to be submodular if it has the property that the function value increases more and more slowly as more elements are added to the input set. Intuitively, these functions have a diminishing returns property. Recently, there have been much research into this field, and applications have been made to both generalized matching markets and game theory. I was introduced to these functions as I was looking into the max cut problem. It turns out that submodular maximization problems are a natural generalization of the max cut problem.
Just like the max cut problem, submodular maximization problems are NP-hard. There have been recent greedy algorithms and approximation algorithms that solve and approximate the submodular maximization problem given certain constraints. First we examine applications of submodular maximization problems to welfare problems, which are generalizations of the matching market problem.
We’ve seen how the bipartite matching problem is the general case of the single item auction problem. This has been done by creating n-1 fake sellers, and buyer i is given a valuation of 0 for the items offered by these fakes. Since the bipartite problem can be used to solve an instance of the single item auction problem, it is in a sense a harder problem to solve. We can see this is the case since the algorithm to compute the bipartite matching is a much more complicated one than finding out who wins in a single item auction.
Now, consider a more general version of the matching matching problem where there are m goods and n players, and a utility function mapping the power set of m to a natural number for each player. This problem is a generalization of the matching market problem since we can set m = n and design the welfare function so that each player gets one good (by making the function only map singleton sets).
We can therefore expect the welfare problem to be a much more difficult one than the bipartite matching problem. We saw how the matching market problem has a simple algorithm to create market clearing prices. The welfare problem, however, does not seem to have a simple poy tine algorithm. We can, however, model the welfare problem as a special case of the submodular maximization problem given a matroid constraint (Vondrak). Using this approach, Vondrak describes a randomized algorithm that can provide a (1−1/e) approximation to the welfare problem.
Submodular functions are also involved in game theory. Consider the cooperative game that was mentioned in Chapter 12, which “studies how a collection of players will divide up the value arising form a collective activity”. The textbook mentions a “core solution” which characterizes stability. It turns out if we generalize this problem to N players, the problem again becomes more difficult. However, referring to the Toriello Lecture, we can design a characteristic function c mapping form the power set of N to a real number, representing the cost that the players pay when working together. It turns out (proof in the Toriello lecture notes) that if c is submodular, the game becomes convex, and there is a deterministic greedy algorithm that can solve the allocations of costs to each player in polynomial time.
In all, we see how generalizing problems make the problems harder and harder to solve. Submodular function maximization is one way to tackle the increased complexity that results from generalization in matching market problems and game theory problems.
Sources used:
http://www2.isye.gatech.edu/~atoriello3/submod.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.104&rep=rep1&type=pdf
http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf