The Expected Number of Nash Equilibria of a Normal Form Game

Fix finite pure strategy sets _S1,…,_Sn , and let S=_S1×⋯×_Sn . In our model of a random game the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere in ℝ^S. For given nonempty _T1⊂_S1,…,_Tn⊂_Sn we give a computationally implementable formula for the mean number of Nash equilibria in which each agent i's mixed strategy has support T_i. The formula is the product of two expressions. The first is the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the sets T_i. The second may be construed as the “probability” that such an equilibrium remains an equilibrium when the strategies in the sets _Si∖_Ti become available.     

A Folk Theorem for Asynchronously Repeated Games

We prove a Folk Theorem for asynchronously repeated games in which the set of players who can move in period t, denoted by I_t, is a random variable whose distribution is a function of the past action choices of the players and the past realizations of I_τ's, τ=1, 2,…,t−1. We impose a condition, the finite periods of inaction (FPI) condition, which requires that the number of periods in which every player has at least one opportunity to move is bounded. Given the FPI condition together with the standard nonequivalent utilities (NEU) condition, we show that every feasible and strictly individually rational payoff vector can be supported as a subgame perfect equilibrium outcome of an asynchronously repeated game.     

Distance graphs on R n with 1-norm

Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,y∈S,x≠y}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,y∈S,d(x,y)∈D}. The current paper studies distance graphs on the n-space R ₁ ⁿ with 1-norm. In particular, most attention is paid to the subset Z ₁ ⁿ of all lattice points of R ₁ ⁿ . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

Restrained domination in cubic graphs

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then g_r(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then g_r(G) ￡ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ _r (G)=γ(G).     

Upper paired-domination in claw-free graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γ_pr(G). We establish bounds on Γ_pr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γ_pr(G)≤4n/5 if δ=1 and n≥3, Γ_pr(G)≤3n/4 if δ=2 and n≥6, and Γ_pr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γ_pr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γ_pr(G)=3n/4 are characterized.     

Paired versus double domination in K 1,r -free graphs

A vertex in G is said to dominate itself and its neighbors. A subset S of vertices is a dominating set if S dominates every vertex of G. A paired-dominating set is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set in G. A subset S?V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ _×2(G). A claw-free graph is a graph that does not contain K _1,3 as an induced subgraph. Chellali and Haynes (Util. Math. 67:161–171, 2005) showed that for every claw-free graph G, we have γ _pr(G)≤γ _×2(G). In this paper we extend this result by showing that for r≥2, if G is a connected graph that does not contain K _1,r as an induced subgraph, then $\gamma_{\mathrm{pr}}(G)\le ( \frac{2r^{2}-6r+6}{r(r-1)} )\gamma_{\times2}(G)$ .     

Restricted domination parameters in graphs

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ _m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r _k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r _k (G,γ _m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r _k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r _k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

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.     

On domination number of Cartesian product of directed paths

Let γ(G) denote the domination number of a digraph G and let P _m □P _n denote the Cartesian product of P _m and P _n , the directed paths of length m and n. In this paper, we give a lower and upper bound for γ(P _m □P _n ). Furthermore, we obtain a necessary and sufficient condition for P _m □P _n to have efficient dominating set, and determine the exact values: γ(P ₂□P _n )=n, g(P₃\square P_n)=n+é\fracn4ù\gamma(P_{3}\square P_{n})=n+\lceil\frac{n}{4}\rceil, g(P₄\square P_n)=n+é\frac2n3ù\gamma(P_{4}\square P_{n})=n+\lceil\frac{2n}{3}\rceil, γ(P ₅□P _n )=2n+1 and g(P₆\square P_n)=2n+é\fracn+23ù\gamma(P_{6}\square P_{n})=2n+\lceil\frac{n+2}{3}\rceil.     

Total restrained domination in claw-free graphs

A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ _tr (G)=n. Also, we show that γ _tr (G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound.     

The Polymatroid Steiner Problems

The Steiner tree problem asks for a minimum cost tree spanning a given set of terminals S⊂eqV in a weighted graph G = (V,E,c), c:E→ R⁺. In this paper we consider a generalization of the Steiner tree problem, so called Polymatroid Steiner Problem, in which a polymatroid P = P(V) is defined on V and the Steiner tree is required to span at least one base of P (in particular, there may be a single base S⊂eqV). This formulation is motivated by the following application in sensor networks – given a set of sensors S = {s₁,…,s_k}, each sensor s_i can choose to monitor only a single target from a subset of targets X_i, find minimum cost tree spanning a set of sensors capable of monitoring the set of all targets X = X₁ ∪ … ∪ X_k. The Polymatroid Steiner Problem generalizes many known Steiner tree problem formulations including the group and covering Steiner tree problems. We show that this problem can be solved with the polylogarithmic approximation ratio by a generalization of the combinatorial algorithm of Chekuri et al. (2002).We also define the Polymatroid directed Steiner problem which asks for a minimum cost arborescence connecting a given root to a base of a polymatroid P defined on the terminal set S. We show that this problem can be approximately solved by algorithms generalizing methods of Chekuri et al. (2002).A preliminary version of this paper appeared in ISAAC 2004     

Small grid drawings of planar graphs with balanced partition

In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It is known that every planar graph G of n vertices has a grid drawing on an (n?2)×(n?2) or (4n/3)×(2n/3) integer grid. In this paper we show that if a planar graph G has a balanced partition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edge-disjoint subgraphs G ₁ and?G ₂, then G has a max?{n ₁,n ₂}×max?{n ₁,n ₂} grid drawing, where n ₁ and n ₂ are the numbers of vertices in G ₁ and?G ₂, respectively. In particular, we show that every series-parallel graph G has a (2n/3)×(2n/3) grid drawing and a grid drawing with area smaller than 0.3941n ² (<(2/3)² n ²).     

Note on the hardness of generalized connectivity

Let G be a nontrivial connected graph of order n and let k be an integer with 2??k??n. For a set S of k vertices of G, let ??(S) denote the maximum number ? of edge-disjoint trees T ₁,T ₂,??,T _? in G such that V(T _i )??V(T _j )=S for every pair i,j of distinct integers with 1??i,j???. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by ?? _k (G), of G is defined by ?? _k (G)=min{??(S)}, where the minimum is taken over all k-subsets S of V(G). Thus ?? ₂(G)=??(G), where ??(G) is the connectivity of G, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of determining the generalized connectivity of a graph. At first, we obtain that for two fixed positive integers k ₁ and k ₂, given a graph G and a k ₁-subset S of V(G), the problem of deciding whether G contains k ₂ internally disjoint trees connecting S can be solved by a polynomial-time algorithm. Then, we show that when k ₁ is a fixed integer of at least 4, but k ₂ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when k ₂ is a fixed integer of at least 2, but k ₁ is not a fixed integer, we show that the problem also becomes NP-complete.     

A combinatorial proof of the cyclic sieving phenomenon for faces of Coxeterhedra

For a Coxeter system (W,S), the subgroup W _J generated by a subset J?S is called a parabolic subgroup of W. The Coxeterhedron PW associated to (W,S) is the finite poset of all cosets {wW _J } _w∈W,J?S of all parabolic subgroups of W, ordered by inclusion. This poset can be realized by the face lattice of a simple polytope, constructed as the convex hull of the orbit of a generic point in ? ⁿ under an action of the reflection group W. In this paper, for the groups W=A _n?1, B _n and D _n in a case-by-case manner, we present an elementary proof of the cyclic sieving phenomenon for faces of various dimensions of PW under the action of a cyclic group generated by a Coxeter element. This result provides a geometric, enumerative and combinatorial approach to re-prove a theorem in Reiner et al. (J. Comb. Theory, Ser. A 108:17–50, 2004). The original proof is proved by an algebraic method that involves representation theory and Springer’s theorem on regular elements.     

On the mod sum number of H m,n

Let N denote the set of all positive integers. The sum graph G ⁺(S) of a finite subset S?N is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an mod sum graph if it is isomorphic to the sum graph of some S?Z _M \{0} and all arithmetic performed modulo M where M≥|S|+1. The mod sum number ρ(G) of G is the smallest number of isolated vertices which when added to G result in a mod sum graph. It is known that the graphs H _m,n (n>m≥3) are not mod sum graphs. In this paper we show that H _m,n are not mod sum graphs for m≥3 and n≥3. Additionally, we prove that ρ(H _m,3)=m for m≥3, H _m,n ∪ρK ₁ is exclusive for m≥3 and n≥4 and $m(n-1) \leq \rho(H_{m,n})\leq \frac{1}{2} mn(n-1)$ for m≥3 and n≥4.     

A hybrid beam search looking-ahead algorithm for the circular packing problem

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r _i and its demand b _i . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.     

Embedded paths and cycles in faulty hypercubes

An important task in the theory of hypercubes is to establish the maximum integer f _n such that for every set ℱ of f vertices in the hypercube Q_n,{\mathcal {Q}}_{n}, with 0≤f≤f _n , there exists a cycle of length at least 2 ⁿ −2f in the complement of ℱ. Until recently, exact values of f _n were known only for n≤4, and the best lower bound available for f _n with n≥5 was 2n−4. We prove that f ₅=8 and obtain the lower bound f _n ≥3n−7 for all n≥5. Our results and an example provided in the paper support the conjecture that f_n=((n) || 2)-2f_{n}={n\choose 2}-2 for each n≥4. New results regarding the existence of longest fault-free paths with prescribed ends are also proved.     

The orbit problem is in the GapL hierarchy

The Orbit problem is defined as follows: Given a matrix A∈ℚ ^n×n and vectors x,y∈ℚ ⁿ , does there exist a non-negative integer i such that A ⁱ x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808–821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C₌L with respect to logspace many-one reductions.     

Packing 5-cycles into balanced complete m-partite graphs for odd m

Let be a complete m-partite graph with partite sets of sizes n ₁,n ₂,…,n _m . A complete m-partite graph is balanced if each partite set has n vertices. We denote this complete m-partite graph by K _m(n). In this paper, we completely solve the problem of finding a maximum packing of the balanced complete m-partite graph K _m(n), m odd, with edge-disjoint 5-cycles and we explicitly give the minimum leaves. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Research of M.-H.W. was supported by NSC 93-2115-M-264-001.     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.