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

In the stable marriage problem (SM), a mechanism that always outputs a stablematching is called a stable mechanism. One of the well-known stable mechanismsis the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property thatit is strategy-proof to the men's side, i.e., no man can obtain a betteroutcome by falsifying a preference list. We call such a mechanism aman-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proofmechanism. Roth has shown that there is no stable mechanism that issimultaneously man-strategy-proof and woman-strategy-proof, which is known asRoth's impossibility theorem.  In this paper, we extend these results to the stable marriage problem withties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth'simpossibility theorem takes over to SMTI. Therefore, we focus on theone-sided-strategy-proofness. In SMTI, one instance can have stable matchingsof different sizes, and it is natural to consider the problem of finding alargest stable matching, known as MAX SMTI. Thus we incorporate the notion ofapproximation ratio used in the theory of approximation algorithms. We say thata stable-mechanism is $c$-approximate-stable mechanism if it always returns astable matching of size at least $1/c$ of a largest one. We also consider arestricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men'slists can contain ties.  Our results are summarized as follows: (i) MAX SMTI admits both aman-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof1.5-approximate-stable mechanism. All these results are tight in terms ofapproximation ratios. Also, all these strategy-proofness results apply forstrategy-proofness against coalitions.

Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists