Julien Lesca

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.

IJCAI Conference 2025 Conference Paper

Online Housing Market

• Julien Lesca

We study an online variant of the celebrated housing market problem, where each agent owns a single house and seeks to exchange it based on her preferences. In this online setting, agents may arrive and depart at any time, meaning not all agents are present in the housing market simultaneously. We extend the well-known serial dictatorship and top trading cycle mechanisms to the online scenario, aiming to retain their desirable properties, such as Pareto efficiency, individual rationality, and strategy-proofness. These extensions also seek to prevent agents from strategically delaying their arrivals or advancing their departures. We demonstrate that achieving all these properties simultaneously is impossible and present several variants that achieve different subsets of these properties.

TCS Journal 2025 Journal Article

Worst-case fair guarantees when spending a common budget

• Pierre Cardi
• Laurent Gourvès
• Julien Lesca

JAAMAS Journal 2023 Journal Article

Hardness of candidate nomination

• Katarína Cechlárová
• Julien Lesca
• Jozef Hanč

Abstract We consider elections where the set of candidates is split into parties and each party can nominate just one candidate. We study the computational complexity of two problems. The Possible President problem asks whether a given party candidate can become the unique winner of the election for some nominations from other parties. The Necessary President is the problem to decide whether a given candidate will be the unique winner of the election for any possible nominations from other parties. We consider several different voting rules and show that for all of them the Possible President problem is NP-complete, even if the size of each party is at most two; for some voting rules we prove that the Necessary President is coNP-complete. Further, we formulate integer programs to solve the Possible President and Necessary President problems and test them on real and artificial data.

AAMAS Conference 2022 Conference Paper

On Fair and Efficient Solutions for Budget Apportionment

• Pierre Cardi
• Laurent Gourves
• Julien Lesca

This works deals with an apportionment problem recently introduced in [9]. In this problem involving multiple agents, it is desirable to propose fair and efficient solutions. Several alternative notions of fairness exist but combining efficiency with fairness is often impossible, and a trade-off has to be made. We first study the computation of almost fair and approximately efficient solutions, and we determine when these two goals can be met. Afterwards, we characterize the price of fairness which bounds the loss of efficiency caused by imposing fairness or one of its relaxations.

AAMAS Conference 2022 Conference Paper

Selecting PhD Students and Projects with Limited Funding

• Jatin Jindal
• Jérôme Lang
• Katarína Cechlárová
• Julien Lesca

In some universities, there is a fixed number of PhD grants, but a larger number of eligible projects and students, each student being allowed to apply on several projects, and a committee builds up a ranking (masterlist) over student-project pairs. The paper analyses three mechanisms to choose the pairs to be funded. The first one, used in some universities, is a greedy mechanism that gives a huge priority to the masterlist and very little to student’s preferences. At the other extremity of the spectrum, we have a priority-list variant of student-oriented Gale-Shapley. It is strategyproof and optimal for students, but has one drawback: it pays too little attention to the masterlist, and thus to the committee. Inbetween, we have an intermediate mechanism which can be seen as a good tradeoff. Among the properties we study, one is specific to our setting: dynamic monotonicity, which deals with cases when a student suddenly leaves the system in the middle of the process.

AAAI Conference 2021 Conference Paper

A Market-Inspired Bidding Scheme for Peer Review Paper Assignment

• Reshef Meir
• Jérôme Lang
• Julien Lesca
• Nicholas Mattei
• Natan Kaminsky

We propose a market-inspired bidding scheme for the assignment of paper reviews in large academic conferences. We provide an analysis of the incentives of reviewers during the bidding phase, when reviewers have both private costs and some information about the demand for each paper; and their goal is to obtain the best possible k papers for a predetermined k. We show that by assigning ‘budgets’ to reviewers and a ‘price’ for every paper that is (roughly) proportional to its demand, the best response of a reviewer is to bid sincerely, i. e. , on her most favorite papers, and match the budget even when it is not enforced. This game-theoretic analysis is based on a simple, prototypical assignment algorithm. We show via extensive simulations on bidding data from real conferences, that our bidding scheme would substantially improve both the bid distribution and the resulting assignment.

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.

JAAMAS Journal 2019 Journal Article

Chore division on a graph

• Sylvain Bouveret
• Katarína Cechlárová
• Julien Lesca

Abstract The paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent’s share has to form a connected subgraph of this graph. Although a similar model has been investigated before for goods, we show that the goods and chores settings are inherently different. In particular, it is impossible to derive the solution of the chores instance from the solution of its naturally associated fair division instance. We consider three common fair division solution concepts, namely proportionality, envy-freeness and equitability, and two individual disutility aggregation functions: additive and maximum based. We show that deciding the existence of a fair allocation is hard even if the underlying graph is a path or a star. We also present some efficiently solvable special cases for these graph topologies.

TCS Journal 2019 Journal Article

Efficient reallocation under additive and responsive preferences

• Haris Aziz
• Péter Biró
• Jérôme Lang
• Julien Lesca
• Jérôme Monnot

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.

JAIR Journal 2018 Journal Article

A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences

• Etsushi Fujita
• Julien Lesca
• Akihisa Sonoda
• Taiki Todo
• Makoto Yokoo

Core-selection is a crucial property of rules in the literature of resource allocation. It is also desirable, from the perspective of mechanism design, to address the incentive of agents to cheat by misreporting their preferences. This paper investigates the exchange problem where (i) each agent is initially endowed with (possibly multiple) indivisible goods, (ii) agents' preferences are assumed to be conditionally lexicographic, and (iii) side payments are prohibited. We propose an exchange rule called augmented top-trading-cycles (ATTC), based on the original TTC procedure. We first show that ATTC is core-selecting and runs in polynomial time with respect to the number of goods. We then show that finding a beneficial misreport under ATTC is NP-hard. We finally clarify relationship of misreporting with splitting and hiding, two different types of manipulations, under ATTC.

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.

IJCAI Conference 2018 Conference Paper

Service Exchange Problem

• Julien Lesca
• Taiki Todo

In this paper, we study the service exchange problem where each agent is willing to provide her service in order to receive in exchange the service of someone else. We assume that agent's preference depends both on the service that she receives and the person who receives her service. This framework is an extension of the housing market problem to preferences including a degree of externalities. We investigate the complexity of computing an individually rational and Pareto efficient allocation of services to agents for ordinal preferences, and the complexity of computing an allocation which maximizes either the utility sum or the utility of the least served agent for cardinal preferences.

AAMAS Conference 2017 Conference Paper

Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets

• Julien Lesca
• Patrice Perny
• Makoto Yokoo

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.

IJCAI Conference 2016 Conference Paper

How Hard Is It for a Party to Nominate an Election Winner?

• Piotr Faliszewski
• Laurent Gourv
• egrave; s
• ocirc; me Lang
• Julien Lesca
• J
• eacute; r
• ocirc; me Monnot

We consider a Plurality-voting scenario, where the candidates are split between parties, and each party nominates exactly one candidate for the final election. We study the computational complexity of deciding if there is a set of nominees such that a candidate from a given party wins in the final election. In our second problem, the goal is to decide if a candidate from a given party always wins, irrespective who is nominated. We show that these problems are computationally hard, but are polynomial-time solvable for restricted settings.

AAMAS Conference 2016 Conference Paper

Optimal Reallocation Under Additive and Ordinal Preferences

• Haris Aziz
• Péter Biró
• Jérôme Lang
• Julien Lesca
• Jérôme Monnot

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over single objects, and that their preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality. General Terms Economics, Theory and Algorithms

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.

AAAI Conference 2015 Conference Paper

A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences

• Etsushi Fujita
• Julien Lesca
• Akihisa Sonoda
• Taiki Todo
• Makoto Yokoo

Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents’ preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.

IJCAI Conference 2013 Conference Paper

Dominance Rules for the Choquet Integral in Multiobjective Dynamic Programming

• Lucie Galand
• Julien Lesca
• Patrice Perny

Multiobjective Dynamic Programming (MODP) is a general problem solving method used to determine the set of Pareto-optimal solutions in optimization problems involving discrete decision variables and multiple objectives. It applies to combinatorial problems in which Pareto-optimality of a solution extends to all its sub-solutions (Bellman principle). In this paper we focus on the determination of the preferred tradeoffs in the Pareto set where preference is measured by a Choquet integral. This model provides high descriptive possibilities but the associated preferences generally do not meet the Bellman principle, thus preventing any straightforward adaptation of MODP. To overcome this difficulty, we introduce here a general family of dominance rules enabling an early pruning of some Pareto-optimal sub-solutions that cannot lead to a Choquet optimum. Within this family, we identify the most efficient dominance rules and show how they can be incorporated into a MODP algorithm. Then we report numerical tests showing the actual efficiency of this approach to find Choquet-optimal tradeoffs in multiobjective knapsack problems.

ECAI Conference 2012 Conference Paper

Almost-truthful Mechanisms for Fair Social Choice Functions

• Julien Lesca
• Patrice Perny

This paper deals with the implementation of Social Choice Functions in fair multiagent decision problems. In such problems the determination of the best alternatives often relies on the maximization of a non-utilitarian Social Welfare Function so as to account for equity. However, in such decision processes, agents may have incentive to misreport their preferences to obtain more favorable choices. It is well known that, for Social Choice Functions based on the maximization of an affine aggregator of individual utilities, we can preclude any manipulation by introducing payments (VCG mechanisms). Unfortunately such truthful mechanisms do not exist for non-affine maximizers (Roberts' Theorem). For this reason, we introduce here a notion of "almost-truthfulness" and investigate the existence of payments enabling the elaboration of almost-truthful mechanisms for non-additive Social Welfare Functions such as Social Gini Evaluation Functions used in fair optimization.

ECAI Conference 2010 Conference Paper

LP Solvable Models for Multiagent Fair Allocation Problems

• Julien Lesca
• Patrice Perny

This paper proposes several operational approaches for solving fair allocation problems in the context of multiagent optimization. These problems arise in various contexts such as assigning conference papers to referees or sharing of indivisible goods among agents. We present and discuss various social welfare functions that might be used to maximize the satisfaction of agents while maintaining a notion of fairness in the distribution. All these welfare functions are in fact non-linear, which precludes the use of classical min-cost max-flow algorithms for finding an optimal allocation. For each welfare function considered, we present a Mixed Integer Linear Programming formulation of the allocation problem that can be efficiently solved using standard solvers. The results of numerical tests we conducted on realistic cases are given at the end of the paper to confirm the practical feasibility of the proposed approaches.