1. Close the Gaps: A Learning-while-Doing Algorithm for a Class of Single-Product Revenue Management Problems
In this work, we consider a retailer selling a single product with limited on-hand inventory over a finite selling season. Customer demand arrives according to a Poisson process, the rate of which is influenced by a single action taken by the retailer (such as price adjustment, sales commission, advertisement intensity, etc.). The relation between the action and the demand rate is not known in advance. The retailer will learn the optimal action policy "on the fly" as she maximizes her total expected revenue based on observed demand reactions. Using the pricing problem as an example, we propose a dynamic "learning-while-doing" algorithm to achieve a near optimal performance. Furthermore, we prove that the convergence rate of our algorithm is almost the fastest among all possible algorithms in terms of asymptotic "regret" (the relative loss comparing to the full information optimal solution). Our result closes the performance gaps between parametric and non-parametric learning and between a post-price mechanism and a customer-bidding mechanism. Important managerial insights from this research are that the value of information on 1) the parametric form of the demand function and 2) each customer's exact reservation price are rather marginal. It also suggests the firms would be better off to perform concurrent dynamic learning and doing, instead of learning-first and doing-second in practice.
2. Hidden-City Ticketing: the Cause, Cost and Impact Hidden-city ticket is an interesting phenomenon existing in airline ticket pricing. It occurs when an itinerary with a connection city is cheaper than a ticket from the origin to the connection point. In such a case, a passenger traveling to the connection city will have the incentive to pretend to be traveling to the final destination, deplane at the connection point and throw away the rest of the ticket. Hidden-city ticketing opportunities are not uncommon nowadays. In this paper, we establish a quantitative model to analyze hidden-city ticketing and its impact on both airlines’ revenues and consumers’ welfare. We first show that this phenomenon arises when there is a large difference in price elasticity on related itineraries. Then we build a dynamic programming model for the airlines that takes into account the hidden-city opportunities which are fully taken by passengers. Under this model, the optimal pricing reaction of the airlines is to eliminate such opportunities, but the airlines’ revenues will always decrease. We show that the decrease could be as much as half, but not more, of the original optimal revenue when the passengers do not take advantage of hidden-city ticketing. Meanwhile, as a reaction of the airlines towards such ticketing practice, the fares to the final destination of a hidden-city itinerary will increase. We first take an exogenous
competition model in our analysis and then validate it through a game theoretic approach. Numerical results are presented to illustrate our results.
Thursday 9-12noon, December 22, 2011
Guanghua School of Management, Room 217
3. A Unified Framework for Dynamic Pari-Mutuel Information Market Design: A Case of On-Line Optimization Recently, several pari-mutuel mechanisms have been introduced to organize prediction markets, such as the logarithmic scoring rule, the cost function formulation, and sequential convex pari-mutuel mechanism (SCPM).In this work, we develop a unified framework that bridges these seemingly unrelated models for centrally organizing contingent-claim markets. Our framework establishes necessary and sufficient conditions for designing mechanisms with many desirable properties such as proper scoring, truthful bidding (in a myopic sense), efficient computation, controllable risk-measure, and guarantees on the worst-case loss. As a result, we develop the very first proper, truthful, risk-controlled, loss-bounded, and polynomial-time scoring rule, which neither of the previous proposed mechanisms possesses simultaneously. Thus, in addition to providing a general framework that unifies and explains all the existing mechanisms, our work would be an effective and instrumental tool in designing new market mechanisms. We also discuss applications of our framework to general open markets for dynamic resource pricing and allocation.
4. Universal Rigidity: Theory of Semidefinite Programming for Graph Realization and Sensor Network Localization
Graph realization is to determine the locations/positions of a set of points under incomplete pair-wise Euclidean distance information. Often, such a problem is complicated by the presence of points whose positions cannot be uniquely determined. Most existing work uses the notion of global rigidity from rigidity theory to address the non–uniqueness issue for a given framework (G,P), where G is the problem graph and P is a given position matrix. However, such notions are not entirely satisfactory, as it has been shown that even if an instance is known to be globally rigid, the problem of determining the point positions is still intractable in general. In this talk, we analyze the notion of universal rigidity to bridge such disconnect. Although the notion of universal rigidity is more restrictive than that of global rigidity, it captures a large class of graphs and is much more relevant to the efficient solvability of the problem. Specifically, we show that both the problem of deciding whether a given graph realization instance is universally rigid and the problem of determining the point positions of a universally rigid instance can be solved efficiently in polynomial time using semidefinite programming (SDP). Then, we give various constructions of universally rigid instances. In particular, we show that trilateration graphs with points in general position are always universally rigid, and triangulation graphs in general position are also universally rigid with a suitable function to maximize in the SDP formulation.
Yinyu Ye received the B.S. degree in System Engineering from the Huazhong University of Science and Technology, Wuhan, China, and the M.S. and Ph.D. degrees in Management Science & Engineering from Stanford University, Stanford. Currently, he is a full Professor of Management Science and Engineering and Institute of Computational and Mathematical Engineering and the Director of the MS&E Industrial Affiliates Program, Stanford University. His current research interests include Continuous and Discrete Optimization, Mathematical Programming, Algorithm Design and Analysis, Computational Game/Market Equilibrium, Metric DistanGeometry, Graph Realization, Dynamic Resource Allocation, and Stochastic and Robust Decision Making,etc.
?
The Optimization Area Editor of Math of Operations Research 2009-, Operations Research 2006-2009, the subject editor of Optimization and Engineering 2002-, and the Co-Chief editor of Pacific J. of Optimization 2005-2009.
