I was reading up on the stable marriage problem and chanced upon this question: Is it possible that a man1 has woman1 on the top of his preference list, and woman1 has man1 on top of hers, but still there exists a stable matching (not necessarily man optimal or woman optimal) where they are not paired together?
Stable Matching Algorithm
360 Views Asked by Anannya Uberoi At
1
There are 1 best solutions below
Related Questions in ALGORITHM
- Two different numbers in an array which their sum equals to a given value
- Given two arrays of positive numbers, re-arrange them to form a resulting array, resulting array contains the elements in the same given sequence
- Time complexity of the algorithm?
- Find a MST in O(V+E) Time in a Graph
- Why k and l for LSH used for approximate nearest neighbours?
- How to count the number of ways of choosing of k equal substrings from a List L(the list of All Substrings)
- Issues with reversing the linkedlist
- Finding first non-repeating number in integer array
- Finding average of an array
- How to check for duplicates with less time in a list over 9000 elements by python
- How to pick a number based on probability?
- Insertion Sort help in javascript -- Khan Academy
- Developing a Checkers (Draughts) engine, how to begin?
- Can Bellman-Ford algorithm be used to find shorthest path on a graph with only positive edges?
- What is the function for the KMP Failure Algorithm?
Related Questions in MATCH
- MySQL match against with 2 fields
- Stopping regex at the first match, it shows two times
- CPP, error, classes, no match for even though the declaration is given
- Find Excel three-columns match in two different sheets
- Match a string against a route
- Updating only certain values of data frame based on match
- Matching elements of a list to a data frame using R
- Matches in a string in Java
- MySQL: Remove JOIN for Matched Row if 2nd Round of Criteria Not Met
- Compare two files and append the values, leave the mismatches as such in the output file
- Searching a range to see if range "contains" a value
- Regex from a html parsing, how do I grab a specific string?
- How to implement "Search Previous" in a "Find Keyword" Windows Form in C#
- How to update one element of an array according to a condition on another element?
- C# Regex Match text until specific character
Related Questions in MATCHING
- subtract column1 (dataframe1) from column2 (dataframe2) based on matching column in both R
- How to get pixel coordinates from Feature Matching in OpenCV Python
- Visiting a supermarket with a shopping list, get all items in the fastest way?
- Java populate array randomly in matching game
- Latent Fingerprint Matching
- Inconsistent match function, if I run twice works (R)
- Search last 4digits and match the exact or nearest result in the database using php
- Javascript Regex partial matching
- Finding matching objects in Java
- Matching two vector paths
- consistent matched pairs in R
- File Handling and making directories to match in bash
- Features matching on multiple images
- Semi-Eulerization Algorithm (for dummies)
- What is the Weight Matrix generated in the Matching package?
Related Questions in DISCRETE-MATHEMATICS
- Sets of combinations of subsets of unspecified sizes including permutations of X elements where sum of subset sizes of a set equal to X
- List Subsequents Method
- I can't figure out this sequence - 11110000111000110010
- automate checking of number set associations
- Algorithmic big o order of growth code
- Populating array with random "Pre-Defined" values , non repeating and fast
- finding frequency min and max of an array of measurements
- Shortest common SuperSequence
- Sum of combinations of numbers
- Find the smallest number have 3 integer roots?
- Algorithm that schedule the right number of tasks to maximize reward: tough or basic?
- Describing the right recurrence
- Why is it not possible to construct a finite state machine in this case?
- Proving optimality for a new algorithm that finds minimum spanning tree
- Graph coloring upper bound
Related Questions in STABLE-MARRIAGE
- Variation of stable marriage -- is there always a stable "solution"?
- Implementing algorithm to find all rotations for the stable marriage problem
- Rank Based Group Assignment Algorithm
- stable match algorithm for different sizes groups and limited places
- Matching Algorithm (Java)
- Stable marriage (SMP) where graph is incomplete
- Many-to-Many Assignment Problem Algorithm with Constraints
- Are the results of the medical residency match algorithm unique?
- Algorithm to verify stable matching?
- stable marriage alteration, searching for infinte loop with 6 people
- How can I implement the Gale-Shapley stable marriage algorithm in Perl?
- What is the largest number of solutions to an instance of Stable Marriage?
- Brute force stable marriage, How to implements all possible pairs between 2 lists?
- What is a stable matching?
- counter example of a stable matching
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
The case you are describing sounds like one that is stable but not strongly stable.
From "The structure of stable marriage with indifference": A matching M is strongly stable if there is no couple (x,y) such that x strictly prefers y to his/her partner in M, and y either strictly prefers x to his/her partner ... For a given instance I of SMP, the existence of a weakly stable matching is guaranteed: ... On the other hand, it is straightforward to construct instances of SMT which admit no strongly stable matching.
So it sounds like the answer is yes... it is possible.