Conference 'Games, Graphs, Generation, Duality'

Kazuhisa Makino, Kyoto University 

Monotone dualization is the problem to compute a prime disjunctive normal form of a monotone Boolean function f from a conjunctive normal form (CNF) of f. Monotone dualization is a problem which, in different disguise, is ubiquitous in many areas including computer science, artificial intelligence, and Game Theory. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 35 years. The corresponding decision problem is known to be solvable in quasi-polynomial time (and thus most likely not co-NP-hard), due to Fredman and Khachiyan. However, it is still open if it can be solved in polynomial time. In this talk, we discuss recent progress on monotone dualization and related topics.

Vladimir Gurvich, HSE

Joint work with Mariya Naumova, We prove a new property of dual hypergraphs and derive from it Nash-solvability of two-person tight game forms. The latter result is old (1975) but our new proof is much simpler than previous ones.

Khaled Elbassioni, Khalifa University of Science and Technology

Stochastic games were introduced by Shapley in 1953, and considered in the perfect information case by Gillette in 1957. Since then, they have been a subject of extensive research due to their generality and thus applicability in different areas. In 1988, Karzanov, Gurvich and Khachiyan considered the deterministic case (so-called cyclic games) and gave an algorithm that reduces any such game to a very special case (called canonical form) where locally optimal strategies are globally optimal and hence the optimal strategies become trivial to compute. In this talk, we describe an extension of their result to the case of stochastic games with perfect information with "limited randomness" and show how this can be used to derive an approximation scheme for this class of games. (Based on joint work with Boros, Gruvich and Makino.)

Khaled Elbassioni, Khalifa University of Science and Technology

A convex polyhedron can be described either by the set of its facets or by the sets of its vertices and extreme directions. Converting from one representation to the other is the well-known "Vertex/Facet Enumeration" problem. In 2006, it was shown that the problem of enumerating the vertices of an unbounded polyhedron cannot be solved in polynomial time unless P=NP, leaving open the question for polytopes. In this talk, we give an outline of this result and some of its implications on the complexity of other related problems. (Based on joint work with Boros, Borys, Gruvich, Khachiyan and Tiwary.)

Matjaž Krnc, University of Primorska

An *extension* of an induced path P in a graph G is an induced path P’ such that deleting the endpoints of P’ results in P. An induced path in a graph is said to be *avoidable* if each of its extensions is contained in an induced cycle. In 2019, Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced k‐vertex path also contains an avoidable induced path of the same length, and proved the result for k = 2. The case k = 1 was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all k in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut, where they also asked whether one could generalize this result to other avoidable structures. We strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced k-vertex paths are *shifts* of each other if their union is an induced path with k + 1 vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths. We also address the question by Bonamy et al.: we specify the concept of avoidability for arbitrary graphs equipped with two terminal vertices and provide both positive and negative results. This is joint work with Vladimir Gurvich, Martin Milanič, and Mikhail Vyalyi.

Michael Vyalyi, HSE

An existence of Nash equilibrium is a central question in game theory. In the talk this question will be discussed for games on graphs. We are interested in pure and stationary (memoryless) strategies. In the talk we present known results and open problems concerning the existence of Nash equilibria in such strategies.

Alexander Kozachinskiy, Steklov mathematical institute

My talk is devoted to the GKK88 algorithm for energy games. It was invented by Gurvich, Karzanov, and Khachyian in 1988. Up to this date, it is the fastest deterministic algorithm for this problem. I will show that GKK88 can be described in terms of moving over breakpoints of a piece-wise linear function, associated with a game. The number of these breakpoints is an intriguing complexity measure, defining how fast GKK88 works on a specific game.

Endre Boros, Rutgers University

We apply a Boolean duality based method, originally proposed by Gurvich and Gvishiani (1983), to the problem of characterizing Nash-solvability of bimatrix games in terms of forbidden 2x2 subgames. (Based on joint works with K. Elbassioni, V. Gurvich, K. Makino and V. Oudalov)

Endre Boros, Rutgers University

We generalize classical NIM to hypergraph NIM games, introduce the hypergraph sum of games, and for several classes of hypergraphs provide the corresponding Sprague-Grundy function. (Based on joint works with V. Gurvich, N.B. Ho, K. Makino and P. Mursic.)

Martin Milanič, University of Primorska

A stable set in a graph is strong if it intersects every maximal clique, and a strong clique is defined analogously. These concepts play an important role in the study of perfect graphs and are related to other concepts in graph theory, including perfect matchings, well-covered graphs and general partition graphs, as well as to concepts in other areas of mathematics, such as crosscuts in partially ordered sets and ovoids and spreads in polar spaces. A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. The study of CIS graphs is rooted in the 1960s in the work of Grillet, who characterized partially ordered sets in which each maximal chain intersects each maximal antichain. The acronym CIS was suggested by Andrade, Boros, and Gurvich in 2018. The more general concept of CIS d-graphs has applications in combinatorial game theory. In the talk we will give an overview of some recent structural and algorithmic results on CIS graphs, and present some open problems.

Eduard Lerner, Kazan Federal University

Talk in Russian 

Given $n$ men, $n$ women, and $n$ dogs, each man has a complete preference list of women, while each woman does a complete preference list of dogs, and each dog does a complete preference list of men. We understand a matching as a collection of $n$ nonintersecting triples, each of which contains a man, a woman, and a dog. A matching is said to be nonstable, if one can find a man, a woman, and a dog which belong to different triples and prefer each other to their current partners in the corresponding triples. Otherwise the matching is said to be stable (a weakly stable matching in 3DSM-CYC problem). E. Boros, V. Gurvich, S. Jaslar, and D. Krasner have proved that $k$-DSM-CYC is solvable if $n\leq k$. K. Eriksson, J. S\"ostrand, and P. Strimling state the conjecture that any 3DSM-CYC has a solution with any $n$ (and this is true for $n<6$). However, C.-K. Lam and G. Paxton (2019) have proposed an algorithm for constructing preference lists in the 3DSM-CYC problem of size $n=90$, which has allowed them to disprove the mentioned conjecture. We construct an instance of the 3DSM-CYC problem with no stable matching whose size $n=20$ and draw the graph of this instance (with 60 vertices).

Paper in English pdf tex 

Bruno Bauwens, HSE

Both in computer science and logic, several important results are proven using the diagonalization method. Unfortunately, some of these results have technical proofs that are hard to parse. A. Lachlan and A. An. Muchnik noted that many questions in these fields can be equivalently stated as the existence of a winning strategy in certain simple games. Although such game proofs are typically long, they are much more pleasant to read and have lead to the solution of longstanding open problems. Moreover, it is easy to involve students in research, because to solve the game, no knowledge from the field is needed. A nice example is a result from S. Epstein and L. Levin that states that if some randomized program produces a set of size 2^n in a time that is computably bounded in n, then this set contains a simple element, i.e., an element with Kolmogorov complexity at most O(1). We overview more longstanding open problems that have been solved using game technique.

Mariya Naumova, Rutgers University

Joint work with Vladimir Gurvich. We consider graphical $n$-person games with perfect information that have no Nash equilibria in pure stationary strategies. Solving these games in mixed strategies, we introduce probabilistic distributions in all non-terminal positions. The corresponding plays can be analyzed under two different basic assumptions: Markov's and a priori realizations. The former one guarantees existence of a uniformly best response of each player in every situation. Nevertheless, Nash equilibrium may fail to exist even in mixed strategies. The classical Nash theorem is not applicable, since Markov's realizations may result in the limit distributions and effective payoff functions that are not continuous. The a priori realization does not share many nice properties of the Markov one (for example, existence of the uniformly best response) but in return, Nash's theorem is applicable. We illustrate both realizations in detail by two examples with $2$ and $3$ players and also provide some general results.

Mariya Naumova, Rutgers University

Joint work with Vladimir Gurvich. Consider the following statement: \centerline{ $B(t, \Delta t)$: a $t$ years old person NN will survive another $\Delta t$ years,} \noindent where $t, \Delta t\in \mathbb{R}$ are nonnegative real numbers. We know only that NN is $t$ years old and nothing about the health conditions, gender, race, nationality, etc. We bet that $B(t, \Delta t)$ holds. It seems that our odds are very good, for any $t$ provided $\Delta t$ is small enough, say, $1 / 365$ (that is, one day). However, this is not that obvious and depends on the life-time probabilistic distribution. Let $F(t)$ denote the probability to live at most $t$ years and set $\Phi(t) = 1 - F(t)$. Clearly, $\Phi(t) \rightarrow 0$ as $t \rightarrow \infty$. It is not difficult to verify that $Pr(B(t, \Delta t)) \rightarrow 0$ as $t \rightarrow \infty$, for any fixed $\Delta t$, whenever the convergence of $\Phi$ is fast enough (say, super-exponential). Statistics provide arguments (based on an extrapolation yet) that this is the case. Hence, for an arbitrarily small positive $\Delta t $ and $\epsilon$ there exists a sufficiently large $t$ such that $Pr(B(t, \Delta t)) < \epsilon$, which means that we should not bet... in theory. However, in practice we can bet safely, because for the inequality $Pr(B(t, \Delta t)) < 1/2$ a very large $t$ is required. For example, $\Delta t = 1/365$ may require $t > 125$ years for some typical distributions $F$ considered in the literature. Yet, on Earth there is no person of such age. Thus, our odds are good, either because the chosen testee NN is not old enough, or for technical (or, more precisely, statistical) reasons - absence of a testee. This situation is similar to the famous St.Petersburg Paradox, in which long sequences of successive heads contribute a very large (infinite) amount to expectation in theory, but can be ignored in practice.

Vladimir Gurvich, HSE

Joint work with Endre Boros. In 1983, Claude Berge and Pierre Duchet conjectured that Perfect Graphs are Kernel-Solvable. In 1996, we reformulated this conjecture in terms of Effectivity Functions and notice that it follows immediately from four known results: Scarf (1967), Lovasz (1971), Keiding (1985), Danilov and Sotskov (1988).