On Certain Greedoid Polyhedra, Partially Indexable Scheduling Problems, and Extended Restless Bandit Allocation Indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid (whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then the problem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

On the Structural Difference between the Evolutionary Approach of Young and that of Kandori, Mailath, and Rob

We provide robust examples of symmetric two-player coordination games in normal form that reveal that equilibrium selection by the evolutionary model of Young (1993) is essentially different from equilibrium selection by the evolutionary model of Kandori, Mailath and Rob (1993).

Structural unemployment

Structural unemployment is due to mismatch between available jobs and workers.We formalize this concept in a simple model of a segmented labor market with searchfrictions within segments. Worker mobility, job mobility and wage bargaining costsacross segments generate structural unemployment. We estimate the contribution ofthese costs to fluctuations in US unemployment, operationalizing segments as statesor industries. Most structural unemployment is due to wage bargaining costs, whichare large but nevertheless contribute little to unemployment fluctuations. Structuralunemployment is as cyclical as overall unemployment and no more persistent, bothin the current and in previous recessions.

Slow recoveries: A structural interpretation

An analysis of the performance of GDP, employment and otherlabor market variables following the troughs in postwar U.S. businesscycles points to much slower recoveries in the three most recentepisodes, but does not reveal any significant change over time in therelation between GDP and employment. This leads us to characterizethe last three episodes as slow recoveries, as opposed to jobless recoveries.We use the estimated New Keynesian model in Galí-Smets-Wouters (2011) to provide a structural interpretation for the slowerrecoveries since the early nineties.

Estimating overidentified, nonrecursive, time-varying coefficients structural VARs

This paper provides a method to estimate time varying coefficients structuralVARs which are non-recursive and potentially overidentified. The procedureallows for linear and non-linear restrictions on the parameters, maintainsthe multi-move structure of standard algorithms and can be used toestimate structural models with different identification restrictions. We studythe transmission of monetary policy shocks and compare the results with thoseobtained with traditional methods.

The effects of structural reforms on productivity and profitability enhancing reallocation: Evidence from Colombia

Estimates for the U.S. suggest that at least in some sectors productivity enhancing reallocationis the dominant factor in accounting for producitivity growth. An open question, particularlyrelevant for developing countries, is whether reallocation is always productivity enhancing. Itmay be that imperfect competition or other barriers to competitive environments imply that thereallocation process is not fully e?cient in these countries. Using a unique plant-levellongitudinal dataset for Colombia for the period 1982-1998, we explore these issues byexamining the interaction between market allocation, and productivity and profitability.Moreover, given the important trade, labor and financial market reforms in Colombia during theearly 1990's, we explore whether and how the contribution of reallocation changed over theperiod of study. Our data permit measurement of plant-level quantities and prices. Takingadvantage of the rich structure of our price data, we propose a sequential mehodology to estimateproductivity and demand shocks at the plant level. First, we estimate total factor productivity(TFP) with plant-level physical output data, where we use downstream demand to instrumentinputs. We then turn to estimating demand shocks and mark-ups with plant-level price data, usingTFP to instrument for output in the inversedemand equation. We examine the evolution of thedistributions of TFP and demand shocks in response to the market reforms in the 1990's. We findthat market reforms are associated with rising overall productivity that is largely driven byreallocation away from low- and towards highproductivity businesses. In addition, we find thatthe allocation of activity across businesses is less driven by demand factors after reforms. Wefind that the increase in aggregate productivity post-reform is entirely accounted for by theimproved allocation of activity.

Spanish monetary policy: A structural VAR analysis

Some past studies analyzed Spanish monetary policy with the standard VAR. Their problem is that this method obliges researchers to impose a certain extreme form of the short run policy rule on their models. Hence, it does not allow researchers to study the possibility of structural changes in this rule, either. This paper overcomes these problems by using the structural VAR. I find that the rule has always been that of partial accommodation. Prior to 1984, it was quite close to money targeting. After 1984, it became closer to the interest rate targeting, with more emphasis on the exchange rate.

Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance

We address the problem of scheduling a multiclass $M/M/m$ queue with Bernoulli feedback on $m$ parallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity;and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical $c \mu$ rule. Our analysis is based on comparing the expected cost of Klimov's ruleto the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set ofwork decomposition laws for the parallel-server system. We further report on the results of a computational study on the quality of the $c \mu$ rule for parallel scheduling.

Structural changes in the US economy: is there a role for monetary policy?

This paper investigates the contribution of monetary policy to the changes in outputgrowth and inflation dynamics in the US. We identify a policy shock and a policy rule ina time-varying coefficients VAR using robust sign restrictions. The transmission of policyshocks has been relatively stable. The variance of the policy shock has decreased over time,but policy shocks account for a small fraction of the level and of the variations in inflationand output growth volatility and persistence. We find little evidence of a significant increasein the long run response of the interest rate to inflation. A more aggressive inflation policyin the 1970s would have produced large output growth costs.

On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid(whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then theproblem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

A structural model of Australia as a small open economy

This paper sets up and estimates a structuralmodel of Australia as a small open economyusing Bayesian techniques. Unlike other recentstudies, the paper shows that a small microfoundedmodel can capture the open economydimensions quite well. Specifically, the modelattributes a substantial fraction of the volatilityof domestic output and inflation to foreigndisturbances, close to what is suggested by unrestrictedVAR studies. The paper also investigatesthe effects of various exogenous shockson the Australian economy.

The structural dynamics of US output and inflation: What explains the changes?

We examine the dynamics of US output and inflation using a structural time varyingcoefficient VAR. We show that there are changes in the volatility of both variables andin the persistence of inflation. Technology shocks explain changes in output volatility,while a combination of technology, demand and monetary shocks explain variations inthe persistence and volatility of inflation. We detect changes over time in the transmission of technology shocks and in the variance of technology and of monetary policyshocks. Hours and labor productivity always increase in response to technology shocks.

What explains the Great Moderation in the US? A structural analysis

This paper investigates what has caused output and inflation volatility to fall in the USusing a small scale structural model using Bayesian techniques and rolling samples. Thereare instabilities in the posterior of the parameters describing the private sector, the policyrule and the standard deviation of the shocks. Results are robust to the specification ofthe policy rule. Changes in the parameters describing the private sector are the largest,but those of the policy rule and the covariance matrix of the shocks explain the changes most.

The structural dynamics of output growth and inflation: some international evidence

We examine the dynamics of output growth and inflation in the US, Euro area and UK using a structural time varying coefficient VAR. There are important similarities in structural inflation dynamics across countries; output growth dynamics differ. Swings in the magnitude of inflation and output growth volatilities and persistences are accounted for by a combination of three structural shocks. Changes over time in the structure of the economy are limited and permanent variations largely absent. Changes in the volatilities of structural shocks matter.

Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case

We address the performance optimization problem in a single-stationmulticlass queueing network with changeover times by means of theachievable region approach. This approach seeks to obtainperformance bounds and scheduling policies from the solution of amathematical program over a relaxation of the system's performanceregion. Relaxed formulations (including linear, convex, nonconvexand positive semidefinite constraints) of this region are developedby formulating equilibrium relations satisfied by the system, withthe help of Palm calculus. Our contributions include: (1) newconstraints formulating equilibrium relations on server dynamics;(2) a flow conservation interpretation of the constraintspreviously derived by the potential function method; (3) newpositive semidefinite constraints; (4) new work decomposition lawsfor single-station multiclass queueing networks, which yield newconvex constraints; (5) a unified buffer occupancy method ofperformance analysis obtained from the constraints; (6) heuristicscheduling policies from the solution of the relaxations.