Allocation is a fundamental task
- Students into flats
- Employees into teams
- Medical students to hospitals
- Students to supervisor for projects
Want the allocation to be ‘stable’
- Of course, probably cannot make everyone happy at the same time!
- Can we at least enforce something reasonable!
- Eg:- If two people prefer each other to their current partners, then they will leave their current partners and become partners.
- We call such pairs as an unstable pair
- An allocation is stable if there are no unstable pairs
Need to introduce notion of preferences