Search for: All records

We consider a dynamic system with multiple types of customers and servers. Each type of waiting customer or server joins a separate queue, forming a bipartite graph with customer-side queues and server-side queues. The platform can match the servers and customers and then the matched pairs leave the system. The platform will charge a customer a price according to their type when they arrive and will pay a server a price according to their type. The arrival rate of each queue is determined by the price according to some unknown demand or supply functions. Our goal is to design pricing and matching algorithms to maximize the profit of the platform with unknown demand and supply functions while keeping queue lengths of both customers and servers below a predetermined threshold. The difficulties of the problem include simultaneous learning and decision making and the tradeoff between maximizing profit and minimizing queue length. We use a longest-queue-first matching algorithm and propose a learning-based pricing algorithm, which combines gradient-free stochastic projected gradient ascent with bisection search. We prove that our proposed algorithm yields a sublinear regret [Formula: see text] and queue-length bound [Formula: see text], where T is the time horizon. We further establish a tradeoff between the regret bound and the queue-length bound. Funding: This research was supported in part by the National Science Foundation [Grants 2112471, 2207548, 2228974, and 2240981]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/stsy.2024.0073 . 

Constrained decentralized team prob- lem formulations are good models for many coop- erative multi-agent systems. Constraints necessitate randomization when solving for optimal solutions— past results show that joint randomization in the team is in general necessary for (strong) Lagrangian duality to hold—, but a better understanding of randomization still remains. For a partially observed multi-agent system with a Borel hidden state, count- able observations, and finite actions, we prove the following: i) independently randomized decentralized policy-profiles—whether behavioral or pure—induce the same occupation measures (on joint-history and joint-action pairs) as decentralized behavioral policy- profiles; and ii) jointly randomized behavioral and pure decentralized policy-profiles induce the same occupation measures. Restricting to finite observa- tions, we also prove that joint mixtures of decen- tralized policy-profiles (both pure and behavioral) and common information based behavioral coordi- nation policies (also mixtures of them) induce the same occupation measures. This generalizes past work that shows equivalence between pure decentralized policy-profiles and pure coordination policies. These results can be used to develop further results on Lagrangian duality, the minimum number of randomizations needed in an optimal behavioral coordination policy, and learning based schemes that can find approximately optimal solutions. 

One of the reasons why stochastic dynamic games with an underlying dynamic system are challenging is because strategic players have access to enormous amount of information which leads to the use of extremely complex strategies at equilibrium. One approach to resolve this challenge is to simplify players’ strategies by identifying appropriate com- pression of information maps so that the players can make decisions solely based on the compressed version of information, called the information state. Such maps allow players to implement their strategies efficiently. For finite dynamic games with asymmetric infor- mation, inspired by the notion of information state for single-agent control problems, we propose two notions of information state, namely mutually sufficient information (MSI) and unilaterally sufficient information (USI). Both these information states are obtained by applying information compression maps that are independent of the strategy profile. We show that Bayes-Nash Equilibria (BNE) and Sequential Equilibria (SE) exist when all players use MSI-based strategies. We prove that when all players employ USI-based strategies, the resulting sets of BNE and SE payoff profiles are the same as the sets of BNE and SE payoff profiles resulting when all players use full information-based strategies. We prove that when all players use USI-based strategies the resulting set of weak Perfect Bayesian Equilibrium (wPBE) payoff profiles can be a proper subset of all wPBE payoff profiles. We identify MSI and USI in specific models of dynamic games in the literature. We end by presenting an open problem: Do there exist strategy-dependent information compression maps that guarantee the existence of at least one equilibrium or maintain all equilibria that exist under perfect recall? We show, by a counterexample, that a well- known strategy-dependent information compression map used in the literature does not possess any of the properties of the strategy-independent compression maps that result in MSI or USI.