Laurent Gourvès

JAIR Journal 2025 Journal Article

Existence, Computation and Efficiency of Nash Stable Outcomes in Hedonic Skill Games

• Laurent Gourvès
• Gianpiero Monaco

This article deals with hedonic skill games, a non-transferable utility counterpart of coalitional skill games which model collaboration among entities through the abstract notions of tasks and the skills required to complete them. In the weighted tasks setting, we show that deciding whether an instance of the game admits a Nash stable outcome is NP-complete. We then characterize the instances admitting a Nash stable outcome. This characterization relies on the fact that every agent holds (resp., every task requires) either a single skill or more than one skill. For these instances, the complexity of computing a Nash stable outcome is determined, together with the possibility that natural dynamics converge to a Nash stable outcome from any initial configuration. Our study is completed with a thorough analysis of the price of anarchy of instances always admitting a Nash stable outcome.

AAAI Conference 2025 Conference Paper

Individually Stable Dynamics in Coalition Formation over Graphs

• Angelo Fanelli
• Laurent Gourvès
• Ayumi Igarashi
• Luca Moscardelli

Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied. We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.

AAMAS Conference 2025 Conference Paper

Minimizing Rosenthal's Potential in Monotone Congestion Games

• Vittorio Bilò
• Angelo Fanelli
• Laurent Gourvès
• Christos Tsoufis
• Cosimo Vinci

Congestion games are attractive because they can model many concrete situations where some competing entities interact through the use of some shared resources, and also because they always admit pure Nash equilibria which correspond to the local minima of a potential function. We explore the problem of computing a state of minimum potential in this setting. Using the maximum number of resources that a player can use at a time, and the possible symmetry in the players’ strategy spaces, we settle the complexity of the problem for instances having monotone (i. e. , either non-decreasing or non-increasing) latency functions on their resources. The picture, delineating polynomial and NP-hard cases, is complemented with tight approximation algorithms.

JAIR Journal 2025 Journal Article

On a Simple Hedonic Game with Graph-Restricted Communication

• Vittorio Bilò
• Laurent Gourvès
• Jérôme Monnot

We study a hedonic game for which feasible coalitions are prescribed by a graph representing the agents’ social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game, everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their efficiency, measured in terms of the price of anarchy and the price of stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is claw-free. Finally, we investigate the complexity of computing socially optimal partitions, as well as extreme Nash stable ones.

JAAMAS Journal 2025 Journal Article

On fair and efficient solutions for budget apportionment

• Pierre Cardi
• Laurent Gourvès
• Julien Lesca

Abstract This article deals with an apportionment problem involving n agents and a common budget B. Each agent submits some demands which are indivisible portions of the budget, and a central authority has to decide which demands to accept. The utility of an agent corresponds to the total amount of her accepted demands. In this context, it is desirable to be fair among the agents and efficient by not wasting the budget. An ideal solution would be to spend exactly B / n for every agent but this is rarely possible because of the indivisibility of the demands. Since combining fairness with efficiency is highly desirable but often impossible, we explore relaxed notions of fairness and efficiency, in order to determine if they go together. Our approach is also constructive because polynomial algorithms that build fair and efficient solutions are also given. The fairness criteria under consideration are the maximization of the minimum agent utility (max–min), proportionality, a customized notion of envy-freeness called jealousy-freeness, and the relaxations up to one or any demand of the previous two concepts. Efficiency in this work is either the maximization of the utilitarian social welfare or Pareto optimality. First we consider fairness and efficiency separately. The existence and computation of solutions that are either fair or efficient are studied. A complete picture of the relations that connect the fairness and efficiency concepts is provided. Second, we determine when fairness and efficiency can be combined for every possible instance. We prove that Pareto optimality is compatible with two notions of fairness, namely max–min and proportionality up to any demand. In contrast, none of the fairness concepts under consideration can be paired with the maximization of utilitarian social welfare. Therefore, we finally conduct a thorough analysis of the price of fairness which bounds the loss of efficiency caused by imposing fairness or one of its relaxations.

AAAI Conference 2025 Conference Paper

On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries

• Dimitris Fotakis
• Laurent Gourvès
• Panagiotis Patsilinakos

We consider committee election of k >= 3 (out of m >= k + 1) candidates, where the voters and the candidates are associated with locations on the real line. Each voter’s cardinal preferences over candidates correspond to her distance to the candidate locations, and each voter’s cardinal preferences over committees is defined as her distance to the nearest candidate elected in the committee. We consider a setting where the true distances and the locations are unknown. We can nevertheless have access to degraded information which consists of an order of candidates for each voter. We investigate the best possible distortion (a worst-case performance criterion) w.r.t. the social cost achieved by deterministic committee election rules based on ordinal preferences submitted by n voters and few additional distance queries. We show that for any k >= 3, the best possible distortion of any deterministic rule that uses at most k−3 distance queries cannot be bounded by any function of n, m and k. We present deterministic rules for k-committee election with distortion of O(n) with O(k) distance queries and O(1) with O(k log(n)) distance queries.

AAMAS Conference 2025 Conference Paper

Satisfactory Budget Division

• Laurent Gourvès
• Michael Lampis
• Nikolaos Melissinos
• Aris Pagourtzis

A divisible budget must be allocated to several projects, and agents are asked for their opinion on how much they would give to each project. We consider that an agent is satisfied by a division of the budget if, for at least a certain predefined number τ of projects, the part of the budget actually allocated to each project is at least as large as the amount the agent requested. The objective is to find a budget division that “best satisfies” the agents. In this context, different problems can be stated and we address the following ones. We study (i) the largest proportion of agents that can be satisfied for any instance, (ii) classes of instances admitting a budget division that satisfies all agents, (iii) the complexity of deciding if, for a given instance, every agent can be satisfied, and finally (iv) the question of finding, for a given instance, the smallest total budget to satisfy all agents. We provide answers to these complementary questions for several natural values of the parameter τ, capturing scenarios where we seek to satisfy for each agent all; almost all; half; or at least one of her requests.

AAMAS Conference 2025 Conference Paper

Social Ranking for Feature Selection

• Laurent Gourvès
• Stefano Moretti
• Satya Tamby

In this paper, we focus on limitations in the use of the Shapley value within the field of eXplainable AI (XAI) through the lens of the axiomatic analysis and its implications in the realm of machine learning. As an alternative to the Shapley value, we analyse the properties of the lex-cel, a social ranking solution introduced in the recent literature at the intersection between coalitional games and social choice theory, showing that axioms characterizing the lex-cel, under certain circumstances, are more suitable for ranking features in machine learning models, compared to those satisfied by the Shapley value. Via experiments conducted on public datasets, we also show that the lex-cel outperforms a commonly employed feature selection algorithm based on the Shapley value, in particular with respect to the capacity of selecting less redundant features.

TCS Journal 2025 Journal Article

Worst-case fair guarantees when spending a common budget

• Pierre Cardi
• Laurent Gourvès
• Julien Lesca

We study the problem of fairly spending a budget that is common to n agents. Agents submit demands to a central planner who uses the budget to fund a subset of them. The utility of an agent is the part of the budget spent on her own accepted demands. In a fair solution, the successful demands of each agent would represent a 1 / n fraction of the budget. However, this is rarely possible because every demand is indivisible, i. e. , either accepted in its entirety or rejected. We are interested in worst-case bounds on the largest proportion of the budget that is dedicated to the least funded agent. Our approach is not to solve the corresponding max-min problem for every instance, but to tackle the problem from a higher level. The size of the largest demand compared to the budget and the number of agents, are two parameters that significantly influence how much the worst-off agent gets. We propose explicit worst-case bounds on the best utility of the least funded agent for the class of instances where the number of agents and the most expensive demand are fixed to given values. A characterization of this quantity is provided for 1 and 2 agents. For more than 2 agents, we propose lower and upper bounds that constitute a 14 15 -approximation of the optimal value. Every existence result is complemented with a polynomial time algorithm that builds a feasible solution satisfying our bounds.

TCS Journal 2024 Journal Article

Filling crosswords is very hard

• Laurent Gourvès
• Ararat Harutyunyan
• Michael Lampis
• Nikolaos Melissinos

We revisit a classical crossword filling puzzle which already appeared in Garey& Jonhson's book. We are given a grid with n vertical and horizontal slots and a dictionary with m words. We are asked to place words from the dictionary in the slots so that shared cells are consistent. We attempt to pinpoint the source of intractability of this problem by carefully taking into account the structure of the grid graph, which contains a vertex for each slot and an edge if two slots intersect. Our main approach is to consider the case where this graph has a tree-like structure. Unfortunately, if we impose the common rule that words cannot be reused, we discover that the problem remains NP-hard under very severe structural restrictions, namely, if the grid graph is a union of stars and the alphabet has size 2, or the grid graph is a matching (so the crossword is a collection of disjoint crosses) and the alphabet has size 3. The problem does become slightly more tractable if word reuse is allowed, as we obtain an m tw algorithm in this case, where tw is the treewidth of the grid graph. However, even in this case, we show that our algorithm cannot be improved to obtain fixed-parameter tractability. More strongly, we show that under the ETH the problem cannot be solved in time m o ( k ), where k is the number of horizontal slots of the instance (which trivially bounds tw). Motivated by these mostly negative results, we also consider the much more restricted case where the problem is parameterized by the number of slots n. Here, we show that the problem does become FPT (if the alphabet has constant size), but the parameter dependence is exponential in n 2. We show that this dependence is also justified: the existence of an algorithm with running time 2 o ( n 2 ), even for binary alphabet, would contradict the randomized ETH. After that, we consider an optimization version of the problem, where we seek to place as many words on the grid as possible. Here it is easy to obtain a 1 2 -approximation, even on weighted instances, simply by considering only horizontal or only vertical slots. We show that this trivial algorithm is also likely to be optimal, as obtaining a better approximation ratio in polynomial time would contradict the Unique Games Conjecture. The latter two results apply whether word reuse is allowed or not. Finally, we present some special cases where the problem is decidable in polynomial time. In particular, we present three reductions, one to 2-SAT, the second to Maximum Matching and the third to Exact Matching.

AAMAS Conference 2023 Conference Paper

On the Distortion of Single Winner Elections with Aligned Candidates

• Dimitris Fotakis
• Laurent Gourvès

We study the problem of selecting a single element from a set of candidates on which a group of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.

TCS Journal 2023 Journal Article

Project games

• Vittorio Bilò
• Laurent Gourvès
• Jérôme Monnot

We consider a strategic game, called project game, where each agent has to choose a project among her own list of available projects. The model includes positive weights expressing the capacity of a given agent to contribute to a given project. The realization of a project produces some reward that has to be allocated to the agents. The reward of a realized project is fully allocated to its contributors according to a simple proportional rule. Existence and computational complexity of pure Nash equilibria is addressed and their efficiency is investigated according to both the utilitarian and the egalitarian social function.

TCS Journal 2022 Journal Article

In memory of Jérôme Monnot

• Bruno Escoffier
• Laurent Gourvès
• Vangelis Paschos

JAAMAS Journal 2022 Journal Article

On the distortion of single winner elections with aligned candidates

• Dimitris Fotakis
• Laurent Gourvès

Abstract We study the problem of selecting a single element from a set of candidates on which a group of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.

AAMAS Conference 2021 Conference Paper

Worst-case Bounds for Spending a Common Budget

• Pierre Cardi
• Laurent Gourvès
• Julien Lesca

We study the problem of spending a budget that is common to 𝑛 agents. Agents submit demands to a central planner who uses the budget to fund a subset of them. The utility of an agent is the part of the budget spent on her own accepted demands. In a fair solution, the successful demands of each agent would represent a 1/𝑛 fraction of the budget. However, this is rarely possible because every demand is indivisible, i. e. either accepted in its entirety or rejected. We are interested in worst-case bounds on the largest proportion of the budget that is dedicated to the least funded agent. Our approach is not to solve the corresponding max min problem for every instance, but to tackle the problem from a higher level. The size of the largest demand compared to the budget and the number of agents, are two parameters that significantly influence how much the worst-off agent gets. We propose worst-case bounds on the best utility of the least funded agent for the class of instances where the number of agents and the most expensive demand are fixed to given values. A characterization of this quantity is provided for 1 and 2 agents. For more than 2 agents, we propose lower and upper bounds that constitute a 14 15 -approximation of the optimal value. Every existence result is complemented with a polynomial algorithm that builds a feasible solution satisfying our bounds.

ECAI Conference 2020 Conference Paper

Object Allocation and Positive Graph Externalities

• Dimitris Fotakis 0001
• Laurent Gourvès
• Stelios Kasouridis
• Aris Pagourtzis

The worth of an entity does not only come from its intrinsic value. The other entities in the neighborhood also influence this quantity. We introduce and study a model where some heterogeneous objects have to be placed on a network so that the elements with high value may exert a positive externality on neighboring elements whose value is lower. We aim at maximizing this positive influence called graph externality. By exploiting a connection with the minimum dominating set problem, we prove that the problem is NP-hard when the maximum degree is 3, but polynomial time solvable when the maximum degree is 2. We also present exact and approximation algorithms for special cases. In particular, if only two valuations exist, then a natural greedy strategy, which works well for maximum coverage problems, leads to a constant approximation algorithm. With extensive numerical experiments we finally show that a greedy algorithm performs very well for general valuations.

TCS Journal 2019 Journal Article

On maximin share allocations in matroids

• Laurent Gourvès
• Jérôme Monnot

The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a ( 1 − ε ) -approximation for two agents, and a ( 8 / 9 − ε ) -approximation for three agents. Apart from the extension to matroids, the ( 8 / 9 − ε ) -approximation for three agents improves on a ( 7 / 8 − ε ) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed.

IJCAI Conference 2019 Conference Paper

On the Problem of Assigning PhD Grants

• Katarína Cechlárová
• Laurent Gourvès
• Julien Lesca

In this paper, we study the problem of assigning PhD grants. Master students apply for PhD grants on different topics and the number of available grants is limited. In this problem, students have preferences over topics they applied to and the university has preferences over possible matchings of student/topic that satisfy the limited number of grants. The particularity of this framework is the uncertainty on a student's decision to accept or reject a topic offered to him. Without using probability to model uncertainty, we study the possibility of designing protocols of exchanges between the students and the university in order to construct a matching which is as close as possible to the optimal one i. e. , the best achievable matching without uncertainty.

TCS Journal 2017 Journal Article

Bi-objective matchings with the triangle inequality

• Laurent Gourvès
• Jérôme Monnot
• Fanny Pascual
• Daniel Vanderpooten

This article deals with a bi-objective matching problem. The input is a complete graph and two values on each edge (a weight and a length) which satisfy the triangle inequality. It is unlikely that every instance admits a matching with maximum weight and maximum length at the same time. Therefore, we look for a compromise solution, i. e. a matching that simultaneously approximates the best weight and the best length. For which approximation ratio ρ can we guarantee that any instance admits a ρ-approximate matching? We propose a general method which relies on the existence of an approximate matching in any graph of small size. An algorithm for computing a 1/3-approximate matching in any instance is provided. The algorithm uses an analytical result stating that every instance on at most 6 nodes must admit a 1/2-approximate matching. We extend our analysis with a computer-aided approach for larger graphs, indicating that the general method may produce a 2/5-approximate matching. We conjecture that a 1/2-approximate matching exists in any bi-objective instance satisfying the triangle inequality.

IJCAI Conference 2017 Conference Paper

Object Allocation via Swaps along a Social Network

• Laurent Gourvès
• Julien Lesca
• Anaëlle Wilczynski

This article deals with object allocation where each agent receives a single item. Starting from an initial endowment, the agents can be better off by exchanging their objects. However, not all trades are likely because some participants are unable to communicate. By considering that the agents are embedded in a social network, we propose to study the allocations emerging from a sequence of simple swaps between pairs of neighbors in the network. This model raises natural questions regarding (i) the reachability of a given assignment, (ii) the ability of an agent to obtain a given object, and (iii) the search of Pareto-efficient allocations. We investigate the complexity of these problems by providing, according to the structure of the social network, polynomial and NP-complete cases.

ECAI Conference 2016 Conference Paper

Strategic Voting in a Social Context: Considerate Equilibria

• Laurent Gourvès
• Julien Lesca
• Anaëlle Wilczynski

In a voting system, voters may adopt a strategic behaviour in order to manipulate the outcome of the election. This naturally entails a game theoretic conception of voting. The specificity of our work is that we embed the voting game into a social context where agents and their relations are given by a graph, i. e. a social network. We aim at integrating the information provided by the graph in a refinement of the game-theotical analysis of an election. We consider coalitional equilibria immune to deviations performed by realistic coalitions based on the social network, namely the cliques of the graph. Agents are not fully selfish as they have consideration for their relatives. The corresponding notion of equilibrium was introduced by Hoefer et al. [12] and called considerate equilibrium. We propose to study its existence and the ability of the agents to converge to such an equilibrium in strategic voting games using well-known voting rules: Plurality, Antiplurality, Plurality with runoff, Borda, k-approval, STV, Maximin and Copeland.

TCS Journal 2015 Journal Article

The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles

• Luerbio Faria
• Laurent Gourvès
• Carlos A. Martinhon
• Jérôme Monnot

We introduce a number of problems regarding edge-color modifications in edge-colored graphs and digraphs. Consider a property π, a c-edge-colored graph G c not satisfying π, and an edge-recoloring cost matrix R = [ r i j ] c × c where r i j ≥ 0 denotes the cost of changing color i of edge e to color j. Basically, in this kind of problem the idea is to change the colors of one or more edges of G c in order to construct a new edge-colored graph such that the total edge-recoloring cost is minimized and property π is satisfied. We also consider the destruction of potentially undesirable structures with the minimum edge-recoloring cost. In this paper, we are especially concerned with the construction and destruction of properly edge-colored and monochromatic paths, trails and cycles in graphs and digraphs. Some related problems and future directions are presented.

TCS Journal 2015 Journal Article

Worst case compromises in matroids with applications to the allocation of indivisible goods

• Laurent Gourvès
• Jérôme Monnot
• Lydia Tlilane

We consider the problem of equitably allocating a set of indivisible goods to n agents with additive utilities so as to provide worst case guarantees on agents' utilities. Demko and Hill [6] showed the existence of an allocation where every agent values his share at least V n ( α ), which is a family of nonincreasing functions of α, defined as the maximum value assigned by an agent to a single good. A deterministic algorithm returning such an allocation in polynomial time was proposed in [15]. Interestingly, V n ( α ) is tight for some values of α, i. e. it matches the highest possible utility of the least happy agent. However, this is not true for all values of α. We propose a family of functions W n such that W n ( x ) ≥ V n ( x ) for all x, and W n ( x ) > V n ( x ) for values of x where V n ( x ) is not tight. The functions W n apply on a problem that generalizes the allocation of indivisible goods. It is to find a base in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas. We also present an upper bound on the utility of the least happy agent.

ECAI Conference 2014 Conference Paper

Near Fairness in Matroids

• Laurent Gourvès
• Jérôme Monnot
• Lydia Tlilane

This article deals with the fair allocation of indivisible goods and its generalization to matroids. The notions of fairness under consideration are equitability, proportionality and envy-freeness. It is long known that some instances fail to admit a fair allocation. However, an almost fair solution may exist if an appropriate relaxation of the fairness condition is adopted. This article deals with a matroid problem which comprises the allocation of indivisible goods as a special case. It is to find a base of a matroid and to allocate it to a pool of agents. We first adapt the aforementioned fairness concepts to matroids. Next we propose a relaxed notion of fairness said to be near to fairness. Near fairness respects the fairness up to one element. We show that a nearly fair solution always exists and it can be constructed in polynomial time in the general context of matroids.

IJCAI Conference 2013 Conference Paper

A Matroid Approach to the Worst Case Allocation of Indivisible Goods

• Laurent Gourvès
• Jérôme Monnot
• Lydia Tlilane

We consider the problem of equitably allocating a set of indivisible goods to n agents so as to maximize the utility of the least happy agent. [Demko and Hill, 1988] showed the existence of an allocation where every agent values his share at least Vn(α), which is a family of nonincreasing functions in a parameter α, defined as the maximum value assigned by an agent to a single good. A deterministic algorithm returning such an allocation in polynomial time was proposed [Markakis and Psomas, 2011]. Interestingly, Vn(α) is tight for some values of α, i. e. it is the best lower bound on the valuation of the least happy agent. However, it is not true for all values of α. We propose a family of functions Wn such that Wn(x) ≥ Vn(x) for all x, and Wn(x) > Vn(x) for values of x where Vn(x) is not tight. The new functions Wn apply on a problem which generalizes the allocation of indivisible goods. It is to find a solution (base) in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas.

TCS Journal 2013 Journal Article

Single approximation for the biobjective Max TSP

• Cristina Bazgan
• Laurent Gourvès
• Jérôme Monnot
• Fanny Pascual

We mainly study the Max TSP with two objective functions. We propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analyzed in three cases. When both (respectively, at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is 5 12 − ε ≈ 0. 41 (respectively, 3 8 − ε ). When the triangle inequality is not assumed on any objective function, the algorithm is 1 + 2 2 14 − ε ≈ 0. 27 -approximate.

ECAI Conference 2012 Conference Paper

Approximate Tradeoffs on Matroids

• Laurent Gourvès
• Jérôme Monnot
• Lydia Tlilane

We consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents an agent's utility. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then, a natural aim is to find tradeoffs. We investigate tradeoff solutions with guarantees for the agents. The focus is on discrete problems having a matroid structure. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.

JAAMAS Journal 2012 Journal Article

Fair solutions for some multiagent optimization problems

• Bruno Escoffier
• Laurent Gourvès
• Jérôme Monnot

Abstract We consider optimization problems in a multiagent setting where a solution is evaluated with a vector. Each coordinate of this vector represents an agent’s utility for the solution. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for all agents. Then, a natural aim is to find solutions that maximize the satisfaction of the least satisfied agent, where the satisfaction of an agent is defined as his relative utility, i. e. , the ratio between his utility for the given solution and his maximum possible utility. This criterion captures a classical notion of fairness since it focuses on the agent with lowest relative utility. We study worst-case bounds on this ratio: for which ratio a feasible solution is guaranteed to exist, i. e. , to what extend can we find a solution that satisfies all agents? How can we build these solutions in polynomial time? For several optimization problems, we give polynomial-time deterministic algorithms which (almost always) achieve the best possible ratio.

TCS Journal 2009 Journal Article

On the minimum hitting set of bundles problem

• Eric Angel
• Evripidis Bampis
• Laurent Gourvès

We consider a natural generalization of the classical minimum hitting set problem, the minimum hitting set of bundles problem (mhsb) which is defined as follows. We are given a set E = { e 1, e 2, …, e n } of n elements. Each element e i ( i = 1, …, n ) has a positive cost c i. A bundle b is a subset of E. We are also given a collection S = { S 1, S 2, …, S m } of m sets of bundles. More precisely, each set S j ( j = 1, …, m ) is composed of g ( j ) distinct bundles b j 1, b j 2, …, b j g ( j ). A solution to mhsb is a subset E ′ ⊆ E such that for every S j ∈ S at least one bundle is covered, i. e. b j l ⊆ E ′ for some l ∈ { 1, 2, …, g ( j ) }. The total cost of the solution, denoted by C ( E ′ ), is ∑ { i ∣ e i ∈ E ′ } c i. The goal is to find a solution with a minimum total cost. We give a deterministic N ( 1 − ( 1 − 1 N ) M ) -approximation algorithm, where N is the maximum number of bundles per set and M is the maximum number of sets in which an element can appear. This is roughly speaking the best approximation ratio that we can obtain, since by reducing mhsb to the vertex cover problem, it implies that mhsb cannot be approximated within 1. 36 when N = 2 and N − 1 − ϵ when N ≥ 3. It has to be noticed that the application of our algorithm in the case of the min k -sat problem matches the best known approximation ratio.

TCS Journal 2004 Journal Article

Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem

• Eric Angel
• Evripidis Bampis
• Laurent Gourvès

Local search has been widely used in combinatorial optimization (Local Search in Combinatorial Optimization, Wiley, New York, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate “good” solutions with performance guarantee. In this paper, we introduce such an approach for the classical traveling salesman problem (TSP) problem (Proc. STOC’00, 2000, pp. 126–133). We show that it is possible to get in linear time, a 3 2 -approximate Pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria TSP(1, 2) problem where every edge is associated to a couple of distances which are either 1 or 2 (Math. Oper. Res. 18 (1) (1993) 1).