More Like this

1. Mechanism Design With Limited Commitment

   https://doi.org/10.3982/ECTA16846  

   Doval, Laura; Skreta, Vasiliki (July 2022, Econometrica)

   Lizzeri, Alessandro (Ed.)

   We develop a tool akin to the revelation principle for dynamic mechanism‐selection games in which the designer can only commit to short‐term mechanisms. We identify acanonicalclass of mechanisms rich enough to replicate the outcomes of any equilibrium in a mechanism‐selection game between an uninformed designer and a privately informed agent. A cornerstone of our methodology is the idea that a mechanism should encode not only the rules that determine the allocation, but also the information the designer obtains from the interaction with the agent. Therefore, how much the designer learns, which is the key tension in design with limited commitment, becomes an explicit part of the design. Our result simplifies the search for the designer‐optimal outcome by reducing the agent's behavior to a series of participation, truth telling, and Bayes' plausibility constraints the mechanisms must satisfy. 

   more » « less
2. Public and Private Affairs in Strategic Reasoning

   https://doi.org/10.24963/kr.2022/14  

   Fijalkow, Nathanaël; Maubert, Bastien; Murano, Aniello; Rubin, Sasha; Vardi, Moshe (July 2022, Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning)

   Do agents know each others’ strategies? In multi-process software construction, each process has access to the processes already constructed; but in typical human-robot interactions, a human may not announce its strategy to the robot (indeed, the human may not even know their own strategy). This question has often been overlooked when modeling and reasoning about multi-agent systems. In this work, we study how it impacts strategic reasoning.To do so we consider Strategy Logic (SL), a well-established and highly expressive logic for strategic reasoning. Its usual semantics, which we call “white-box semantics”, models systems in which agents “broadcast” their strategies. By adding imperfect information to the evaluation games for the usual semantics, we obtain a new semantics called “black-box semantics”, in which agents keep their strategies private. We consider the model-checking problem and show that the black-box semantics has much lower complexity than white-box semantics for an important fragment of Strategy Logic. 

   more » « less
3. Strategic-Agent Equilibria in the Operation of Natural Gas and Power Markets

   https://doi.org/10.3390/en13040868  

   Chen, Sheng; Conejo, Antonio J. (February 2020, Energies)

   We consider strategic gas/power producers and strategic gas/power consumers operating in both gas and power markets. We build a flexible multi-period complementarity model to characterize day-ahead equilibria in those markets. This model is an equilibrium program with equilibrium constraints that characterizes the market behavior of all market agents. Using a realistic case study, we analyze equilibria under perfect and oligopolistic competition. We also analyze equilibria under different levels of information disclosure regarding market outcomes. We study as well equilibria under different ownership schemes: no hybrid agent, some hybrid agents, and only hybrid agents. Finally, we derive policy recommendations for the regulators of both the gas and the power markets. 

   more » « less
4. Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty

   Shi, Laixi; Mazumdar, Eric; Chi, Yuejie; Wierman, Adam (July 2024, Proceedings of the 41st International Conference on Machine Learning)

   To overcome the sim-to-real gap in reinforcement learning (RL), learned policies must maintain robustness against environmental uncertainties. While robust RL has been widely studied in single-agent regimes, in multi-agent environments, the problem remains understudied-- despite the fact that the problems posed by environmental uncertainties are often exacerbated by strategic interactions. This work focuses on learning in distributionally robust Markov games (RMGs), a robust variant of standard Markov games, wherein each agent aims to learn a policy that maximizes its own worst-case performance when the deployed environment deviates within its own prescribed uncertainty set. This results in a set of robust equilibrium strategies for all agents that align with classic notions of game-theoretic equilibria. Assuming a non-adaptive sampling mechanism from a generative model, we propose a sample-efficient model-based algorithm (DRNVI) with finite-sample complexity guarantees for learning robust variants of various notions of game-theoretic equilibria. We also establish an information-theoretic lower bound for solving RMGs, which confirms the near-optimal sample complexity of DR-NVI with respect to problem-dependent factors such as the size of the state space, the target accuracy, and the horizon length. 

   more » « less
5. Leibniz International Proceedings in Informatics (LIPIcs):Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.26  

   Chawla, Shuchi; Gergatsouli, Evangelia; McMahan, Jeremy; Tzamos, Christos (January 2023, APPROX RANDOM)

   Megow, Nicole; Smith, Adam (Ed.)

   We revisit the classic Pandora’s Box (PB) problem under correlated distributions on the box values. Recent work of [Shuchi Chawla et al., 2020] obtained constant approximate algorithms for a restricted class of policies for the problem that visit boxes in a fixed order. In this work, we study the complexity of approximating the optimal policy which may adaptively choose which box to visit next based on the values seen so far. Our main result establishes an approximation-preserving equivalence of PB to the well studied Uniform Decision Tree (UDT) problem from stochastic optimization and a variant of the Min-Sum Set Cover (MSSC_f) problem. For distributions of support m, UDT admits a log m approximation, and while a constant factor approximation in polynomial time is a long-standing open problem, constant factor approximations are achievable in subexponential time [Ray Li et al., 2020]. Our main result implies that the same properties hold for PB and MSSC_f. We also study the case where the distribution over values is given more succinctly as a mixture of m product distributions. This problem is again related to a noisy variant of the Optimal Decision Tree which is significantly more challenging. We give a constant-factor approximation that runs in time n^Õ(m²/ε²) when the mixture components on every box are either identical or separated in TV distance by ε. 

   more » « less