More Like this

1. Online Fair Allocation of Reusable Resources

   https://doi.org/10.1145/3727121  

   Liu, Qingsong; Hajiesmaili, Mohammad (May 2025, Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   Motivated by the emerging paradigm of resource allocation that integrates classical objectives, such as cost minimization, with societal objectives, such as carbon awareness, this paper proposes a general framework for the online fair allocation of reusable resources. Within this framework, an online decision-maker seeks to allocate a finite resource with capacityCto a sequence of requests arriving with unknown distributions of types, utilities, and resource usage durations. To accommodate diverse objectives, the framework supports multiple actions and utility types, and the goal is to achieve max-min fairness among utilities, i.e., maximize the minimum time-averaged utility across all utility types. Our performance metric is an (α,β)-competitive guarantee of the form: ALG ≥ α • OPT^*- O(T^β-1),; α, β ∈ (0, 1], where OPT^*and ALG are the time-averaged optimum and objective value achieved by the decision maker, respectively. We propose a novel algorithm that achieves a competitive guarantee of (1-O(√(log C/C)), 2/3) under the bandit feedback. As resource capacity increases, the multiplicative competitive ratio term 1-O(√ logC/C) asymptotically approaches optimality. Notably, when the resource capacity exceeds a certain threshold, our algorithm achieves an improved competitive guarantee of (1, 2/3). Our algorithm employs an optimistic penalty-weight mechanism coupled with a dual exploration-discarding strategy to balance resource feasibility, exploration, and fairness among utilities. 

   more » « less
2. Multi-Agent Maximization of a Monotone Submodular Function via Maximum Consensus

   https://doi.org/10.1109/CDC45484.2021.9682818  

   Rezazadeh, Navid; Kia, Solmaz S. (December 2021, IEEE Conference on Decision and Control)

   This paper studies distributed submodular optimization subject to partition matroid. We work in the value oracle model where the only access of the agents to the utility function is through a black box that returns the utility function value. The agents are communicating over a connected undirected graph and have access only to their own strategy set. As known in the literature, submodular maximization subject to matroid constraints is NP-hard. Hence, our objective is to propose a polynomial-time distributed algorithm to obtain a suboptimal solution with guarantees on the optimality bound. Our proposed algorithm is based on a distributed stochastic gradient ascent scheme built on the multilinear-extension of the submodular set function. We use a maximum consensus protocol to minimize the inconsistency of the shared information over the network caused by delay in the flow of information while solving for the fractional solution of the multilinear extension model. Furthermore, we propose a distributed framework of finding a set solution using the fractional solution. We show that our distributed algorithm results in a strategy set that when the team objective function is evaluated at worst case the objective function value is in 1−1/e−O(1/T) of the optimal solution in the value oracle model where T is the number of communication instances of the agents. An example demonstrates our results. 

   more » « less
3. An NDN-Enabled Fog Radio Access Network Architecture With Distributed In-Network Caching

   Taki, Sifat Ut; Mastorakis, Spyridon (January 2023, International Conference on Communications)

   To meet the increasing demands of next-generation cellular networks (e.g., 6G), advanced networking technologies must be incorporated. On one hand, the Fog Radio Access Network (F-RAN), has been proposed as an enhancement to the Cloud Radio Access Network (C-RAN). On the other hand, efficient network architectures, such as Named Data Networking (NDN), have been recognized as prominent Future Internet candidates. Nevertheless, the interplay between F-RAN and NDN warrants further investigation. In this paper, we propose an NDN-enabled F-RAN architecture featuring a strategy for distributed in-network caching. Through a simulation study, we demonstrate the superiority of the proposed in-network caching strategy in comparison with baseline caching strategies in terms of network resource utilization, cache hits, and front haul channel usage. 

   more » « less
4. Fair Allocation of Indivisible Goods: Improvement

   https://doi.org/10.1287/moor.2020.1096  

   Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi (August 2021, Mathematics of Operations Research)

   null (Ed.)

   We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive setting. They showed that in delicately constructed examples, not everyone can obtain a utility of at least her maximin value. They mitigated this impossibility result with a beautiful observation: no matter how the utility functions are made, we always can allocate the items to the agents to guarantee each agent’s utility is at least 2/3 of her maximin value. They left open whether this bound can be improved. Our main contribution answers this question in the affirmative. We improve their approximation result to a 3/4 factor guarantee. 

   more » « less
5. No-regret Caching via Online Mirror Descent

   https://doi.org/10.1145/3605209  

   Si Salem, Tareq; Neglia, Giovanni; Ioannidis, Stratis (December 2023, ACM Transactions on Modeling and Performance Evaluation of Computing Systems)

   We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small fraction of each file. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that bounds for the regret crucially depend on the diversity of the request process, provided by the diversity ratio R/h , where R is the size of the batch and h is the maximum multiplicity of a request in a given batch. We characterize the optimality of OMD caching policies w.r.t. regret under different diversity regimes. We also prove that, when the cache must store the entire file, rather than a fraction, OMD strategies can be coupled with a randomized rounding scheme that preserves regret guarantees, even when update costs cannot be neglected. We provide a formal characterization of the rounding problem through optimal transport theory, and moreover we propose a computationally efficient randomized rounding scheme. 

   more » « less