Desk-Mates (Stable Matching) with Privacy of Preferences, and a New Distributed CSP Framework.
Marius-Cǎlin Silaghi, Amit Abhyankar, Markus Zanker, Roman Barták · 2005
Abstract. The desk-mates matcher application solves the need of placing students in pairs of two for working in projects (need that is similar to the well known problems of stable matchings or stable roommates). Each of the persons in the previous application has a (hopefully stable) secret preference between every two possible partners. The participants want to find an allocation satisfying their secret preferences and without leaking any of these secret preferences, except for what a participant can infer from the identity of the partner that was recommended to her. The peculiarities of this problem requires solvers based on old distributed CSP frameworks to use models whose search spaces are higher than those in centralized solvers, with bad effects on efficiency. We introduce a distributed weighted constraint satisfaction (DisWCSP) framework where the actual constraints are secrets that are not known by any agent. They are defined by a set of functions on some secret inputs from all agents. The solution is also kept secret and each agent learns just the result of applying an agreed function on the solution. The new framework is shown to improve the efficiency (O(2 m3 −log(m) ) times) in modeling and solving the aforementioned problem with m participants. We show how to extend our previous techniques to solve securely problems modeled with the new formalism, and exemplify with the problem in the title. An applet-based solver is available [Sil04a]. 1