SocialCOP: Reusable Building Blocks for Collective Constraint Optimization

Distributing limited resources among a group of agents is a fundamental challenge in both algorithmic decision support systems and everyday life. The goal of achieving a socially desirable allocation of these resources instead of mere economic efficiency is relevant to many types of allocation problems under hard constraints. At the same time, modeling languages and high-level libraries for combinatorial optimization problems are becoming more widespread. Although fairness is an important key factor in optimization processes, there is currently no way to use fairness constraints and objectives – unless they are written from scratch. Thus, combining and experimenting with different fairness criteria is tedious as no predefined set of constraints and objectives is available in modeling languages. We propose SocialCOP, a toolbox of reusable constraint modeling building blocks of concepts derived from social choice theory, fair division, and algorithmic fairness (namely, Envy-freeness, Leximin, Rawlsianism, Utilitarianism, Pareto). Our toolbox provides a convenient and reusable solution for adding fairness constraints to existing collective constraint optimization problems formulated in MiniZinc. Our created building blocks can be combined or added individually to the existing satisfaction problem. Experimental results show that a much richer combination of fairness objectives can be modeled, leading to the discovery of solutions that are optimal in more than one way.