We consider the item pricing problem for revenue maximization, where a single seller with multiple distinct items caters to multiple buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items, and we design randomized pricing strategies to maximize expected revenue. We consider dynamic uniform strategies, which can change the price upon the arrival of each buyer but the price on all unsold items is the same at all times, and static nonuniform strategies, which can assign different prices to different items but can never change it after setting it initially. We design pricing strategies that guarantee poly-logarithmic (in number of items) approximation to maximum possible social welfare, which is an upper bound on revenue. We also show that any static uniform pricing strategy cannot yield such approximation, thus highlighting a large gap between the powers of dynamic and static pricing. Finally, our pricing strategies imply poly-logarithmic approximation for revenue-optimal incentive compatible mechanisms, in multiparameter combinatorial auctions with subaddititve buyer valuations, which is the best known guarantee given by efficient mechanisms for both prior-free and Bayesian settings.

Market making refers broadly to trading strategies that seek to profit by providing liquidity to other traders, while avoiding accumulating a large net position in a stock. In this paper, we study the profitability of market making strategies in a variety of timeseries models for the evolution of a stock's price. We first provide a precise theoretical characterization of the profitability of a simple and natural market making algorithm in the absence of any stochastic assumptions on price evolution. This characterization exhibits a trade-off between the positive effect of local price fluctuations and the negative effect of net price change. We then use this general characterization to prove that market making is generally profitable on mean reverting time series --- time series with a tendency to revert to a long-term average. Mean reversion has been empirically observed in many markets, especially foreign exchange and commodities. We show that the slightest mean reversion yields positive expected profit, and also obtain stronger profit guarantees for a canonical stochastic mean reverting process, known as the Ornstein-Uhlenbeck (OU) process, as well as other stochastic mean reverting series studied in the finance literature. We also show that market making remains profitable in expectation for the OU process even if some realistic restrictions on trading frequency are placed on the market maker.

Cut games and party affiliation games are well-known classes of potential games. Schaffer and Yannakakis showed that computing pure Nash equilibrium in these games is PLS-complete. In general potential games, even the problem of computing any finite approximation to a pure equilibrium is also PLS-complete. We show that for any ∈ > 0, we design an algorithm to compute in polynomial time a (3+∈)-approximate pure Nash equilibrium for cut and party affiliation games. Prior to our work, only a trivial polynomial factor approximation was known for these games. Our approach extends beyond cut and party affiliation games to a more general class of satisfiability games.

We report on a series of highly controlled human subject experiments in networked bargaining. The basic interaction between two players is the decision of how to share a mutual payment; we extend this to situate the players in a network. Various theories predict, to different levels of uniqueness, what the shares will be. We analyze our experimental results from three points of view: social efficiency, nodal differences, and human differences; and contrast our behavioral results with the theories.

We study the ITEM PRICING problem for revenue maximization in the limited supply setting, where a single seller with n distinct items caters to m buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items. Each buyer buys a subset of yet unsold items that maximizes her utility. Our goal is to design pricing strategies that guarantee an expected revenue that is within a small multiplicative factor of the optimal social welfare an upper bound on the maximum revenue that can be generated by any pricing mechanism. Most earlier work has focused on the unlimited supply setting, where selling an item to a buyer does not affect the availability of the item to the future buyers. Recently, Balcan et. al. studied the limited supply setting, giving a randomized pricing strategy that achieves a 2O(?(log n log log n)-approximation; their strategy assigns a single price to all items (uniform pricing), and never changes it (static pricing). They also showed that no pricing strategy that is both static and uniform can give better than 2??(log1/4 n)-approximation. Our first result is a strengthening of the lower bound on approximation achievable by static uniform pricing to 2??(log n). We then design dynamic uniform pricing strategies (all items are identically priced but item prices can change over time), that achieves O(log2n)-approximation, and also show a lower bound of ? ((log n/ log log n)2) for this class of strategies. Our strategies are simple to implement, and in particular, one strategy is to smoothly decrease the price over time. We also design a static nonuniform pricing strategy (different items can have different prices but prices do not change over time), that give poly-logarithmic approximation in a more restricted setting with few buyers. Thus in the limited supply setting, our results highlight a strong separation between the power of dynamic and non-uniform pricing strategies versus static uniform pricing strategy. To our knowledge, this is the first non-trivial analysis of dynamic and non-uniform pricing schemes for revenue maximization in a setting with multiple distinct items.

We consider models for bargaining in social networks, in which players are represented by vertices and edges represent bilateral opportunities for deals between pairs of players. Each deal yields some fixed wealth if its two players can agree on how to divide it; otherwise it yields no wealth. In such a setting, Chakraborty and Kearns (WINE 2008) introduced a simple axiomatic model that stipulates an equilibrium concept in which all players are rationally satisfied with their shares. We further explore that equilibrium concept here. In particular, we give an FPTAS to compute approximate equilibrium in bipartite graphs. We also show that equilibrium is not unique, and give conditions that ensure uniqueness on regular graphs. Finally, we explore the effect of network structure on solutions given by our model, using simulation methods and statistical analysis.

We study the survivable network design problem (SNDP) for vertex connectivity. Given a graph G(V,E) with costs on edges, the goal of SNDP is to find a minimum cost subset of edges that ensures a given set of pairwise vertex connectivity requirements. When all connectivity requirements are between a special vertex, called the source, and vertices in a subset T ⊆ V, called terminals, the problem is called the single-source SNDP. Our main result is a randomized kO(k2) log4n-approximation algorithm for single-source SNDP where k denotes the largest connectivity requirement for any source-terminal pair. In particular, we get a poly-logarithmic approximation for any constant k. Prior to our work, no non-trivial approximation guarantees were known for this problem for any k ≥ 3. We also show that SNDP is kΩ(1)-hard to approximate and provide an elementary construction that shows that the well-studied set-pair linear programming relaxation for this problem has an Ω(k1/3) integrality gap.

We study the complexity of reachability problems on various classes of grid graphs. Reachability on certain classes of grid graphs gives natural examples of problems that are hard for NC1under AC0reductions but are not known to be hard far L; they thus give insight into the structure of L. In addition to explicating the structure of L, another of our goals is to expand the class of digraphs for which connectivity can be solved in logspace, by building on the work of Jakoby et al. (2001), who showed that reachability in series-parallel digraphs is solvable in L. We show that reachability for single-source multiple sink planar dags is solvable in L