Approximate Core for Committee Selection via Multilinear Extension and Market Clearing
Motivated by civic problems such as participatory budgeting and multiwinner elections, we consider the problem of public good allocation: Given a set of indivisible projects (or candidates) of different sizes, and voters with different monotone utility functions over subsets of these candidates, the goal is to choose a budget- constrained subset of these candidates (or a committee) that provides fair utility to the voters. The notion of fairness we adopt is that of core stability from cooperative game theory: No subset of voters should be able to choose another blocking committee of proportionally smaller size that provides strictly larger utility to all voters that deviate. The core provides a strong notion of fairness, subsuming other notions that have been widely studied in computational social choice. It is well-known that an exact core need not exist even when utility functions of the voters are additive across candidates. We therefore relax the problem to allow approximation: Voters can only deviate to the blocking committee if after they choose any extra candidate (called an additament), their utility still increases by an factor. If no blocking committee exists under this definition, we call this an fi-core. Our main result is that an -core, for < 67:37, always exists when utilities of the voters are arbitrary monotone submodular functions, and this can be computed in polynomial time. This result improves to < 9:27 for additive utilities, albeit without the polynomial time guarantee. Our results are a signifficant improvement over prior work that only shows logarithmic approximations for the case of additive utilities. We complement our results with a lower bound of > 1:015 for submodular utilities, and a lower bound of any function in the number of voters and candidates for general monotone utilities.