Random paths to P-stability in the roommate problem

For solvable roommate problems with strict preferences Diamantoudi et al. (Games Econ Behav 48: 18–28, 2004) show that for any unstable matching, there exists a finite sequence of successive myopic blocking pairs leading to a stable matching. In this paper, we define P-stable matchings associated with stable partitions and, by using a proposal-rejection procedure, generalize the previous result for the entire class of roommate problems.     

Inconsistency indices for pairwise comparison matrices: a numerical study

Evaluating the level of inconsistency of pairwise comparisons is often a crucial step in multi criteria decision analysis. Several inconsistency indices have been proposed in the literature to estimate the deviation of expert’s judgments from a situation of full consistency. This paper surveys and analyzes ten indices from the numerical point of view. Specifically, we investigate degrees of agreement between them to check how similar they are. Results show a wide range of behaviors, ranging from very strong to very weak degrees of agreement.     

Paths to stability in two-sided matching under uncertainty

We consider one-to-one matching problems under two modalities of uncertainty in which types are assigned to agents either with or without replacement. Individuals have preferences over the possible types of the agents from the opposite market side and initially know the ‘name’ but not the ‘type’ of their potential partners. In this context, learning occurs via matching and using Bayes’ rule. We introduce the notion of a stable and consistent outcome, and show how the interaction between blocking and learning behavior shapes the existence of paths to stability in each of these two uncertainty environments. Existence of stable and consistent outcomes then follows as a side result.     

Endogenous matching in a market with heterogeneous principals and agents

We employ the assignment game of Shapley and Shubik (Int J Game Theory 1:111–130, 1972) to study the endogenous matching patterns in a market that consists of heterogenous principals and agents. We show that, in general, the equilibrium matching is non-assortative. We then characterize the equilibrium relationship between risk and performance pay and risk and fixed compensation. This is the first paper that characterizes the equilibrium matching, to its fullest possible extent, building on the Holmstrom and Milgrom (Econometrica 55:303–328, 1987) principal-agent model. This model has been used extensively in the empirical literature and therefore we hope that our results will be of value to empirical researchers who wish to study a principal-agent market.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

Paths to stability and uniqueness in two-sided matching markets

The deferred acceptance algorithm introduced by Gale and Shapley is a centralized algorithm, where a social planner solicits the preferences from two sides of a market and generates a stable matching. On the other hand, the algorithm proposed by Knuth is a decentralized algorithm. In this article, we discuss conditions leading to the convergence of Knuth’s decentralized algorithm. In particular, we show that Knuth’s decentralized algorithm converges to a stable matching if either the Sequential Preference Condition (SPC) holds or if the market admits no cycle. In fact, acyclicity turns out to be a special case of SPC. We then consider markets where agents may prefer to remain single rather than being matched with someone. We introduce a generalized version of SPC for such markets. Under this notion of generalized SPC, we show that the market admits a unique stable matching, and that Knuth’s decentralized algorithm converges. The generalized SPC seems to be the most general condition available in the literature for uniqueness in two-sided matching markets.     

The information value of logistics platforms in a freight matching market

The information asymmetry in the freight matching of the long-haul trucking industry usually pushes shippers to join a logistics platform that has better knowledge of truckers’ cost information. A logistics platform that is plugged into a freight transportation system helps shippers overcome their information disadvantage but produces the double marginalization effect. We investigate the equilibrium characteristics of a shipper and logistics platform in the freight matching market and find that the shipper prefers to cooperate with the logistics platform in a small-scale sales market but searches for truckers by himself in a large-scale sales market. We show that the information value of a logistics platform for the freight system consists of two aspects: (i) employ low-cost truckers for the shipper and avoid the shipper’s inefficient expansion of the selling quantity in a moderate-scale sales market with greatly heterogeneous truckers, and (ii) improve both the total profit and social welfare of the freight system in a small-scale sales market. We further find that the shipper’s private information may hurt the logistics platform and the logistics platform can mitigate her double marginalization disadvantage by improving value-added services or lowering the logistics price in a large-scale market. Our findings provide guidelines for the shipper and logistics platform on how to choose the appropriate transportation strategy and employment strategy in different logistics markets.     

Determination of paths to vendor market efficiency using parallel coordinates representation: A negotiation tool for buyers

This study demonstrates the use of data envelopment analysis for measuring vendor performance and efficiency. An algorithm by Inselberg is employed for determining points of vendor efficiency on multiple criteria. This study then demonstrates how parallel coordinates graphical representation can be used to display the efficiency of vendors on multiple criteria, and, in so doing, visually identify benchmark values on these criteria for negotiating with inefficient vendors. An example of a firm purchasing in a JIT manufacturing environment is used to illustrate this approach. The results of this approach point to its flexibility for use in vendor negotiations.     

Sensitivity analysis for the matching problem and its use in solving matching problems with a single side constraint

This paper develops certain sensitivity analysis capabilities for use with a primaldual matching code. The specific problem addressed is reoptimizing after the costs of a subset of the edges have been increased by a constant amount. This capability is applied to a dual ascent procedure for a Lagrangian relaxation of a matching problem with a single generalized upper bound side constraint. Some of the sensitivity analysis capabilities should be useful in other contexts as well. In particular, we give a method for solving for a set of dual variables that satisfy the strong complementary conditions given a blossom structure.Part of this work was performed while this author was visiting the University of Waterloo.     

Full predictivistic modeling of stock market data: Application to change point problems

In change point problems in general we should answer three questions: how many changes are there? Where are they? And, what is the distribution of the data within the blocks? In this paper, we develop a new full predictivistic approach for modeling observations within the same block of observation and consider the product partition model (PPM) for treating the change point problem. The PPM brings more flexibility into the change point problem because it considers the number of changes and the instants when the changes occurred as random variables. A full predictivistic characterization of the model can provide a more tractable way to elicit the prior distribution of the parameters of interest, once prior opinions will be required only about observable quantities. We also present an application to the problem of identifying multiple change points in the mean and variance of a stock market return time series.     

Nearest feasible paths in optimal control problems: Theory,examples, and counterexamples

Many infinite-horizon optimal control problems in management science and economics have optimal paths that approach some stationary level. Often, this path has the property of being the nearest feasible path to the stationary equilibrium. This paper obtains a simple multiplicative characterization for a single-state single-control problem to have this property. By using Green's theorem it is shown that the property is observed as long as the stationary level is sustainable by a feasible control. If not, the property is, in general, shown to be false. The paper concludes with an important theorem which states that even in the case of multiple equilibria, the optimal path is a nearest feasible path to one of them.The author thanks J. Bona for his helpful comments.     

Random A-permutations: Convergence to a Poisson process

Suppose that S _n is the permutation group of degree n, A is a subset of the set of natural numbers ?, and T _n(A) is the set of all permutations from S _n whose cycle lengths belong to the set A. Permutations from T _n are usually called A-permutations. We consider a wide class of sets A of positive asymptotic density. Suppose that ζ _mn is the number of cycles of length m of a random permutation uniformly distributed on T _n. It is shown in this paper that the finite-dimensional distributions of the random process {tz _mn, m ε A} weakly converge as n → ∞ to the finite-dimensional distributions of a Poisson process on A.     

A counterexample to a conjecture on paths of bounded length

In a recent paper Lovász, Neumann-Lara, and Plummer studied Mengerian theorems for paths of bounded length. Their study led to a conjecture concerning the extent to which Menger's theorem can fail when restricted to paths of bounded length. In this paper we offer counterexamples to this conjecture.     

Random Walks in Random Media on a Cayley Tree

We present sufficient conditions for the transience of random walks with bounded jumps in random media on a Cayley tree.     

Memory,market stability and attractors coexistence in a nonlinear cobweb model

We investigate the dynamics of a cobweb type model with nonlinear demand and supply curves in which producers make forecasts on future prices with a backward looking expectation formation mechanism: the expected price for the next period is obtained by a weighted average of the prices observed in the last two periods. The study herewith presents aims at confirming the existence of a locally stabilising effect due to the presence of memory, but an increase of memory in price expectations can be globally qualitatively destabilising, in the sense that it leads to coexistence of different attractors with their respective basins of attraction.     

Local stability of solutions to differentiable optimization problems in banach spaces

This paper considers a class of nonlinear differentiable optimization problems depending on a parameter. We show that, if constraint regularity, a second-order sufficient optimality condition, and a stability condition for the Lagrange multipliers hold, then for sufficiently smooth perturbations of the constraints and the objective function the optimal solutions locally obey a type of Lipschitz condition. The results are applied to finite-dimensional problems, equality constrained problems, and optimal control problems.