# Introduction iven two different sets, the elements of one set mapped to the elements of another set is known as matching. A matching is called stable if there is no pair (A, B) such that both are better matched than their current matched element. If there is an element A of one set which desires another element B of the second set over its current matched and the element B as well desires A over its current matched element, this matching is known as not stable matching. A stable matching problem consists of finding a stable matching given two evenly sized sets of elements as well as an ordering of the elements' preferences. The solution obtained from this type of algorithms guarantee that the assigned pairs of elements won't prefer any other partners to their current partners. There are also some stable matching algorithms which allow ties in their preference lists. The absence of an unmatched pairs of elements where those elements prefers each other to its current matched element is required for the stability of the solution of this type of algorithms. There are many variants of stable matching problems: ? Stable marriage problem [7]: This problem consists on finding a stable matching of n couples. There will a list of n men with their preferred list of n women, a list of n women with their preferred list of n men. The preference list will contain the ranking of the individuals according to their choices from high to low. A man will propose a woman, according to his preference list and if the woman is available, then it will be paired with that man and the output will be a certain list containing the matched couple. ? Stable roommates problem [3] [8]: This problem is very similar to stable marriage problem, however it requires to have a single set with n cardinality, with each member having preferences respect the rest of the members. The stable matching is considered as the initial set partitioned into n/2 pairs such that there is no two unmatched members that both of them prefer each other instead of their current partners. There is a possibility of a stable matching does not exist. ? Assignment problem [9]: The problem consists in finding the best possible assignment to a set of jobs to complete for a set of persons, where the jobs are ranked by total scores or by the ratings of the employees assigned to those jobs. ? College admission problem [5]: This problem is also known as hospital/residents problem and it also very similar to stable marriage problem. The main difference between these two problems are that in the hospital/resident problem one hospital can take more than one residents where as in stable marriage problem a man take have only one woman. That is, here one-to-many relationship is permitted. ? Hospitals/residents problem with couples [6]: This problem is a variation of the previous problem adding some other constraints. Here, the residents which are couples must be mapped to the same hospital. The members of a couple will have their own list of preferences in order to rank the hospitals and the joint preference list will be consider for matching. Researchers have been using trust theories to construct different type of trust models to overcome unacceptable behaviors. Trust issues have become more suitable nowadays to prove the efficiency of certain algorithmic issues. These trust models have been used to model various aspects such as network security approaches, user authorization [17] or firewall access control measurements. The trust and reputation of the models are vital to ensure a correct behavior among the agents involved. Consider the example of real estate consultancy site, the required elements are finding a suitable plot are, best interior facilities, etc., where the integrity trust is vital and is based on elements such as the existence of fraudulent charges on customers. In this particular context, an agency with lowest integrity trust will be preferred where having better deals are more considered than the risks of being fraud. There are many types of trust models: ? McKnights Trust Model [13] ? Computational Trust Models [11]: The context and situation trust is described in this type of models which are involving dynamic environment. Applications such as trust on social networking sites or access control in P2P networks [10] are based on this type of modeling. Matching is present in all aspects of human life such as the selection of education institutions, the selection of a country for higher education or the selection of a new residency and finding a stable matching of these problems are crucial. Researchers have been successfully demonstrated that is possible to find a solution of these type of problems having an ordered list of preferences. Even though these algorithms are well structured and strongly illustrated, in practice these are not widely studied. The human mind is still an immense mystery and in any time human perception can be changed, that is, their preferences can be changed suddenly which is the main motivation of this research paper. These type of algorithms are based on the preferences of people or institutions (e.g. there is a human mind behind it) and such preferences can be changed in any time so how the stability of the algorithms can be defined on such situations. The same situation can be modeled in the network flow of a packet where the paths that the packet can flow may varies given the environment constraints. In this paper the stable marriage problem has been chosen to be modeled in a dynamic environment using computational trust models (specifically, dynamic trust model) and find the instability of this algorithm. The paper is organized as follows. Section I contains the introduction of paper emphasizing on this motivation of the research work and section II describes and reviews the related works. In section III the research proposal is explained in detail, section IV contains the experimental results explained with example in detail. The section V and VI contains possible future directions and limitations of this research study respectively. The paper concluded with conclusion in section VII. # II. # Literature Review In order to proceed with the proposed research study understanding the entire concept of stable marriage problem and how the dynamic trust model works is essential. The following papers are the main basis of this study: ? Gale-Shapley Algorithm [5] [16]: The stable marriage problem is first studied by Gale and Shapley in the paper [5]. They studied marriage problem and defined an algorithm to solve it with a stable matching solution, as well as they prove that the stable matching is possible. The main purpose is to match the men with women (oneto-one relationship) in such a way so that no unmatched couple prefers each other instead of their current partner. By solving this problem, this authors extended their solution to college admission problem. ? computational model has been proposed for providing security in communication of multi-agent systems. In this research study the authors uses different trust calculations on the agents to find the existence of any malicious behavior among those and proposed a comprehensive model for such trust calculations and a load balancing algorithm to possible the cope up with malicious agents behaviors at the same time providing an efficient workload distribution to the agents. Very few works have been done combining stable matching with trust models. However, there are some works which are concerned with the stability of stable matching. The most important are: ? In this paper [1], the researchers demonstrate that the stability of stable matchings in the social context make a huge difference. They study the stable matching problems where players are entrenched in the social context, and relation such as friendship or altruism may impact in their decisions. Basically, the care towards friends among players plays a vital difference in the quality of stable matching solutions. ? In paper [4], they propose a stable matching algorithm which can provide an almost stable matching by knowing only its neighborhood. They show there results by applying the proposed algorithm in bicolored graphs to find maximumweight matching and for the size of stable matching a centralized randomized constant-time approximation scheme is used. ? The preferences of the participants are exposed in the existing stable matching algorithms which violates their privacy as well as it creates a possibility of manipulation of the algorithm. Having in mind all this concern a private stable matching algorithm is proposed in [6] which guarantees to provide a stable solution. ? The complexity of stable matching problems has been studied in [14]. In this paper, the roommate problem and residents problem with couples have been studied and demonstrated the NPcompleteness of these problems if ties are allowed or not. They show that the roommate problem is NPcomplete if ties are allowed and residents problem with couples is NP-complete with or without ties. ? The two-side matching problems are addressed in [15], mainly the market failures associated with the instability of the stable matching has been studied. Allowing random selection of pairs will converge to stable matching with probability one is shown in this research. III. # Methodology The proposed approach is proving the instability of stable matching solution of the stable marriage problem using dynamic trust model. The dynamic model is based on specific trust calculations, such as historic trust or expected trust; the paper [2] has been studied for the following measurements and to implement stable marriage solution the paper [5] has been focused. Basically, the trust models have been used to model the human behavior computationally. The following steps have been followed to prove the instability of the stable matching: ? Evaluate current satisfaction for current transaction. Satisfaction means the degree of comfort the couple has together. Current satisfaction represents the satisfaction for the most recent transaction. As in real life the behavior of a person cannot be pre assumed and human behavior can changed time to time, so for our implementation we took random value form 0 to 1 of evaluating current satisfaction. ? Calculate Direct trust up to current transaction satisfaction. the weight changes changes based on the accumulated deviation Here c is constant factor which controls to what extent participants will react to recent errors The recent value of satisfaction is given more significance than past trusts. So, if we increase the value of c then we give more significance to the recent deviation than the accumulated deviation and vice versa. Again, we can see that as recent error increases so does which means that recent satisfaction is given higher weight than accumulated satisfaction. ? Calculate Recent trust. Recent trust reflects only the recent behavior. The recent trust between participants is calculated as follows: ? Calculate Historical trust up to current time interval. Historical trust means past experience of the participants to one another. As in real life human forget past so for calculating historical trust forgetting factor is introduced. ? Calculate Expected trust based on Recent trust and Historical Trust. Expected trust reflects expected behavior of the couple to one another. In real life it is deduced from both recent and historical trust. In other words, we are combining both recent behavior and historical behavior to get a prediction of the future behavior. # Initially as expectation remains zero before any transaction. We calculate the expected trust of each pair of participants for each time interval and generated trust matrix at time interval t. ? Update preference matrix based on Expected trust. Based on the Expected trust of the participants the preference matrix for stable matching is generated. If the amount of satisfaction the couple p and q have together at n th transaction in t th time interval, then direct trust is calculated as follows: DT 0 0 (p, q) = 0. DT t n (p, q) = ? × Sat cur + (1 ? ?)DT t (n?1) (p, q) ? = threshold + c × ? t n (p, q) 1 + ? t n (p, q) ? t n?1 (p, q). ? ? t n (p, q) = c × ? t n (p, q) + (1 ? c) × ? t n?1 (p, q) ? t n (p, q) (? t n (p, q)) ? RT t n (p, q) = DT t n (p, q) HT t n (p, q) = ? × HT t n?1 (p, q) + RT t n?1 (p, q) 2 E t n (p, q) = ?RT t n (p, q) + (1 ? ?)HT t n (p, q) E t n (p, q) = 0 (1) The satisfaction of participant's transaction has not been selected randomly, instead a defined range has been used. # IV. # Experimental Results The experimental results show the result of matching N men with N women where N=5 with time interval 3. The step-wise expected trust and preference calculation has been shown in the below tables. # Table I: Expected Trust Table I shows the expected trust of the participants of 3 time intervals. means Expected Trust of Participant i to Participant at time interval t after n transaction and vice versa. Based on the expected trust preference of male and female is calculated for different time interval. V al(i, j, t) j th i th t. V al(i, j, t) j th i th t. Fig. 1: Unstable couples created in different time intervals 1 Figure 1 shows the number of unstable couples created with different time intervals, where the number of participants is 50 and time interval of 30 have been considered. Using dynamic trust modeling we have proved the instability of stable matching algorithm which is clearly shown in above graph. V. # Limitations The proposed approach has some limitations as it takes in consideration some specific constraints. The approach only takes N men and N women, whereas the number of men and women may vary time to time. The time decay model has not been considered for the implementation which imposes one of the boundaries of this approach and lastly only direct experience has been considered. # VI. # Future Scope In future, this research can be further expanded to different stable matching problems such as assignment problem or college admission problem. In the proposed approach only one-to-one mapping has been considered, thus many-to-one or many-to-many problems can also be addressed in future. Also, the limitation can be overcome by considering different trust models and including time decay model. # VII. # Conclusion There are many algorithms that states that matching problems can find a stable solution. However, the stability of these solution have not studied so far. In this paper, we proposed a novel approach to identify the instability of stable matching solutions given by those algorithms. Mainly, stable marriage problem has been considered to be mapped in a dynamic environment where human behavior is modeled by using trust models. Even though the instability of stable matching has been proved, there are some limitations in this approach which the researchers have planned to overcome in future by integrating different trust calculations as well as by integrating time decay model. ![Computer Science and Technology Volume XVIII Issue III Version I Year 2018 © 2018 Global Journals Direct trust keeps record of the satisfaction level of all the transaction the couple have together. Initial Sat cur =](image-2.png "") IITable II shows the preference of Female atdifferent time intervalspreference ofFemale at time interval IIITable III shows the preference of Male atdifferent time intervalspreference ofMale at time intervalAfter 1st interval stable matching is done basedon the preference list of male and female after 1st timeinterval. IV VIInstability of Stable Matching: A Dynamic Trust ApproachTime interval: 20.9088 0.5559 0.5107 0.5379 0.90760.4082 0.9171 0.4612 0.4713 0.9232Year 20180.4700 0.5257 0.9057 0.6220 0.8990 0.4310 0.6355 0.4956 0.8979 0.8965 0.9257 0.8871 0.8965 0.9236 0.896322Time interval: 3Volume XVIII Issue III Version I0.9553 0.4056 0.5466 0.5289 0.9458 0.5846 0.9462 0.5328 0.3969 0.9425 0.5337 0.5342 0.9534 0.4396 0.9300 0.5491 0.4302 0.5882 0.9168 0.9362 0.9465 0.9270 0.9363 0.9309 0.9239 V al(i, j, t) j( ) GJournal of Computer Science and Technology© 2018 Global Journals 1 Vst2 nd3 rd4 th5 th51342254133514254312213451 st2 nd3 rd4 th5 th1524352431354214523114352FemaleMale5112334425 IXYear 2018Volume XVIII Issue III Version I( ) GGlobal Journal of Computer Science and Technology© 2018 Global Journals VII VIII1 st2 nd3 rd4 th5 th15243253413541254132124351 st2 nd3 rd4 th5 th1534225134352145431213425Time interval: 11123324455Time interval: 21521334452Time interval: 31122334554 * Friendship and stable matching ElliotAnshelevich OnkarBhardwaj MartinHoefer European Symposium on Algorithms Berlin, Heidelberg Springer 2013 * SecuredTrust: a dynamic trust computation model for secured communication in multiagent systems AnupamDas Mohammad MahfuzulIslam IEEE Transactions on Dependable and Secure Computing 9 2 2012 * An algorithm for a super-stable roommates problem Fleiner RobertWTams DavidFIrving Manlove Theoretical Computer Science 412 50 2011 * Almost stable matchings by truncating the GaleShapley algorithm PatrikFloren PetteriKaski ValentinPolishchuk JukkaSuomela Algorithmica 58 1 2010 * A private stable matching algorithm PhilippeGolle International Conference on Financial Cryptography and Data Security * Springer 2006 Berlin, Heidelberg * The stable marriage problem: structure and algorithms DanGusfield RobertWIrving 1989 MIT press * An efficient algorithm for the stable roommates problem RobertWIrving Journal of Algorithms 6 4 1985 * The Hungarian method for the assignment problem HaroldWKuhn Naval Research Logistics (NRL) 2 12 1955 * A computational trust model for access control in P2P BoLang Science China Information Sciences 53 5 2010 * PhD diss., PhD dissertation-Dept SMarsh 1994 of Computer Science and Math., Univ. of Stirling Formalizing Trust as a Concept * Conceptualizing trust: A typology and e-commerce customer relationships model DMcknight NormanLHarrison Chervany Proceedings of the 34th Annual Hawaii International Conference on the 34th Annual Hawaii International Conference on IEEE 2001. 2001 10 System Sciences * NP-complete stable matching problems EytanRonn Journal of Algorithms 11 2 1990 * Random paths to stability in two-sided matching AlvinERoth JohnHVande Vate Econometrica: Journal of the Econometric Society 1990 * Gale-shapley stable marriage problem revisited: Strategic issues and applications Chung-PiawTeo JaySethuraman Wee-PengTan Management Science 47 9 2001 * A computational dynamic trust model for user authorization YuhuiZhong BharatBhargava YiLu PelinAngin IEEE Transactions on Dependable and Secure Computing 12 1 2015 * College admissions and the stability of marriage DavidGale LloydSShapley The American Mathematical Monthly 69 1 1962 * Keeping partners together: algorithmic results for the hospitals/residents problem with couples EricJMcdermid DavidFManlove Journal of Combinatorial Optimization 19 3 2010