Smith and Rawls share a room

We consider one-to-one matching (roommate) problems in which agents (students) can either be matched as pairs or remain single. The aim of this paper is twofold. First, we review a key result for roommate problems (the ``lonely wolf'' theorem) for which we provide a concise and elementary proof. Second, and related to the title of this paper, we show how the often incompatible concepts of stability (represented by the political economist Adam Smith) and fairness (represented by the political philosopher John Rawls) can be reconciled for roommate problems.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

EMU sovereign debt market crisis: Fundamentals-based or pure contagion?

We empirically investigate whether the transmission of the recent crisis in euro area sovereign debt markets was due to fundamentals-based or pure contagion. To do so, we examine the behaviour of EMU sovereign bond yield spreads with respect to the German bund for a sample of both central and peripheral countries from January 1999 to December 2012. First we apply a dynamic approach to analyse the evolution of the degree of Grangercausality within the 90 pairs of sovereign bond yield spreads in our sample, in order to detect episodes of significantly increased causality between them (which we associate with contagion) and episodes of significantly reduced interconnection (which we associate with immunisation). We then use an ordered logit model to assess the determinants of the occurrence of the episodes detected. Our results suggest the importance of variables proxying market sentiment and of variables proxying macrofundamentals in determining contagion and immunisation outcomes. Therefore, our findings underline the coexistence of “pure” and “fundamentals-based contagion” during the recent European debt crisis.

EMU sovereign debt market crisis: Fundamentals-based or pure contagion?

We empirically investigate whether the transmission of the recent crisis in euro area sovereign debt markets was due to fundamentals-based or pure contagion. To do so, we examine the behaviour of EMU sovereign bond yield spreads with respect to the German bund for a sample of both central and peripheral countries from January 1999 to December 2012. First we apply a dynamic approach to analyse the evolution of the degree of Grangercausality within the 90 pairs of sovereign bond yield spreads in our sample, in order to detect episodes of significantly increased causality between them (which we associate with contagion) and episodes of significantly reduced interconnection (which we associate with immunisation). We then use an ordered logit model to assess the determinants of the occurrence of the episodes detected. Our results suggest the importance of variables proxying market sentiment and of variables proxying macrofundamentals in determining contagion and immunisation outcomes. Therefore, our findings underline the coexistence of “pure” and “fundamentals-based contagion” during the recent European debt crisis.