Predict compatibility of 2 people as boolean classification problem
Your approach to modeling compatibility seems sound, and definitely makes more sense than market basket analysis. From what I could gather, your goal is to predict compatibility, and you have access to a certain signal that you can use as your compatibility label for the training set (for example, you know for a fact that persons X and Y are compatible but Y and Z are not). In these circumstances, supervised learning definitely sounds appropriate.

Based on the example you gave, there are a few things about this problem that you may consider (if you haven't already):


Should the features (e.g. compassion, extroversion, humor) be binary, or on a continuous spectrum? This depends on your data, of course, but perhaps you may get a better measure of compatibility if you can get the finer grain of detail that continuous features provide.
Same for the class: is it exclusively binary (classification) or could this be treated as a regression problem (predict the degree of compatibility)? Even if treating it as classification, certain models output class posterior probabilities, which could be interpreted as degrees of compatibility.
Compatibility is most likely a symmetrical relationship: if a is compatible with b, then b is compatible with a. If your dataset is formed of the two individuals' data concatenated, should you create two examples per pair (one in each order)? Is there another way to enforce symmetry in your model? Also, can the signal you use for your compatibility label really be interpreted in this symmetrical sense, or does it only tell you that, for instance person A likes person B, but not necessarily the other way around.
How will you evaluate your model? If compatibility is more continuous than discrete, for example, then perhaps recall, precision and accuracy aren't the best metrics, and you may want to use something like RMSE?