---
title: "Fair Submodular Maximization over a Knapsack Constraint"
authors:
  - "Lijun Li"
  - "Chenyang Xu"
  - "Liuyi Yang"
  - "Ruilong Zhang"
doi: "10.24963/ijcai.2025/438"
url: "https://ijcai.org/proceedings/2025/438"
pdf: "https://ijcai.org/proceedings/2025/0438.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3934-3942"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: GTEP: Computational social choice"
  - "Agent-based and Multi-agent Systems: MAS: Resource allocation"
---

# Fair Submodular Maximization over a Knapsack Constraint

Lijun Li, Chenyang Xu, Liuyi Yang, Ruilong Zhang

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 3934-3942. DOI: [10.24963/ijcai.2025/438](https://doi.org/10.24963/ijcai.2025/438)

## Abstract

We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a cost and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total cost does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint).

While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem -- without relaxing either the knapsack or fairness constraints -- remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of (1-1/e-epsilon) can be obtained in expectation for any epsilon >0.