More Like this

1. Platforms for Efficient and Incentive-Aware Collaboration

   Haghtalab, Nika; Qiao, Mingda; Yang, Kunhe (January 2025, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM)

   Collaboration is crucial for reaching collective goals. However, its effectiveness is often undermined by the strategic behavior of individual agents -- a fact that is captured by a high Price of Stability (PoS) in recent literature [Blum et al., 2021]. Implicit in the traditional PoS analysis is the assumption that agents have full knowledge of how their tasks relate to one another. We offer a new perspective on bringing about efficient collaboration among strategic agents using information design. Inspired by the growing importance of collaboration in machine learning (such as platforms for collaborative federated learning and data cooperatives), we propose a framework where the platform has more information about how the agents' tasks relate to each other than the agents themselves. We characterize how and to what degree such platforms can leverage their information advantage to steer strategic agents toward efficient collaboration. Concretely, we consider collaboration networks where each node is a task type held by one agent, and each task benefits from contributions made in their inclusive neighborhood of tasks. This network structure is known to the agents and the platform, but only the platform knows each agent's real location -- from the agents' perspective, their location is determined by a random permutation. We employ private Bayesian persuasion and design two families of persuasive signaling schemes that the platform can use to ensure a small total workload when agents follow the signal. The first family aims to achieve the minmax optimal approximation ratio compared to the optimal collaboration, which is shown to be Θ(n‾√) for unit-weight graphs, Θ(n2/3) for graphs with constant minimum edge weights, and O(n3/4) for general weighted graphs. The second family ensures per-instance strict improvement compared to full information disclosure. 

   more » « less
2. Platforms for Efficient and Incentive-Aware Collaboration

   Haghtalab, Nika; Qiao, Mingda; Yang, Kunhe (January 2025, ACM-SIAM Symposium on Discrete Algorithms (SODA 2025))

   Collaboration is crucial for reaching collective goals. However, its potential for effectiveness is often undermined by the strategic behavior of individual agents — a fact that is captured by a high Price of Stability (PoS) in recent literature [BHPS21]. Implicit in the traditional PoS analysis is the assumption that agents have full knowledge of how their tasks relate to one another. We offer a new perspective on bringing about efficient collaboration across strategic agents using information design. Inspired by the increasingly important role collaboration plays in machine learning (such as platforms for collaborative federated learning and data cooperatives), we propose a framework in which the platform possesses more information about how the agents’ tasks relate to each other than the agents themselves. Our results characterize how and to what degree such platforms can leverage their information advantage and steer strategic agents towards efficient collaboration. Concretely, we consider collaboration networks in which each node represents a task type held by one agent, and each task benefits from contributions made to the task itself and its neighboring tasks. This network structure is known to the agents and the platform. On the other hand, the real location of each agent in the network is known to the platform only — from the perspective of the agents, their location is determined by a uniformly random permutation. We employ the framework of private Bayesian persuasion and design two families of persuasive signaling schemes that the platform can use to guarantee a small total workload when agents follow the signal. The first family aims to achieve the minmax optimal approximation ratio compared to the total workload in the optimal collaboration, which is shown to be for unit-weight graphs, for graphs with edge weights lower bounded by Ω(1), and for general weighted graphs. The second family ensures per-instance strict improvement in the total workload compared to scenarios with full information disclosure. 

   more » « less
3. Towards Collaborative Plan Acquisition through Theory of Mind Modeling in Situated Dialogue

   https://doi.org/10.24963/ijcai.2023/330  

   Bara, Cristian-Paul; M, Ziqiao; Yu, Yingzhuo; Shah, Julie; Chai, Joyce (August 2023, 2023 International Joint Conferences on Artificial Intelligence)

   Collaborative tasks often begin with partial task knowledge and incomplete initial plans from each partner. To complete these tasks, agents need to engage in situated communication with their partners and coordinate their partial plans towards a complete plan to achieve a joint task goal. While such collaboration seems effortless in a human-human team, it is highly challenging for human-AI collaboration. To address this limitation, this paper takes a step towards collaborative plan acquisition, where humans and agents strive to learn and communicate with each other to acquire a complete plan for joint tasks. Specifically, we formulate a novel problem for agents to predict the missing task knowledge for themselves and for their partners based on rich perceptual and dialogue history. We extend a situated dialogue benchmark for symmetric collaborative tasks in a 3D blocks world and investigate computational strategies for plan acquisition. Our empirical results suggest that predicting the partner's missing knowledge is a more viable approach than predicting one's own. We show that explicit modeling of the partner's dialogue moves and mental states produces improved and more stable results than without. These results provide insight for future AI agents that can predict what knowledge their partner is missing and, therefore, can proactively communicate such information to help their partner acquire such missing knowledge toward a common understanding of joint tasks. 

   more » « less
4. A Mechanism Design Approach to Vendor Managed Inventory

   https://doi.org/10.1287/mnsc.2019.3297  

   Kadiyala, Bharadwaj; Özer, Özalp; Bensoussan, Alain (October 2019, Management Science)

   This paper studies an inventory management problem faced by an upstream supplier that is in a collaborative agreement, such as vendor-managed inventory (VMI), with a retailer. A VMI partnership provides the supplier an opportunity to manage in- ventory for the supply chain in exchange for point-of-sales (POS)- and inventory-level information from the retailer. However, retailers typically possess superior local market information and as has been the case in recent years, are able to capture and analyze customer purchasing behavior beyond the traditional POS data. Such analyses provide the retailer access to market signals that are otherwise hard to capture using POS information. We show and quantify the implication of the financial obligations of each party in VMI that renders communication of such important market signals as noncredible. To help insti- tute a sound VMI collaboration, we propose learn and screen—a dynamic inventory mechanism—for the supplier to effectively manage inventory and information in the supply chain. The proposed mechanism combines the ability of the supplier to learn about market conditions from POS data (over multiple selling periods) and dynamically de- termine when to screen the retailer and acquire his private demand information. Inventory decisions in the proposed mechanism serve a strategic purpose in addition to their classic role of satisfying customer demand. We show that our proposed dynamic mechanism significantly improves the supplier’s expected profit and increases the efficiency of the overall supply chain operations under a VMI agreement. In addition, we determine the market conditions in which a strategic approach to VMI results in significant profit im- provements for both firms, particularly when the retailer has high market power (i.e., when the supplier highly depends on the retailer) and when the supplier has relatively less knowledge about the end customer/market compared with the retailer. 

   more » « less
5. Information Design in Spatial Resource Competition

   Yang, Pu; Iyer, Krishnamurthy; Frazier, Peter I. (December 2019, Lecture notes in computer science)

   We consider information design in spatial resource competition, motivated by ride sharing platforms sharing information with drivers about rider demand. Each of N co-located agents (drivers) decides whether to move to another location with an uncertain and possibly higher resource level (rider demand), where the utility for moving increases in the resource level and decreases in the number of other agents that move. A principal who can observe the resource level wishes to share this information in a way that ensures a welfare-maximizing number of agents move. Analyzing the principal’s information design problem using the Bayesian persuasion framework, we study both private signaling mechanisms, where the principal sends personalized signals to each agent, and public signaling mechanisms, where the principal sends the same information to all agents. We show: 1) For private signaling, computing the optimal mechanism using the standard approach leads to a linear program with 2 N variables, rendering the computation challenging. We instead describe a computationally efficient two-step approach to finding the optimal private signaling mechanism. First, we perform a change of variables to solve a linear program with O(N^2) variables that provides the marginal probabilities of recommending each agent move. Second, we describe an efficient sampling procedure over sets of agents consistent with these optimal marginal probabilities; the optimal private mechanism then asks the sampled set of agents to move and the rest to stay. 2) For public signaling, we first show the welfare-maximizing equilibrium given any common belief has a threshold structure. Using this, we show that the optimal public mechanism with respect to the sender-preferred equilibrium can be computed in polynomial time. 3) We support our analytical results with numerical computations that show the optimal private and public signaling mechanisms achieve substantially higher social welfare when compared with no-information and full-information benchmarks. 

   more » « less