Jakub Dargaj

We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary k-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.

It is well-known that for infinitely repeated games, there are computable strategies that have best responses, but no computable best responses. These results were originally proved for either specific games (e.g., Prisoner’s dilemma), or for classes of games satisfying certain conditions not known to be both necessary and sufficient. We derive a complete characterization in the form of simple necessary and sufficient conditions for the existence of a computable strategy without a computable best response under limit-of-means payoff. We further refine the characterization by requiring the strategy profiles to be Nash equilibria or subgame-perfect equilibria, and we show how the characterizations entail that it is efficiently decidable whether an infinitely repeated game has a computable strategy without a computable best response.

A classic result in computational game theory states that there are infinitely repeated games where one player has a computable strategy that has a best response, but no computable best response. For games with discounted payoff, the result is known to hold for a specific class of games—essentially generalizations of Prisoner’s Dilemma—but until now, no necessary and sufficient condition is known. To be of any value, the computable strategy having no computable best response must be part of a subgame-perfect equilibrium, as otherwise a rational, self-interested player would not play the strategy.We give the first necessary and sufficient conditions for a two-player repeated game ( G ) to have such a computable strategy with no computable best response for all discount factors above some threshold. The conditions involve existence of a Nash equilibrium of the repeated game whose discounted payoffs satisfy certain conditions involving the min–max payoffs of the underlying stage game. We show that it is decidable in polynomial time in the size of the payoff matrix of ( G ) whether it satisfies these conditions.