Sharp Identification Regions in Models With Convex Moment Predictions

We provide a tractable characterization of the sharp identification region of the parameter vector θ in a broad class of incomplete econometric models. Models in this class have set‐valued predictions that yield a convex set of conditional or unconditional moments for the observable model variables. In short, we call these models with convex moment predictions. Examples include static, simultaneous‐move finite games of complete and incomplete information in the presence of multiple equilibria; best linear predictors with interval outcome and covariate data; and random utility models of multinomial choice in the presence of interval regressors data. Given a candidate value for θ, we establish that the convex set of moments yielded by the model predictions can be represented as the Aumann expectation of a properly defined random set. The sharp identification region of θ, denoted Θ_I, can then be obtained as the set of minimizers of the distance from a properly specified vector of moments of random variables to this Aumann expectation. Algorithms in convex programming can be exploited to efficiently verify whether a candidate θ is in Θ_I. We use examples analyzed in the literature to illustrate the gains in identification and computational tractability afforded by our method.     

Multiperson Bargaining and Strategic Complexity

We investigate the effect of introducing costs of complexity in the n‐person unanimity bargaining game. As is well‐known, in this game every individually rational allocation is sustainable as a Nash equilibrium (also as a subgame perfect equilibrium if players are sufficiently patient and if n & 2). Moreover, delays in agreement are also possible in such equilibria. By limiting ourselves to a plausible notion of complexity that captures length of memory, we find that the introduction of complexity costs (lexicographically with the standard payoffs) does not reduce the range of possible allocations but does limit the amount of delay that can occur in any agreement. In particular, we show that in any n‐player game, for any allocation z, an agreement on z at any period t can be sustained as a Nash equilibrium of the game with complexity costs if and only if t≤n. We use the limit on delay result to establish that, in equilibrium, the strategies implement stationary behavior. Finally, we also show that ‘noisy Nash equilibrium’ with complexity costs sustains only the unique stationary subgame perfect equilibrium allocation.     

Finding the anti-block vital edge of a shortest path between two nodes

Let P _G (s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A detour at a node u∈P _G (s,t)=(s,…,u,v,…,t) is defined as a shortest path P _G−e (u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e=(u,v)∈P _G (s,t) whose removal produces a detour at node u such that the ratio of the length of P _G−e (u,t) to the length of P _G (u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks are shown. This research is supported by NSF of China under Grants 70471035, 70525004, 701210001 and 60736027, and PSF of China under Grant 20060401003.     

Beliefs in Repeated Games

Consider a two‐player discounted infinitely repeated game. A player's belief is a probability distribution over the opponent's repeated game strategies. This paper shows that, for a large class of repeated games, there are no beliefs that satisfy three properties: learnability, a diversity of belief condition called CSP, and consistency. Loosely, if players learn to forecast the path of play whenever each plays a strategy that the other anticipates (in the sense of being in the support of that player's belief) and if the sets of anticipated strategies are sufficiently rich, then neither anticipates any of his opponent's best responses. This generalizes results in Nachbar (1997).     

On the total domination subdivision number in some classes of graphs

A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G)\mathrm {sd}_{\gamma_{t}}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that sd_gt(G) ￡ g_t(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1 for some classes of graphs.     

A Fractional Dickey–Fuller Test for Unit Roots

This paper presents a new test for fractionally integrated (FI) processes. In particular, we propose a testing procedure in the time domain that extends the well–known Dickey–Fuller approach, originally designed for the I(1) versus I(0) case, to the more general setup of FI(d₀) versus FI(d₁), with d₁<d₀. When d₀=1, the proposed test statistics are based on the OLS estimator, or its t–ratio, of the coefficient on Δ^d1y_t−1 in a regression of Δy_t on Δ^d1y_t−1 and, possibly, some lags of Δy_t. When d₁ is not taken to be known a priori, a pre–estimation of d₁ is needed to implement the test. We show that the choice of any T^1/2–consistent estimator of d₁∈[0 ,1) suffices to make the test feasible, while achieving asymptotic normality. Monte–Carlo simulations support the analytical results derived in the paper and show that proposed tests fare very well, both in terms of power and size, when compared with others available in the literature. The paper ends with two empirical applications.     

Finding an anti-risk path between two nodes in undirected graphs

Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent site of the blocked edge. Let ℘={P _G (s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper will propose the Anti-risk Path Problem of finding a path P _G (s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n ²log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively. This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of China under Grant 20060401003.     

Efficiency in Repeated Games Revisited: The Role of Private Strategies

Most theoretical or applied research on repeated games with imperfect monitoring has focused on public strategies: strategies that depend solely on the history of publicly observable signals. This paper sheds light on the role of private strategies: strategies that depend not only on public signals, but also on players' own actions in the past. Our main finding is that players can sometimes make better use of information by using private strategies and that efficiency in repeated games can be improved. Our equilibrium private strategy for repeated prisoners' dilemma games consists of two states and has the property that each player's optimal strategy is independent of the other player's state.     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Cooperation in Repeated Games When the Number of Stages is not Commonly Known

It is shown that an exponentially small departure from the common knowledge assumption on the number T of repetitions of the prisoners' dilemma already enables cooperation. More generally, with such a departure, any feasible individually rational outcome of any one-shot game can be approximated by a subgame perfect equilibrium of a finitely repeated version of that game. The sense in which the departure from common knowledge is small is as follows: (I) With probability one, the players know T with precision ±K. (ii) With probability 1 −ε, the players know T precisely; moreover, this knowledge is mutual of order εT. (iii) The deviation of T from its finite expectation is exponentially small.     

Reputation in Continuous‐Time Games

We study reputation dynamics in continuous‐time games in which a large player (e.g., government) faces a population of small players (e.g., households) and the large player's actions are imperfectly observable. The major part of our analysis examines the case in which public signals about the large player's actions are distorted by a Brownian motion and the large player is either a normal type, who plays strategically, or a behavioral type, who is committed to playing a stationary strategy. We obtain a clean characterization of sequential equilibria using ordinary differential equations and identify general conditions for the sequential equilibrium to be unique and Markovian in the small players' posterior belief. We find that a rich equilibrium dynamics arises when the small players assign positive prior probability to the behavioral type. By contrast, when it is common knowledge that the large player is the normal type, every public equilibrium of the continuous‐time game is payoff‐equivalent to one in which a static Nash equilibrium is played after every history. Finally, we examine variations of the model with Poisson signals and multiple behavioral types.     

A Characterization of Rationalizable Consumer Behavior

For an arbitrary data set D = {(p, x)} ⊆ (ℝ₊^m∖ {0}) × ℝ₊^m, finite or infinite, it is shown that the following three conditions are equivalent: (a) D satisfies GARP; (b) D can be rationalized by a utility function; (c) D can be rationalized by a utility function that is quasiconcave, nondecreasing, and that strictly increases when all its coordinates strictly increase. Examples of infinite data sets satisfying GARP are provided for which every utility rationalization fails to be lower semicontinuous, upper semicontinuous, or concave. Thus condition (c) cannot be substantively improved upon.     

Decomposition of K m,n into 4-cycles and 2t-cycles

In this paper we show the sufficient conditions for the decomposition of the complete bipartite graphs K _2m,2n and K _2n+1,2n+1−F into cycles of two different lengths 4 and 2t, t>2, where F is a 1-factor of K _2n+1,2n+1. After that we prove that the results are true for t=5 and 6. Dedicated to Frank K. Hwang on the occasion of his 65th birthday. An erratum to this article can be found at     

The Folk Theorem for Games with Private Almost‐Perfect Monitoring

We prove the folk theorem for discounted repeated games under private, almost‐perfect monitoring. Our result covers all finite, n‐player games that satisfy the usual full‐dimensionality condition. Mixed strategies are allowed in determining the individually rational payoffs. We assume no cheap‐talk communication between players and no public randomization device.     

Distributed Decisions in Networks: Laboratory Study of Routing Splittable Flow

We study network games in which users choose routes in computerized networks susceptible to congestion. In the “unsplittable” condition, route choices are completely unregulated, players are symmetric, each player controls a single unit of flow and chooses a single origin–destination (O–D) path. In the “splittable” condition, which is the main focus of this study, route choices are partly regulated, players are asymmetric, each player controls multiple units of flow and chooses multiple O–D paths to distribute her fleet. In each condition, users choose routes in two types of network: a basic network with three parallel routes and an augmented network with five routes sharing joint links. We construct and subsequently test equilibrium solutions for each combination of condition and network type, and then propose a Markov revision protocol to account for the dynamics of play. In both conditions, route choice behavior approaches equilibrium and the Braess Paradox is clearly manifested.     

Likelihood Inference for a Fractionally Cointegrated Vector Autoregressive Model

We consider model based inference in a fractionally cointegrated (or cofractional) vector autoregressive model, based on the Gaussian likelihood conditional on initial values. We give conditions on the parameters such that the process X_t is fractional of order d and cofractional of order d−b; that is, there exist vectors β for which β^′X_t is fractional of order d−b and no other fractionality order is possible. For b=1, the model nests the I(d−1) vector autoregressive model. We define the statistical model by 0 < bd, but conduct inference when the true values satisfy 0d₀−b₀<1/2 and b₀≠1/2, for which β₀^′X_t is (asymptotically) a stationary process. Our main technical contribution is the proof of consistency of the maximum likelihood estimators. To this end, we prove weak convergence of the conditional likelihood as a continuous stochastic process in the parameters when errors are independent and identically distributed with suitable moment conditions and initial values are bounded. Because the limit is deterministic, this implies uniform convergence in probability of the conditional likelihood function. If the true value b₀>1/2, we prove that the limit distribution of is mixed Gaussian, while for the remaining parameters it is Gaussian. The limit distribution of the likelihood ratio test for cointegration rank is a functional of fractional Brownian motion of type II. If b₀<1/2, all limit distributions are Gaussian or chi‐squared. We derive similar results for the model with d = b, allowing for a constant term.     

The total {k}-domatic number of a graph

For a positive integer k, a total {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0,1,2,…,k} such that for any vertex v∈V(G), the condition ∑ _u∈N(v) f(u)≥k is fulfilled, where N(v) is the open neighborhood of v. A set {f ₁,f ₂,…,f _d } of total {k}-dominating functions on G with the property that ?_i=1^df_i(v) ￡ k\sum_{i=1}^{d}f_{i}(v)\le k for each v∈V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by d_t^{k}(G)d_{t}^{\{k\}}(G). Note that d_t^{1}(G)d_{t}^{\{1\}}(G) is the classic total domatic number d _t (G). In this paper we initiate the study of the total {k}-domatic number in graphs and we present some bounds for d_t^{k}(G)d_{t}^{\{k\}}(G). Many of the known bounds of d _t (G) are immediate consequences of our results.     

Strategic Innovation,Corporate Entrepreneurship and Matching Outside-in to Inside-out Approaches to Strategy Research1

This paper calls upon strategy researchers to employ a more holistic view of research into the firm. In the past the division between the outside-in, or market selection and positioning perspective, and the inside-out, or management of internal change perspective, has acted to spur advances in knowledge. Now it is acting as an impediment to further progress. One avenue through which these perspectives can fruitfully be combined is in a deeper exploration of the role of innovation and corporate entrepreneurship. Four propositions are offered upon which a useful platform can be built and it is suggested that the implied research agenda will help the field move forward, faster.     

The Wheels of the Orthogonal Latin Squares Polytope: Classification and Valid Inequalities

A wheel in a graph G(V,E) is an induced subgraph consisting of an odd hole and an additional node connected to all nodes of the hole. In this paper, we study the wheels of the intersection graph of the Orthogonal Latin Squares polytope (P_I). Our work builds on structural properties of wheels which are used to categorise them into a number of collectively exhaustive classes. These classes give rise to families of inequalities that are valid for P_I and facet-defining for its set-packing relaxation. The classification introduced allows us to establish the cardinality of the whole wheel class and determine the range of the coefficients of any variable included in a lifted wheel inequality. Finally, based on this classification, a constant-time recognition algorithm for wheel-inducing circulant matrices, is introduced.     

Comparison of Subsidy Schemes for Reducing Waiting Times in Healthcare Systems

This study analyzes subsidy schemes that are widely used in reducing waiting times for public healthcare service. We assume that public healthcare service has no user fee but an observable delay, while private healthcare service has a fee but no delay. Patients in the public system are given a subsidy s to use private service if their waiting times exceed a pre‐determined threshold t. We call these subsidy schemes (s, t) policies. As two extreme cases, the (s, t) policy is called an unconditional subsidy scheme if t = 0, and a full subsidy scheme if s is equal to the private service fee. There is a fixed budget constraint so that a scheme with larger s has a larger t. We assess policies using two criteria: total patient cost and serviceability (i.e., the probability of meeting a waiting time target for public service). We prove analytically that, if patients are equally sensitive to delay, a scheme with a smaller subsidy outperforms one with a larger subsidy on both criteria. Thus, the unconditional scheme dominates all other policies. Using empirically derived parameter values from the Hong Kong Cataract Surgery Program, we then compare policies numerically when patients differ in delay sensitivity. Total patient cost is now unimodal in subsidy amount: the unconditional scheme still yields the lowest total patient cost, but the full subsidy scheme can outperform some intermediate policies. Serviceability is unimodal too, and the full subsidy scheme can outperform the unconditional scheme in serviceability when the waiting time target is long.