As a pivotal technique of multi-criteria decision making, the happiness maximization query is used to select a compact subset from a large dataset to meet the requirements of various users. Most existing researches on the happiness maximization query merely concentrate on maximizing overall users’ satisfaction, but overlook the potential dissatisfaction that can be aroused among users. However, this situation likely fails to capture the diverse needs and preferences of different user groups, leading to negative consequences. In this paper, we propose and study the problem of fairness among user groups in the happiness maximization query. By introducing two classical fairness notions, i.e., envy-freeness and proportionality into the problem, we turn to study solutions for the two forms of this problem namely EF1HMQ and MMSHMQ. Then we propose the algorithm framework FairHMQ using two fairness strategies Round-Robin and Envy-Cycle Elimination respectively. Extensive experiments on real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed algorithms.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Balancing Fairness Among User Groups in Happiness Maximization Queries

  • Jie Dong,
  • Chaoyi Jiang,
  • Conghao Liu,
  • Teng Teng

摘要

As a pivotal technique of multi-criteria decision making, the happiness maximization query is used to select a compact subset from a large dataset to meet the requirements of various users. Most existing researches on the happiness maximization query merely concentrate on maximizing overall users’ satisfaction, but overlook the potential dissatisfaction that can be aroused among users. However, this situation likely fails to capture the diverse needs and preferences of different user groups, leading to negative consequences. In this paper, we propose and study the problem of fairness among user groups in the happiness maximization query. By introducing two classical fairness notions, i.e., envy-freeness and proportionality into the problem, we turn to study solutions for the two forms of this problem namely EF1HMQ and MMSHMQ. Then we propose the algorithm framework FairHMQ using two fairness strategies Round-Robin and Envy-Cycle Elimination respectively. Extensive experiments on real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed algorithms.