Fractional assignment methods ensure fair and strategic object distributions
Fractional Assignment with $\ell_1$ Preferences
Computer Science and Game Theory
Summary
This paper looks at a situation where multiple people want to share items in parts rather than getting just one whole item. Instead of each person wanting only one item, they may want a mix, and the goal is to match these preferences as closely as possible. The authors provide two ways to do this so that everyone feels treated fairly, no one envies others’ shares, and people cannot benefit by lying about their preferences. One method is better at preventing groups from cheating, while the other improves overall fairness among individuals.
What this means in practice
- •For resource allocation engineers: Design algorithms for allocating divisible resources fairly and efficiently based on user preference distributions rather than single-item assignments.
- •For advertising platform developers: Implement fair ad slot auctions that consider fractional interests of advertisers to improve overlap with their ideal ad distribution profiles.$Commercial implications: Enables creation of ad allocation tools that sell more personalized and efficient campaigns by respecting partial interest distributions of advertisers.
Authors
Yasushi Kawase, Warut Suksompong, Hanna Sumita, Yu Yokoi
Abstract
We study a fractional assignment setting where $n$ objects are to be assigned to $n$ agents with unit capacity, and each agent specifies an ideal distribution over the objects. Unlike in classic random assignment, these ideal distributions are not necessarily degenerate, as agents may prefer a mixture of objects rather than any single object. We assume that agents seek to minimize the $\ell_1$ distance between their ideal distribution and the distribution they receive, which is equivalent to maximizing the overlap between the two distributions. We propose two mechanisms, one based on water filling (WF) and the other on quadratic programming (QP), and show that both mechanisms are utilitarian-optimal (and hence Pareto efficient), envy-free, strategyproof, and satisfy equal treatment of equals. Moreover, we highlight a distinct advantage of each mechanism: while the WF mechanism satisfies the stronger property of group-strategyproofness, the QP mechanism is more robust in terms of egalitarian overlap welfare.