---
title: "Logarithmic Approximations for Fair k-Set Selection"
authors:
  - "Shi Li"
  - "Chenyang Xu"
  - "Ruilong Zhang"
doi: "10.24963/ijcai.2025/439"
url: "https://ijcai.org/proceedings/2025/439"
pdf: "https://ijcai.org/proceedings/2025/0439.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3943-3951"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: CSO: Mixed discrete and continuous optimization"
  - "Agent-based and Multi-agent Systems: MAS: Resource allocation"
  - "Game Theory and Economic Paradigms: GTEP: Computational social choice"
  - "Game Theory and Economic Paradigms: GTEP: Fair division"
---

# Logarithmic Approximations for Fair k-Set Selection

Shi Li, Chenyang Xu, Ruilong Zhang

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

## Abstract

We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i.e., the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G:=(L cup R, E), our problem is equivalent to selecting k vertices from R such that the maximum (weighted) number selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research.

We first prove that the problem is NP-hard even if the maximum degree Delta of the input bipartite graph is 3, and the problem is in P when Delta=2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O(log n/(log log n))-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log(Delta))-approximation on bipartite graphs with a maximum degree Delta. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming.