UNIVERSITY PARK, Pa. — When organizations need to divvy up indivisible items among multiple parties with different needs and preferences — such as providing limited COVID-19 vaccines to medical facilities or distributing food bank donations to families with varying dietary restrictions — how can they ensure that everyone gets their fair share?
To ensure fair sharing, a research team at Penn State has proposed two new algorithms to computationally guarantee agreeable allocations of both desirable and undesirable goods, services and tasks.
Both of the team’s algorithms ask participants to follow the ordinal notion of fairness, which simply rank orders which bundles of items the individual perceives as more or less desirable. This approach improves on existing methods of fair division by being more robust and less sensitive to changes or noise in the values placed on the items.
"If you know that you don’t like taking out the garbage, but you don’t know exactly how much you don’t like taking it out, the existing approximations are very sensitive to that; if you make a small adjustment, suddenly the whole solution will change,” said Hadi Hosseini, assistant professor in Penn State’s College of Information Sciences and Technology (IST), who led the team. “This ordinal approximation is not sensitive to that, as long as ordinally you know which chore you dislike more or which good you like more.”
The team’s algorithm for positively valued items, which was published this month in the Journal of Artificial Intelligence, builds on existing frameworks to achieve fairness by assigning a single recipient of items to divide them into separate bundles they feel are of equal value. These items are then distributed after each recipient places a value on a single bundle based on their preferences. The recipient who divided the items is the last to receive a share.
According to Hosseini, however, this approach doesn’t guarantee fairness because they are, in part, too sensitive to small changes in an individual’s preferences. In their new framework, Hosseini’s team guarantees fairness by increasing the number of bundles to be divided by 50%.
“If there are 10 people, for example, the divider would put the goods into 15 bundles. That is something we can satisfy and compute efficiently,” Hosseini explained.
In this approach, each participant would place a value on individual bundles, identifying a minimum threshold for what distribution they’d perceive as fair.
“Our method provides a more robust approximation; it is as if you add dummy individuals and ask participants to divide the items fairly to all recipients’ satisfaction,” he said.
Separately, the researchers proposed a second algorithm for dividing undesirable items or tedious tasks, such as splitting weekly cleaning duties among roommates or managing waste removal within a city. Their work was published in a paper presented at the 2022 International Conference on Autonomous Agents and Multiagent Systems in May.
The researchers again proposed the concept of a participant partitioning tasks or chores into bundles. But this time the number of bundles was reduced, increasing the potential value of each for participants.
“Imagine there are four bundles and there are six people; and one of the bundles has the lowest value for one participant, named Alice,” said Hosseini. “Because this is the lowest value, this gives a threshold for Alice. Now Alice would say ‘if I get anything better than this, I’m happy,’ because we packed more stuff into fewer bundles.”
The team's findings could ultimately impact computer systems that support a variety of goods or resource allocation processes — including distributing food bank donations, enrolling students in college courses, and scheduling surgeons to operating rooms.
“In the real world you can think about how resources at a high level can be distributed to multiple parties in a fair way,” said Hosseini. “It’s a theoretical framework that can be applied to many use cases.”
Hosseini collaborated on both papers with his former graduate student Andrew Searns of Johns Hopkins University Applied Physics Laboratory and Erel Segal-Halevi of Ariel University. The work was supported by the National Science Foundation.