Search

Paid curbside parking can be advantageously modeled as a network of interdependent queues. To this end, we introduce methods for analyzing a special class of networks of finite capacity queues where drivers arrive from an exogenous source, join the queue if there is an available parking space, or continue to search at an adjacent queue for an available space. Furthermore, we apply this model to estimate the proportion of drivers cruising in the neighborhood of Belltown, Seattle, WA, USA. Using occupancy approximated by parking transaction data, we estimate the percentage of drivers cruising for curbside parking by comparing the rate of drivers unable to find parking to bulk through-traffic measurement data. We find percentages of up to 50% for a Belltown’s 1st Ave. depending on the time, day, and direction of travel. We then calculate a per vehicle travel-time cost to social welfare incurred by this proportion: upward of a 10% increase in travel time to all drivers along 1st Ave. Last, we introduce a simulation tool and test assumptions made when estimating interesting performance metrics like the probability of a block-face being full. Our results suggest that while assuming exponential service time distributions is not justified, mean rate solutions under a Markovian relaxation of the problem is comparable to service times representative of parking transaction data in simulation.

Learning processes in games explain how players grapple with one another in seeking an equilibrium. We study a natural model of learning based on individual gradients in two-player continuous games. In such games, the arguably natural notion of a local equilibrium is a differential Nash equilibrium. However, the set of locally exponentially stable equilibria of the learning dynamics do not necessarily coincide with the set of differential Nash equilibria of the corresponding game. To characterize this gap, we provide formal guarantees for the stability or instability of such fixed points by leveraging the spectrum of the linearized game dynamics. We provide a comprehensive understanding of scalar games and find that equilibria that are both stable and Nash are robust to variations in learning rates., Comment: Accepted to 2020 IEEE Conference on Decision and Control

In this paper, we propose a distributed no-regret learning algorithm for network games using a primal-dual method, i.e., dual averaging. With only locally available observations, we consider the scenario where each player optimizes a global objective, formed by local objective functions on the nodes of a given communication graph. Our learning algorithm for each player involves taking steps along their individual payoff gradients, dictated by local observations of the other player’s actions. The output is then projected back-again locally–to the set of admissible actions for each player. We provide the regret analysis of this distributed learning algorithm for the case of a deterministic network that is subjected to two teams with distinct objectives, and obtain an $O(\sqrt T \log (T))$ regret bound. Our analysis indicates the key correlation between the rate of convergence and network connectivity that also appears in the distributed optimization setup via dual averaging. Furthermore, we show that the point of convergence of the proposed algorithm would be a Nash Equilibrium of the game. Finally, we showcase by an illustrative example the performance of our algorithm in relation to the size and connectivity of the network.

We prove that differential Nash equilibria are generic amongst local Nash equilibria in continuous zero-sum games. That is, there exists an open-dense subset of zero-sum games for which local Nash equilibria are non-degenerate differential Nash equilibria. The result extends previous results to the zero-sum setting, where we obtain even stronger results; in particular, we show that local Nash equilibria are generically hyperbolic critical points. We further show that differential Nash equilibria of zero-sum games are structurally stable. The purpose for presenting these extensions is the recent renewed interest in zero-sum games within machine learning and optimization. Adversarial learning and generative adversarial network approaches are touted to be more robust than the alternative. Zero-sum games are at the heart of such approaches. Many works proceed under the assumption of hyperbolicity of critical points. Our results justify this assumption by showing `almost all' zero-sum games admit local Nash equilibria that are hyperbolic., A shorter version of this paper was presented at the 2019 IEEE Conference on Decision and Control

We apply control theoretic and optimization techniques to adaptively design incentives. In particular, we consider the problem of a planner with an objective that depends on data from strategic decision makers. The planner does not know the process by which the strategic agents make decisions. Under the assumption that the agents are utility maximizers, we model their interactions as a non-cooperative game and utilize the Nash equilibrium concept as well as myopic update rules to model the selection of their decision. By parameterizing the agents' utility functions and the incentives offered, we develop an algorithm that the planner can employ to learn the agents' decision-making processes while simultaneously designing incentives to change their response to a more desirable response from the planner's perspective. We provide convergence results for this algorithm both in the noise-free and noisy cases and present illustrative examples.

We study the equilibrium behavior in a multi-commodity selfish routing game with many types of uncertain users where each user over- or under-estimates their congestion costs by a multiplicative factor. Surprisingly, we find that uncertainties in different directions have qualitatively distinct impacts on equilibria. Namely, contrary to the usual notion that uncertainty increases inefficiencies, network congestion actually decreases when users over-estimate their costs. On the other hand, under-estimation of costs leads to increased congestion. We apply these results to urban transportation networks, where drivers have different estimates about the cost of congestion. In light of the dynamic pricing policies aimed at tackling congestion, our results indicate that users' perception of these prices can significantly impact the policy's efficacy, and "caution in the face of uncertainty" leads to favorable network conditions., Currently under review

We address the problem of inverse reinforcement learning in Markov decision processes where the agent is risksensitive. In particular, we model risk-sensitivity in a reinforcement learning framework by making use of models of human decision-making having their origins in behavioral psychology and economics. We propose a gradient-based inverse reinforcement learning algorithm that minimizes a loss function defined on the observed behavior. We demonstrate the performance of the proposed technique on two examples, the first of which is the canonical Grid World example and the second of which is an MDP modeling passengers' decisions regarding ride-sharing. In the latter, we use pricing and travel time data from a ride-sharing company to construct the transition probabilities and rewards of the MDP.

We present two approaches for leveraging correlations in learning the utilities of non-cooperative agents' competing in a game: correlation and coalition utility learning. In the former, we estimate the correlations between agents using constrained Feasible Generalized Least Squares with noise estimation and then use the estimated correlations to generate a correlation utility function for each agent which is a weighted sum of its own estimated utility function and all the agents' estimated utilities that are highly correlated with them. We then optimize the weights to boost the performance of the estimators. In the latter, we use a small amount of training data to estimate the correlations between players and form coalitions between agents that are positively correlated. We then estimate the parameters of the utility functions for each coalition where agents in a coalition jointly optimize their utilities. The correlation utility learning method outperforms existing schemes while the coalition utility learning method is simple enough to be adapted to an online framework after an initial training phase, yet it matches the performance of much more complex schemes. To demonstrate the efficacy of the estimation schemes, we apply them to data collected from a social game framework for incentivizing more efficient shared resource consumption in smart buildings.

In many smart infrastructure applications flexibility in achieving sustainability goals can be gained by engaging end-users. However, these users often have heterogeneous preferences that are unknown to the decision-maker tasked with improving operational efficiency. Modeling user interaction as a continuous game between non-cooperative players, we propose a robust parametric utility learning framework that employs constrained feasible generalized least squares estimation with heteroskedastic inference. To improve forecasting performance, we extend the robust utility learning scheme by employing bootstrapping with bagging, bumping, and gradient boosting ensemble methods. Moreover, we estimate the noise covariance which provides approximated correlations between players which we leverage to develop a novel correlated utility learning framework. We apply the proposed methods both to a toy example arising from Bertrand-Nash competition between two firms as well as to data from a social game experiment designed to encourage energy efficient behavior amongst smart building occupants. Using occupant voting data for shared resources such as lighting, we simulate the game defined by the estimated utility functions to demonstrate the performance of the proposed methods., accepted for publication in IEEE Transactions on Control Systems Technology

We address the problem of inverse reinforcement learning in Markov decision processes where the agent is risk-sensitive. In particular, we model risk-sensitivity in a reinforcement learning framework by making use of models of human decision-making having their origins in behavioral psychology, behavioral economics, and neuroscience. We propose a gradient-based inverse reinforcement learning algorithm that minimizes a loss function defined on the observed behavior. We demonstrate the performance of the proposed technique on two examples, the first of which is the canonical Grid World example and the second of which is a Markov decision process modeling passengers' decisions regarding ride-sharing. In the latter, we use pricing and travel time data from a ride-sharing company to construct the transition probabilities and rewards of the Markov decision process., Comment: v3 (comments regarding updates): We significantly extended the theory (Theorem 2, 3, 5 and Proposition 3). We also correct some minor typos throughout the document; v2 (comments regarding updates): We corrected some notational typos and made clarifications in the proof. We also added clarifying remarks regarding reference points and acceptance levels which were previously conflated

In this paper, we introduce a preliminary model for interactions in the data market. Recent research has shown ways in which a data aggregator can design mechanisms for users to ensure the quality of data, even in situations where the users are effort-averse (i.e. prefer to submit lower-quality estimates) and the data aggregator cannot observe the effort exerted by the users (i.e. the contract suffers from the principal-agent problem). However, we have shown that these mechanisms often break down in more realistic models, where multiple data aggregators are in competition. Under minor assumptions on the properties of the statistical estimators in use by data aggregators, we show that there is either no Nash equilibrium, or there is an infinite number of Nash equilibrium. In the latter case, there is a fundamental ambiguity in who bears the burden of incentivizing different data sources. We are also able to calculate the price of anarchy, which measures how much social welfare is lost between the Nash equilibrium and the social optimum, i.e. between non-cooperative strategic play and cooperation.

We provide a method for designing a quadratic pricing scheme to induce a desired local Nash equilibrium in an open-loop differential game with nonlinear dynamics. In addition, we present conditions when the induced equilibrium is a global equilibrium. The results are applied to the problem of inducing network managers to invest in security in a multi-network with an epidemic model of the spread of malware.

We present analysis and results of a social game encouraging energy efficient behavior in occupants by distributing points which determine the likelihood of winning in a lottery. We estimate occupants utilities and formulate the interaction between the building manager and the occupants as a reversed Stackelberg game in which there are multiple followers that play in a non-cooperative game. The estimated utilities are used for determining the occupant behavior in the non-cooperative game. Due to nonconvexities and complexity of the problem, in particular the size of the joint distribution across the states of the occupants, we solve the resulting the bilevel optimization problem using a particle swarm optimization method. Drawing from the distribution across player states, we compute the Nash equilibrium of the game using the resulting leader choice. We show that the behavior of the agents under the leader choice results in greater utility for the leader.

We show that non-degenerate differential Nash equilibria are generic among local Nash equilibria in games with smooth costs and continuous strategy spaces, and demonstrate that such equilibria are structurally stable with respect to smooth perturbations in player costs. This implies that second-order conditions suffice to characterize local Nash equilibria in an open-dense set of games where player costs are smooth functions. Furthermore, equilibria that are computable using decoupled myopic approximate best-response persist under perturbations to the cost functions of individual players.

We show that designing prices to induce a socially optimal Nash equilibrium that is robust to small parameter perturbations in a linear-quadratic game can be framed as a convex program. In addition, we use a similar analysis to develop convex conditions that guarantee that the induced equilibrium is stable with respect to small deviations in players' feedback strategies.

Provided an arbitrary nonintrusive load monitoring (NILM) algorithm, we seek bounds on the probability of distinguishing between scenarios, given an aggregate power consumption signal. We introduce a framework for studying a general NILM algorithm, and analyze the theory in the general case. Then, we specialize to the case where the error is Gaussian. In both cases, we are able to derive upper bounds on the probability of distinguishing scenarios. Finally, we apply the results to real data to derive bounds on the probability of distinguishing between scenarios as a function of the measurement noise, the sampling rate, and the device usage., Submitted to the 3rd ACM International Conference on High Confidence Networked Systems (HiCoNS)