José Verschae

Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth et al.

Despite the wide use of $k$-Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neighbors classifiers offer interpretability from a "data perspective", in which the classification of an input vector $\bar{x}$ is explained by identifying the vectors $\bar{v}_1, \ldots, \bar{v}_k$ in the training set that determine the classification of $\bar{x}$, we argue that such explanations can be impractical in high-dimensional applications, where each vector has hundreds or thousands of features and it is not clear what their relative importance is. Hence, we focus on understanding nearest neighbor classifications through a "feature perspective", in which the goal is to identify how the values of the features in $\bar{x}$ affect its classification. Concretely, we study abductive explanations such as "minimum sufficient reasons", which correspond to sets of features in $\bar{x}$ that are enough to guarantee its classification, and "counterfactual explanations" based on the minimum distance feature changes one would have to perform in $\bar{x}$ to change its classification. We present a detailed landscape of positive and negative complexity results for counterfactual and abductive explanations, distinguishing between discrete and continuous feature spaces, and considering the impact of the choice of distance function involved. Finally, we show that despite some negative complexity results, Integer Quadratic Programming and SAT solving allow for computing explanations in practice.

Alejandro Jofré, Angel Pardo, David Salas et al.

Understanding the strategic behavior of miners in a blockchain is of great importance for its proper operation. A common model for mining games considers an infinite time horizon, with players optimizing asymptotic average objectives. Implicitly, this assumes that the asymptotic behaviors are realized at human-scale times, otherwise invalidating current models. We study the mining game utilizing Markov Decision Processes. Our approach allows us to describe the asymptotic behavior of the game in terms of the stationary distribution of the induced Markov chain. We focus on a model with two players under immediate release, assuming two different objectives: the (asymptotic) average reward per turn and the (asymptotic) percentage of obtained blocks. Using tools from Markov chain analysis, we show the existence of a strategy achieving slow mixing times, exponential in the policy parameters. This result emphasizes the imperative need to understand convergence rates in mining games, validating the standard models. Towards this end, we provide upper bounds for the mixing time of certain meaningful classes of strategies. This result yields criteria for establishing that long-term averaged functions are coherent as payoff functions. Moreover, by studying hitting times, we provide a criterion to validate the common simplification of considering finite states models. For both considered objectives functions, we provide explicit formulae depending on the stationary distribution of the underlying Markov chain. In particular, this shows that both mentioned objectives are not equivalent. Finally, we perform a market share case study in a particular regime of the game. More precisely, we show that an strategic player with a sufficiently large processing power can impose negative revenue on honest players.