Hugo Gilbert

IJCAI Conference 2025 Conference Paper

Constrained Serial Dictatorships Can Be Fair

• Sylvain Bouveret
• Hugo Gilbert
• Jérôme Lang
• Guillaume Méroué

When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). Agents who come earlier in the sequence have a larger choice of items; however, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model. We conclude with experimental results showing how the optimal sequence is impacted by various parameters.

ECAI Conference 2024 Conference Paper

Learning and Optimizing with an SSB Representation of Intransitive Preferences on Sets

• Hugo Gilbert
• Mohamed Ouaguenouni
• Olivier Spanjaard

We propose a Skew-Symmetric Bilinear (SSB) model to represent intransitive preferences on subsets of a ground set of items. More precisely, the SSB model accounts for preference intensities between pairs of subsets. We provide a procedure to learn the parameters of the SSB model from a set of known pairwise preferences between subsets, managing to find a sparse model, and as simple as possible in terms of the degree of interaction between items. The SSB model can be viewed as a concise representation of a weighted tournament on subsets. We study the complexity of determining the winners according to various tournament rules. Numerical tests on synthetic and real-world data are carried out.

ECAI Conference 2023 Conference Paper

A Hybrid Approach to Preference Learning with Interaction Terms

• Hugo Gilbert
• Mohamed Ouaguenouni
• Meltem Öztürk
• Olivier Spanjaard

Preference learning is an essential component in numerous applications, such as recommendation systems, decision-making processes, and personalized services. We propose here a novel approach to preference learning that interleaves Gaussian Processes (GP) and Robust Ordinal Regression (ROR). A Gaussian process gives a probability distribution on the latent function values that generate users’ preferences. Our method extends the traditional non-parametric Gaussian process framework by approximating the latent function by a very flexible parameterized function, that we call θ-additive function, where θ is the parameter set. The set θ reflects the degree of sophistication of the generalized additive model that can potentially represent the user’s preferences. To learn what are the components of θ, we update a probability distribution on the space of all possible sets θ, depending on the ability of the parameterized function to approximate the latent function. We predict pairwise preferences by using the parameter set θ that maximizes the posterior distribution and by performing robust ordinal regression based on this parameter set. Experimental results on synthetic data demonstrate the effectiveness and robustness of our proposed methodology.

ECAI Conference 2023 Conference Paper

Fair Rent Division on a Budget Revisited

• Stéphane Airiau
• Hugo Gilbert
• Umberto Grandi
• Jérôme Lang
• Anaëlle Wilczynski

Rent division consists in simultaneously computing an allocation of rooms to agents and a payment, starting from an individual valuation of each room by each agent. When agents have budget limits, it is known that envy-free solutions do not necessarily exist. We propose two solutions to overcome this problem. In the first one, we relax envy-freeness to account for budget disparities. In the second one, we allow fractional allocations, in which agents may change rooms during the duration of the lease.

AAMAS Conference 2023 Conference Paper

Measuring a Priori Voting Power - Taking Delegations Seriously

• Rachael Colley
• Théo Delemazure
• Hugo Gilbert

In this paper, we introduce new power indices to measure the criticality of voters involved in different elections where delegations play a key role, namely, two variants of the proxy voting setting and a liquid democracy setting. We argue that our power indices are natural extensions of the Penrose-Banzhaf index in classic simple voting games; we show that recursive formulas can compute these indices for weighted voting games in pseudo-polynomial time; and we provide numerical results to illustrate how introducing delegation options modifies the voting power of voters.

IJCAI Conference 2023 Conference Paper

Measuring a Priori Voting Power in Liquid Democracy

• Rachael Colley
• Théo Delemazure
• Hugo Gilbert

We introduce new power indices to measure the a priori voting power of voters in liquid democracy elections where an underlying network restricts delegations. We argue that our power indices are natural extensions of the standard Penrose-Banzhaf index in simple voting games. We show that computing the criticality of a voter is #P-hard even in weighted games with weights polynomially-bounded in the size of the instance. However, for specific settings, such as when the underlying network is a bipartite or complete graph, recursive formulas can compute these indices for weighted voting games in pseudo-polynomial time. We highlight their theoretical properties and provide numerical results to illustrate how restricting the possible delegations can alter voters' voting power.

AAMAS Conference 2023 Conference Paper

Robust Ordinal Regression for Collaborative Preference Learning with Opinion Synergies

• Hugo Gilbert
• Mohamed Ouaguenouni
• Meltem Öztürk
• Olivier Spanjaard

This work focuses on a robust learning methodology in a collaborative filtering context. We wish to predict preferences between alternatives characterized by binary attributes, where each attribute represents the opinion of a reference user on the alternative. The model whose parameters we learn is general enough to be compatible with any strict weak order on the attribute vectors, thanks to the consideration of opinion synergies. Moreover, we accept not to predict some preferences if the data collected are not compatible with a reliable prediction. A predicted preference will be considered reliable if all the simplest models explaining the training data agree on it. Following the robust ordinal regression methodology, our predictions are based on an ordinal dominance relation between alternatives introduced by Fishburn and LaValle [11] which relies on an uncertainty set encompassing the possible values of the parameters of the multi-attribute utility function.

TCS Journal 2022 Journal Article

Beyond pairwise comparisons in social choice: A setwise Kemeny aggregation problem

• Hugo Gilbert
• Tom Portoleau
• Olivier Spanjaard

AAMAS Conference 2022 Conference Paper

Computation and Bribery of Voting Power in Delegative Simple Games

• Gianlorenzo D'Angelo
• Esmaeil Delfaraz
• Hugo Gilbert

Following Zhang and Grossi (AAAI 2021), we study in more depth a variant of weighted voting games in which agents’ weights are induced by a transitive support structure. This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results.

JAIR Journal 2022 Journal Article

Fairness in Influence Maximization through Randomization

• Ruben Becker
• Gianlorenzo D’Angelo
• Sajjad Ghobadi
• Hugo Gilbert

The influence maximization paradigm has been used by researchers in various fields in order to study how information spreads in social networks. While previously the attention was mostly on efficiency, more recently fairness issues have been taken into account in this scope. In the present paper, we propose to use randomization as a mean for achieving fairness. While this general idea is not new, it has not been applied in this area. Similar to previous works like Fish et al. (WWW ’19) and Tsang et al. (IJCAI ’19), we study the maximin criterion for (group) fairness. In contrast to their work however, we model the problem in such a way that, when choosing the seed sets, probabilistic strategies are possible rather than only deterministic ones. We introduce two different variants of this probabilistic problem, one that entails probabilistic strategies over nodes (node-based problem) and a second one that entails probabilistic strategies over sets of nodes (set-based problem). After analyzing the relation between the two probabilistic problems, we show that, while the original deterministic maximin problem was inapproximable, both probabilistic variants permit approximation algorithms that achieve a constant multiplicative factor of 1 − 1/ e minus an additive arbitrarily small error that is due to the simulation of the information spread. For the node-based problem, the approximation is achieved by observing that a polynomial-sized linear program approximates the problem well. For the set-based problem, we show that a multiplicative-weight routine can yield the approximation result. For an experimental study, we provide implementations of multiplicative-weight routines for both the set-based and the node-based problems and compare the achieved fairness values to existing methods. Maybe non-surprisingly, we show that the ex-ante values, i.e., minimum expected value of an individual (or group) to obtain the information, of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This indicates that studying fairness via randomization is a worthwhile path to follow. Interestingly and maybe more surprisingly, we observe that even the ex-post fairness values, i.e., fairness values of sets sampled according to the probabilistic strategies computed by our routines, dominate over the fairness achieved by previous methods on many of the instances tested.

AAAI Conference 2021 Conference Paper

Fairness in Influence Maximization through Randomization

• Ruben Becker
• Gianlorenzo D'Angelo
• Sajjad Ghobadi
• Hugo Gilbert

The influence maximization paradigm has been used by researchers in various fields in order to study how information spreads in social networks. While previously the attention was mostly on efficiency, more recently fairness issues have been taken into account in this scope. In the present paper, we propose to use randomization as a mean for achieving fairness. While this general idea is not new, it has not been applied in the area of information spread in networks. Similar to previous works like Fish et al. (WWW ’19) and Tsang et al. (IJCAI ’19), we study the maximin criterion for (group) fairness. By allowing randomized solutions, we introduce two different variants of this problem. While the original deterministic maximin problem has been shown to be inapproximable, interestingly, we show that both probabilistic variants permit approximation algorithms with a constant multiplicative factor of 1 − 1/e plus an additive arbitrarily small error due to the simulation of the information spread. For an experimental study, we provide implementations of our methods and compare the achieved fairness values to existing methods. Non-surprisingly, the ex-ante values, i. e. , minimum expected value of an individual (or group) to obtain the information, of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This confirms that studying fairness via randomization is a worthwhile direction. More surprisingly, we observe that even the ex-post fairness values, i. e. , fairness values of sets sampled according to the probabilistic strategies, computed by our routines dominate over the fairness achieved by previous methods on most of the instances tested.

AAMAS Conference 2021 Conference Paper

Maximizing Influence-Based Group Shapley Centrality

• Ruben Becker
• Gianlorenzo D'Angelo
• Hugo Gilbert

A key problem in network analysis is the influence maximization problem, which consists of finding a set S of at most k seed users in a social network, such that the spread of information from S is maximized. We investigate the problem of choosing the best set of seeds when there exists an unknown pre-existing set of seed nodes. Our work extends the one of Chen and Teng (WWW’17) who introduced the so-called Shapley centrality of a node to measure the efficiency of nodes acting as seeds within a pre-existing but unknown set of seeds. We instead consider the question: Which set of cardinality k to target in this kind of scenario? The resulting optimization problem reveals very challenging, that is, assuming common computational complexity conjectures, we obtain strong hardness of approximation results. Nevertheless, we design a greedy algorithm which achieves an approximation factor of 1−1/e k − ϵ for any ϵ > 0, showing that not all is lost in settings wherek is bounded.

AAAI Conference 2020 Conference Paper

Balancing Spreads of Influence in a Social Network

• Ruben Becker
• Federico Corò
• Gianlorenzo D'Angelo
• Hugo Gilbert

The personalization of our news consumption on social media has a tendency to reinforce our pre-existing beliefs instead of balancing our opinions. To tackle this issue, Garimella et al. (NIPS’17) modeled the spread of these viewpoints, also called campaigns, using the independent cascade model introduced by Kempe, Kleinberg and Tardos (KDD’03) and studied an optimization problem that aims to balance information exposure when two opposing campaigns propagate in a network. This paper investigates a natural generalization of this optimization problem in which μ different campaigns propagate in the network and we aim to maximize the expected number of nodes that are reached by at least ν or none of the campaigns, where μ ≥ ν ≥ 2. Following Garimella et al. , despite this general setting, we also investigate a simplified one, in which campaigns propagate in a correlated manner. While for the simplified setting, we show that the problem can be approximated within a constant factor for any constant μ and ν, for the general setting, we give reductions leading to several approximation hardness results when ν ≥ 3. For instance, assuming the gap exponential time hypothesis to hold, we obtain that the problem cannot be approximated within a factor of n−g(n) for any g(n) = o(1) where n is the number of nodes in the network. We complement our hardness results with an Ω(n−1/2 )-approximation algorithm for the general setting when ν = 3 and μ is arbitrary.

AAAI Conference 2020 Conference Paper

Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem

• Hugo Gilbert
• Tom Portoleau
• Olivier Spanjaard

In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. It reveals useful to divide the aggregation problem into several sub-problems. We conclude with numerical tests.

AAAI Conference 2020 Conference Paper

Iterative Delegations in Liquid Democracy with Restricted Preferences

• Bruno Escoffier
• Hugo Gilbert
• Adèle Pass-Lanneau

Liquid democracy is a collective decision making paradigm which lies between direct and representative democracy. One main feature of liquid democracy is that voters can delegate their votes in a transitive manner so that: A delegates to B and B delegates to C leads to A delegates to C. Unfortunately, because voters’ preferences over delegates may be conflicting, this process may not converge. There may not even exist a stable state (also called equilibrium). In this paper, we investigate the stability of the delegation process in liquid democracy when voters have restricted types of preference on the agent representing them (e. g. , single-peaked preferences). We show that various natural structures of preference guarantee the existence of an equilibrium and we obtain both tractability and hardness results for the problem of computing several equilibria with some desirable properties.

ECAI Conference 2020 Conference Paper

Parameterized Complexity of Manipulating Sequential Allocation

• Michele Flammini
• Hugo Gilbert

The sequential allocation protocol is a simple and popular mechanism to allocate indivisible goods, in which the agents take turns to pick the items according to a predefined sequence. While this protocol is not strategy-proof, it has been recently shown that finding a successful manipulation for an agent is an NP-hard problem [1]. Conversely, it is also known that finding an optimal manipulation can be solved in polynomial time in a few cases: if there are only two agents or if the manipulator has a binary or a lexicographic utility function. In this work, we take a parameterized approach to provide several new complexity results on this manipulation problem. More precisely, we give a complete picture of its parameterized complexity w. r. t. the following three parameters: the number n of agents, the number μ(a 1 ) of times the manipulator a 1 picks in the picking sequence, and the maximum range rg max of an item. This third parameter is a correlation measure on the preference rankings of the agents. In particular, we provide XP algorithms for parameters n and μ(a 1 ), and we show that the problem is fixed-parameter tractable w. r. t. r gmax and n + μ(a 1 ). Interestingly enough, we show that w. r. t. the single parameters n and μ(a 1 ) it is W[1]-hard.

UAI Conference 2017 Conference Paper

Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility

• Hugo Gilbert
• Olivier Spanjaard

We study the complexity of solving decision trees with a Skew-Symmetric Bilinear (SSB) utility function. The SSB model is an extension of Expected Utility (EU) with enhanced descriptive possibilities. Unlike EU, the optimality principle does not hold for SSB, which makes its optimization trickier. We show that determining an SSB optimal plan is NP-hard if one only considers deterministic plans while it is polynomial time if one allows randomized plans. With the Weighted EU model (a special case of SSB), the problem becomes polynomial in both settings. Our numerical tests show the operationality of the methods.

IJCAI Conference 2017 Conference Paper

Incremental Decision Making Under Risk with the Weighted Expected Utility Model

• Hugo Gilbert
• Nawal Benabbou
• Patrice Perny
• Olivier Spanjaard
• Paolo Viappiani

This paper deals with decision making under risk with the Weighted Expected Utility (WEU) model, which is a model generalizing expected utility and providing stronger descriptive possibilities. We address the problem of identifying, within a given set of lotteries, a (near-)optimal solution for a given decision maker consistent with the WEU theory. The WEU model is parameterized by two real-valued functions. We propose here a new incremental elicitation procedure to progressively reduce the imprecision about these functions until a robust decision can be made. We also give experimental results showing the practical efficiency of our method.

AAAI Conference 2017 Conference Paper

Optimizing Quantiles in Preference-Based Markov Decision Processes

• Hugo Gilbert
• Paul Weng
• Yan Xu

In the Markov decision process model, policies are usually evaluated by expected cumulative rewards. As this decision criterion is not always suitable, we propose in this paper an algorithm for computing a policy optimal for the quantile criterion. Both finite and infinite horizons are considered. Finally we experimentally evaluate our approach on random MDPs and on a data center control problem.

UAI Conference 2016 Conference Paper

Model-Free Reinforcement Learning with Skew-Symmetric Bilinear Utilities

• Hugo Gilbert
• Bruno Zanuttini
• Paul Weng
• Paolo Viappiani
• Esther Nicart

In reinforcement learning, policies are typically evaluated according to the expectation of cumulated rewards. Researchers in decision theory have argued that more sophisticated decision criteria can better model the preferences of a decision maker. In particular, Skew-Symmetric Bilinear (SSB) utility functions generalize von Neumann and Morgenstern’s expected utility (EU) theory to encompass rational decision behaviors that EU cannot accommodate. In this paper, we adopt an SSB utility function to compare policies in the reinforcement learning setting. We provide a model-free SSB reinforcement learning algorithm, SSB Q-learning, and prove its convergence towards a policy that is -optimal according to SSB. The proposed algorithm is an adaptation of fictitious play [Brown, 1951] combined with techniques from stochastic approximation [Borkar, 1997]. We also present some experimental results which evaluate our approach in a variety of settings.

IJCAI Conference 2015 Conference Paper

Solving MDPs with Skew Symmetric Bilinear Utility Functions

• Hugo Gilbert
• Olivier Spanjaard
• Paolo Viappiani
• Paul Weng

In this paper we adopt Skew Symmetric Bilinear (SSB) utility functions to compare policies in Markov Decision Processes (MDPs). By considering pairs of alternatives, SSB utility theory generalizes von Neumann and Morgenstern’s expected utility (EU) theory to encompass rational decision behaviors that EU cannot accommodate. We provide a game-theoretic analysis of the problem of identifying an SSB-optimal policy in finite horizon MDPs and propose an algorithm based on a double oracle approach for computing an optimal (possibly randomized) policy. Finally, we present and discuss experimental results where SSB-optimal policies are computed for a popular TV contest according to several instantiations of SSB utility functions.