A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

Interviews and adverse selection

Interviewing in professional labor markets is a costly process for firms. Moreover, poor screening can have a persistent negative impact on firms bottom lines and candidates careers. In a simple dynamic model where firms can pay a cost to interview applicants who have private information about their own ability, potentially large inefficiencies arise from information-based unemployment, where able workers are rejected by firms because of their lack of offers in previous interviews. This effect may make the market less efficient than random matching. We show that the first best can be achieved using either a mechanism with transfers or one without transfers.

Adverse selection, credit and efficiency: The case of the missing market

We analyze a standard environment of adverse selection in credit markets. In our environment,entrepreneurs who are privately informed about the quality of their projects need toborrow from banks. Conventional wisdom says that, in this class of economies, the competitiveequilibrium is typically inefficient.We show that this conventional wisdom rests on one implicit assumption: entrepreneurscan only borrow from banks. If an additional market is added to provide entrepreneurs withadditional funds, efficiency can be attained in equilibrium. An important characteristic of thisadditional market is that it must be non-exclusive, in the sense that entrepreneurs must be ableto simultaneously borrow from many different lenders operating in it. This makes it possible toattain efficiency by pooling all entrepreneurs in the new market while separating them in themarket for bank loans.

Adverse selection, credit and efficiency: The case of the missing market

We analyze a standard environment of adverse selection in credit markets. In our environment,entrepreneurs who are privately informed about the quality of their projects needto borrow in order to invest. Conventional wisdom says that, in this class of economies, thecompetitive equilibrium is typically inefficient.We show that this conventional wisdom rests on one implicit assumption: entrepreneurscan only access monitored lending. If a new set of markets is added to provide entrepreneurswith additional funds, efficiency can be attained in equilibrium. An important characteristic ofthese additional markets is that lending in them must be unmonitored, in the sense that it doesnot condition total borrowing or investment by entrepreneurs. This makes it possible to attainefficiency by pooling all entrepreneurs in the new markets while separating them in the marketsfor monitored loans.

Hiring and firing costs, adverse selection and long-term unemployment

In this paper, we present a matching model with adverse selection that explains why flows into and out of unemployment are much lower in Europe compared to North America, while employment-to-employment flows are similar in the two continents. In the model,firms use discretion in terms of whom to fire and, thus, low quality workers are more likely to be dismissed than high quality workers. Moreover, as hiring and firing costs increase, firms find it more costly to hire a bad worker and, thus, they prefer to hire out of the pool of employed job seekers rather than out of the pool of the unemployed, who are more likely to turn out to be 'lemons'. We use microdata for Spain and the U.S. and find that the ratio of the job finding probability of the unemployed to the job finding probability of employed job seekers was smaller in Spain than in the U.S. Furthermore, using U.S. data, we find that the discrimination of the unemployed increased over the 1980's in those states that raised firing costs by introducing exceptions to the employment-at-will doctrine.

Improved estimation of the covariance matrix of stock returns with an application to portofolio selection

This paper proposes to estimate the covariance matrix of stock returnsby an optimally weighted average of two existing estimators: the samplecovariance matrix and single-index covariance matrix. This method isgenerally known as shrinkage, and it is standard in decision theory andin empirical Bayesian statistics. Our shrinkage estimator can be seenas a way to account for extra-market covariance without having to specifyan arbitrary multi-factor structure. For NYSE and AMEX stock returns from1972 to 1995, it can be used to select portfolios with significantly lowerout-of-sample variance than a set of existing estimators, includingmulti-factor models.

On the efficiency and sensitivity of a pyramidal classification algorithm

In this paper we propose a Pyramidal Classification Algorithm,which together with an appropriate aggregation index producesan indexed pseudo-hierarchy (in the strict sense) withoutinversions nor crossings. The computer implementation of thealgorithm makes it possible to carry out some simulation testsby Monte Carlo methods in order to study the efficiency andsensitivity of the pyramidal methods of the Maximum, Minimumand UPGMA. The results shown in this paper may help to choosebetween the three classification methods proposed, in order toobtain the classification that best fits the original structureof the population, provided we have an a priori informationconcerning this structure.

Dynamic adverse selection and debt

This paper argues that the strategic use of debt favours the revelationof information in dynamic adverse selection problems. Our argument is basedon the idea that debt is a credible commitment to end long term relationships.Consequently, debt encourages a privately informed party to disclose itsinformation at early stages of a relationship. We illustrate our pointwith the financing decision of a monopolist selling a good to a buyerwhose valuation is private information. A high level of (renegotiable)debt, by increasing the scope for liquidation, may induce the highvaluation buyer to buy early at a high price and thus increase themonopolist's expected payoff. By affecting the buyer's strategy, it mayreduce the probability of excessive liquidation. We investigate theconsequences of good durability and we examine the way debt mayalleviate the ratchet effect.

Generalized canonical correlation analysis of matrices with different row and column orders

A Method is offered that makes it possible to apply generalized canonicalcorrelations analysis (CANCOR) to two or more matrices of different row and column order. The new method optimizes the generalized canonical correlationanalysis objective by considering only the observed values. This is achieved byemploying selection matrices. We present and discuss fit measures to assessthe quality of the solutions. In a simulation study we assess the performance of our new method and compare it to an existing procedure called GENCOM,proposed by Green and Carroll. We find that our new method outperforms the GENCOM algorithm both with respect to model fit and recovery of the truestructure. Moreover, as our new method does not require any type of iteration itis easier to implement and requires less computation. We illustrate the methodby means of an example concerning the relative positions of the political parties inthe Netherlands based on provincial data.

Long-run selection and the work ethic

That individuals contribute in social dilemma interactions even when contributing is costly is a well-established observation in the experimental literature. Since a contributor is always strictly worse off than a non-contributor the question is raised if an intrinsic motivation to contribute can survive in an evolutionary setting. Using recent results on deterministic approximation of stochastic evolutionary dynamics we give conditions for equilibria with a positive number of contributors to be selected in the long run.

Equilibrium selection through incomplete information in coordination games: An experimental study

We perform an experiment on a pure coordination game with uncertaintyabout the payoffs. Our game is closely related to models that have beenused in many macroeconomic and financial applications to solve problemsof equilibrium indeterminacy. In our experiment each subject receives anoisy signal about the true payoffs. This game has a unique strategyprofile that survives the iterative deletion of strictly dominatedstrategies (thus a unique Nash equilibrium). The equilibrium outcomecoincides, on average, with the risk-dominant equilibrium outcome ofthe underlying coordination game. The behavior of the subjects convergesto the theoretical prediction after enough experience has been gained. The data (and the comments) suggest that subjects do not apply through"a priori" reasoning the iterated deletion of dominated strategies.Instead, they adapt to the responses of other players. Thus, the lengthof the learning phase clearly varies for the different signals. We alsotest behavior in a game without uncertainty as a benchmark case. The gamewith uncertainty is inspired by the "global" games of Carlsson and VanDamme (1993).

Optimal contracts, adverse selection and social preferences: An experiment

It has long been standard in agency theory to search for incentive-compatible mechanisms on the assumption that people care only about their own material wealth. However, this assumption is clearly refuted by numerous experiments, and we feel that it may be useful to consider nonpecuniary utility in mechanism design and contract theory. Accordingly, we devise an experiment to explore optimal contracts in an adverse-selection context. A principal proposes one of three contract menus, each of which offers a choice of two incentive-compatible contracts, to two agents whose types are unknown to the principal. The agents know the set of possible menus, and choose to either accept one of the two contracts offered in the proposed menu or to reject the menu altogether; a rejection by either agent leads to lower (and equal) reservation payoffs for all parties. While all three possible menus favor the principal, they do so to varying degrees. We observe numerous rejections of the more lopsided menus, and approach an equilibrium where one of the more equitable contract menus (which one depends on the reservation payoffs) is proposed and agents accept a contract, selecting actions according to their types. Behavior is largely consistent with all recent models of social preferences, strongly suggesting there is value in considering nonpecuniary utility in agency theory.