The problem of maximizing a non-negative submodular function was introduced by Feige, Mirrokni, and Vondrak [FOCS07] who provided a deterministic local-search based algorithm that guarantees an approximation ratio of $frac 1 3$, as well as a randomiz
ed $frac 2 5$-approximation algorithm. An extensive line of research followed and various algorithms with improving approximation ratios were developed, all of them are randomized. Finally, Buchbinder et al. [FOCS12] presented a randomized $frac 1 2$-approximation algorithm, which is the best possible. This paper gives the first deterministic algorithm for maximizing a non-negative submodular function that achieves an approximation ratio better than $frac 1 3$. The approximation ratio of our algorithm is $frac 2 5$. Our algorithm is based on recursive composition of solutions obtained by the local search algorithm of Feige et al. We show that the $frac 2 5$ approximation ratio can be guaranteed when the recursion depth is $2$, and leave open the question of whether the approximation ratio improves as the recursion depth increases.
In this note we study the greedy algorithm for combinatorial auctions with submodular bidders. It is well known that this algorithm provides an approximation ratio of $2$ for every order of the items. We show that if the valuations are vertex cover f
unctions and the order is random then the expected approximation ratio imrpoves to $frac 7 4$.
We study equilibria of markets with $m$ heterogeneous indivisible goods and $n$ consumers with combinatorial preferences. It is well known that a competitive equilibrium is not guaranteed to exist when valuations are not gross substitutes. Given the
widespread use of bundling in real-life markets, we study its role as a stabilizing and coordinating device by considering the notion of emph{competitive bundling equilibrium}: a competitive equilibrium over the market induced by partitioning the goods for sale into fixed bundles. Compared to other equilibrium concepts involving bundles, this notion has the advantage of simulatneous succinctness ($O(m)$ prices) and market clearance. Our first set of results concern welfare guarantees. We show that in markets where consumers care only about the number of goods they receive (known as multi-unit or homogeneous markets), even in the presence of complementarities, there always exists a competitive bundling equilibrium that guarantees a logarithmic fraction of the optimal welfare, and this guarantee is tight. We also establish non-trivial welfare guarantees for general markets, two-consumer markets, and markets where the consumer valuations are additive up to a fixed budget (budget-additive). Our second set of results concern revenue guarantees. Motivated by the fact that the revenue extracted in a standard competitive equilibrium may be zero (even with simple unit-demand consumers), we show that for natural subclasses of gross substitutes valuations, there always exists a competitive bundling equilibrium that extracts a logarithmic fraction of the optimal welfare, and this guarantee is tight. The notion of competitive bundling equilibrium can thus be useful even in markets which possess a standard competitive equilibrium.
We study the necessity of interaction between individuals for obtaining approximately efficient allocations. The role of interaction in markets has received significant attention in economic thinking, e.g. in Hayeks 1945 classic paper. We consider
this problem in the framework of simultaneous communication complexity. We analyze the amount of simultaneous communication required for achieving an approximately efficient allocation. In particular, we consider two settings: combinatorial auctions with unit demand bidders (bipartite matching) and combinatorial auctions with subadditive bidders. For both settings we first show that non-interactive systems have enormous communication costs relative to interactive ones. On the other hand, we show that limited interaction enables us to find approximately efficient allocations.
