Date: Wednesday, May 31, 2023 Time: 9:30–11:00 Location: Weil 401E and over Zoom (Meeting ID 932 4514 0475)
You are cordially invited to attend the 2023 Mini-Workshop on Fair Resource Allocation hosted by the Center for Applied Optimization at the University of Florida. This workshop is intended for early-stage doctoral students to present their progress in research on fair division, computational social choice, mechanism design, or related computational economics topics. It is meant to be highly interactive for students to receive feedback about their work and to facilitate connections across topics.
Abstract: We consider the problem of fairly dividing a set of items among a group of individuals. Each item in the set has a certain number of copies. It is often desirable to find an allocation that is envy-free, meaning that no individual prefers the allocation of another. However, for indivisible items, it is not always possible to find an envy-free allocation. In such cases, we can instead aim for an envy-freeable allocation, where envy can be eliminated by making payments to the individuals involved.
It is known that for the case of goods (i.e., items that are valued positively by every individual) without copies, the maximum payment we need to make to anyone is bounded above by one dollar. Such an allocation is obtained by running an iterative matching procedure. However, in the case of goods with copies, the matching based approach fails to give us the same bound.
We seek to determine the payments that we need to make to any individual in order to eliminate their envy. To this end, we propose an algorithm that evaluates an envy-freeable allocation in polynomial time. Additionally, we aim to investigate whether it is possible to place a bound on the maximum payment made to any individual.