A historical collection of technical reports
| Date | Title | Author | Summary |
| 2012 | |||
| 2012-01-24 | A Hybrid Method for Distance Metric Learning | Kao, Yi-hao; Van Roy, Benjamin; Rubin, Daniel; Xu, Jiajing; Faruque, Jessica; Napel, Sandy | We consider the problem of learning a measure of distance among vectors in a feature space and propose a hybrid method that simultaneously learns from similarity ratings assigned to pairs of vectors and class labels assigned to individual vectors. Our method is based on a generative model in which class labels can provide information that is not encoded in feature vectors but yet relates to perceived similarity between objects. Experiments with synthetic data as well as a real medical image retrieval problem demonstrate that leveraging class labels through use of our method improves retrieval performance significantly. |
| 2012-01-24 | Directed Time Series Regression for Control | Kao, Yi-hao; Van Roy, Benjamin | We propose directed time series regression, a new approach to estimating parameters of time-series models for use in certainty equivalent model predictive control. The approach combines merits of least squares regression and empirical optimization. Through a computational study involving a stochastic version of a well known inverted pendulum balancing problem, we demonstrate that directed time series regression can generate signicant improvements in controller performance over either of the aforementioned alternatives. |
| 2010 | |||
| 2010-01-11 | Information Aggregation in Smooth Markets | Iyer, Krishnamurthy; Johari, Ramesh; Moallemi, Ciamac C. | Recent years have seen extensive investigation of the information aggregation properties of prediction markets. However, relatively little is known about conditions under which a market will aggregate the private information of rational risk averse traders who optimize their portfolios over time. We consider a market model involving finitely many informed risk-averse traders interacting with a market maker. Our main result identifies a basic *smoothness* condition on the price in the market that ensures information will be aggregated. We give conditions under which cost function market makers (or, equivalently, market makers based on market scoring rules) satisfy the smoothness requirement. We further show that regardless of the level of risk aversion of the traders, the final allocation and prices together constitute a *competitive equilibrium*; thus, in particular, the final portfolios of the traders are *ex post* Pareto efficient. |
| 2009 | |||
| 2009-01-26 | Carbon Markets and Technological Innovation | Weber, Thomas; Neuhoff, Karsten | This paper examines the effects of firm-level innovation in carbon-abatement technologies on optimal cap-and-trade schemes with and without price controls. We characterize optimal cap-and-trade regulation with price cap and price floor, and compare it to the special cases of pure taxation and simple emissions cap. Innovation shifts the tradeoff between price- and quantity-based instruments towards quantity-based emissions trading schemes. More specifically, an increase in innovation effectiveness lowers the optimal emissions cap, and leads to relaxed price controls unless the marginal environmental damage cost is small. Because of the decrease in the emissions cap, innovation in abatement technologies can lead to a higher expected carbon price, so as to provide sufficient incentives for private R&D investments. The expected carbon price decreases once innovative technologies are widely used. |
| 2008-10-09 | Option Contracting in the California Water Market | Tomkins, Claire; Weber, Thomas | Temporary resource transfers, as achievable under option contracts, reduce transaction cost associated with the sale of permanent resource rights. As such, they facilitate the realization of gains from trade that would go unrealized under failed permanent transfers. In the California water sector, there has been considerable resistance to permanent water rights transfers. The advent of option trading has led to an increase in urban-agricultural water transfers and has the potential to stimulate the California water market. This paper develops a bilateral option contracting model for water, which includes the possibility of conveyance losses and random delivery. Seller-optimal and socially optimal option contracts are characterized in terms of relevant upfront and strike prices, as well as contract volumes, from an ex-ante and an ex-post point of view. Actual contract prices are compared to model-predicted prices, and the social welfare gains from option contracting in the California water market to date are estimated. The sensitivity of future gains to commodity prices and the cost of electricity, implying the marginal cost of water conveyance, is also discussed. |
| 2008-09-18 | Price Theory in Economics | Weber, Thomas | This paper reviews topics in price theory. |
| 2008-09-10 | Monotone Approximation of Decision Problems | Chehrazi, Naveed; Weber, Thomas | Many decision problems exhibit structural properties in the sense that the objective function is a composition of different component functions that can be identified using empirical data. We consider the approximation of such objective functions, subject to general monotonicity constraints on the component functions. Using a constrained B-spline approximation we provide a data-driven robust optimization method for environments that can be sample-sparse. The method is illustrated for the problem of optimal debt settlement in the credit-card industry. |
| 2008-09-01 | Traffic Engineering vs. Content Distribution: A Game Theoretic Perspective | DiPalantino, Dominic; Johari, Ramesh | In this paper we explore the interaction between content distribution and traffic engineering. Because a traffic engineer may be unaware of the structure of content distribution systems or overlay networks, his management of the network does not fully anticipate how traffic might change as a result of his actions. Content distribution systems that assign servers at the application level can respond very rapidly to changes in the routing of the network. Consequently, the decisions of the traffic engineer may almost never be applied to the intended traffic. We use a game-theoretic framework in which infinitesimal users of a network select the source of content, and the traffic engineer decides how the traffic will route through the network. We formulate a game and prove the existence of equilibria. Additionally, we present a setting in which equilibria are socially optimal, essentially unique, and stable. Conditions under which efficiency loss may be bounded are presented, and the results are extended to the cases of general overlay networks and multiple autonomous systems. |
| 2008-08-27 | Designing Reputation Mechanisms for Efficient Trade | Aperjis, Christina; Johari, Ramesh | A seller in an online marketplace with an effective reputation mechanism should expect that dishonest behavior results in higher payments now, while honest behavior results in higher reputation---and thus higher payments---in the future. We study two widely used classes of reputation mechanisms. First, we show that weighting all past ratings equally gives sellers an incentive to falsely advertise. This result supports the recent decision of eBay to base the Positive Feedback percentage on the past 12 months of feedback, rather than the entire lifetime of the seller. We then study reputation mechanisms that weight recent ratings more heavily. We show the following dichotomy: under increasing returns to reputation the optimal strategy of a sufficiently patient and sufficiently high quality seller is to always advertise honestly, while under decreasing returns to reputation the seller will not always be honest. Finally, we suggest approaches for designing a reputation mechanism that maximizes the range of parameters for which it is optimal for the seller to be truthful. We show that mechanisms that use information from a larger number of past transactions tend to provide incentives for patient sellers to be more truthful, but for higher quality sellers to be less truthful. |
| 2008-03-06 | On the Equivalence of Hicksian Welfare Measures and the Normative Endowment Effect | Weber, Thomas | We show that the Hicksian welfare measures of compensating variation and equivalent variation are equivalent if one is evaluated at a compensated income. Based on this we demonstrate that the normative endowment effect, when a consumer,s willingness to accept exceeds her willingness to pay at a given income level, occurs if and only if the consumer,s compensated-income function is submodular in the attributes describing the underlying welfare change. Lastly, we provide various necessary and sufficient conditions for the normative endowment effect, including monotonicity, complementarity of the welfare-change attribute and income, and proximity to indifference points, and discuss empirical implications. |
| 2008-02-21 | Two-Stage Myopic Dynamics in Network Formation Games | Arcaute, Esteban; Johari, Ramesh; Mannor, Shie | We consider a network formation game where nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths. Cost is incurred to a node from three sources: (1) traffic related costs; (2) maintaining links to other nodes; and (3) payments made to other nodes (from contracts). Two models for traffic related costs are studied: cost that arises from routing packets and cost that is related to distance, or latency. We define a network to be stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together.
We study such games under a natural form of myopic local best-response dynamics. In each step there are two stages. During the first stage, an exogenously designated node u considers all possible unilateral deviations. Then, during the second stage, it considers forming a new contract with a node v in its neighborhood. That contract can be accepted or rejected by v. Both nodes choose their actions to maximize their prospective payoff after the second stage, and consider the current network state when making a decision. These dynamics generalize best-response dynamics and allow some flexibility to the deviating nodes. We characterize certain assumptions under which these dynamics converge to a pairwise stable network topology; our assumptions are satisfied by the contractual model that corresponds to uniform cost sharing. Notably, for both cost models that we consider, our dynamics select efficient pairwise stable equilibria. These are notable results since some pairwise stable outcomes can be highly inefficient, so our dynamics act as a decentralized procedure for selection of desirable equilibria. |
| 2008-02-18 | The Role of Prices in Peer-Assisted Content Distribution | Aperjis, Christina; Freedman, Michael J.; Johari, Ramesh | Peer-assisted content distribution matches user demand for content with available supply at other peers in the network. Inspired by this supply-and-demand interpretation of the nature of content sharing, we employ price theory to study peer-assisted content distribution. In this approach, the market-clearing prices are those which exactly align supply and demand, and the system is studied through the characterization of price equilibria. Our work provides two separate steps forward. First, we rigorously analyze the efficiency and robustness gains that are enabled by price-based multilateral exchange. We show that multilateral exchanges satisfy several desirable efficiency and robustness properties that bilateral exchanges such as BitTorrent do not, particularly when considering multiple files. Second, we propose and evaluate a system design that realizes many of the benefits of a price-based multilateral exchange; our design encourages sharing of desirable content and network-friendly resource utilization. Bilateral barter-based systems such as BitTorrent have been attractive in large part because of their simplicity; however, little attention has been devoted to studying the efficiency and robustness lost in return for this simplicity. Our research takes a significant step in filling this gap, both through formal analysis and system design. |
| 2007 | |||
| 2007-10-29 | Simple Methods for Evaluating and Comparing Binary Experiments | Weber, Thomas | We consider a confidence parametrization of binary information sources in terms of appropriate likelihood ratios. This parametrization is used to construct tools for Bayesian belief updates and for equivalent comparisons of binary experiments. Firstly, we provide a Bayesian Update Diagram, which enables a decision maker to generate belief updates, largely without the use of formulas. Secondly, we present a Confidence-Augmented ROC Space for sharp comparisons between binary experiments for a class of balanced decision problems. The resulting confidence order is stronger than the Blackwell informativeness order. |
| 2007-09-02 | A Message-Passing Paradigm for Resource Allocation | Moallemi, Ciamac; Van Roy, Benjamin | We propose a message-passing paradigm for resource allocation problems. This is a framework for decentralized management that generalizes price-based systems by allowing incentives to vary across activities and consumption levels. Message-based incentives are defined through a new equilibrium concept. We demonstrate that message-based incentives lead to system-optimal behavior for convex resource allocation problems, yet yield allocations superior to those from price-based incentives for non-convex resource allocation problems. We describe a distributed and asynchronous algorithm for computing equilibrium messages and allocations, and demonstrate this in the context of a network resource allocation problem. |
| 2007-09-02 | Convergence of the Min-Sum Algorithm for Convex Optimization | Moallemi, Ciamac; Van Roy, Benjamin | We establish that the min-sum message-passing algorithm and its asynchronous variants converge for a large class of unconstrained convex optimization problems. |
| 2007-07-26 | Delayed Multiattribute Product Differentiation | Weber, Thomas | We develop a two-stage model for versioning products with respect to both vertical and horizontal attributes. At first, a firm positions its top-quality flagship product in a market with an imperfectly known distribution of tastes and reservation prices. In the second stage, the firm learns these consumer characteristics and has the option of extending its product line by versioning the flagship product using pure horizontal differentiation, quality degrading, or both. The firms nonconvex versioning problem is solved analytically for the two-product case. We find that ex ante extending the product line through vertical differentiation is optimal for low marginal cost of quality (development cost); otherwise pure horizontal differentiation is superior. Given quasilinear consumer preferences and a uniform distribution of consumer characteristics, versioning with respect to both horizontal and vertical attributes is never optimal. Under delayed differentiation the optimal policy is contingent on the observed demand realization and may lead to horizontal cannibalization and price dispersion for equal-quality products. The firm tends to increase its investment in product quality unless it adopts a state-contingent policy of horizontal versioning for high and vertical versioning for low demand realizations. Following a state-contingent policy, the optimal upfront development effort may be significantly lower than under full ex-ante commitment. The option value of delayed differentiation is generally nonmonotonic in the firms development cost. |
| 2007-07-25 | On the Equivalence of Hicksian Welfare Measures | Weber, Thomas | We establish exact relations between compensating variation and equivalent variation, or between willingness to pay and willingness to accept, following an exogenous welfare change. These relations improve earlier results by Weber (2003). Tight bounds for the difference between the two welfare measures are also provided. |
| 2007-04-06 | Efficiency of Scalar-Parameterized Mechanisms | Johari, Ramesh; Tsitsiklis, John N. | We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we restrict to mechanisms that satisfy certain scalability constraints motivated by large scale communication networks; in particular, we restrict attention to mechanisms where users are restricted to one-dimensional strategy spaces. We first study the efficiency guarantees possible when the mechanism is not allowed to price differentiate. We study the worst-case efficiency loss (ratio of the utility associated with a Nash equilibrium to the maximum possible utility), and show that the proportional allocation mechanism of Kelly (1997) minimizes the efficiency loss when users are price anticipating. We then turn our attention to mechanisms where price differentiation is permitted; using an adaptation of the Vickrey-Clarke-Groves class of mechanisms, we construct a class of mechanisms with one-dimensional strategy spaces where Nash equilibria are fully efficient. These mechanisms are shown to be fully efficient even in general convex environments, under reasonable assumptions. Our results highlight a fundamental insight in mechanism design: when the pricing flexibility available to the mechanism designer is limited, restricting the strategic flexibility of bidders may actually *improve* the efficiency guarantee. |
| 2007-02-27 | Network Formation: Bilateral Contracting and Myopic Dynamics | Arcaute, Esteban; Dallal, Eric; Johari, Ramesh; Mannor, Shie | We consider a network formation game where a finite number of nodes wish to send traffic to each other. Nodes contract bilaterally with each other to form bidirectional communication links; once the network is formed, traffic is routed along shortest paths (if possible). Cost is incurred to a node from four sources: (1) routing traffic; (2) maintaining links to other nodes; (3) disconnection from destinations the node wishes to reach; and (4) payments made to other nodes. We assume that a network is stable if no single node wishes to unilaterally deviate, and no pair of nodes can profitably deviate together (a variation on the notion of pairwise stability). We study such a game under a form of *myopic best response dynamics*. In choosing their best strategy, nodes optimize their single period payoff only. We characterize a simple set of assumptions under which these dynamics will converge to a pairwise stable network topology; we also characterize an important special case, where the dynamics converge to a star centered at a node with minimum cost for routing traffic. In this sense, our dynamics naturally *select* an efficient equilibrium. Further, we show that these assumptions are satisfied by a contractual model motivated by bilateral Rubinstein bargaining with infinitely patient players. |
| 2007-02-04 | Investment and Market Structure in Industries with Congestion | Weintraub, Gabriel Y.; Johari, Ramesh; Van Roy, Benjamin | We analyze investment incentives and market structure under oligopoly competition in service industries with congestion effects. Firms compete by choosing prices and investments; increasing investment reduces the congestion disutility experienced by consumers. We investigate this model through the Nash equilibria of the pricing and investment game played by firms. We find that returns to investment and the timing of strategic decisions are critical determinants of the outcome of the game. For a broad range of models for which (1) firms choose prices and investments simultaneously, and (2) the model exhibits nonincreasing returns to investment, we show that if a pure strategy Nash equilibrium exists, it is unique and efficient; we also establish conditions for existence of pure strategy Nash equilibrium. This result does not hold if either (1) or (2) are violated; we show that highly inefficient outcomes can be obtained in these scenarios . In addition, we investigate several extensions, including modeling the entry of firms into the market. Our model and results provide a framework through which a range of service industries and network technologies can be studied, offering guidance for policy analysis. |
| 2006 | |||
| 2006-12-17 | Additive Envelopes of Continuous Functions | Strulovici, Bruno; Weber, Thomas | We present an iterative method for constructing additive envelopes of continuous functions on a compact set, with contact at a prespecified point. For elements of a class of submodular functions we provide closed-form expressions for such additive envelopes. |
| 2006-12-14 | Generalized Monotonicity Analysis | Strulovici, Bruno; Weber, Thomas | Complex economic problems often lack the structure for the application of standard comparative statics techniques. Addressing this difficulty, Generalized Monotonicity Analysis (GMA) generates parameter directions along which solutions, or functions thereof, increase. By providing criteria for the problem structure that guarantee monotone solutions, GMA helps reparameterize the problem accordingly. GMA generates all monotonicity relations between solutions and parameters, subject to the available information. Several applications are discussed, including constrained optimization, aggregation, quantitative monotonicity analysis and robust inference, non-supermodular games, and monotone comparative dynamics. |
| 2006-11-23 | Dynamic Pricing with a Prior on Market Response | Farias, Vivek; Van Roy, Benjamin | We study a problem of dynamic pricing faced by a vendor with limited inventory, uncertain about the number of potential customers, aiming to maximize expected discounted revenue over an infinite time horizon. The vendor learns from purchase data, so his strategy must take into account the impact of price on both revenue and future observations. We focus on a model in which customers arrive according to a Poisson process, each with an independent, identically distributed reservation price. Upon arrival, a customer purchases a unit of inventory if his reservation price equals or exceeds the vendor's prevailing price; otherwise, he exits the system. The vendor knows the reservation price distribution but not the customer arrival rate -- for this he has a Gamma-distributed prior. We propose a new heuristic approach to pricing, which we refer to as decay balancing. In the case where reservation prices are exponentially distributed, we prove that decay balancing always garners at least 33.3% of the maximum expected discounted revenue. Decay balancing appropriately increases price with arrival rate variance, in contrast to certainty equivalent and greedy heuristics, recently proposed by Aviv and Pazgal (2005) and Araman and Caldentey (2005), respectively. Further, computational experiments demonstrate that decay balancing offers significant revenue gains over these alternatives. We also extend the three aforementioned heuristics to address a model involving multiple customer segments and stores and provide experimental results demonstrating similar relative merits in this context. |
| 2006-11-08 | Piecewise Polynomial Replication Strategies and Moment Matrices in Convex Optimization based Option | Primbs, James | This paper develops a framework for optimization based bounds on option prices by using piecewise polynomial sub or super replicating strategies of existing options and assets whose value at discrete time points can be represented as piecewise polynomial functions. The optimization problems are presented as polynomial programs which can be modified to a convex optimization problem using the sum-of-squares methodology. The dual approach is then developed by relaxing a martingale pricing problem to an optimization problem involving moment matrices of measures consistent with martingale pricing measures. Both formulations use semidefinite programming to bound option prices while also being able to consistently incorporate existing option price data. Computation of the bounds is demonstrated using data consistent with the standard Black-Scholes option pricing model and Mertons jump diffusion model. |
| 2006-07-26 | Partially Optimal Routing | Acemoglu, Daron; Johari, Ramesh; Ozdaglar, Asuman | Most large-scale communication networks, such as the Internet, consist of interconnected administrative domains. While source (or selfish) routing, where transmission follows the least cost path for each source, is reasonable across domains, service providers typically engage in traffic engineering to improve operating performance within their own network. Motivated by this observation, we develop and analyze a model of partially optimal routing, where optimal routing within subnetworks is overlaid with selfish routing across domains. We demonstrate that optimal routing within a subnetwork does not necessarily improve the performance of the overall network. In particular, when Braess' paradox occurs in the network, partially optimal routing may lead to worse overall network performance. We provide bounds on the worst-case loss of efficiency that can occur due to partially optimal routing. For example, when all congestion costs can be represented by affine latency functions and all administrative domains have a single entry and exit point, the worst-case loss of efficiency is no worse than 25% relative to the optimal solution. In the presence of administrative domains incorporating multiple entry and/or exit points, however, the performance of partially optimal routing can be arbitrarily inefficient even with linear latencies. We also provide conditions for traffic engineering to be individually optimal for service providers. |
| 2006-07-24 | A Peer-to-Peer System as an Exchange Economy | Aperjis, Christina; Johari, Ramesh | We formulate a peer-to-peer filesharing system as an exchange economy: a price is associated with each file, and users exchange files only when they can afford it. This formulation solves the free-riding problem, since uploading files is a necessary condition for being able to download. However, we do not explicitly introduce a currency; users must upload files in order to earn a budget for downloading. We discuss existence, uniqueness, and dynamic stability of the competitive equilibrium, which is always guaranteed to be Pareto efficient. In addition, a novel aspect of our approach is an allocation mechanism for clearing the market out of equilibrium.We analyze this mechanism when users can anticipate how their actions affect the allocation mechanism (price anticipating behavior). For this regime we characterize the Nash equilibria that will occur, and show that as the number of users increases, the Nash equilibrium rates become approximately Pareto efficient. |
| 2006-06-29 | Monotone Comparative Statics: A Geometric Approach | Strulovici, Bruno; Weber, Thomas | We consider comparative statics of solutions to parameterized optimization problems. A geometric method is developed for finding a vector field that, at each point in the parameter space, indicates a direction in which monotone comparative statics obtain. Given such a vector field, we provide sufficient conditions under which the problem can be reparameterized on the parameter space (or a subset thereof) in a way that guarantees monotone comparative statics. A key feature of our method is that it does not require the feasible set to be a lattice and works in the absence of the standard quasi-supermodularity and single-crossing assumptions on the objective function. We illustrate our approach with a variety of applications. |
| 2006-06-26 | Efficient Contract Design in Multi-Principal Multi-Agent Supply Chains | Weber, Thomas; Xiong, Hongxia | We consider a general multi-principal multi-agent contracting game in a complete-information supply-chain setting and determine coordinating equilibrium transfer schedules in closed form. The resulting contracts manage to align incentives for decentralized decision-making and achieve first-best channel solutions. We allow for multidimensional actions and arbitrary payoff externalities between all members of the supply chain. For the coordinating contracts to exist it suffices that all payoff functions are continuous on the compact action sets in a general sense that accommodates discrete action sets. Our approach unifies and generalizes a significant portion of the extant supply-chain literature. It can be applied to a very large class of many-to-many supply-chain settings. |
| 2006-06-09 | AdWords Allocation Problem with Unreliable Estimates | Mahdian, Mohammad; Nazerzadeh, Hamid; Saberi, Amin | |
| 2006-06-04 | A Convex Parimutuel Formulation for Contingent Claim Markets | Peters, Mark; Man-Cho So, Anthony; Ye, Yinyu | In this paper we study the problem of centrally organizing a market where the participants submit bids for contingent claims over the outcome of a future event and the market organizer must determine which bids to accept. The bidder will select a set of future states and a price at which he is willing to buy the contingent claims. By accepting a bid, the market organizer agrees to pay the bidder a fixed amount if one of the bidder's selected states is realized. We will specifically study markets which are run as call auctions where the organizer holds the auction open until a certain time and then determines the bids to accept and reject. This type of market has broad usage in financial markets, betting markets and general prediction markets. Lange and Economides have developed a parimutuel mechanism for solving such a market with many positive characteristics. However, one drawback of their formulation is that their mathematical model is not convex and no efficient algorithm is known to solve it. In this paper, we introduce a new mathematical formulation called the Convex Parimutuel Call Auction Mechanism (CPCAM). This formulation produces many of the same advantageous properties of the Lange and Economides model but can more easily be solved due to its convexity. In particular, our model yields the first fully polynomial-time approximation scheme (FPTAS) for the problem. Moreover, we show that our model actually produces identical state prices as the Lange and Economides model. As a corollary, we show that by first obtaining the state prices from our model, the Lange and Economides model becomes a linear program and hence can be solved in polynomial time. |
| 2006-06-04 | Fast Generation of Random Graphs via Sequential Importance Sampling | Bayati, Mohsen; Saberi, Amin | In this article we use sequential importance sampling to develop an efficient algorithm for generating simple random graphs with a given degree sequence. If the degree sequence is such that dmax = o(m^(1/4−Epsilon)), our algorithm generates an asymptotically uniform random graph with that degree sequence in almost linear time. Here dmax is maximum degree and m is the number of edges in the graphs. Our method also gives an independent proof of McKay and Wormald's estimate [28] for number of graphs. |
| 2006-06-04 | A Path to the Arrow-Debreu Competitive Market Equilibrium | Ye, Yinyu | We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and n players. Both of them have the arithmetic operation complexity bound of O(n^4 log(1/Epsilon)) for computing an Epsilon-equilibrium solution. If the problem data are rational numbers and their bit-length is L, then the bound to generate an exact solution is O((n^4)L) which is in line with the best complexity bound for linear programming of the same dimension and size. This is a significant improvement over the previously best bound O(n^8 log(1/Epsilon)) for approximating the two problems using other methods. The key ingredient to derive these results is to show that these problems admit convex optimization formulations, efficient barrier functions and fast rounding techniques. We also present a continuous path leading to the set of the Arrow-Debreu equilibrium, similar to the central path developed for linear programming interior-point methods. This path is derived from the weighted logarithmic utility and barrier functions and the Brouwer fixed-point theorem. The defining equations are bilinear and possess some primal-dual structure for the application of the Newton-based path-following method. |
| 2006-06-04 | Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements | Biswas, Pratik; Liang, Tzu-Chen; Toh, Kim-Chuan; Ye, Yinyu | A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP) based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space, which when projected onto the lower dimensional space generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to validate our methods and show that they outperform existing SDP methods. |
| 2006-06-04 | Dynamic Order Promising: Real-time ATP | Robinson, Anne G.; Carlson, Robert C. | We study a problem of dynamic pricing faced by a vendor with limited inventory, uncertain about the number of potential customers, aiming to maximize expected discounted revenue over an infinite time horizon. The vendor learns from purchase data, so his strategy must take into account the impact of price on both revenue and future observations. We focus on a model in which customers arrive according to a Poisson process, each with an independent, identically distributed reservation price. Upon arrival, a customer purchases a unit of inventory if his reservation price equals or exceeds the vendor's prevailing price; otherwise, he exits the system. The vendor knows the reservation price distribution but not the customer arrival rate -- for this he has a Gamma-distributed prior. We propose a new heuristic approach to pricing, which we refer to as decay balancing. In the case where reservation prices are exponentially distributed, we prove that decay balancing always garners at least 33.3% of the maximum expected discounted revenue. Decay balancing appropriately increases price with arrival rate variance, in contrast to certainty equivalent and greedy heuristics, recently proposed by Aviv and Pazgal (2005) and Araman and Caldentey (2005), respectively. Further, computational experiments demonstrate that decay balancing offers significant revenue gains over these alternatives. We also extend the three aforementioned heuristics to address a model involving multiple customer segments and stores and provide experimental results demonstrating similar relative merits in this context. |
| 2006-06-02 | Pricing for fairness: distributed resource allocation for multiple objectives | Cho, Sung-Woo; Goel, Ashish | In this paper, we present a simple distributed algorithm for resource allocation which simultaneously approximates the optimum value for a large class of objective functions. In particular, we consider the class of canonical utility functions $U$ that are symmetric, non-decreasing, concave, and satisfy $U(0)$ = 0. Our distributed algorithm is based on primal-dual updates. We prove that this algorithm is an $O(log ho)$-approximation for all canonical utility functions simultaneously, i.e. without any knowledge of $U$. The algorithm needs at most $O(log^2 ho)$ iterations. Here $n$ is the number of flows, $m$ is the number of edges, $R$ is the ratio between the maximum capacity and the minimum capacity of the edges in the network, and $ ho$ is $max left{n, m, R ight}$. We extend this result to multi-path routing, and also to a natural pricing mechanism that results in a simple and practical protocol for bandwidth allocation in a network. When the protocol reaches equilibrium, the allocated bandwidths are the same as when the distributed algorithm converges; hence the protocol is also an $O(log ho)$ approximation for all canonical utility functions. |
| 2006-06-02 | Truthful Auctions for Pricing Search Keywords | Aggarwal, Gagan; Goel, Ashish; Motwani, Rajeev | We present a truthful auction for pricing advertising slots on a web-page assuming that advertisements for different merchants must be ranked in decreasing order of their (weighted) bids. This captures both the Overture model where bidders are ranked in order of the submitted bids, and the Google model where bidders are ranked in order of the expected revenue (or utility) that their advertisement generates. Assuming separable click-through rates, we prove revenue-equivalence between our auction and the non-truthful next-price auctions currently in use. |
| 2006-05-01 | Bayesian Incentive Compatible Parametrization of Mechanisms | Weber, Thomas; Bapna, Abhishek | We consider a general scheme to construct Bayesian incentive compatible mechanisms using a suitable variable mechanism parametrization. The key idea is to perturb a given direct mechanism, which might not be truth revealing, introducing sufficient variability as a function of agents' announcements to generate incentives for truthful revelation. We discuss a variable-price auction in a general setting as an example. |
| 2006-04-28 | A Model of Search Intermediaries and Paid Referrals | Weber, Thomas; Zheng, Zhiqiang (Eric) | In this paper we pursue three main objectives: (1) to develop a model of an intermediated search market in which matching between consumers and firms takes place primarily via paid referrals; (2) to address the important managerial question (for a search intermediary) of finding a suitable mechanism for selling referrals to firms; and (3) to characterize and analyze the firms resulting equilibrium bidding strategies given consumers equilibrium search behavior. To achieve these objectives we develop a two-stage model of search intermediaries in a vertically differentiated product market. In the first stage an intermediary chooses a search engine design that specifies to which extent a firm's search rank is determined by its bid and to which extent it is determined by the product offering's overall performance. In the second stage, based on the search engine design, competing firms place their open bids to be paid for each referral by the search engine. We find that the revenue-maximizing search engine design bases rankings on a weighted average of relative product performance and bid amount. The firms' bid amounts are generally nonmonotonic in product performance and a nonzero pure-strategy equilibrium of the underlying discontinuous bidding game does not exist. We derive the unique mixed-strategy Nash equilibrium and show that firms of low product performance tend to fully dissipate their rents. These rents are fully appropriated by the search intermediary and the better firm, and are therefore not socially wasteful. However, the intermediary's design choice, by attributing a positive weight to the firms' bids, generally obfuscates search results and reduces overall consumer surplus compared to the socially optimal design of providing fully transparent results ranked purely on product performance. |
| 2006-04-20 | A Short Proof of Optimality for the MIN Cache Replacement Algorithm | Van Roy, Benjamin | The MIN algorithm is an offline strategy for deciding which item to replace when writing a new item to a cache. Its optimality has been established by Mattson, Gecsei, Slutz, and Traiger [2] through a lengthy analysis. We offer here a short and elementary proof based on a dynamic programming argument. |
| 2006-04-20 | Convergence of the Min-Sum Message Passing Algorithm for Quadratic Optimization | Moallemi, Ciamac; Van Roy, Benjamin | We establish the convergence of the min-sum message passing algorithm for minimization of a quadratic objective function given a convex decomposition. Our results also apply to the equivalent problem of the convergence of Gaussian belief propagation. |
| 2006-03-31 | Efficient Dynamic Allocation with Uncertain Valuations | Bapna, Abhishek; Weber, Thomas | In this paper we consider the problem of efficiently allocating a given resource or object repeatedly over time. The agents, who may temporarily receive access to the resource, learn more about its value through its use. When the agents' beliefs about their valuations at any given time are public information, this problem reduces to the classic multi-armed bandit problem, the solution to which is obtained by determining a Gittins index for every agent. In the setting we study, agents observe their valuations privately, and the efficient dynamic resource allocation problem under asymmetric information becomes a problem of truthfully eliciting every agent's Gittins index. We introduce two bounding mechanisms, under which agents announce types corresponding to Gittins indices either at least as high as or at most as high as their true Gittins indices. Using an announcement-contingent affine combination of the bounding mechanisms it is possible to implement the efficient dynamic allocation policy. We provide necessary and sufficient conditions for global Bayesian incentive compatibility, guaranteeing a truthful efficient allocation of the resource. Using essentially the same method, it is possible to approximately implement truthful mechanisms corresponding to a large variety of surplus distribution objectives the principal might have, for instance a dynamic second-price Gittins-index auction which maximizes the principal's revenue subject to implementing an efficient allocation policy. |
| 2005 | |||
| 2005-11-09 | Markov Perfect Industry Dynamics with Many Firms | Weintraub, Gabriel Y.; Benkard, C. Lanier; Van Roy, Benjamin | We propose an approximation method for analyzing Ericson and Pakes (1995)-style dynamic models of imperfect competition. We develop a simple algorithm for computing an ?oblivious equilibrium,? in which each firm is assumed to make decisions based only on its own state and knowledge of the long run average industry state, but where firms ignore current information about competitors? states. We prove that, as the market becomes large, if the equilibrium distribution of firm states obeys a certain ?light-tail? condition, then oblivious equilibria closely approximate Markov perfect equilibria. We develop bounds that can be computed to assess the accuracy of the approximation for any given applied problem. Through computational experiments, we find that the method often generates useful approximations for industries with hundreds of firms and in some cases even tens of firms. |
| 2005-10-25 | Pricing a new asset in a Hierarchical Segmented Market | Li, Qi; Primbs, James | This paper explores the pricing of a new asset in a hierarchical segmented market. Motivated by the idea of projection pricing in an integrated market, we develop formulas for pricing in segmented markets that utilize existing pricing information. We develop the fundamental structure of an appropriate segmentation pricing formula for a new asset. Furthermore, we show that the simple concept of projection pricing does not generalize in a completely satisfactory manner to segmented markets. However, we are able to develop a formula under a CARA utility function and Gaussian payoffs that fully incorporates existing information. These ideas are illustrated through a simple continuous time model of an IPO. |
| 2005-10-25 | Asset Pricing, Portfolio Selection, and Welfare Analysis in Hierarchical Segmented Markets | Li, Qi; Primbs, James | This paper develops explicit pricing models under a Gaussian, single period CARA utility based model in segmented markets that possess specific structure, referred to as hierarchical. The hierarchical structure allows us to present general asset pricing formulas, analyze the portfolio holdings of investor groups, and determine welfare implications. Furthermore, we are able to recover a number of previous results as special cases of hierarchical segmentation. Finally, our findings shed new light on the formation of segmented markets, and indicate that segmentation is likely to exist even in equilibrium. |
| 2005-10-25 | Asset Pricing in Hierarchical Segmented Markets | Li, Qi; Primbs, James | This paper develops a new framework for asset pricing theory in segmented markets from a stochastic discount factor point of view. In segmented markets that possess specific structure, which we term hierarchical, an orthogonalization procedure can be performed that simplifies the allowable structure of prices. In this case, we derive general stochastic discount factor formulas, beta models, and factor models for pricing that must hold in the absence of arbitrage. |
| 2005-09-14 | Leontief Economies Encode Nonzero Sum Two-Player Games | Codenotti, Bruno; Varadarajan, Kasturi; Saberi, Amin | We give a reduction from any two-player game to a special case of the Leontief exchange economy, previously studied by Ye, with the property that the Nash equilibria of the game and the equilibria of the market are in one-to-one correspondence. Our reduction exposes a potential hurdle inherent in solving certain families of market equilibrium problems: nding an equilibrium for Leontief economies is at least as hard as finnding a Nash equilibrium for two-player nonzero sum games. |
| 2005-09-14 | Adwords and Generalizad Online Matching | Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh | How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two algorithms achieving competitive ratios of 1 - 1/e for this problem. |
| 2005-06-24 | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal?Difference Learning | Choi, David; Van Roy, Benjamin | The traditional Kalman filter can be viewed as a recursive stochastic algorithm that approximates an unknown function via a linear combination of prespecified basis functions given a sequence of noisy samples. In this paper, we generalize the algorithm to one that approximates the fixed point of an operator that is known to be a Euclidean norm contraction. Instead of noisy samples of the desired fixed point, the algorithm updates parameters based on noisy samples of functions generated by application of the operator, in the spirit of Robbins?Monro stochastic approximation. The algorithm is motivated by temporal?difference learning, and our developments lead to a possibly more efficient variant of temporal?difference learning. We establish convergence of the algorithm and explore efficiency gains through computational experiments involving optimal stopping and queueing problems. |
| 2005-06-24 | Approximation Algorithms for Dynamic Resource Allocation | Farias, Vivek; Van Roy, Benjamin | We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T time periods. During each period, a task is assigned to each activity. Each task consumes resources, generates utility, and determines the subsequent state of the activity. The goal is to maximize average utility. We establish that the problem is NP-hard to approximate to within any constant factor. We then propose and study two polynomial-time approximation algorithms which guarantee small performance losses in different regimes. The first leads to an error of no more than UMT/N, where U is the maximal time-averaged utility that can be generated by an activity. The second algorithm promises O(UN ln(MT)/R) loss, where R is the available quantity of the scarcest resource. The first algorithm extends to situations in which, rather than being classified as one among M types, each resource can fill a subset among M roles. |
| 2005-06-24 | A Non-Parametric Approach to Multi-Product Pricing | Rusmevichientong, Paat; Van Roy, Benjamin; Glynn, Peter | Developed by General Motors (GM), the Auto Choice Advisor web site (http://www.auto choiceadvisor.com) recommends vehicles to consumers based on their requirements and budget constraints. Through the web site, GM has access to large quantities of data that reflect consumer preferences. Motivated by the availability of such data, we formulate a non-parametric approach to multi-product pricing. We consider a class of models of consumer purchasing behavior, each of which relates observed data on a consumer?s requirements and budget constraint to subsequent purchasing tendencies. To price products, we aim at optimizing prices with respect to a sample of consumer data. We offer a bound on the sample size required for the resulting prices to be near optimal with respect to the true distribution of consumers. The bound exhibits a dependence of O(n log n) on the number n of products being priced, showing that ? in terms of sample complexity ? the approach is scalable to large numbers of products. With regards to computational complexity, we establish that computing optimal prices with respect to a sample of consumer data is NP-complete in the strong sense. However, when prices are constrained by a price ladder ? an ordering of prices defined prior to price determination ? the problem becomes one of maximizing a supermodular function with real-valued variables. It is not yet known whether this problem is NP-hard. We provide a heuristic for our price-ladder constrained problem together with encouraging computational results. |
| 2005-06-24 | Opportunities and Challenges in Using Online Preference Data For Vehicle Pricing: A Case Study | Rusmevichientong, Paat; Salisbury, Joyce; Truss, Lynn; Glynn, Peter | Developed by General Motors (GM), the Auto Choice Advisor web site (http://www. autochoiceadvisor.com) recommends vehicles to consumers based on their requirements and budget constraints. Through the web site, GM has access to large quantities of data that reflect consumer preferences. Motivated by the availability of such data, we formulate a non-parametric approach to pricing GM vehicles, highlight opportunities and challenges in using online data, and contrast our approach with existing methodologies and traditional data sources. Our analysis provides insights into the current pricing practice and suggests enhancements that may lead to a more effective pricing strategy. |
| 2005-06-24 | Tetris: A Study of Randomized Constraint Sampling | Farias, Vivek; Van Roy, Benjamin | Using the linear programming approach to approximate dynamic programming, we generate an algorithm for playing Tetris. In the process, we explore practical issues arising in the use of constraint sampling techniques. |
| 2005-06-24 | Solitaire: Man Versus Machine | Yan, Xiang; Diaconis, Persi; Rusmevichientong, Paat | In this paper, we use the rollout method for policy improvement to analyze a version of Klondike solitaire. This version, sometimes called thoughtful solitaire, has all cards revealed to the player, but then follows the usual Klondike rules. A strategy that we establish, using iterated rollouts, wins about twice as many games on average as an expert human player does. |
| 2005-06-24 | Performance Loss Bounds for Approximate Value Iteration with State Aggregation | Van Roy, Benjamin | We consider approximate value iteration with a parameterized approximator in which the state space is partitioned and the optimal cost-to-go function over each partition is approximated by a constant. We establish performance loss bounds for policies derived from approximations associated with fixed points. These bounds identify benefits to using invariant distributions of appropriate policies as projection weights. Such projection weighting relates to what is done by temporal-difference learning. Our analysis also leads to the first performance loss bound for approximate value iteration with an average cost objective. |
| 2005-06-24 | A Linear Program for Bellman Error Minimization with Performance Guarantees | de Farias, Daniela; Van Roy, Benjamin | We introduce a new algorithm based on linear programming for optimization of average-cost Markov decision processes (MDPs). The algorithm approximates the differential cost function of a perturbed MDP via a linear combination of basis functions. The approximation minimizes a version of Bellman error. We establish an error bound that scales gracefully with the number of states without imposing the (strong) Lyapunov condition required by its counterpart in [8]. We investigate implications of this result in the context of a queueing problem. |
| 2005-06-24 | Consensus Propagation | Moallemi, Ciamac; Van Roy, Benjamin | We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than pairwise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge. |
| 2005-05-17 | Screening with Externalities | Weber, Thomas | We consider a general screening model with payoff externalities. The principal can design contract instruments of arbitrary dimension to influence each agent?s valuation of the proposed transaction, which also depends on the anticipated choice of other agents. In the absence of the standard supermodularity or single-crossing assumptions, we characterize the class of all implementable menus and provide necessary optimality conditions. |
