Fair Allocation of Indivisible Chores: Beyond Additive Valuations

---

Dr. Bo Li

Department of Computing at The Hong Kong Polytechnic University.

Abstract. Discrete fair division has recently attracted significant attention, driven by its real-world applications and theoretical complexities. A key difficulty is that the traditional fairness concepts cannot be satisfied. Among the various concepts proposed to address this issue, maximin share (MMS) fairness is one of the most popular and widely accepted. While MMS fairness has been extensively studied and well understood in the context of allocating goods, its application to chores—especially under non-additive valuations—remains less explored.

In this work, we first provide a fundamental hardness result: no algorithm can guarantee better than a \( \min\!\left\{ n, \frac{\log m}{\log \log m} \right\} \)-approximation when agents have binary submodular cost functions, where \( m \) is the number of chores and \( n \) is the number of agents. This result shows a sharp contrast with the allocation of goods, where constant approximations exist even for general submodular valuations. We then prove that for arbitrary subadditive cost functions, there always exists an allocation that is \( \min\!\{ n, \lceil \log m \rceil \} \)-approximation, and thus the approximation ratio is asymptotically tight.

We then shift our focus to concrete combinatorial settings where the valuations are subadditive. In particular, we consider three well-motivated models: vertex cover, job scheduling, and bin packing. For the vertex cover model, each agent incurs a cost for selecting vertices that cover the edges (viewed as items) assigned to them. For the job scheduling model, each agent manages a set of (unrelated) machines to process the jobs (viewed as items) allocated to them. For the bin packing model, each agent must pack their allocated items into bins, incurring a cost based on the number of bins used. For each model, we design algorithms and prove that constant approximate MMS can be guaranteed, and we also provide matched lower bounds on the best-possible approximations.

Biography. Bo Li is an assistant professor in the Department of Computing at The Hong Kong Polytechnic University. Formerly, he was a Postdoctoral Fellow at the University of Oxford and the University of Texas at Austin. He received his Ph.D. in Computer Science from Stony Brook University and B.S. in Applied Maths from Ocean University of China. He is broadly interested in algorithms and game theory, including problems related to algorithmic game theory, computational social choice, fair division, and approximation and online algorithms.

(Distributed) AI for Interdependent Cyberphysical Systems

---

M. Hadi Amini, Ph.D., D.Eng.

Associate Professor, Knight Foundation School of Computing and Information Sciences, Florida International University.

Abstract. Increasing integration of advanced computing and communication technologies requires secure and efficient computational methods to deal with complex decision-making problems. In the centralized settings, there is a need for control centers to solve large-scale learning and optimization problems on behalf of end-users, which increases the computational complexity and requires extensive information sharing.

This talk presents a comprehensive overview of the role of (distributed) AI for interdependent cyber physical systems, where interdependencies among networks, ranging from power and transportation infrastructures to public safety, pose unique challenges for real-time decision-making and learning. The first part of this talk is devoted to motivating development of distributed/decentralized learning methods for interdependent decision making. These algorithms introduce major advantages as compared with centralized solutions, such as reducing the computational complexity of the large-scale machine learning problems and enabling scalability. Second part of this talk is devoted to two major research contributions of our group: First, Coupled Learning and Optimization for Interdependent Networks, where we introduce decentralized optimization and reinforcement learning algorithms that account for network inter dependencies and physical constraints. Second, AI for Public Safety, focusing on how we can leverage AI to identify anomalous activities. The final part of the talk outlines emerging directions, particularly in Securing and Decentralizing Large Language Models (LLMs) as two promising research areas.

Biography. Dr. M. Hadi Amini is an Associate Professor at the Knight Foundation School of Computing and Information Sciences at Florida International University. He is the founding director of Security, Optimization, and Learning for InterDependent networks laboratory (www.solidlab.network) and Associate Director of the USDOT National Center for Transportation Cybersecurity and Resiliency (TraCR). He received his Ph.D. in Electrical and Computer Engineering from Carnegie Mellon University in 2019. He conducts research in federated learning, distributed optimization and learning algorithms, and their applications in real-world problems, such as cybersecurity, interdependent cyber physical systems, and public safety. He received the 2025 IEEE Big Data Security Junior Research Award for contributions to Big Data Security in Cyber Physical Systems. He was selected as one of the Rising Stars (Science) by The Academy of Science, Engineering and Medicine of Florida (ASEMFL) for pioneering research in bridging the gap between computing sciences (learning and optimization) and cyber-physical critical infrastructures security and resilience in 2025. He was elevated to Senior Member of IEEE in 2022, and is a recipient of the Best Paper Award from “2019 IEEE Conference on Computational Science & Computational Intelligence”, the 2021 Best Journal Paper Award from “Springer Nature Operations Research Forum Journal”, 2025 FIU College of Engineering and Computing Faculty Excellence in Mentorship Award, 2024 FIU Top Scholar Award, Research and Creative Activities (Sciences), and the 2023 FIU “Faculty Senate Excellence in Teaching Award”. He serves as Associate Editor of IEEE Transactions on Information Forensics and Security, and IEEE Transactions on Machine Learning in Communications and Networking.