We consider the problem of capacity expansion in telecommunication networks under uncertain economic conditions with various market structures. We assume that the demands for network capacity have constant price-elasticity, and demand functions are parameterized by an economic condition that is modeled by a discrete time Markov process. We apply dynamic programming to obtain a state-dependent capacity expansion strategy that maximizes expected total discounted cash flow. We incorporate partial reversibility of investment by differentiating the purchasing cost and the salvage value of the capacity. This partial reversibility makes the value function non-differentiable and divides the solution space into BUY, KEEP, and SELL regions. By identifying certain structural properties of the optimal solution, we perform sensitivity analyses on the optimal investment decisions with respect to market parameters. Under the condition that the level of cost depreciation is larger than that of the downside movement of the economic condition in each time period, we are able to obtain an analytical expression for the optimal capacity level and reduce the multi-period investment decision problem into a single-period myopic problem. As a result, optimal capacity increment depends only on the current economic condition. We study this problem under both monopolistic and oligopolistic market structures. In particular, we investigate investment decisions by two firms in a duopoly setting with Cournot competition. We prove the existence and the uniqueness of the Cournot equilibrium strategies in the duopolistic capacity investment problem. In addition, we show how competition between firms affects total available capacity in the market, capacity price, consumer surplus, expected time to a certain level of price reduction, and expected time to the first investment. We perform an empirical analysis to test a theoretical prediction obtained from our model through linear regression utilizing historical market data. By examining several alternative indices as a proxy to the economic condition considered in our model, we show that the Civilian Employment is the best proxy to use in validating the linear relationship between telecommunications capacity expansion and the economic indicator.

The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for algorithm design, which is to optimize in the presence of strategic behavior. Second, it has prompted us to consider the computational aspects of various solution concepts from game theory, economics and auction design which have traditionally been considered mainly in a non-constructive manner. In this thesis we present progress along both these directions. We first consider optimization problems that arise in the design of combinatorial auctions. We provide an online algorithm in the important case of budget-bounded utilities. This model is motivated by the recent development of the business of online auctions of search engine advertisements. Our algorithm achieves a factor of $1-1/e$, via a new linear programming based technique to determine optimal tradeoffs between bids and budgets. We also provide lower bounds in terms of hardness of approximation in more general submodular settings, via a PCP-based reduction. Second, we consider truth-revelation in auctions, and provide an equivalence theorem between two notions of strategy-proofness in randomized auctions of digital goods. Last, we consider the problem of computing an approximate Nash equilibrium in multi-player general-sum games, for which we provide the first subexponential time algorithm.