Algorithms for Average Regret Minimization

Type of Publication: Contribution to a conference collection
Publication status: Published
Author: Storandt, Sabine; Funke, Stefan
Year of publication: 2019
Conference: The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), Jan 27, 2019 - Feb 1, 2019, Honolulu
Published in: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. - Palo Alto : AAAI Press, 2019. - pp. 1600-1607. - ISSN 2159-5399. - eISSN 2374-3468. - ISBN 978-1-57735-809-1
Summary:
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 S of d-dimensional objects a minimum sized subset S0 with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S0. 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 d up to 7.
Subject (DDC): 004 Computer Science
Bibliography of Konstanz: Yes

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

STORANDT, Sabine, Stefan FUNKE, 2019. Algorithms for Average Regret Minimization. The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19). Honolulu, Jan 27, 2019 - Feb 1, 2019. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Palo Alto:AAAI Press, pp. 1600-1607. ISSN 2159-5399. eISSN 2374-3468. ISBN 978-1-57735-809-1

@inproceedings{Storandt2019Algor-46796, title={Algorithms for Average Regret Minimization}, year={2019}, isbn={978-1-57735-809-1}, issn={2159-5399}, address={Palo Alto}, publisher={AAAI Press}, booktitle={Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence}, pages={1600--1607}, author={Storandt, Sabine and Funke, Stefan} }

Storandt, Sabine 2019-09-05T10:51:51Z 2019 Funke, Stefan Storandt, Sabine 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 S of d-dimensional objects a minimum sized subset S<sup>0</sup> with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S<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 d up to 7. Algorithms for Average Regret Minimization eng Funke, Stefan 2019-09-05T10:51:51Z

This item appears in the following Collection(s)

Search KOPS


Browse

My Account