Properties of Preference Matrices in the Context of the Maximum Preference Grouping Problem

The problem of forming groups from among a given set of people or entities arises in numerous settings and situations. In all these cases, there are preferences that exist among the people or entities involved, to work together or be together in the same group. It is beneficial to assign persons to the same group who prefer each other than to someone else, for the overall better outcomes of the work done by the groups. However, this boils down to a balancing act, since trying to satisfy the preferences of members in a group might result in forcing members to be in the same group as others who are much lower in their preference lists. The combinatorial explosion of the solution space makes obtaining the optimal solution intractable. Central to finding solutions to the grouping problem is the preference matrix. This paper presents the properties of the preference matrix leading to interesting implications on the groupings.