Due to the lack of coordination, it is unlikely that the selfish players of a strategic game reach a socially good state. A possible way to cope with selfishness is to compute a desired outcome (if it is tractable) and impose it. However this answer is often inappropriate because compelling an agent can be costly, unpopular or just hard to implement. Since both situations (no coordination and full coordination) show opposite advantages and drawbacks, it is natural to study possible tradeoffs. In this paper we study a strategic game where the nodes of a simple graph G are independent agents who try to form pairs: e.g. jobs and applicants, tennis players for a match, etc. In many instances of the game, a Nash equilibrium significantly deviates from a social optimum. We analyze a scenario where we fix the strategy of some players; the other players are free to make their choice. The goal is to compel a minimum number of players and guarantee that any possible equilibrium of the modified game is a social optimum, i.e. created pairs must form a maximum matching of G. We mainly show that this intriguing problem is NP-hard and propose an approximation algorithm with a constant ratio.
The mfv problem is related to the well known stable marriage problem ( smp ) @cite_11 . In the smp there are @math women and @math men who rank the persons of the opposite sex in a strict order of preference. A solution is a matching of size @math ; it is unstable if two participants prefer being together than being with their respective partner. Interestingly a stable matching always exists and one can compute it with the algorithm of Gale and Shapley @cite_11 . Many variants of the smp were studied in the literature: all participants are of the same gender (the stable roommates problem ) @cite_1 , ties in preferences are allowed @cite_6 , players can give an incomplete list @cite_6 , etc. In fact the mfv problem has some similarities with the stable roommates problem with simplified preferences: every participant gives a list of equivalent interchangeable partners, omitting only those persons he would never accept under any circumstances.
@cite_1 @cite_6 @cite_11
2516943925 2047128428 178770064 1480100487
In the stable roommates (SR) problem we have n agents, where each agent ranks all other agents in strict order of preference. The problem is then to match agents into pairs such that no two agents prefer each other to their matched partners, and this is a stable matching. The stable marriage (SM) problem is a special case of SR, where we have two equal sized sets of agents, men and women, where men rank only women and women rank only men. Every instance of SM admits at least one stable matching, whereas for SR as the number of agents increases the number of instances with stable matchings decreases. So, what will happen if in SM we allow men to rank men and women to rank women, i.e. we relax gender separation? Will stability abruptly disappear? And what happens in a stable roommates scenario if agents do not rank all other agents? Again, is stability uncommon? And finally, what happens if there are an odd number of agents? We present empirical evidence to answer these questions. The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, n men and n women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as O(n log(n)), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, despite the NP-hardness of this problem. We present the first complete algorithm for the SMTI problem, the stable marriage problem with ties and incomplete lists. We do this in the form of a constraint programming encoding of the problem. With this we are able to carry out the first empirical study of the complete solution of SMTI instances. In the stable marriage problem (SM) [5] we have n men and n women. Each man ranks the women, giving himself a preference list. Similarly each woman ranks the men, giving herself a preference list. The problem is then to marry men and women such that they are stable i.e. such that there is no incentive for individuals to divorce and elope. This problem is polynomial time solvable. However, when preference lists contain ties and are incomplete (SMTI) the problem of determining if there is a stable matching of size n is then NP-complete, as is the optimisation problem of finding the largest or smallest stable matching [6, 10]. In this paper we present constraint programming solutions for the SMTI decision and optimisation problems, a problem generator for random instances of SMTI, and an empirical study of this problem. The original stable marriage problem requires all men and women to submit a complete and strictly ordered preference list. This is obviously often unrealistic in practice, and several relaxations have been proposed, including the following two common ones: one is to allow an incomplete list, i.e., a man is permitted to accept only a subset of the women and vice versa. The other is to allow a preference list including ties. Fortunately, it is known that both relaxed problems can still be solved in polynomial time. In this paper, we show that the situation changes substantially if we allow both relaxations (incomplete lists and ties) at the same time: the problem not only becomes NP-hard, but also the optimal cost version has no approximation algorithm achieving the approximation ratio of N1-Ɛ, where N is the instance size, unless P=NP.