Ioannis Caragiannis, Aarhus University

Title: Proportional Fairness in Non-Centroid Clustering

Abstract: We revisit the recently developed framework of proportionally fair clustering, where the goal is to provide group fairness guarantees that become stronger for groups of data points that are large and cohesive. Prior work applies this framework to centroid-based clustering, where points are partitioned into clusters, and the cost to each data point is measured by its distance to a centroid assigned to its cluster. However, real-life applications often do not require such centroids. We extend the theory of proportionally fair clustering to non-centroid clustering by considering a variety of cost functions, both metric and non-metric, for a data point to be placed in a cluster with other data points. Our results indicate that Greedy Capture, a clustering algorithm developed for centroid clustering, continues to provide strong proportional fairness guarantees for non-centroid clustering, although the guarantees are significantly different and establishing them requires novel proof ideas.

Joint work with Evi Micha and Nisarg Shah

Mohamad Latifian, University of Edinburgh

Title: Fair Division with Market Values

Abstract: We introduce a model of fair division with market values, where indivisible goods must be partitioned among agents with (additive) subjective valuations, and each good additionally has a market value. The market valuation can be viewed as a separate additive valuation that holds identically across all the agents. We seek allocations that are simultaneously fair with respect to the subjective valuations and with respect to the market valuation. We show that an allocation that satisfies stochastically-dominant envy-freeness up to one good (SD-EF1) with respect to both the subjective valuations and the market valuation does not always exist, but the weaker guarantee of EF1 with respect to the subjective valuations along with SD-EF1 with respect to the market valuation can be guaranteed. We also study a number of other guarantees such as Pareto optimality, EFX, and MMS. In addition, we explore non-additive valuations and extend our model to cake-cutting. 

This is based on a joint work with Siddharth Barman, Soroush Ebadian, and Nisarg Shah.

Bo Li, Hong Kong Polytechnic University

Title: Fair Allocation of Indivisible Chores: Beyond Additive Valuations

Abstract: Discrete fair division has recently attracted significant attention, driven by its real-world applications and theoretical complexities.  A key difficulty is that the traditional fairness concepts cannot be satisfied. Among the various concepts proposed to address this issue, maximin share (MMS) fairness is one of the most popular and widely accepted. While MMS fairness has been extensively studied and well understood in the context of allocating goods, its application to chores -- especially under non-additive valuations -- remains less explored.

In this work, we first provide a fundamental hardness result: no algorithm can guarantee better than a $\min\left\{n, \frac{\log m}{\log \log m}\right\}$-approximation when agents have binary submodular cost functions, where $m$ is the number of chores and $n$ is the number of agents.  This result shows a sharp contrast with the allocation of goods, where constant approximations exist even for general submodular valuations.  We then prove that for arbitrary subadditive cost functions, there always exists an allocation that is $\min\{n,\lceil\log m\rceil\}$-approximation, and thus the approximation ratio is asymptotically tight.

We then shift our focus to concrete combinatorial settings where the valuations are subadditive. In particular, we consider three well-motivated models: vertex cover, job scheduling, and bin packing. For the vertex cover model, each agent incurs a cost for selecting vertices that cover the edges (viewed as items) assigned to them. For the job scheduling model, each agent manages a set of (unrelated) machines to process the jobs (viewed as items) allocated to them; For the bin packing model, each agent must pack their allocated items into bins, incurring a cost based on the number of bins used. For each model, we design algorithms and prove that constant approximate MMS can be guaranteed. We also provide the (matched) lower bounds on the best-possible approximations.

Joint work with Fangxiao Wang, Shiji Xing and Yu Zhou.

Alkmini Sgouritsa, Athens University of Economics and Business; Archimedes, Athena Research Center

Title: EFX allocations in (Multi)Graphs

Abstract: We study envy-freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We provide constructions of EFX allocations in simple graph settings and in multi-graph settings under minor but essential structural assumptions.