Search

We consider a Cournot oligopoly model where multiple suppliers (oligopolists) compete by choosing quantities. We compare the social welfare achieved at a Cournot equilibrium to the maximum possible, for the case where the inverse market demand function is convex. We establish a lower bound on the efficiency of Cournot equilibria in terms of a scalar parameter derived from the inverse demand function, namely, the ratio of the slope of the inverse demand function at the Cournot equilibrium to the average slope of the inverse demand function between the Cournot equilibrium and a social optimum. Also, for the case of a single, monopolistic, profit maximizing supplier, or of multiple suppliers who collude to maximize their total profit, we establish a similar but tighter lower bound on the efficiency of the resulting output. Our results provide nontrivial quantitative bounds on the loss of social welfare for several convex inverse demand functions that appear in the economics literature. © 2014 Elsevier B.V., National Science Foundation (Grant CMMI-0856063)

We show that when a one-supplier/one-newsvendor supply chain is capacity-constrained, wholesale price contracts have some flexibility in allocating the channel-optimal profit. We analyze how this flexibility changes as we change the supply chain׳s capacity constraint and market demand. We also explore the allocation that is achieved in equilibrium in a newsvendor procurement game. Finally, we generalize our results to risk-sharing contracts and show that those contracts also gain additional flexibility in allocating the channel-optimal profit.

We compare the aggregate profit achieved at a Cournot equilibrium to the maximum possible, which would be obtained if the suppliers were to collude. We establish a lower bound on the profit of Cournot equilibria in terms of a scalar parameter that captures qualitative properties of the inverse demand function and the number of suppliers (or the maximum of the suppliers’ market shares). The lower bounds are tight when the inverse demand function is affine.

A problem that often arises in the process of searching for a job or for a candidate to fill a position is that applicants do not know if they will receive an offer from any given firm with which they interview, and, conversely, firms do not know whether applicants will definitely take positions they are offered. In this paper, we model the search process as an optimal stopping problem with probabilistic appearance of offers from the perspective of a single decision-maker who wants to maximize the realized value of the offer she accepts. Our main results quantify the value of information in the following sense: how much better off is the decision-maker if she knows each time whether an offer appeared or not, compared to the case where she is only informed when offers actually appear? We show that for some common distributions of offer values, she can expect to receive very close to her optimal value even in the lower information case, as long as she knows the probability that any given offer will appear. However, her expected value in the low information case (as compared to the high information case) can fall dramatically when she does not know the appearance probability ex ante but must infer it from data. This suggests that hiring and job-search mechanisms may not suffer from serious losses in efficiency or stability from participants hiding information about their decisions, unless agents are uncertain of their own attractiveness as employees or employers., National Science Foundation (U.S.) (contract ECS-0312921)

We consider a finite two-player zero-sum game with vector-valued rewards. We study the question of whether a given polyhedral set D is “approachable,” that is, whether Player 1 (the “decision maker”) can guarantee that the long-term average reward belongs to D , for any strategy of Player 2 (the “adversary”). We examine Blackwell's necessary and sufficient conditions for approachability, and show that the problem of checking these conditions is NP-hard, even in the special case where D is a singleton. We then consider a Stackelberg variant whereby, at each stage, the adversary gets to act after observing the decision maker's action. We provide necessary and sufficient conditions for approachability, and again establish that checking these conditions is NP-hard, even when D is a singleton. On the other hand, if the dimension of the reward vector is fixed, an approximate version of these conditions can be checked in polynomial time.

We formulate a model of sequential decision-making, dubbed the Goal Prediction game, to study the extent to which an overseeing adversary can predict the final goal of an agent who tries to reach that goal quickly, through a sequence of intermediate actions. Our formulation is motivated by the increasing ubiquity of large-scale surveillance and data collection infrastructures, which can be used to predict an agent's intentions and future actions, despite the agent's desire for privacy.Our main result shows that with a carefully chosen strategy, the predictability of the agent's goal can be made inversely proportional to the time she is willing to spend in reaching it, and that this is essentially the best possible. Moreover, this characterization depends on the topology of the agent's state space only through its diameter.

The unichain condition requires that every policy in an MDP result in a single ergodic class, and guarantees that the optimal average cost is independent of the initial state. We show that checking whether the unichain condition fails to hold is an NP-complete problem. We conclude with a brief discussion of the merits of the more general weak accessibility condition.

We consider a network game where the nodes of the network wish to form a graph to route traffic between themselves. We present a model where costs are incurred for routing traffic, as well as for a lack of network connectivity. We focus on directed links and the link stability equilibrium concept, and characterize connected link stable equilibria. The structure of connected link stable networks is analyzed for several special cases.

We study a linear stochastic approximation algorithm that arises in the context of reinforcement learning. The algorithm employs a decreasing step-size, and is driven by Markov noise with time-varying statistics. We show that under suitable conditions, the algorithm can track the changes in the statistics of the Markov noise, as long as these changes are slower than the rate at which the step-size of the algorithm goes to zero.

We show that the boundedness of the set of all products of a given pair Sigma of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius rho(Sigma) is not computable: because testing whether rho(Sigma)less than or equal to1 is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called "finiteness conjecture". Our results are based on a simple reduction from the emptiness problem for probabilistic finite automata, which is known to be undecidable. (C) 2000 Elsevier Science B.V. All rights reserved.

The purpose of this paper is twofold: (a) to provide a tutorial introduction to some key concepts from the theory of computational complexity, highlighting their relevance to systems and control theory, and (b) to survey the relatively recent research activity lying at the interface between these fields. We begin with a brief introduction to models of computation, the concepts of undecidability, polynomial-time algorithms, NP-completeness, and the implications of intractability results. We then survey a number of problems that arise in systems and control theory, some of them classical, some of them related to current research. We discuss them from the point of view of computational complexity and also point out many open problems. In particular, we consider problems related to stability or stabilizability of linear systems with parametric uncertainty, robust control, time-varying linear systems, nonlinear and hybrid systems, and stochastic optimal control.

We propose a variant of temporal-difference learning that approximates average and differential costs of an irreducible aperiodic Markov chain. Approximations are comprised of linear combinations of fixed basis functions whose weights are incrementally updated during a single endless trajectory of the Markov chain. We present a proof of convergence (with probability 1) and a characterization of the limit of convergence. We also provide a bound on the resulting approximation error that exhibits an interesting dependence on the ''mixing time'' of the Markov chain. The results parallel previous work by the authors, involving approximations of discounted cost-to-go.

In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable (NP-hard). As a special case, we consider a class of hybrid systems in which the state space is partitioned into two halfspaces, and the dynamics in each halfspace correspond to a different linear system.

We propose an algorithm for solving optimal stopping problems, and we provide theoretical results concerning convergence and approximation error. This algorithm can be viewed as a "neuro-dynamic programming" method for optimal stopping problems. The applicability of the algorithm is illustrated through a computational case study involving the pricing of a path-dependent financial derivative security that gives rise to an optimal stopping problem with a one-hundred-dimensional state space.

A set of matrices over the integers is said to be k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal if it is k-mortal for some finite k. We show that the problem of deciding whether a pair of 48 × 48 integer matrices is mortal is undecidable, and that the problem of deciding, for a given k, whether a pair of matrices is k-mortal is NP-complete.

In this paper, the problem of asymptotic identification for fading memory systems in the presence of bounded noise is studied. For any experiment, the worst-case error is characterized in terms of the diameter of the worst-case uncertainty set. Optimal inputs that minimize the radius of uncertainty are studied and characterized. Finally, a convergent algorithm that does not require knowledge of the noise upper bound is furnished. The algorithm is based on interpolating data with spline functions, which are shown to be well suited for identification in the presence of bounded noise—more so than other basis functions such as polynomials.

We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some δ > 0. We focus on the case of linear systems with a finite impulse response. It is known that the optimal identification error is related (within a factor of 2) to the diameter of a so-called uncertainty set and that the latter diameter is upper-bounded by 2δ, if a sufficiently long identification experiment is performed. We establish that, for any K ⩾ 1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2Kδ behaves like 2 Nf( 1 K ) , when N is large, where N is the length of the impulse response and ⨍ is a positive function known in closed form. While the framework is entirely deterministic, our results are proved using probabilistic tools.

We consider the following basic communication problems in a hypercube network of processors: the problem of a single processor sending a different packet to each of the other processors, the problem of simultaneous broadcast of the same packet from every processor to all other processors, and the problem of simultaneous exchange of different packets between every pair of processors. The algorithms proposed for these problems are optimal in terms of execution time and communication resource requirements; that is, they require the minimum possible number of time steps and packet transmissions. In contrast, algorithms in the literature are optimal only within an additive or multiplicative factor.

We consider iterative algorithms of the form x := f ( x ), executed by a parallel or distributed computing system. We first consider synchronous executions of such iterations and study their communication requirements, as well as issues related to processor synchronization. We also discuss the parallelization of iterations of the Gauss-Seidel type. We then consider asynchronous implementations whereby each processor iterates on a different component of x , at its own pace, using the most recently received (but possibly outdated) information on the remaining components of x . While certain algorithms may fail to converge when implemented asynchronously, a large number of positive convergence results is available. We classify asynchronous algorithms into three main categories, depending on the amount of asynchronism they can tolerate, and survey the corresponding convergence results. We also discuss issues related to their termination.

We present a simple characterization of the maximum possible rank of the product of several real matrices, when certain entries of the matrices are constrained to be zero. Our result relates this ‘generic rank’ to the maximum number of independent ‘information paths’ through the matrices, and has as corollaries, besides several previous attempts at this problem, a new characterization of structurally fixed modes for linear time-invariant dynamical systems. Furthermore, our characterization translates immediately to an 0( n”*) algorithm for calculating the generic rank (and therefore detecting fixed modes), by solving a network flow problem (here n is the sum of the dimensions of the matrices). Kqvwords: Structurally fixed modes, Maximum flow. Generic rank, Decentralized systems.

We consider iterative algorithms of the form x := f(x) , executed by a distributed network of processors. We first discuss a few possibilities for synchronous execution. We then consider asynchronous implementations whereby each processor iterates on a different component of x , at its own pace, using the most recently received (but possibly outdated) information on the remaining components of x . While certain algorithms may fail to converge when implemented asynchronously, a large number of positive convergence results is available. We classify asynchronous algorithms into three main categories, depending on the amount of asynchronism they can tolerate, survey the corresponding convergence results, and discuss some applications

In bimatrix games we study the process of successively eliminating strategies which are dominated by other pure strategies. We show how to perform this simplification in O(n^3) time, where n is the number of strategies. We also prove that the problem is P-complete, which suggests that it is inherently sequential.

We provide tight lower bounds on the computational complexity of discretetime, stationary, infinite horizon, discounted stochastic control problems, for the case where the state space is continuous and the problem is to be solved approximately, within a specified accuracy. We study the dependence of the complexity on the desired accuracy and on the discount factor.

We consider the asynchronous distributed simulation of a stochastic system using the rollback method and we show that the simulation can be incorrect, meaning that the sample path generated is not distributed according to the desired statistics, unless some precautions are taken. In particular, if part of the simulation is performed for a second time, due to a rollback, one should use the same random numbers that were used the first time.

The complexity of two problems of distributed computation and decision-making is studied. It is shown that deciding whether two distant agents can arrive at compatible decisions without any communication can be done in polynomial time if there are two possible decisions for each agent, but is NP-complete if one agent has three or more alternatives. It is also shown that minimizing the amount of communication necessary for the distributed computation of a function, when two distant computers receive each a part of the input, is NP-complete. This proves a conjecture due to A. Yao.