Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic

The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $mathcal{G}$ and $mathcal{H}$, decide whether $mathcal{H}$ consists precisely of all minimal transversals of $mathcal{G}$ (in which case we say that $mathcal{G}$ is the dual of $mathcal{H}$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $mathrm{GC}(log^2 n,mathrm{PTIME})$, where $mathrm{GC}(f(n),mathcal{C})$ denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $mathcal{C}$. It was conjectured that non-DUAL is in $mathrm{GC}(log^2 n,mathrm{LOGSPACE})$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $mathrm{GC}(log^2 n,mathrm{TC}^0)$ which is a subclass of $mathrm{GC}(log^2 n,mathrm{LOGSPACE})$. We here refer to the logtime-uniform version of $mathrm{TC}^0$, which corresponds to $mathrm{FO(COUNT)}$, i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for non-DUAL that requires to guess $O(log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in $mathrm{FO(COUNT)}$. From this result, by the well known inclusion $mathrm{TC}^0subseteqmathrm{LOGSPACE}$, it follows that DUAL belongs also to $mathrm{DSPACE}[log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $mathcal{G}$ and $mathcal{H}$, computes in quadratic logspace a transversal of $mathcal{G}$ missing in $mathcal{H}$.

Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints

Coalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions. In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts.

On the Complexity of Core, Kernel, and Bargaining Set

Coalitional games are mathematical models suited to analyze scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental problem for coalitional games is to single out the most desirable outcomes in terms of appropriate notions of worth distributions, which are usually called solution concepts. Motivated by the fact that decisions taken by realistic players cannot involve unbounded resources, recent computer science literature reconsidered the definition of such concepts by advocating the relevance of assessing the amount of resources needed for their computation in terms of their computational complexity. By following this avenue of research, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonable compact form (otherwise, if the worths of all coalitions are explicitly listed, the input sizes are so large that complexity problems are---artificially---trivial). The starting investigation point is the setting of graph games, about which various open questions were stated in the literature. The paper gives an answer to these questions, and in addition provides new insights on the setting, by characterizing the computational complexity of the three concepts in some relevant generalizations and specializations.