English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of matchings under two-sided preferences in thepresence of maximum as well as minimum quota requirements for the agents. Thissetting, studied as the Hospital Residents with Lower Quotas (HRLQ) inliterature, models important real world problems like assigning medical interns(residents) to hospitals, and teaching assistants to instructors where aminimum guarantee is essential. When there are no minimum quotas, stability isthe de-facto notion of optimality. However, in the presence of minimum quotas,ensuring stability and simultaneously satisfying lower quotas is not anattainable goal in many instances.  To address this, a relaxation of stability known as envy-freeness, isproposed in literature. In our work, we thoroughly investigate envy-freenessfrom a computational view point. Our results show that computing envy-freematchings that match maximum number of agents is computationally hard and alsohard to approximate up to a constant factor. Additionally, it is known thatenvy-free matchings satisfying lower-quotas may not exist. To circumvent thesedrawbacks, we propose a new notion called relaxed stability. We show thatrelaxed stable matchings are guaranteed to exist even in the presence oflower-quotas. Despite the computational intractability of finding a largestmatching that is feasible and relaxed stable, we give efficient algorithms thatcompute a constant factor approximation to this matching in terms of size.

Envy-freeness and Relaxed Stability under lower quotas