Dr. Sreoshi Banerjee

Banerjee, Sreoshi, Parikshit De, and Manipushpak Mitra. "Generalized welfare lower bounds and strategyproofness in sequencing problems". Social Choice and Welfare (2024): 1-35. 

Abstract: In an environment with private information, we study the class of sequencing problems with welfare lower bounds. The “generalized welfare lower bound” represents some of the lower bounds that have been previously studied in the literature. Every agent is offered a protection in the form of a minimum guarantee on their utilities. We provide a necessary and sufficient condition to identify an outcome efficient and strategyproof mechanism that satisfies generalized welfare lower bound. We then characterize the entire class of mechanisms that satisfy outcome efficiency, strategyproofness and generalized welfare lower bound. These are termed as “relative pivotal mechanisms”. Our paper proposes relevant theoretical applications namely; ex-ante initial order, identical costs bound and expected cost bound. We also give insights on the issues of feasibility and/or budget balance. 

Banerjee, Sreoshi, and Manipushpak Mitra. "Lorenz optimality for sequencing problems with welfare bounds".  Economics Letters 205 (2021): 109963. 

Abstract: In the sequencing context, we explore the possibility of designing mechanisms which uphold the notion of justness and safeguard an agent’s individual interest. Every agent is guaranteed a minimum level of utility by imposing the generalized minimum welfare bound. Our main result shows that the constrained egalitarian mechanism is Lorenz optimal in the class of mechanisms that are feasible and satisfy the generalized minimum welfare bound.

Jurisdictional Reward Funds for Tropical Forest Conservation with Max Franks, Matthias Kalkuhl, Lennart Stern, and Xuan Xie. 

Offsets with Endogenous Government Policy with Nikolaj Moretti, Esteban Muñoz Sobrado, and Lennart Stern. 

E-FAST agreements for abating Marine Plastics Pollution with Christopher Stapenhurst, funded by the Sustainable Development and Technologies National Programme of the Hungarian Academy of Sciences.  (under review)

Abstract: In 2022, the UN environmental agency resolved to establish an international agreement for abating marine plastic pollution. We use data from 120 countries across the globe to derive an efficient abatement policy that maximises collective welfare. But this efficient policy is both unfair (poor countries bear the costs while rich countries reap the benefits) and unstable (the costs outweigh the benefits for some countries). Using new game-theoretic concepts, we design a “fair” and “stable” compensation scheme to redistribute the gains from the efficient Surprisingly, we discover that cooperation can sometimes make countries collectively worse off.

On the (non-) coincidence of the Serial and Shapley solutions in multi-server waiting line problems with Christian Trudeau.

Abstract:  The existing literature on single-server waiting line problems—including sequencing, queueing, and scheduling—has traditionally designed equitable compensations by modeling each problem as a transferable utility (TU) game and assigning agents their respective Shapley payoffs. This paper demonstrates that, in more general settings, it is equally crucial to study the ‘serial’ and ‘reverse serial’ cost-sharing rules. Specifically, we show that the recommendation of the optimistic Shapley value aligns with the serial rule in the following cases: (1) multi-server queueing with divisible and indivisible jobs; and (2) multi-server scheduling with indivisible jobs. However, this coincidence fails in the case of multi-server scheduling with divisible jobs. Furthermore, we establish that the recommendation of the pessimistic Shapley value aligns with the reverse serial rule only for multi-server queueing with both divisible and indivisible jobs. This coincidence breaks down for multi-server scheduling with either divisible or indivisible jobs. Notably, in this latter scenario, the pessimistic Shapley value exhibits an undesirable property known as ’order reversal,’ in contrast to the reverse serial rule, which satisfies ’order preservation.’ We also provide characterizations of the serial and reverse serial rules for the above-mentioned classes of problems.

Complexity of the Shapley Value of Scheduling Games with Haris Aziz. (under review)
(available on request)

Abstract: We consider scheduling games that involve a given number of identical machines and a set of agents, each with its own job of a certain length. The jobs are divisible, and one unit of a job is processed by a machine is one time step. The cost of a single agent is the time taken to process its job completely. The cost of a coalition of agents is the minimum total cost to serve the agents. The Shapley value is well-known to coincide the Serial Rule of Moulin and Shenker when there is a single machine. Recently, it has been shown that this coincidence disappears when there are multiple identical machines. We examine the complexity of the Shapley value in such settings.

Fairness and stability in weighted sequencing games 

Abstract: We model sequencing problems as coalitional games and study the Shapley value and the non-emptiness of the core. The ”optimistic” cost of a coalition is its minimum waiting cost when the members are served first in an order. The ”pessimistic” cost of a coalition is its minimum waiting cost when the members are served last. We take the weighted average of the two extremes and define the class of ”weighted optimistic pessimistic (WOP)” cost games. If the weight is zero, we get the optimistic scenario, and if it is one, we get the pessimistic scenario. We find a necessary and sufficient condition on the associated weights for the core to be non-empty. We also find a necessary and sufficient condition on these weights for the Shapley value to be an allocation in the core. We impose ”upper bounds” to protect agents against arbitrarily high disutilities from waiting. If an agent’s disutility level is his Shapley payoff from the WOP cost game, we find necessary and sufficient conditions on the upper bounds for the Shapley value to conform to them. 

Fairness and stability in sequencing games: optimistic and pessimistic approaches 

Abstract: Sequencing deals with the problem of assigning slots to agents who are waiting for a service. We study sequencing problems as coalition form games defined in optimistic and pessimistic scenarios. Each agent’s level of utility is his Shapley value payoff from the corresponding coalition form game. First, we show that while the core of the optimistic game is always empty, the Shapley value of the pessimistic game is an allocation in its core. Second, we impose the ”generalized welfare lower bound” (GWLB) that ex-ante guarantees each agent a minimum level of utility. One of many application of GWLB is the ”expected costs bound”. It guarantees each agent his expected cost when all arrival orders are equally likely. We prove that the Shapley value payoffs (in both optimistic and pessimistic scenarios) satisfy GWLB if and only if it satisfies the expected costs bound (ECB).  

Scheduling with divisible jobs and multiple machines (with Christian Trudeau).  Slides (preliminary results) 

Abstract: We consider the problem of scheduling jobs over multiple machines, with agents having the same waiting costs per period, but different job lengths. However, we suppose that jobs are divisible, meaning that a job of length l can be interpreted as l jobs of length one. As an example, consider printing jobs, which can be processed over multiple printers simultaneously. We contrast with the traditional assumption of indivisible jobs. The resulting optimal schedule is very simple: we process the shortest job on all machines simultaneously until completed, then the second shortest, etc. We then study how to share the costs. We define the optimistic (a coalition has first access to the machines) and pessimistic (a coalition comes after its complement set) TU-games and provide closed-form solutions for their respective Shapley values and the transfers they imply. We then examine the (anti) cores and examine various core sharing methods. 

Gains from income redistribution through progressive transfers (with Ramses Abul Naga).