A randomized concave programming method for choice network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing froman offer set, have recently become popular in assortment optimization and revenue management.The dynamic program for these models is intractable and approximated by a deterministiclinear program called the CDLP which has an exponential number of columns. However, whenthe segment consideration sets overlap, the CDLP is difficult to solve. Column generationhas been proposed but finding an entering column has been shown to be NP-hard. In thispaper we propose a new approach called SDCP to solving CDLP based on segments and theirconsideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound onthe dynamic program but coincides with CDLP for the case of non-overlapping segments. Ifthe number of elements in a consideration set for a segment is not very large (SDCP) can beapplied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by(i) simulations, called the randomized concave programming (RCP) method, and (ii) by addingcuts to a recent compact formulation of the problem for a latent multinomial-choice model ofdemand (SBLP+). This latter approach turns out to be very effective, essentially obtainingCDLP value, and excellent revenue performance in simulations, even for overlapping segments.By formulating the problem as a separation problem, we give insight into why CDLP is easyfor the MNL with non-overlapping considerations sets and why generalizations of MNL posedifficulties. We perform numerical simulations to determine the revenue performance of all themethods on reference data sets in the literature.

A tractable consideration set structure for network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing from an offerset, have recently become popular in assortment optimization and revenue management. The dynamicprogram for these models is intractable and approximated by a deterministic linear program called theCDLP which has an exponential number of columns. When there are products that are being consideredfor purchase by more than one customer segment, CDLP is difficult to solve since column generationis known to be NP-hard. However, recent research indicates that a formulation based on segments withcuts imposing consistency (SDCP+) is tractable and approximates the CDLP value very closely. In thispaper we investigate the structure of the consideration sets that make the two formulations exactly equal.We show that if the segment consideration sets follow a tree structure, CDLP = SDCP+. We give acounterexample to show that cycles can induce a gap between the CDLP and the SDCP+ relaxation.We derive two classes of valid inequalities called flow and synchronization inequalities to further improve(SDCP+), based on cycles in the consideration set structure. We give a numeric study showing theperformance of these cycle-based cuts.

Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

Do agglomeration economies reduce the sensitivity of firm location to tax differentials?

Low corporate taxes can help attract new firms. This is the main mechanism underpinning the standard 'race-to-the-bottom'view of tax competition. A recent theoretical literature has qualified this view by formalizing the argument that agglomeration forces can reduce firms' sensitivity to tax differentials across locations. We test this proposition using data on firm startups across Swiss municipalities. We find that, on average, high corporate income taxes do deter new firms, but that this relationship is significantly weaker in the most spatially concentrated sectors. Location choices of firms in sectors with an agglomeration intensity at the twentieth percentile of the sample distribution are estimated to be twice as responsive to a given difference in local corporate tax burdens as firms in sectors with an agglomeration intensity at the eightieth percentile. Hence, our analysis confirms the theoretical prediction: agglomeration economies can neutralize the impact of tax differentials on firms' location choices.

Targeting fertility and female participation through the income tax

We evaluate the effect of a 2003 reform in the Spanish income tax on fertility and the employment of mothers with small children. The reform introduced a tax credit for working mothers with children under the age of three, while also increasing child deductions for all households with children. Theoretically, given the interplay of these two components, the expected effect of the reform is ambiguous on both outcomes. We find that the combined reforms significantly increased both fertility (by almost five percent) and the employment rate of mothers with children under three (by two percent). These effects were more pronounced among less-educated women. In addition, to disentangle the impact of the two reform components, we use an earlier reform that increased child deductions in 1999. We find that the child deductions affect mothers employment negatively, which implies that the 2003 tax credit would have increased employment even more (up to five percent) in the absence of the change in child deductions.

The changing relationship between tax and financial reporting in Spain

The degree of connection between tax and financial reporting is regarded as a key factor in the study of international accounting differences. The position for Spain is briefly outlined in previous research but without examination of any specific accounting issues except, in outline only, depreciation and the tax-free revaluation of assets from 1977 to 1983. The absence of a detailed study of the major tax/accounting linkages for Spain is of particular importance because the relationship is regarded as having changed dramatically in the early 1990s, from a position of tax dominance. In order to measure the links between tax and financial reporting, we adopt the methodology of Lamb et al. (1998) by assessing major accounting topics using a five-case classification shown as Table 1. We refute the proposition that suggests that the link between tax/accounting has been reduced substantially.

Tax incentives and the city

It is difficult to justify tax incentives within the existing economicsliterature on tax competition. We develop a model in which communitiesare interested in attracting firms not only for their own capital butalso for the concentration externalities, a form of agglomerationeconomies, their location bestows on existing firms. We find that itis efficient in this case for communities to offer tax incentives,defined as a tax rate below the benefit tax level, to firms. We presentthe recent relocation of the Boeing Corporation's headquarters fromSeattle to Chicago as a case study.

The sustainable debts of Philip II: A reconstruction of Castile's fiscal position, 1566-1596

The defaults of Philip II have attained mythical status as the origin of sovereigndebt crises. We reassess the fiscal position of Habsburg Castile, derivingcomprehensive estimates of revenue, debt, and expenditure from new archivaldata. The king s debts were sustainable. Primary surpluses were large and rising.Debt-to-revenue ratios remained broadly unchanged during Philip s reign.Castilian finances in the sixteenth century compare favorably with those of otherearly modern fiscal states at the height of their imperial ambitions, includingBritain. The defaults of Philip II therefore reflected short-term liquidity crises,and were not a sign of unsustainable debts.

Revenue management under general discrete choice model of consumer behavior

Customer choice behavior, such as 'buy-up' and 'buy-down', is an importantphe-nomenon in a wide range of industries. Yet there are few models ormethodologies available to exploit this phenomenon within yield managementsystems. We make some progress on filling this void. Specifically, wedevelop a model of yield management in which the buyers' behavior ismodeled explicitly using a multi-nomial logit model of demand. Thecontrol problem is to decide which subset of fare classes to offer ateach point in time. The set of open fare classes then affects the purchaseprobabilities for each class. We formulate a dynamic program todetermine the optimal control policy and show that it reduces to a dynamicnested allocation policy. Thus, the optimal choice-based policy caneasily be implemented in reservation systems that use nested allocationcontrols. We also develop an estimation procedure for our model based onthe expectation-maximization (EM) method that jointly estimates arrivalrates and choice model parameters when no-purchase outcomes areunobservable. Numerical results show that this combined optimization-estimation approach may significantly improve revenue performancerelative to traditional leg-based models that do not account for choicebehavior.

The impact of tax credits on labour supply

One of the principle aims of the Working Families' Tax Credit in the UK was to increase the participation of single mothers. The literature to date concludes there was approximately a five-percentage-point increase in employment of single mothers. The differences-in-differences methodology that is typically used compares single mother with single women without children. However, the characteristics of these groups are very different, and change over time in relative covariates are likely to violate the identifying assumption. We find that when we control for differential trends between women with and without children, the employment effect of the policy falls significantly. Moreover, the effect is borne solely by those working full-time (30 hours or more), while having no effect on inducing people into the labor market from inactivity. Looking closely at important covariates over time, we can see sizeable changes in the relative returns to employment between the treatment and control groups.

Forecasting and turning point predictions in a Bayesian panel VAR model

We provide methods for forecasting variables and predicting turning points in panel Bayesian VARs. We specify a flexible model which accounts for both interdependencies in the cross section and time variations in the parameters. Posterior distributions for the parameters are obtained for a particular type of diffuse, for Minnesota-type and for hierarchical priors. Formulas for multistep, multiunit point and average forecasts are provided. An application to the problem of forecasting the growth rate of output and of predicting turning points in the G-7 illustrates the approach. A comparison with alternative forecasting methods is also provided.