Agenda

Speaker: Cosimo Vinci, Università del Salento

Abstract:
Fair allocation of resources has been extensively studied in the past.
In a common setting, we have $n$ agents and m items, and each agent has an individual valuation for each of the items.
One of the basic results in this field states that the set of items can be partitioned among agents in such a way that the resulting allocation is envy-free-up-to-one-good (EF1), that is to say, any agent is not envious of anyone else's bundle after removing at most one item from it.
However, in many situations agents may have more than one valuation - for example when the items have a well defined monetary value aside of a personal value of each agent.

To deal with this and other general scenarios, in this paper we introduce and study a novel {\em multi-criteria fair allocation} framework: a generalization of standard fair allocation settings where each agent can have multiple (say r>=1) individual valuations/criteria for each item.
The goal is to find an allocation that, for an integer k>=1 which is as small as possible, is multi-criteria-envy-free-up-to-k-items (MEF-k): for any agent i and any valuation of i, such agent is not envious of anyone else's bundle after removing at most k items from it, according to the considered valuation.

We present initial encouraging results for valuations that are non-negative, monotone and additive: (i) MEF-k allocations, with k=O(nr^2), can be computed in polynomial time; (ii) for the restricted case of two valuations per-agent, with one valuation that is common, we can compute in polynomial time a MEF-1 allocation; (iii) MEF-1 allocations can be also guaranteed for the case of two agents with two binary valuations each one. We also obtained some results for a relaxation of MEF-k, called multi-criteria-proportionality-up-to-k-items (MPROP-k), that generalizes to multiple criteria the standard notion of approximate proportionality. Last but not least, we also provide some impossibility results, holding even for two agents with binary common valuations. This is done by establishing a connection to the Discrepancy theory, that has been extensively studied by diverse mathematics, optimization and computer science methods.

Bio Sketch:
Cosimo Vinci is an Assistant Professor of Computer Science at the University of Salento. Previously he has been Assistant Professor at the University of Salerno, postdoc at the Gran Sasso Science Institute, as well as at the University of L'Aquila. Cosimo holds a PhD in Computer Science from the Gran Sasso Science Institute. His research activity covers a diverse set of topics in Theoretical Computer Science and Mathematics, most particularly in Algorithmics. Specific areas of interest include Algorithmic Game Theory, Approximation/Online/Randomized Algorithms, Stochastic Optimization, and Combinatorial Optimization. Cosimo has received both the "Best Italian PhD Thesis in Theoretical Computer Science" (2019) and the "Best Italian Young Researcher in Theoretical Computer Science" (2023) award from the Italian Chapter of the European Association of Theoretical Computer Science.