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
- MCNP 6 - Doubts about cells
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What is the algorithm behind math.gcd and why it is faster Euclidean algorithm?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- Dots and Boxes with apha-beta pruning
- What is the average and worst-case time complexity of my string searching algorithm?
- Building a School Schedule Generator
- TC problem 5-2:how to calculate the probability of the indicator random variable?
- LCA of a binary tree implemented in Python
- Identify the checksum algorithm
- Algorithm for finding a subset of nodes in a weighted connected graph such that the distance between any pair nodes are under a postive number?
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Algorithm to find neighbours of point by distance with no repeats
- Asking code suggestions about data structure and algorithm
- Heap sort with multithreading
Related Questions in MATCH
- Matching hundreds non-adjaccent keywords in large text corpus in Python
- Google sheets formula based upon a unique identifier and a date match (in between two dates)
- How to check for matches where fields are different?
- Using Closing Stock Balance as Opening Stock in subsequent line item
- Merge and combine time frames for excel file
- match a partially moved enum Rust
- Index match to retrieve based on contains VBA
- Use Record Number and Heading Names to sort rows to columns, skipping blank cells
- if cell B1 is blank, find the next cell in column A with matching data that also has data in column B. Input the data found in column B into B1
- Check Groovy string if it matches dynamically changing substring
- sum in multiple sheets with corresponding values in excel
- Create a formula in spry to extract a data output if the columns match multiple custom fields
- regex avoid replace number from (.*) replacement
- Return Column heading in table, after looking up row and values in row
- How to make regex_match patterns case insensitive in osquery queries?
Related Questions in MATCHING
- why result of regular expression match in not as expected?
- Importing large contact file error message and failure --why?
- Custom pattern matching between two columns and replacing to keep within-column groups consistent
- Unable to find a match for a substring in column of my dataframe
- numerical/user defined similarity calculation in reclin2
- Combining matchit objects for descriptive analysis (CRAN/R)
- Adding together matrices of two different dimensions with column/row matching
- Copy and paste specific data from an Excel sheet to a web page based on a specific condition, repeating this process more than 1000 times
- R Coarsened Exact Matching, list with matched controls
- record matching/similarity calculation for numbers and characters
- Searchbox on Sheet1 for finding a specific row on a table placed in Sheet2
- I want to highlight cells that are not represented in table
- PowerShell move all files containg exact string in their body
- Matching up values in two separate columns using VBA
- Replacing rows of NA with another row meeting specific column matching
Related Questions in DISCRETE-MATHEMATICS
- Sequences - Find the next term in the sequence
- Is my logic correct? A bit string of n with more 0s than 1s
- Binary Tree Propositional Calculator in C language
- NDSolve fails to solve partial differential equation
- Prove that (p → q) → ((r ∨ p) → (r ∨ q)) is a tautology without using truth table
- How can I add one stop point to the distance between two cities in the Dijkstra algorithm?
- How to distribute files among dirs to have an equal quantity in each set and no initial files remain in any set?
- Some confusion regarding the Binary tree Property about the Number of external nodes = Number of Internal Node + 1
- Solving numerically a second order ODE with Maple
- (MATLAB) ALL integer positive solutions for a linear equation
- What's wrong with my bron-kerbosch-algorithm
- When will these functions be different?
- How to resolve Horn clause-like tag implications with Django and Postgres database
- Propositional Logic in Prolog - Incorrect Representations
- Dynamic programming with memoization on the rob house problem
Related Questions in STABLE-MARRIAGE
- Issues when Reading Preferences from Input File in Java for Stable Matching Problem
- Stable marriage algorithm variation
- Implementing algorithm to find all rotations for the stable marriage problem
- Are the results of the medical residency match algorithm unique?
- How to approach Stable Marriage Problem with restricted pairs
- Stable Marriage problem variant that only cares about the preference of one party
- Many-to-Many Assignment Problem Algorithm with Constraints
- stable match algorithm for different sizes groups and limited places
- Rank Based Group Assignment Algorithm
- stable marriage problem happiness coefficient
- Stable Marriage Problem - Empty preference lists
- Stable matching matches least preferable
- Gale-Shapley Algorithm Stability Test
- Algorithm to verify stable matching?
- Is there any python code or a modification for the Gale Shapley algorithm so it can solve stable marriage problem with incomplete preference lists
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 # Hahtags
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.