We present algorithms for a class of resource allocation problems both in the online setting with stochastic input and in the offline setting. This class of problems contains many interesting special cases such as the Adwords problem. In the online setting we introduce a new distributional model called the adversarial stochastic input model, which is a generalization of the i.i.d model with unknown distributions, where the distributions can change over time. In this model we give a 1-O(ε) approximation algorithm for the resource allocation problem, with almost the weakest possible assumption: the ratio of the maximum amount of resource consumed by any single request to the total capacity of the resource, and the ratio of the profit contributed by any single request to the optimal profit is at most O(ε²/log(n/ε)) where n is the number of resources available. There are instances where this ratio is ε²/log(n/ε) such that no randomized algorithm can have a competitive ratio of 1-o(ε) even in the i.i.d model. The upper bound on ratio that we require improves on the previous upper-bound for the i.i.d case by a factor of n.

Our proof technique also gives a very simple proof that the greedy algorithm has a competitive ratio of 1-1/e for the Adwords problem in the i.i.d model with unknown distributions, and more generally in the adversarial stochastic input model, when there is no bound on the bid to budget ratio. All the previous proofs assume that either bids are very small compared to budgets or something very similar to this.

In the offline setting we give a fast algorithm to solve very large LPs with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1+ε) the mixed packing-covering problem with O(δγmlog(m/ε)/ε²) oracle calls where the constraint matrix of this LP has dimension mn, the success probability of the algorithm is 1-δ, and γ is a parameter which is very similar to the ratio described for the online setting. We discuss several applications, and how our algorithms improve existing results in some of these applications

The convexity assumptions required for the Arrow-Debreu theorem are reasonable and realistic for preferences; however, they are highly problematic for production because they rule out economies of scale. We take a complexity-theoretic look at economies with non-convex production. It had been known that in such markets equilibrium prices may not exist; we show that it is an intractable problem to achieve Pareto efficiency, the fundamental objective achieved equilibrium prices. The same is true for core efficiency or any one of an array of concepts of stability, with the degree of intractability ranging from FΔ₂^P-completeness to PSPACE-completeness. We also identify a novel phenomenon that we call complexity equilibrium in which agents quiesce, not because there is no way for any one of group of them to improve their situation, but because discovering the changes necessary for (individual or group) improvement is intractable. In fact, we exhibit a somewhat natural distribution of economies that gives an average-case hard complexity equilibrium.

Following Babaioff, Kleinberg, and Slivkins [BKS10], we study single-call mechanisms --- truthful mechanisms that evaluate an allocation function only once per instantiation.

First, we show that single-call mechanisms are possible for maximal-in-distributional-range (MIDR) allocation rules, i.e. computing truthful payments is essentially as easy as computing a single allocation. We give a procedure that transforms a multi-parameter MIDR allocation rule into a truthful in expectation mechanism that makes a single black-box call to the allocation function. The resulting mechanism gives the optimal outcome with probability arbitrarily close to 1. We also characterize all single-call black-box reductions for MIDR allocation rules and prove our transformation optimizes the trade-off between the probability of selecting the outcome of the original allocation rule and the magnitude of the largest payment.

Second, we study optimal transformations in single-parameter settings. In [BKS10], Babaioff et al. ask if their transformation optimizes the trade-off between the largest rebate and the probability of selecting the right outcome --- we answer this question in the affirmative and show that generalizing their construction gives a family of optimal transformations under two natural definitions of rebate. In the process, we succinctly characterize the space of truthful in expectation single-call transformations for single-parameter domains, and we show that a single-call mechanism may be implemented with no positive transfers if a sufficiently good approximation is known.

We also analyze a special case of the single-parameter setting where the allocation function depends only on the relative order of the bids. We show that a simple construction performs better than [BKS10] in this setting.

We study the information content of equilibrium prices using the market communication model of Deng, Papadimitriou, and Safra. We show that, in the worst case, communicating an equilibrium in a production economy requires a number of bits that is a quadratic polynomial in the number of goods, the number of agents, the number of firms, and the number of bits used to represent an endowment.

We show a range of complexity results for the Ricardo and Heckscher-Ohlin models of international trade (as Arrow-Debreu production markets). For both models, we show three types of results:

1. When utility functions are Leontief and production functions are linear, it is NP-hard to decide if a market has an equilibrium.
2. When utility functions and production functions are linear, equilibria are efficiently computable (which was already known for Ricardo).
3. When utility functions are Leontief, equilibria are still efficiently computable when the diversity of producers and inputs is limited.

Our proofs are based on a general reduction between production and exchange equilibria. One interesting byproduct of our work is a generalization of Ricardo's Law of Comparative Advantage to more than two countries, a fact that does not seem to have been observed in the Economics literature.