Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

Comment on "On the Uniqueness of Stable Marriage Matchings" [Economic Letters 69(1):1-8, 2000]

We prove with the help of a counterexample that Lemma 6 and Corollary 7 from Eeckhout [1] are incorrect.

Matching Markets under (In)complete Information

We are the first to introduce incomplete information to centralized many-to-one matching markets such as those to entry-level labor markets or college admissions. This is important because in real life markets (i) any agent is uncertain about the other agents' true preferences and (ii) most entry-level matching is many-to-one (and not one-to-one). We show that for stable (matching) mechanisms there is a strong and surprising link between Nash equilibria under complete information and Bayesian Nash equilibria under incomplete information. That is,given a common belief, a strategy profile is a Bayesian Nash equilibrium under incomplete information in a stable mechanism if and only if, for any true profile in the support of the common belief, the submitted profile is a Nash equilibrium under complete information at the true profile in the direct preference revelation game induced by the stable mechanism. This result may help to explain the success of stable mechanisms in these markets.

On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets

We consider two–sided many–to–many matching markets in which each worker may work for multiple firms and each firm may hire multiple workers. We study individual and group manipulations in centralized markets that employ (pairwise) stable mechanisms and that require participants to submit rank order lists of agents on the other side of the market. We are interested in simple preference manipulations that have been reported and studied in empirical and theoretical work: truncation strategies, which are the lists obtained by removing a tail of least preferred partners from a preference list, and the more general dropping strategies, which are the lists obtained by only removing partners from a preference list (i.e., no reshuffling). We study when truncation / dropping strategies are exhaustive for a group of agents on the same side of the market, i.e., when each match resulting from preference manipulations can be replicated or improved upon by some truncation / dropping strategies. We prove that for each stable mechanism, truncation strategies are exhaustive for each agent with quota 1 (Theorem 1). We show that this result cannot be extended neither to group manipulations (even when all quotas equal 1 – Example 1), nor to individual manipulations when the agent’s quota is larger than 1 (even when all other agents’ quotas equal 1 – Example 2). Finally, we prove that for each stable mechanism, dropping strategies are exhaustive for each group of agents on the same side of the market (Theorem 2), i.e., independently of the quotas.

Essays on the Axiomatic Theory of Matching

This dissertation mimics the Turkish college admission procedure. It started with the purpose to reduce the inefficiencies in Turkish market. For this purpose, we propose a mechanism under a new market structure; as we prefer to call, semi-centralization. In chapter 1, we give a brief summary of Matching Theory. We present the first examples in Matching history with the most general papers and mechanisms. In chapter 2, we propose our mechanism. In real life application, that is in Turkish university placements, the mechanism reduces the inefficiencies of the current system. The success of the mechanism depends on the preference profile. It is easy to show that under complete information the mechanism implements the full set of stable matchings for a given profile. In chapter 3, we refine our basic mechanism. The modification on the mechanism has a crucial effect on the results. The new mechanism is, as we call, a middle mechanism. In one of the subdomain, this mechanism coincides with the original basic mechanism. But, in the other partition, it gives the same results with Gale and Shapley's algorithm. In chapter 4, we apply our basic mechanism to well known Roommate Problem. Since the roommate problem is in one-sided game patern, firstly we propose an auxiliary function to convert the game semi centralized two-sided game, because our basic mechanism is designed for this framework. We show that this process is succesful in finding a stable matching in the existence of stability. We also show that our mechanism easily and simply tells us if a profile lacks of stability by using purified orderings. Finally, we show a method to find all the stable matching in the existence of multi stability. The method is simply to run the mechanism for all of the top agents in the social preference.

Preference Structure and Random Paths to Stability in Matching Markets

This paper examines how preference correlation and intercorrelation combine to influence the length of a decentralized matching market's path to stability. In simulated experiments, marriage markets with various preference specifications begin at an arbitrary matching of couples and proceed toward stability via the random mechanism proposed by Roth and Vande Vate (1990). The results of these experiments reveal that fundamental preference characteristics are critical in predicting how long the market will take to reach a stable matching. In particular, intercorrelation and correlation are shown to have an exponential impact on the number of blocking pairs that must be randomly satisfied before stability is attained. The magnitude of the impact is dramatically different, however, depending on whether preferences are positively or negatively intercorrelated.

QoE-aware power management in vehicle-to-grid networks:a matching-theoretic approach

Frequency, time and places of charging and discharging have critical impact on the Quality of Experience (QoE) of using Electric Vehicles (EVs). EV charging and discharging scheduling schemes should consider both the QoE of using EV and the load capacity of the power grid. In this paper, we design a traveling plan-aware scheduling scheme for EV charging in driving pattern and a cooperative EV charging and discharging scheme in parking pattern to improve the QoE of using EV and enhance the reliability of the power grid. For traveling planaware scheduling, the assignment of EVs to Charging Stations (CSs) is modeled as a many-to-one matching game and the Stable Matching Algorithm (SMA) is proposed. For cooperative EV charging and discharging in parking pattern, the electricity exchange between charging EVs and discharging EVs in the same parking lot is formulated as a many-to-many matching model with ties, and we develop the Pareto Optimal Matching Algorithm (POMA). Simulation results indicates that the SMA can significantly improve the average system utility for EV charging in driving pattern, and the POMA can increase the amount of electricity offloaded from the grid which is helpful to enhance the reliability of the power grid.

Matching theory based travel plan aware charging algorithms in V2G smart grid networks

The frequency, time and places of charging have large impact on the Quality of Experience (QoE) of EV drivers. It is critical to design effective EV charging scheduling system to improve the QoE of EV drivers. In order to improve EV charging QoE and utilization of CSs, we develop an innovative travel plan aware charging scheduling scheme for moving EVs to be charged at Charging Stations (CS). In the design of the proposed charging scheduling scheme for moving EVs, the travel routes of EVs and the utility of CSs are taken into consideration. The assignment of EVs to CSs is modeled as a two-sided many-to-one matching game with the objective of maximizing the system utility which reflects the satisfactory degrees of EVs and the profits of CSs. A Stable Matching Algorithm (SMA) is proposed to seek stable matching between charging EVs and CSs. Furthermore, an improved Learning based On-LiNe scheduling Algorithm (LONA) is proposed to be executed by each CS in a distributed manner. The performance gain of the average system utility by the SMA is up to 38.2% comparing to the Random Charging Scheduling (RCS) algorithm, and 4.67% comparing to Only utility of Electric Vehicle Concerned (OEVC) scheme. The effectiveness of the proposed SMA and LONA is also demonstrated by simulations in terms of the satisfactory ratio of charging EVs and the the convergence speed of iteration.

A further note on the college admission game

When a stable matching rule is used for a college admission market, questions on incentives facing agents of both sides of the market naturally emerge. This note states and proves four important results which fill a gap in the theory of incentives for the college admission model. Two of them have never been demonstrated but have been used along the years and are responsible for the success that this theory has had in explaining empirical economic phenomena.

Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

A stable graph-based representation for object recognition through high-order matching

Many Object recognition techniques perform some flavour of point pattern matching between a model and a scene. Such points are usually selected through a feature detection algorithm that is robust to a class of image transformations and a suitable descriptor is computed over them in order to get a reliable matching. Moreover, some approaches take an additional step by casting the correspondence problem into a matching between graphs defined over feature points. The motivation is that the relational model would add more discriminative power, however the overall effectiveness strongly depends on the ability to build a graph that is stable with respect to both changes in the object appearance and spatial distribution of interest points. In fact, widely used graph-based representations, have shown to suffer some limitations, especially with respect to changes in the Euclidean organization of the feature points. In this paper we introduce a technique to build relational structures over corner points that does not depend on the spatial distribution of the features. © 2012 ICPR Org Committee.

Robust facial feature extraction and matching

Automated feature extraction and correspondence determination is an extremely important problem in the face recognition community as it often forms the foundation of the normalisation and database construction phases of many recognition and verification systems. This paper presents a completely automatic feature extraction system based upon a modified volume descriptor. These features form a stable descriptor for faces and are utilised in a reversible jump Markov chain Monte Carlo correspondence algorithm to automatically determine correspondences which exist between faces. The developed system is invariant to changes in pose and occlusion and results indicate that it is also robust to minor face deformations which may be present with variations in expression.

Highly luminescent and thermally stable lanthanide coordination polymers designed from 4-(dipyridin-2-yl)aminobenzoate: efficient energy transfer from Tb3+ to Eu3+ in a mixed lanthanide coordination compound

Herein, a new aromatic carboxylate ligand, namely, 4-(dipyridin-2-yl)aminobenzoic acid (HL), has been designed and employed for the construction of a series of lanthanide complexes (Eu3+ = 1, Tb3+ = 2, and Gd3+ = 3). Complexes of 1 and 2 were structurally authenticated by single-crystal X-ray diffraction and were found to exist as infinite 1D coordination polymers with the general formulas {Eu(L)(3)(H2O)(2)]}(n) (1) and {Tb(L)(3)(H2O)]center dot(H2O)}(n) (2). Both compounds crystallize in monoclinic space group C2/c. The photophysical properties demonstrated that the developed 4-(dipyridin-2-yl)aminobenzoate ligand is well suited for the sensitization of Tb3+ emission (Phi(overall) = 64%) thanks to the favorable position of the triplet state ((3)pi pi*) of the ligand the energy difference between the triplet state of the ligand and the excited state of Tb3+ (Delta E) = (3)pi pi* - D-5(4) = 3197 cm(-1)], as investigated in the Gd3+ complex. On the other hand, the corresponding Eu3+ complex shows weak luminescence efficiency (Phi(overall) = 7%) due to poor matching of the triplet state of the ligand with that of the emissive excited states of the metal ion (Delta E = (3)pi pi* - D-5(0) = 6447 cm(-1)). Furthermore, in the present work, a mixed lanthanide system featuring Eu3+ and Tb3+ ions with the general formula {Eu0.5Tb0.5(L)(3)(H2O)(2)]}(n) (4) was also synthesized, and the luminescent properties were evaluated and compared with those of the analogous single-lanthanide-ion systems (1 and 2). The lifetime measurements for 4 strongly support the premise that efficient energy transfer occurs between Tb3+ and Eu3+ in a mixed lanthanide system (eta = 86%).

Matching and sorting in online dating

Using data on user attributes and interactions from an online dating site, we estimate mate preferences, and use the Gale-Shapley algorithm to predict stable matches. The predicted matches are similar to the actual matches achieved by the dating site, and the actual matches are approximately efficient. Out-of-sample predictions of offline matches, i.e., marriages, exhibit assortative mating patterns similar to those observed in actual marriages. Thus, mate preferences, without resort to search frictions, can generate sorting in marriages. However, we underpredict some of the correlation patterns; search frictions may play a role in explaining the discrepancy.

Design and evaluation of tinnitus synthesis methods: From spectral to spatial matching

Purpose
This study was designed to investigate methods to help patients suffering from unilateral tinnitus synthesizing an auditory replica of their tinnitus.

Materials and methods
Two semi-automatic methods (A and B) derived from the auditory threshold of the patient and a method (C) combining a pure tone and a narrow band-pass noise centred on an adjustable frequency were devised and rated on their likeness over two test sessions. A third test evaluated the stability over time of the synthesized tinnitus replica built with method C, and its proneness to merge with the patient's tinnitus. Patients were then asked to try and control the lateralisation of this single percept through the adjustment of the tinnitus replica level.

Results
The first two tests showed that seven out of ten patients chose the tinnitus replica built with method C as their preferred one. The third test, performed on twelve patients, revealed pitch tuning was rather stable over a week interval. It showed that eight patients were able to consistently match the central frequency of the synthesized tinnitus (presented to the contralateral ear) to their own tinnitus, which leaded to a unique tinnitus percept. The lateralisation displacement was consistent across patients and revealed an average range of 29dB to obtain a full lateral shift from the ipsilateral to the contralateral side.

Conclusions
Although spectrally simpler than the semi-automatic methods, method C could replicate patients' tinnitus, to some extent. When a unique percept between synthesized tinnitus and patients' tinnitus arose, lateralisation of this percept was achieved.