Yann Chevaleyre

ICML Conference 2025 Conference Paper

Improving Diversity in Language Models: When Temperature Fails, Change the Loss

• Alexandre Verine
• Florian Le Bronnec
• Kunhao Zheng
• Alexandre Allauzen
• Yann Chevaleyre
• Benjamin Négrevergne

Increasing diversity in language models is a challenging yet essential objective. A common approach is to raise the decoding temperature. In this work, we investigate this approach through a simplistic yet common case to provide insights into why decreasing temperature can improve quality (Precision), while increasing it often fails to boost coverage (Recall). Our analysis reveals that for a model to be effectively tunable through temperature adjustments, it must be trained toward coverage. To address this, we propose rethinking loss functions in language models by leveraging the Precision-Recall framework. Our results demonstrate that this approach achieves a substantially better trade-off between Precision and Recall than merely combining negative log-likelihood training with temperature scaling. These findings offer a pathway toward more versatile and robust language modeling techniques.

NeurIPS Conference 2023 Conference Paper

On the Role of Randomization in Adversarially Robust Classification

• Lucas Gnecco Heredia
• Muni Sreenivas Pydi
• Laurent Meunier
• Benjamin Negrevergne
• Yann Chevaleyre

Deep neural networks are known to be vulnerable to small adversarial perturbations in test data. To defend against adversarial attacks, probabilistic classifiers have been proposed as an alternative to deterministic ones. However, literature has conflicting findings on the effectiveness of probabilistic classifiers in comparison to deterministic ones. In this paper, we clarify the role of randomization in building adversarially robust classifiers. Given a base hypothesis set of deterministic classifiers, we show the conditions under which a randomized ensemble outperforms the hypothesis set in adversarial risk, extending previous results. Additionally, we show that for any probabilistic binary classifier (including randomized ensembles), there exists a deterministic classifier that outperforms it. Finally, we give an explicit description of the deterministic hypothesis set that contains such a deterministic classifier for many types of commonly used probabilistic classifiers, i. e. randomized ensembles and parametric/input noise injection.

NeurIPS Conference 2023 Conference Paper

Precision-Recall Divergence Optimization for Generative Modeling with GANs and Normalizing Flows

• Alexandre Verine
• Benjamin Negrevergne
• Muni Sreenivas Pydi
• Yann Chevaleyre

Achieving a balance between image quality (precision) and diversity (recall) is a significant challenge in the domain of generative models. Current state-of-the-art models primarily rely on optimizing heuristics, such as the Fr\'echet Inception Distance. While recent developments have introduced principled methods for evaluating precision and recall, they have yet to be successfully integrated into the training of generative models. Our main contribution is a novel training method for generative models, such as Generative Adversarial Networks and Normalizing Flows, which explicitly optimizes a user-defined trade-off between precision and recall. More precisely, we show that achieving a specified precision-recall trade-off corresponds to minimizing a unique $f$-divergence from a family we call the \mbox{\em PR-divergences}. Conversely, any $f$-divergence can be written as a linear combination of PR-divergences and corresponds to a weighted precision-recall trade-off. Through comprehensive evaluations, we show that our approach improves the performance of existing state-of-the-art models like BigGAN in terms of either precision or recall when tested on datasets such as ImageNet.

NeurIPS Conference 2022 Conference Paper

An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits

• Geovani Rizk
• Igor Colin
• Albert Thomas
• Rida Laraki
• Yann Chevaleyre

We propose the first regret-based approach to the \emph{Graphical Bilinear Bandits} problem, where $n$ agents in a graph play a stochastic bilinear bandit game with each of their neighbors. This setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. In this paper, we fill this gap and present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of $\tilde{O}(\sqrt{T})$ on the $\alpha$-regret and evidences the impact of the graph structure on the rate of convergence. Finally, we show through various experiments the validity of our approach.

IROS Conference 2022 Conference Paper

Reactive Stepping for Humanoid Robots using Reinforcement Learning: Application to Standing Push Recovery on the Exoskeleton Atalante

• Alexis Duburcq
• Fabian Schramm
• Guilhem Boéris
• Nicolas Bredèche
• Yann Chevaleyre

State-of-the-art reinforcement learning is now able to learn versatile locomotion, balancing and push-recovery capabilities for bipedal robots in simulation. Yet, the reality gap has mostly been overlooked and the simulated results hardly transfer to real hardware. Either it is unsuccessful in practice because the physics is over-simplified and hardware limitations are ignored, or regularity is not guaranteed, and unexpected hazardous motions can occur. This paper presents a reinforcement learning framework capable of learning ro-bust standing push recovery for bipedal robots that smoothly transfer to reality, providing only instantaneous proprioceptive observations. By combining original termination conditions and policy smoothness conditioning, we achieve stable learning, sim-to-real transfer and safety using a policy without memory nor explicit history. Reward engineering is then used to give insights into how to keep balance. We demonstrate its performance in reality on the lower-limb medical exoskeleton Atalante.

NeurIPS Conference 2022 Conference Paper

Towards Consistency in Adversarial Classification

• Laurent Meunier
• Raphael Ettedgui
• Rafael Pinot
• Yann Chevaleyre
• Jamal Atif

In this paper, we study the problem of consistency in the context of adversarial examples. Specifically, we tackle the following question: can surrogate losses still be used as a proxy for minimizing the $0/1$ loss in the presence of an adversary that alters the inputs at test-time? Different from the standard classification task, this question cannot be reduced to a point-wise minimization problem, and calibration needs not to be sufficient to ensure consistency. In this paper, we expose some pathological behaviors specific to the adversarial problem, and show that no convex surrogate loss can be consistent or calibrated in this context. It is therefore necessary to design another class of surrogate functions that can be used to solve the adversarial consistency issue. As a first step towards designing such a class, we identify sufficient and necessary conditions for a surrogate loss to be calibrated in both the adversarial and standard settings. Finally, we give some directions for building a class of losses that could be consistent in the adversarial framework.

ICML Conference 2021 Conference Paper

Best Arm Identification in Graphical Bilinear Bandits

• Geovani Rizk
• Albert Thomas 0001
• Igor Colin
• Rida Laraki
• Yann Chevaleyre

We introduce a new graphical bilinear bandit problem where a learner (or a \emph{central entity}) allocates arms to the nodes of a graph and observes for each edge a noisy bilinear reward representing the interaction between the two end nodes. We study the best arm identification problem in which the learner wants to find the graph allocation maximizing the sum of the bilinear rewards. By efficiently exploiting the geometry of this bandit problem, we propose a \emph{decentralized} allocation strategy based on random sampling with theoretical guarantees. In particular, we characterize the influence of the graph structure (e. g. star, complete or circle) on the convergence rate and propose empirical experiments that confirm this dependency.

ICML Conference 2021 Conference Paper

Mixed Nash Equilibria in the Adversarial Examples Game

• Laurent Meunier
• Meyer Scetbon
• Rafael Pinot
• Jamal Atif
• Yann Chevaleyre

This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually allow only one player to use randomized strategies, we show the necessity of considering randomization for both the classifier and the attacker. We demonstrate that this game has no duality gap, meaning that it always admits approximate Nash equilibria. We also provide the first optimization algorithms to learn a mixture of classifiers that approximately realizes the value of this game, \emph{i. e. } procedures to build an optimally robust randomized classifier.

AAAI Conference 2021 Conference Paper

On Lipschitz Regularization of Convolutional Layers using Toeplitz Matrix Theory

• Alexandre Araujo
• Benjamin Negrevergne
• Yann Chevaleyre
• Jamal Atif

This paper tackles the problem of Lipschitz regularization of Convolutional Neural Networks. Lipschitz regularity is now established as a key property of modern deep learning with implications in training stability, generalization, robustness against adversarial examples, etc. However, computing the exact value of the Lipschitz constant of a neural network is known to be NP-hard. Recent attempts from the literature introduce upper-bounds to approximate this constant that are either efficient but loose or accurate but computationally expensive. In this work, by leveraging the theory of Toeplitz matrices, we introduce a new upper-bound for convolutional layers that is both tight and easy to compute. Based on this result we devise an algorithm to train Lipschitz regularized Convolutional Neural Networks.

ICRA Conference 2020 Conference Paper

Online Trajectory Planning Through Combined Trajectory Optimization and Function Approximation: Application to the Exoskeleton Atalante

• Alexis Duburcq
• Yann Chevaleyre
• Nicolas Bredèche
• Guilhem Boéris

Autonomous robots require online trajectory planning capability to operate in the real world. Efficient offline trajectory planning methods already exist, but are computationally demanding, preventing their use online. In this paper, we present a novel algorithm called Guided Trajectory Learning that learns a function approximation of solutions computed through trajectory optimization while ensuring accurate and reliable predictions. This function approximation is then used online to generate trajectories. This algorithm is designed to be easy to implement, and practical since it does not require massive computing power. It is readily applicable to any robotics systems and effortless to set up on real hardware since robust control strategies are usually already available. We demonstrate the computational performance of our algorithm on flat-foot walking with the self-balanced exoskeleton Atalante.

ICML Conference 2020 Conference Paper

Randomization matters How to defend against strong adversarial attacks

• Rafael Pinot
• Raphael Ettedgui
• Geovani Rizk
• Yann Chevaleyre
• Jamal Atif

\emph{Is there a classifier that ensures optimal robustness against all adversarial attacks? } This paper tackles this question by adopting a game-theoretic point of view. We present the adversarial attacks and defenses problem as an \emph{infinite} zero-sum game where classical results (\emph{e. g. } Nash or Sion theorems) do not apply. We demonstrate the non-existence of a Nash equilibrium in our game when the classifier and the Adversary are both deterministic, hence giving a negative answer to the above question in the deterministic regime. Nonetheless, the question remains open in the randomized regime. We tackle this problem by showing that any deterministic classifier can be outperformed by a randomized one. This gives arguments for using randomization, and leads us to a simple method for building randomized classifiers that are robust to state-or-the-art adversarial attacks. Empirical results validate our theoretical analysis, and show that our defense method considerably outperforms Adversarial Training against strong adaptive attacks, by achieving 0. 55 accuracy under adaptive PGD-attack on CIFAR10, compared to 0. 42 for Adversarial training.

ECAI Conference 2020 Conference Paper

Understanding and Training Deep Diagonal Circulant Neural Networks

• Alexandre Araujo
• Benjamin Négrevergne
• Yann Chevaleyre
• Jamal Atif

In this paper, we study deep diagonal circulant neural networks, which are deep neural networks in which weight matrices are the product of diagonal and circulant ones. Besides making a theoretical analysis of their expressivity, we introduce principled techniques for training these models: we devise an initialization scheme and propose a smart use of non-linearity functions in order to train deep diagonal circulant networks. Furthermore, we show that these networks outperform recently introduced deep networks with other types of structured layers. We conduct a thorough experimental study to compare the performance of deep diagonal circulant networks with state-of-the-art models based on structured matrices and with dense models. We show that our models achieve better accuracy than other structured approaches while requiring 2x fewer weights than the next best approach. Finally, we train compact and accurate deep diagonal circulant networks on a real world video classification dataset with over 3. 8 million training examples.

JAAMAS Journal 2019 Journal Article

Local envy-freeness in house allocation problems

• Aurélie Beynier
• Yann Chevaleyre
• Anaëlle Wilczynski

Abstract We study the fair division problem consisting in allocating one item per agent so as to avoid (or minimize) envy, in a setting where only agents connected in a given network may experience envy. In a variant of the problem, agents themselves can be located on the network by the central authority. These problems turn out to be difficult even on very simple graph structures, but we identify several tractable cases. We further provide practical algorithms and experimental insights.

IJCAI Conference 2018 Conference Paper

Accountable Approval Sorting

• Khaled Belahcene
• Yann Chevaleyre
• Christophe Labreuche
• Nicolas Maudet
• Vincent Mousseau
• Wassila Ouerdane

We consider decision situations in which a set of points of view (voters, criteria) are to sort a set of candidates to ordered categories (Good/Bad). Candidates are judged good, when approved by a sufficient set of points of view; this corresponds to NonCompensatory Sorting. To be accountable, such approval sorting should provide guarantees about the decision process and decisions concerning specific candidates. We formalize accountability using a feasibility problem expressed as a boolean satisfiability formulation. We illustrate different forms of accountability when a committee decides with approval sorting and study the information that should be disclosed by the committee.

AAMAS Conference 2018 Conference Paper

Local Envy-Freeness in House Allocation Problems

• Aur�lie Beynier
• Yann Chevaleyre
• Laurent Gourv�s
• Julien Lesca
• Nicolas Maudet
• Ana�lle Wilczynski

We study the fair division problem consisting in allocating one item per agent so as to avoid (or minimize) envy, in a setting where only agents connected in a given social network may experience envy. In a variant of the problem, agents themselves can be located on the network by the central authority. These problems turn out to be difficult even on very simple graph structures, but we identify several tractable cases. We further provide practical algorithms and experimental insights.

AIJ Journal 2017 Journal Article

Distributed fair allocation of indivisible goods

• Yann Chevaleyre
• Ulle Endriss
• Nicolas Maudet

Distributed mechanisms for allocating indivisible goods are mechanisms lacking central control, in which agents can locally agree on deals to exchange some of the goods in their possession. We study convergence properties for such distributed mechanisms when used as fair division procedures. Specifically, we identify sets of assumptions under which any sequence of deals meeting certain conditions will converge to a proportionally fair allocation and to an envy-free allocation, respectively. We also introduce an extension of the basic framework where agents are vertices of a graph representing a social network that constrains which agents can interact with which other agents, and we prove a similar convergence result for envy-freeness in this context. Finally, when not all assumptions guaranteeing envy-freeness are satisfied, we may want to minimise the degree of envy exhibited by an outcome. To this end, we introduce a generic framework for measuring the degree of envy in a society and establish the computational complexity of checking whether a given scenario allows for a deal that is beneficial to every agent involved and that will reduce overall envy.

IJCAI Conference 2017 Conference Paper

Voting by sequential elimination with few voters

• Sylvain Bouveret
• Yann Chevaleyre
• François Durand
• Jérôme Lang

We define a new class of low-communication voting rules, tailored for contexts with few voters and possibly many candidates. These rules are defined by a predefined sequence of voters: at each stage, the designated voter eliminates a candidate, and the last remaining candidate wins. We study both deterministic (non-anonymous) variants, and randomized (and anonymous) versions of these rules. We focus on a subfamily of these rules defined by ``non-interleaved'' sequences. We first focus on the axiomatic properties of our rules. Then we focus on the identification of the non-interleaved sequence that gives the best approximation of the Borda score under the impartial culture. Finally, we apply our rules to randomly generated data. Our conclusion is that, in contexts where there are more candidates than voters, elimination-based rules allow for a very low communication complexity (and especially, avoid asking voters to rank alternatives), and yet can be good approximations of common voting rules, while enjoying a number of good properties.

ICML Conference 2013 Conference Paper

Rounding Methods for Discrete Linear Classification

• Yann Chevaleyre
• Frédéric Koriche
• Jean-Daniel Zucker

Learning discrete linear functions is a notoriously difficult challenge. In this paper, the learning task is cast as combinatorial optimization problem: given a set of positive and negative feature vectors in the Euclidean space, the goal is to find a discrete linear function that minimizes the cumulative hinge loss of this training set. Since this problem is NP-hard, we propose two simple rounding algorithms that discretize the fractional solution of the problem. Generalization bounds are derived for two important classes of binary-weighted linear functions, by establishing the Rademacher complexity of these classes and proving approximation bounds for rounding methods. These methods are compared on both synthetic and real-world data.

TARK Conference 2011 Conference Paper

Compilation and communication protocols for voting rules with a dynamic set of candidates

• Yann Chevaleyre
• Jérôme Lang
• Nicolas Maudet
• Jérôme Monnot

We address the problem of designing communication protocols for voting rules when the set of candidates can evolve via the addition of new candidates. We show that the necessary amount of communication that must be transmitted between the voters and the central authority depends on the amount of space devoted to the storage of the votes over the initial set of candidates. This calls for a bicriteria evaluation of protocols. We consider a few usual voting rules, and three types of storage functions: full storage, where the full votes on the initial set of voters are stored; null storage, where nothing is stored; and anonymous storage, which lies in-between. For some of these pairs (voting rule, type of storage) we design protocols and show that they are asymptotically optimal by determining the communication complexity of the rule under the storage function considered.

ECAI Conference 2010 Conference Paper

Learning conditionally lexicographic preference relations

• Richard Booth 0001
• Yann Chevaleyre
• Jérôme Lang
• Jérôme Mengin
• Chattrakul Sombattheera

We consider the problem of learning a user's ordinal preferences on a multiattribute domain, assuming that her preferences are lexicographic. We introduce a general graphical representation called LP-trees which captures various natural classes of such preference relations, depending on whether the importance order between attributes and/or the local preferences on the domain of each attribute is conditional on the values of other attributes. For each class we determine the Vapnik-Chernovenkis dimension, the communication complexity of preference elicitation, and the complexity of identifying a model in the class consistent with a set of user-provided examples.

AAAI Conference 2010 Conference Paper

Possible Winners when New Candidates Are Added: The Case of Scoring Rules

• Yann Chevaleyre
• Jérôme Lang
• Nicolas Maudet
• Jérôme Monnot

In some voting situations, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number k of new candidates will be added. Focusing on scoring rules, we give complexity results for the above possible winner problem.

IJCAI Conference 2009 Conference Paper

• Yann Chevaleyre
• Jérôme Lang
• Nicolas Maudet
• Guillaume Ravilly-Abadie

In many practical contexts where a number of agents have to find a common decision, the votes do not come all together at the same time. In such situations, we may want to preprocess the information given by the subelectorate (consisting of the voters who have expressed their votes) so as to “compile” the known votes for the time when the latecomers have expressed their votes. We study the amount of space necessary for such a compilation, as a function of the voting rule, the number of candidates, and the number of votes already known. We relate our results to existing work, especially on communication complexity.

JAAMAS Journal 2009 Journal Article

Simple negotiation schemes for agents with simple preferences: sufficiency, necessity and maximality

• Yann Chevaleyre
• Ulle Endriss
• Nicolas Maudet

Abstract We investigate the properties of an abstract negotiation framework where agents autonomously negotiate over allocations of indivisible resources. In this framework, reaching an allocation that is optimal may require very complex multilateral deals. Therefore, we are interested in identifying classes of valuation functions such that any negotiation conducted by means of deals involving only a single resource at a time is bound to converge to an optimal allocation whenever all agents model their preferences using these functions. In the case of negotiation with monetary side payments amongst self-interested but myopic agents, the class of modular valuation functions turns out to be such a class. That is, modularity is a sufficient condition for convergence in this framework. We also show that modularity is not a necessary condition. Indeed, there can be no condition on individual valuation functions that would be both necessary and sufficient in this sense. Evaluating conditions formulated with respect to the whole profile of valuation functions used by the agents in the system would be possible in theory, but turns out to be computationally intractable in practice. Our main result shows that the class of modular functions is maximal in the sense that no strictly larger class of valuation functions would still guarantee an optimal outcome of negotiation, even when we permit more general bilateral deals. We also establish similar results in the context of negotiation without side payments.

TCS Journal 2008 Journal Article

The complexity of deciding reachability properties of distributed negotiation schemes

• Paul E. Dunne
• Yann Chevaleyre

Distributed negotiation schemes offer one approach to agreeing an allocation of resources among a set of individual agents. Such schemes attempt to agree a distribution via a sequence of locally agreed ‘deals’–reallocations of resources among the agents–ending when the result satisfies some accepted criteria. Our aim in this article is to demonstrate that some natural decision questions arising in such settings can be computationally significantly harder than questions related to optimal clearing strategies in combinatorial auctions. In particular we prove that the problem of deciding whether it is possible to progress from a given initial allocation to some desired final allocation via a sequence of “rational” steps is pspace-complete.

AAMAS Conference 2008 Conference Paper

Trajectories of Goods in Distributed Allocation

• Yann Chevaleyre
• Ulle Endriss
• Nicolas Maudet

Distributed allocation mechanisms rely on the agents’ autonomous (and supposedly rational) behaviour: states evolve as a result of agents contracting deals and exchanging resources. It is no surprise that restrictions on potential deals also restrict the reachability of some desirable states, for instance states where goods are efficiently allocated. In particular topological restrictions make any attempt to guarantee asymptotic convergence to an optimal allocation impossible in most cases. In this paper, we concentrate on the dynamics of such systems; more precisely we study the trajectories of goods in such iterative reallocative processes. Our first contribution is to propose an upper bound on the length of the trajectories of goods, when agent utility functions are modular. The second innovative aspect of the paper is then to discuss how this affects, on average, the quality of the states that are reached. Finally, a preliminary study of the non-modular case is proposed, examining how synergetic effects between items can affect their trajectories.

IJCAI Conference 2007 Conference Paper

• Yann Chevaleyre
• Ulle Endriss
• Sylvia Estivie
• Nicolas Maudet

Mechanisms for dividing a set of goods amongst a number of autonomous agents need to balance efficiency and fairness requirements. A common interpretation of fairness is envy-freeness, while efficiency is usually understood as yielding maximal overall utility. We show how to set up a distributed negotiation framework that will allow a group of agents to reach an allocation of goods that is both efficient and envy-free.

AAAI Conference 2007 Conference Paper

Allocating Goods on a Graph to Eliminate Envy

• Yann Chevaleyre

We introduce a distributed negotiation framework for multiagent resource allocation where interactions between agents are limited by a graph defining a negotiation topology. A group of agents may only contract a deal if that group is fully connected according to the negotiation topology. An important criterion for assessing the quality of an allocation of resources, in terms of fairness, is envy-freeness: an agent is said to envy another agent if it would prefer to swap places with that other agent. We analyse under what circumstances a sequence of deals respecting the negotiation topology may be expected to converge to a state where no agent envies any of the agents it is directly connected to. We also analyse the computational complexity of a related decision problem, namely the problem of checking whether a given negotiation state admits any deal that would both be beneficial to every agent involved and reduce envy in the agent society.

KR Conference 2006 Conference Paper

Expressive Power of Weighted Propositional Formulas for Cardinal Preference Modelling

• Yann Chevaleyre
• Ulle Endriss
• Jerome Lang

As proposed in various places, a set of propositional formulas, each associated with a numerical weight, can be used to model the preferences of an agent in combinatorial domains. If the range of possible choices can be represented by the set of possible assignments of propositional symbols to truth values, then the utility of an assignment is given by the sum of the weights of the formulas it satisfies. Our aim in this paper is twofold: (1) to establish correspondences between certain types of weighted formulas and well-known classes of utility functions (such as monotonic, concave or k-additive functions); and (2) to obtain results on the comparative succinctness of different types of weighted formulas for representing the same class of utility functions.

AAMAS Conference 2006 Conference Paper

How Equitable Is Rational Negotiation?

• Sylvia Estivie
• Yann Chevaleyre
• Ulle Endriss
• Nicolas Maudet

AAMAS Conference 2006 Conference Paper

Tractable Negotiation in Tree-structured Domains

• Yann Chevaleyre
• Ulle Endriss
• Nicolas Maudet

KER Journal 2005 Journal Article

Multiagent resource allocation

• Yann Chevaleyre
• Paul E. Dunne
• Ulle Endriss
• Jérôme Lang
• Nicolas Maudet
• Juan A. Rodríguez-Aguilar

Resource allocation in multiagent systems is a central research issue in the AgentLink community. The aim of the Technical Forum Group on Multiagent Resource Allocation (TFG-MARA) is to provide a venue for the exchange of ideas in this area and to foster collaboration between different research groups. In this article we report on the first meeting of TFG-MARA, which was held as part of the Second AgentLink III Technical Forum in Ljubljana.

AAMAS Conference 2005 Conference Paper

Negotiating over Small Bundles of Resources

• Yann Chevaleyre
• Ulle Endriss
• J
• eacute; r
• ocirc; me Lang
• Nicolas Maudet

IJCAI Conference 2005 Conference Paper

On Maximal Classes of Utility Functions for Efficient one-to-one Negotiation

• Yann Chevaleyre
• Ulle Endriss
• Nicolas

We investigate the properties of an abstract negotiation framework where agents autonomously negotiate over allocations of discrete resources. In this framework, reaching an optimal allocation potentially requires very complex multilateral deals. Therefore, we are interested in identifying classes of utility functions such that any negotiation conducted by means of deals involving only a single resource at at time is bound to converge to an optimal allocation whenever all agents model their preferences using these functions. We show that the class of modular utility functions is not only sufficient but also maximal in this sense.