Author name cluster

Bojana Kodric

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

AAAI Conference 2026 Conference Paper

Greedily Maximizing Ex-Ante Fairness

Ruben Becker
Bojana Kodric
Cosimo Vinci

We study a general framework of optimization with the aim to compute fair solutions in settings with a set of agents whose valuations are combined using an aggregation function. The strength of our framework lies (1) in its generality and (2) in the fact that we leverage the power of ex-ante fairness, a concept that has recently gained much attention in the scope of fair allocation and fairness in AI in general. More precisely, in our setting there are n set functions f₁, …, fₙ (e.g., the valuation functions of n agents) that are combined using an aggregation function g (e.g., the minimum, Nash social welfare, p-norm). The power of ex-ante fairness is obtained by allowing as a feasible solution not simply a finite set S, but instead a distribution Π over feasible sets. The goal in our setting is then to find a probability distribution p in Π that maximizes the value resulting from aggregating (using g) the n expected values of the functions f₁, …, fₙ obtained when sampling a set S according to the distribution p. We stress that this is different from maximizing the expected value of g (ex-post fairness) and typically allows for much fairer solutions. We give three different greedy algorithms for three different settings of this framework and prove that they achieve constant approximation guarantees under certain realistic assumptions. For some of the settings, we show that these approximation guarantees are tight. Specific scenarios that can be modelled using our framework include fair information diffusion in social networks, fair submodular matching problems, and ex-ante versions of item assignment problems.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

$\varepsilon$-fractional core stability in Hedonic Games.

Simone Fioravanti
Michele Flammini
Bojana Kodric
Giovanna Varricchio

Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i. e. a partition of agents into coalitions) satisfies some form of stability. The most well-known and natural of such notions is arguably core-stability. Informally, a partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core-blocking coalition. Unfortunately, core-stable partitions seldom exist and even when they do, it is often computationally intractable to find one. To circumvent these problems, we propose the notion of $\varepsilon$-fractional core-stability, where at most an $\varepsilon$-fraction of all possible coalitions is allowed to core-block. It turns out that such a relaxation may guarantee both existence and polynomial-time computation. Specifically, we design efficient algorithms returning an $\varepsilon$-fractional core-stable partition, with $\varepsilon$ exponentially decreasing in the number of agents, for two fundamental classes of HGs: Simple Fractional and Anonymous. From a probabilistic point of view, being the definition of $\varepsilon$-fractional core equivalent to requiring that uniformly sampled coalitions core-block with probability lower than $\varepsilon$, we further extend the definition to handle more complex sampling distributions. Along this line, when valuations have to be learned from samples in a PAC-learning fashion, we give positive and negative results on which distributions allow the efficient computation of outcomes that are $\varepsilon$-fractional core-stable with arbitrarily high confidence.

PDF Details

AAAI Conference 2023 Conference Paper

PAC Learning and Stabilizing Hedonic Games: Towards a Unifying Approach.

Simone Fioravanti
Michele Flammini
Bojana Kodric
Giovanna Varricchio

We study PAC learnability and PAC stabilizability of Hedonic Games (HGs), i.e., efficiently inferring preferences or core-stable partitions from samples. We first expand the known learnability/stabilizability landscape for some of the most prominent HGs classes, providing results for Friends and Enemies Games, Bottom Responsive, and Anonymous HGs. Then, having a broader view in mind, we attempt to shed light on the structural properties leading to learnability/stabilizability, or lack thereof, for specific HGs classes. Along this path, we focus on the fully expressive Hedonic Coalition Nets representation of HGs. We identify two sets of conditions that lead to efficient learnability, and which encompass all of the known positive learnability results. On the side of stability, we reveal that, while the freedom of choosing an ad hoc adversarial distribution is the most obvious hurdle to achieving PAC stability, it is not the only one. First, we show a distribution independent necessary condition for PAC stability. Then, we focus on W-games, where players have individual preferences over other players and evaluate coalitions based on the least preferred member. We prove that these games are PAC stabilizable under the class of bounded distributions, which assign positive probability mass to all coalitions. Finally, we discuss why such a result is not easily extendable to other HGs classes even in this promising scenario. Namely, we establish a purely computational property necessary for achieving PAC stability.

PDF Details DOI

AIJ Journal 2022 Journal Article

Strategyproof mechanisms for Friends and Enemies Games

Michele Flammini
Bojana Kodric
Giovanna Varricchio

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classifies any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation ( FA ) and Enemies Aversion ( EA ). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies. We focus on the objective of maximizing the sum of the utilities of the agents and provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic n-approximation mechanism, n being the number of agents, and then show that a much better approximation can be achieved by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple ( 1 + 2 ) n -approximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O ( n 1 − ε ) for any fixed ε > 0. We also show that, if computational efficiency is not a concern, it is possible to achieve a ( 1 + 2 ) -approximation by means of a deterministic strategyproof mechanism with exponential runtime. Finally, we show how to extend our results in the presence of neutrals, i. e. , when agents can also be indifferent about other agents.

Details DOI

IJCAI Conference 2021 Conference Paper

Distance Polymatrix Coordination Games

Alessandro Aloisio
Michele Flammini
Bojana Kodric
Cosimo Vinci

In polymatrix coordination games, each player x is a node of a graph and must select an action in her strategy set. Nodes are playing separate bimatrix games with their neighbors in the graph. Namely, the utility of x is given by the preference she has for her action plus, for each neighbor y, a payoff which strictly depends on the mutual actions played by x and y. We propose the new class of distance polymatrix coordination games, properly generalizing polymatrix coordination games, in which the overall utility of player x further depends on the payoffs arising by mutual actions of players v, z that are the endpoints of edges at any distance h<d from x, for a fixed threshold value d≤n. In particular, the overall utility of player x is the sum of all the above payoffs, where each payoff is proportionally discounted by a factor depending on the distance h of the corresponding edge. Under the above framework, which is a natural generalization that is well-suited for capturing positive community interactions, we study the social inefficiency of equilibria resorting to standard measures of Price of Anarchy and Price of Stability. Namely, we provide suitable upper and lower bounds for the aforementioned quantities, both for bounded-degree and general graphs.

PDF Details DOI

JAIR Journal 2021 Journal Article

Strategyproof Mechanisms for Additively Separable and Fractional Hedonic Games

Michele Flammini
Bojana Kodric
Gianpiero Monaco
Qiang Zhang

Additively separable hedonic games and fractional hedonic games have received considerable attention in the literature. They are coalition formation games among selfish agents based on their mutual preferences. Most of the work in the literature characterizes the existence and structure of stable outcomes (i.e., partitions into coalitions) assuming that preferences are given. However, there is little discussion of this assumption. In fact, agents receive different utilities if they belong to different coalitions, and thus it is natural for them to declare their preferences strategically in order to maximize their benefit. In this paper we consider strategyproof mechanisms for additively separable hedonic games and fractional hedonic games, that is, partitioning methods without payments such that utility maximizing agents have no incentive to lie about their true preferences. We focus on social welfare maximization and provide several lower and upper bounds on the performance achievable by strategyproof mechanisms for general and specific additive functions. In most of the cases we provide tight or asymptotically tight results. All our mechanisms are simple and can be run in polynomial time. Moreover, all the lower bounds are unconditional, that is, they do not rely on any computational complexity assumptions.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Strategyproof Mechanisms for Friends and Enemies Games

Michele Flammini
Bojana Kodric
Giovanna Varricchio

We investigate strategyproof mechanisms for Friends and Enemies Games, a subclass of Hedonic Games in which every agent classiﬁes any other one as a friend or as an enemy. In this setting, we consider the two classical scenarios proposed in the literature, called Friends Appreciation (FA) and Enemies Aversion (EA). Roughly speaking, in the former each agent gives priority to the number of friends in her coalition, while in the latter to the number of enemies. We provide strategyproof mechanisms for both settings. More precisely, for FA we ﬁrst present a deterministic napproximation mechanism, and then show that a much better result can be accomplished by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple (1 + √ 2)napproximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O(n1−ε ) for any ﬁxed ε > 0. Finally, we show how to extend our results in the presence of neutrals, i. e. , when agents can also be indifferent about other agents, and we discuss anonymity.

PDF Details

JAAMAS Journal 2020 Journal Article

Two approximation algorithms for probabilistic coalition structure generation with quality bound

Kouki Matsumura
Bojana Kodric
Katsutoshi Hirayama

Abstract How to form effective coalitions is an important issue in multi-agent systems. Coalition Structure Generation ( ${{\mathsf {CSG}}}$ ) is a fundamental problem whose formalization can encompass various applications related to multi-agent cooperation. ${{\mathsf {CSG}}}$ involves partitioning a set of agents into coalitions such that the social surplus (i. e. , the sum of the values of all coalitions) is maximized. In traditional ${\mathsf {CSG}}$, we are guaranteed that all coalitions will be successfully established, that is, the attendance rate of each agent for joining any coalition is assumed to be 1. 0. Having the real world in mind, however, it is natural to consider the uncertainty of agents’ availabilities, e. g. , an agent might be available only two or three days a week because of his/her own schedule. Probabilistic Coalition Structure Generation ( ${{\mathsf {PCSG}}}$ ) is an extension of ${\mathsf {CSG}}$ where the attendance type of each agent is considered. The aim of this problem is to find the optimal coalition structure which maximizes the sum of the expected values of all coalitions. In ${\mathsf {PCSG}}$, since finding the optimal coalition structure easily becomes intractable, it is important to consider approximation algorithms, i. e. , to consider a trade-off between the quality of the returned solution and tractability. In this paper, a formal framework for ${\mathsf {PCSG}}$ is introduced. Approximation algorithms for ${\mathsf {PCSG}}$ called Bounded Approximation Algorithm based on Attendance Types ( ${{\mathsf {BAAAT}}}$ ) and Involved ${\mathsf {BAAAT}}$ ( ${{\mathsf {IBAAAT}}}$ ) are then presented. We prove a priori bounds on the quality of the solution returned by ${\mathsf {BAAAT}}$ and ${\mathsf {IBAAAT}}$ with respect to the optimum and perform experimental evaluations on a number of benchmarks.

Details DOI