Relevant Degree Programs
Graduate Student Supervision
Doctoral Student Supervision (Jan 2008 - Nov 2019)
This dissertation studies three topics in transport economics and operations management. The first topic is on the economic regulation of congested airports. The second one is revenue sharing between airlines and airports. In the third topic, we investigate the impact of strategic customer behavior on the channel profits.Chapter 2 studies the effects of concession revenue sharing between an airport and its airlines. It is found that the degree of revenue sharing will be affected by how airlines' services are related to each other (complements, independent, or substitutes). It is further found that airport competition results in a higher degree of revenue sharing than in the case of single airports. The airport-airline chains may nevertheless derive lower profits through the revenue-sharing rivalry, and the situation is similar to a Prisoners' Dilemma. Chapter 3 considers price-cap regulation of an airport where the airport facility (e.g., its runway) is congested and air carriers have market power. In the case of airports, there are two versions of price-cap regulation: the single-till approach and the dual-till approach. We show that when airport congestion is not a major problem, single-till price-cap regulation dominates dual-till price-cap regulation with respect to social welfare. Furthermore, we identify situations where dual-till regulation performs better than single-till regulation when there is significant airport congestion. Chapter 4 investigates the impact of customer and firm discounting as well as downstream retailer competition on the benefit of decentralization when customers are strategic. We consider a dynamic two-period model consisting of one manufacturer who sells a product through multiple retailers under linear wholesale price contracts. No firm can credibly commit to future prices or quantities. With strategic customers, we find that a decentralized channel may have higher profit than that of a centralized channel. We show that in addition to the double marginalization effect, both customer and firm discounting and retailer competition are also driving factors of the higher decentralized channel profit.
We study scheduling of jobs on a highly utilized resource when the processing durations are stochastic and there are significant underage (resource idle-time) and overage (job waiting and/or resource overtime) costs. Our work is motivated by surgery scheduling and physician appointments. We consider several extensions and applications.In the first manuscript, we determine an optimal appointment schedule (planned start times) for a given sequence of jobs (surgeries) on a single resource (operating room, surgeon). Random processing durations are integers and given by a discrete probability distribution. The objective is to minimize the expected total underage and overage costs. We show that an optimum solution is integer and can be found in polynomial time.In the second manuscript, we consider the appointment scheduling problem under the assumption that the duration probability distributions are not known and only a set of independent samples is available, e.g., historical data. We develop a sampling-based approach and determine bounds on the number of independent samples required to obtain a provably near-optimal solution with high probability.In manuscript three, we focus on determining the number of surgeries for an operating room in an incentive-based environment. We explore the interaction between the hospital and the surgeon in a game theoretic setting, present empirical findings and suggest incentive schemes that the hospital may offer to the surgeon to reduce its idle time and overtime costs.In manuscript four, we consider an application to inventory management in a supply chain context. We introduce advance multi-period quantity commitment with stochastic characteristics (demand or yield) and describe several real-world applications. We show these problems can be solved as special cases of the appointment scheduling problem.In manuscript five, an appendix, we develop an alternate solution approach for the appointment scheduling problem. We find a lower bound value, obtain a subgradient of the objective function, and develop a special-purpose integer rounding algorithm combining discrete convexity and non-smooth convex optimization methods.
Computing solution concepts in games is an important endeavor in the field of algorithmicgame theory. This thesis explores two contexts – simultaneous games and sequential games – for computing solution concepts in games where some or all of the decisions of players canbe modeled as integer vectors. In the case of simultaneous games, the problem of computing pure strategy in Nashequilibrium (pure NE) is considered in two classes of compactly represented games; that is, games where the set of players, actions or utilities are expressed compactly by an input smaller than the standard normal form representation. The first class considered is integer programming games where actions are sets of integer points and utilities have a special difference of piecewise linear convex structure. The second class considered is symmetric games with general piecewise linear utilities. Both classes can be highly expressive of general normal form games, but can also be highly compact. The main results are polynomial-time algorithms for counting and finding pure NE when certain parameters are fixed and where the input is a description of the piecewise linear utilities. In both cases this can yield improved efficiency over known algorithms.In the case of sequential games, the problem of finding optimal “optimistic solutions” to bilevel integer programs are explored. In particular by using recent results from parametric integer programming, a polynomial-time (in fixed dimension) algorithm is derived. Existence results for optima in a more general setting involving a multilinear lower level objective representing leader-controlled units costs are also stated using a decomposition of the originaliiproblem into a finite set of simpler subproblems. This decomposition theorem is derived from an algebraic theory of integer programming using Gr ̈obner bases.Another contribution of this work is the use of a theory of encoding lattice points in polytopes as rational generating functions to encode sets of pure equilibria and bilevel op- timal solutions, which are viewed as lattice point sets. This encoding then yields efficient algorithms to count, enumerate and optimize over our sets of interest.