We investigate the representation of game-theoretic measures of network centrality using a framework that blends a social network representation with the formalism of cooperative skill games. We discuss the expressiveness of the new framework and highlight some of its advantages, including a fixed-parameter tractability result for computing centrality measures under such representations. As an application we introduce new network centrality measures

https://gabrielistrate.wordpress.com/2019/01/30/de-ce-sa-finantam-cercetarea-romaneasca/ Citiți un (scurt) eseu cu acest titlu.

We investigate the manipulation of power indices in TU-cooperative games by stimulating (subject to a budget constraint) changes in the propensity of other players to participate to the game. We display several algorithms that show that the problem is often tractable for so-called network centrality games and influence attribution games, as well as an example when optimal manipulation is intractable, even though computing power indices is feasible.

We prove that the propositional translations of the Kneser-Lovasz theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counting-based combinatorial proof of the Kneser-Lovasz theorem that avoids the topological arguments of prior proofs. We introduce a miniaturization of the octahedral Tucker lemma, called the truncated Tucker lemma. The propositional translations of the truncated Tucker lemma

  We investigate the dependence of steady-state properties of Schelling's segregation model on the agents' activation order. Our basic formalism is the Pollicott-Weiss version of Schelling's segregation model. Our main result modifies this baseline scenario by 1. employing a log-linear response rule 2. incorporating "contagion" in the decision to move: agents are connected by a second, "word-of-mouth", network. Agents' activation is specified by

We study languages and formal power series associated to (variants of) Hammersley's process. We show that the ordinary Hammersley process yields a regular language and the Hammersley tree process yields deterministic context-free (but non-regular) languages. For the extension to intervals of the Hammersley process we show that there are two relevant formal language variants. One of them leads to the same class of languages as the ordinary Hammersley

A simple ruin-game is studied on Erdos-Renyi type graphs. Initially the players have the same wealth. At each time step a monopolist game is played on all active links (links that connects nodes with nonzero wealth). In such a game each player puts a unit wealth in the pot and the pot is won with equal probability by one of the players. The game ends when there are no connected players such that both of them have non-zero wealth. In order to characterize

We study minimum entropy submodular set cover, a variant of the submodular set cover problem (Wolsey, Fujito, etc) that generalizes the minimum entropy set cover problem (Halperin and Karp, Cardinal et al.) We give a general bound of the approximation performance of the greedy algorithm using an approach that can be interpreted in terms of a particular type of biased network flows. As an application we rederive known results for the Minimum Entropy

We outline results and open problems concerning partitioning of integer sequences and partial orders into heapable subsequences (previously defined and established by Byers et al.)