TY - JOUR AU - Storandt, Sabine AU - Funke, Stefan PY - 2019/07/17 Y2 - 2024/03/28 TI - Algorithms for Average Regret Minimization JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Constraint Satisfaction and Optimization DO - 10.1609/aaai.v33i01.33011600 UR - https://ojs.aaai.org/index.php/AAAI/article/view/3975 SP - 1600-1607 AB - <p>In this paper, we study a problem from the realm of multicriteria decision making in which the goal is to select from a given set <em>S</em> of <em>d</em>-dimensional objects a minimum sized subset <em>S</em><sup>0</sup> with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set <em>S</em> but now can only select their favorite object from the subset <em>S</em><sup>0</sup>. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with <em>d</em> up to 7.</p> ER -