Drashthi Doshi

Ashwin Goyal, Drashthi Doshi, Swaprava Nath

Motivated by the fact that the worth of a coalition may depend on the order in which agents arrive, Nowak and Radzik (1994) (NR) introduced cooperative games with generalized characteristic functions. We study such temporal cooperative games (TCGs), where the worth function v is defined on sequences of agents π rather than sets S. This order sensitivity necessitates a re-examination of axioms for reward sharing. NR and subsequent work proposed several axioms; the resulting solution concepts are still inherently order-oblivious and closely tied to the Shapley value. In contrast, we focus on sequential solution concepts that explicitly depend on the realized order π. We study reward-sharing mechanisms satisfying incentive for optimal arrival (I4OA), which promotes orders maximizing total worth; online individual rationality (OIR), which ensures agents are not harmed by later arrivals; and sequential efficiency (SE), which requires that the worth of any sequence is fully distributed among its agents. These axioms are intrinsic to TCGs, and we characterize a class of reward-sharing mechanisms uniquely determined by them. The classical Shapley value does not directly extend to this setting. We therefore construct natural Shapley analogs in two worlds: a sequential world, where rewards are defined for each sequence agent pair, and an extended world, where rewards are defined per agent, consistent with the NR framework. In both cases, the axioms of efficiency, additivity, and null player uniquely characterize the corresponding Shapley analogs. But, these Shapley analogs are disjoint from the class of solutions satisfying the sequential axioms, even for convex and simple TCGs.

Drashthi Doshi, Aditya Vema Reddy Kesari, Avishek Ghosh et al.

Classical federated learning (FL) assumes that the clients have a limited amount of noisy data with which they voluntarily participate and contribute towards learning a global, more accurate model in a principled manner. The learning happens in a distributed fashion without sharing the data with the center. However, these methods do not consider the incentive of an agent for participating and contributing to the process, given that data collection and running a distributed algorithm is costly for the clients. The question of rationality of contribution has been asked recently in the literature and some results exist that consider this problem. This paper addresses the question of simultaneous parameter learning and incentivizing contribution in a truthful manner, which distinguishes it from the extant literature. Our first mechanism incentivizes each client to contribute to the FL process at a Nash equilibrium and simultaneously learn the model parameters. We also ensure that agents are incentivized to truthfully reveal information in the intermediate stages of the algorithm. However, this equilibrium outcome can be away from the optimal, where clients contribute with their full data and the algorithm learns the optimal parameters. We propose a second mechanism that enables the full data contribution along with optimal parameter learning. Large scale experiments with real (federated) datasets (CIFAR-10, FEMNIST, and Twitter) show that these algorithms converge quite fast in practice, yield good welfare guarantees and better model performance for all agents.