Publications
Generalized welfare lower bounds and strategyproofness in sequencing problems
with Parikshit De and Manipushpak Mitra · Social Choice and Welfare, 63(2): 323–357, 2024
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 “relative pivotal mechanisms”. We propose relevant theoretical applications, namely ex-ante initial order, identical costs bound and expected cost bound, and give insights on feasibility and budget balance.
Lorenz optimality for sequencing problems with welfare bounds
with Manipushpak Mitra · Economics Letters, 205: 109963, 2021
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.
Essays on sequencing problems with welfare bounds
PhD thesis, Indian Statistical Institute, 2022 · Supervisor: Prof. Manipushpak Mitra
Working papers
Jurisdictional Reward Funds for Tropical Forest Conservation
with Max Franks, Matthias Kalkuhl, Lennart Stern and Xuan Xie · SSRN Working Paper 6915562 · Circulating
Funded by the German Federal Ministry for Economic Cooperation and Development (BMZ) under the TRANSFORM project.
Efficient, Fair and Stable Agreements for Marine Plastic Pollution
with Christopher Stapenhurst · SSRN Working Paper 5033617 · Revise and resubmit, Journal of Environmental Economics and Management
Funded by the Sustainable Development and Technologies National Programme, Hungarian Academy of Sciences.
Abstract: In 2022, the UN Environment Assembly resolved to establish an international agreement for abating marine plastic pollution. We use data from 120 countries 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 policy. Surprisingly, we find 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 · SSRN Working Paper 5339395 · Revise and resubmit, European Journal of Operations Research
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. We show that the optimistic Shapley value aligns with the serial rule in multi-server queueing with divisible and indivisible jobs, and in multi-server scheduling with indivisible jobs, but not in multi-server scheduling with divisible jobs. The pessimistic Shapley value aligns with the reverse serial rule only for multi-server queueing; in multi-server scheduling it exhibits ‘order reversal’, whereas the reverse serial rule satisfies ‘order preservation’. We also characterize the serial and reverse serial rules for these classes of problems.
Queueing and scheduling problems with multiple servers
with Christian Trudeau · SSRN Working Paper 6269361 · Revise and resubmit, Mathematical Social Sciences
Abstract: We examine the implications of extending queueing and scheduling problems from the single-server to the multiple-server case, under three assumptions on job divisibility: indivisible, discretely divisible and continuously divisible jobs. We examine whether the corresponding optimistic and pessimistic cost functions satisfy convexity/concavity and 2-additivity. While all properties carry over in the continuously divisible case, many results do not carry over to the multiple-server case: 2-additivity does not carry over, and pessimistic functions are no longer concave. Optimistic functions retain convexity in most cases.
The accountable function: a new approach to scheduling problems
with Christian Trudeau · University of Windsor Working Paper 2507 · Ready for submission
Abstract: We study cooperative cost-sharing in scheduling problems where agents differ in job lengths but share identical waiting costs. The symmetry between optimistic and pessimistic cost functions, well established for queueing problems, breaks down for scheduling, and the pessimistic Shapley value rewards longer jobs. We propose an “accountable cost” of serving a coalition, under which coalition members are served first but internalize the externality imposed on non-members. The accountable cost game is concave and its Shapley value coincides with the decreasing serial rule, restoring the lost symmetry. We provide axiomatic characterizations of the optimistic and accountable Shapley values and explore multi-server extensions.
Shapley Value of Scheduling Games: Algorithms and Complexity
with Haris Aziz and Angus Ritossa · Submitted
Abstract: We consider scheduling problems with divisible jobs and multiple identical machines, where the cost of a coalition is the minimum sum of waiting times to serve all its members. Computing the Shapley value of the corresponding cooperative game is #P-complete; if the number of machines or the job lengths are represented in unary, there is a polynomial-time algorithm, and there exists a fully polynomial-time randomized approximation scheme.
Fairness and stability in weighted sequencing games
MPRA Paper 120188, University Library of Munich
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 its members are served first; the “pessimistic” cost is its minimum waiting cost when they are served last. Taking a weighted average of the two, we define “weighted optimistic–pessimistic (WOP)” cost games and find necessary and sufficient conditions on the weights for the core to be non-empty and for the Shapley value to lie in the core. We also impose upper bounds that protect agents against arbitrarily high disutilities from waiting, and find conditions under which the Shapley value conforms to them.
Work in progress
Offsets with endogenous government policy
with Nikolaj Moretti, Esteban Muñoz-Sobrado and Lennart Stern · In progress
When do the serial and Shapley solutions coincide?
with Christian Trudeau · Initial draft in preparation
Gains from income redistribution through progressive transfers
with Ramses H. Abul Naga · In progress
Scheduling with divisible jobs and multiple machines
with Christian Trudeau · In progress · Slides (preliminary results)