Most optimization algorithms aim to allocate limited resources among a set of agents. If human stakeholders are benefitting or suffering from this allocation, it is required to add a social perspective to the goal of efficient optimized allocation. SocialCOP introduces a library to integrate social choice concepts to a variety of existing MiniZinc optimization problems.
Table of Contents
Many real-world combinatorial optimization problems dealing with the sharing of constrained resources involve multiple objectives belonging to their respective stakeholders. Examples thereof include shared mobility (carpooling, organizing collective trips, choosing which sites to visit and in what order), hoteling systems for shared office space (allocating desks to employees, respecting WFH restrictions or making joint reservations), shared manufacturing, or managing the charging of electric vehicles (EVs) in a shared parking lot. We call them collective combinatorial optimization problems. Aggregating stakeholders’ goals in a socially desirable way (e.g., fairness, proportional access, respect for democratic majority) while balancing this with other overarching goals is challenging. We therefore introduce a reusable library of constraints (e.g., envy-freeness or utilitarianism) and search procedures derived from social choice and fair division theory for a generic modeling language such as e.g. MiniZinc.
Please follow this guideline to install SocialCOP and use the different social choice concept in your existing MiniZinc problem.
Please install MiniZinc-python with the DZN flag activated
-
MiniZinc
pip install minizinc[dzn]
- Clone the repo
git clone https://github.com/AImotion-Bavaria/SocialCOP.git
To connect your MiniZinc problem to the social choice building blocks, a social mapping file is required. It can be expressed using a JSON file. This file is required to map the fixed concepts to the respective names in your model formulation at hand. Required hooks like the array of agents taking part in the distribution, an array of utility decision variables, as well as the names of share functions and share utilities can therefore be named according to the underlying problem and do not need to be the same for all models.
Example:
"agents_array" : "Agents",
"utility_array" : "utilities",
"num_agents" : "n_agents",
"main_variables": ["assigned"]
}
Envy-Freeness is given if no agent envies the distribution of another agent. To integrate it into your existing MiniZinc model, you can use the following code.
if not SHARE_FUNCTION in social_mapping: # it is not a division problem
return None
simple_runner = prepare_envy_free_runner(social_mapping)
simple_runner.timeout = TIME_LIMIT_EVAL
result = simple_runner.run(model, solver)
return result
Rawls runner is searching for the best result for the worst-off agent. To integrate it into your existing MiniZinc model, you can use the following code.
simple_runner = prepare_rawls_runner(social_mapping)
simple_runner.timeout = TIME_LIMIT_EVAL
result = simple_runner.run(model, solver)
return result
The Nash welfare is searching for the highest product of utilities. To integrate it into your existing MiniZinc model, you can use the following code.
simple_runner = prepare_nash_runner(social_mapping)
simple_runner.timeout = TIME_LIMIT_EVAL
result = simple_runner.run(model, solver)
return result
This runner is iteratively searching for rawls solution for all agents. The worst-off agent is maximized, followed by the second-worst agent in the next iteration. This is continued until all utilities for agents are optimized. To integrate it into your existing MiniZinc model, you can use the following code.
simple_runner = prepare_leximin_runner(social_mapping)
simple_runner.debug = True
simple_runner.debug_dir = create_debug_folder(os.path.dirname(__file__))
simple_runner.timeout = TIME_LIMIT_EVAL
result = simple_runner.run(model, solver)
return result
Utilitarianism is searching for the result with the maximum overall utility. To integrate it into your existing MiniZinc model, you can use the following code.
simple_runner = prepare_utilitarian_runner(social_mapping)
if SHARE_FUNCTION in social_mapping: # it is a division problem - I want to record envy counts as well
simple_runner.add(envy_freeness_mixin)
simple_runner.timeout = TIME_LIMIT_EVAL
result = simple_runner.run(model, solver)
return result
If you want to combine different social choice concepts e.g. Utilitarianism and Envy-Freeness you can implement it as follows:
if not SHARE_FUNCTION in social_mapping: # it is not a division problem
return None
simple_runner : SimpleRunner = prepare_utilitarian_runner(social_mapping)
simple_runner.model += [envy_freeness_mixin, enforce_envy_freeness]
simple_runner.timeout = TIME_LIMIT_EVAL
result = simple_runner.run(model, solver)
return result
See the open issues for a full list of proposed features (and known issues).
Alexander Schiendorfer - Alexander.Schiendorfer@thi.de
Julia Ruttmann - jur9766@thi.de
Project Link: https://github.com/AImotion-Bavaria/SocialCOP