Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Strategy-Proof Approximation Algorithms for the Stable Marriage Problem
  with Ties and Incomplete Lists   In the stable marriage problem (SM), a mechanism that always outputs a stable
matching is called a stable mechanism. One of the well-known stable mechanisms
is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that
it is strategy-proof to the men's side, i.e., no man can obtain a better
outcome by falsifying a preference list. We call such a mechanism a
man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof
mechanism. Roth has shown that there is no stable mechanism that is
simultaneously man-strategy-proof and woman-strategy-proof, which is known as
Roth's impossibility theorem.
  In this paper, we extend these results to the stable marriage problem with
ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth's
impossibility theorem takes over to SMTI. Therefore, we focus on the
one-sided-strategy-proofness. In SMTI, one instance can have stable matchings
of different sizes, and it is natural to consider the problem of finding a
largest stable matching, known as MAX SMTI. Thus we incorporate the notion of
approximation ratio used in the theory of approximation algorithms. We say that
a stable-mechanism is $c$-approximate-stable mechanism if it always returns a
stable matching of size at least $1/c$ of a largest one. We also consider a
restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men's
lists can contain ties.
  Our results are summarized as follows: (i) MAX SMTI admits both a
man-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof
2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof
2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof
1.5-approximate-stable mechanism. All these results are tight in terms of
approximation ratios. Also, all these strategy-proofness results apply for
strategy-proofness against coalitions.

36
The categories of this paper are: cmp-lg
0
The categories of this paper are: hep-ph
16
The categories of this paper are: stat
23
The categories of this paper are: solv-int
27
The categories of this paper are: comp-gas
2
The categories of this paper are: math
26
The categories of this paper are: bayes-an
34
The categories of this paper are: chem-ph
10
The categories of this paper are: q-bio
24
The categories of this paper are: dg-ga
3
The categories of this paper are: physics
6
The categories of this paper are: astro-ph
7
The categories of this paper are: hep-th
12
The categories of this paper are: nucl-th
19
The categories of this paper are: eess
8
The categories of this paper are: hep-ex