Abstract Realistic objects are not only described by their own attributes, but also described by their mutual relationships in a specific domain. By mainly considering the mutual associations among the given objects, in this paper we propose a method for multi-objective categorization based on the game theory and Markov process. We adopt Shapley value in coalitional games to measure the player’s satisfaction degree in a group. We then give the concept of priority groups and an algorithm to combine small-size priority groups to large-size ones, and thus the efficiency of calculating the players’ satisfaction degree can be improved. We further define a improving-replay Markov process to model the process of forming a reasonable payoff configuration. Accordingly, we give a simulation algorithm to obtain the desired payoff configuration to categorize players into groups by their satisfaction degrees. Finally, we give experimental results and performance studies to verify the efficiency and effectiveness of our methods.