Making Collective Decisions with TCP-nets using Penalty Score-based Heuristic

Abstract. This paper studies the problem of collective decision-making in com-binatorial domain, where the agents ’ preferences are represented by qualitative models with Tradeoffs-enhanced Conditional Preference Networks (TCP-nets). The features of TCP-nets enable us to easily encode human preferences and the relative importance between the decision variables; however, many group decision-making methods require numerical measures of degrees of desirability of alternative outcomes. To permit a natural way for preference elicitation while providing quantitative comparisons between outcomes, we present a computa-tionally efficient approach that compiles individual TCP-nets into ordinal penalty scoring functions. After the individual penalty scores are computed, we further define a collective penalty scoring function to aggregate multiple agents ’ pref-erences. As there are large number of possible outcomes in combinatorial do-main, we address the collective decision-making problem by introducing an effi-cient heuristic algorithm, called HeTCP, to search for an optimal collective deci-sion according to the given aggregation rule. Experiment results are presented to demonstrate the feasibility and efficiency of the proposed approach. Key words: Group decision-making; TCP-nets; Penalty scoring function