1,720,970 research outputs found
Hedonic games with social context
No full textHedonic games are coalition formation games in which coalitions are created as a result of the strategic interaction of independent players. To this day, the literature on non-cooperative hedonic games has considered totally selfish players; our aim is that of defining and studying a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and study their existence, convergence and performance with respect to the classical notions of price of anarchy and price of stability. In particular, we provide an exact potential function for SCHGs implying the existence and convergence to Nash equilibria, and we prove tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCHGs
Stable outcomes in modified fractional hedonic games
No full textIn coalition formation games self-organized coalitions are created
as a result of the strategic interactions of independent agents. For
each couple of agents (i, j), weight wi,j = wj,i reflects how much
agents i and j benefit from belonging to the same coalition. We
consider the modified fractional hedonic game, that is a coalition
formation game in which agents’ utilities are such that the total
benefit of agent i belonging to a coalition (given by the sum of wi,j
over all other agents j belonging to the same coalition) is averaged
over all the other members of that coalition, i.e., excluding herself.
Modified fractional hedonic games constitute a class of succinctly
representable hedonic games.
We are interested in the scenario in which agents, individually
or jointly, choose to form a new coalition or to join an existing
one, until a stable outcome is reached. To this aim, we consider
common stability notions, leading to strong Nash stable outcomes,
Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general
weights and in the case of 0-1 weights. In particular, we completely
characterize the existence of the considered stable outcomes and
show many tight or asymptotically tight results on the performance
of these natural stable outcomes for modified fractional hedonic
games, also highlighting the differences with respect to the model
of fractional hedonic games, in which the total benefit of an agent
in a coalition is averaged over all members of that coalition, i.e.,
including herself
Hedonic games with social context
No full textHedonic games are coalition formation games in which coalitions are created as a result of the strategic interaction of independent players. To this day, the literature on non-cooperative hedonic games has considered totally selfish players; our aim is that of defining and studying a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and study their existence, convergence and performance with respect to the classical notions of price of anarchy and price of stability. In particular, we provide an exact potential function for SCHGs implying the existence and convergence to Nash equilibria, and we prove tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCHGs
Generalized Budgeted Submodular Set Function Maximization
Full text linkIn this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements.
We first present an algorithm that guarantees an approximation factor of 1/2(1-1/e^alpha), where alpha <= 1 is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us alpha=1- epsilon if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees alpha=1-1/e-epsilon for the general case. The gap between our approximation guarantees and the known inapproximability bounds is 1/2.
We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor beta >= 1 to guarantee a 1/2(1-1/e^(alpha beta))-approximation. If we set beta=1/(alpha)ln (1/(2 epsilon)), the algorithm achieves an approximation factor of 1/2-epsilon, for any arbitrarily small epsilon>0
On the Maximum Betweenness Improvement Problem
No full textAbstractThe betweenness is a well-known measure of centrality of a node in a network. We consider the problem of determining how much a node can increase its betweenness centrality by creating a limited amount of new edges incident to it. If the graph is directed, this problem does not admit a polynomial-time approximation scheme (unless P=NP) and a simple greedy approximation algorithm guarantees an almost tight approximation ratio [E. D. Demaine and M. Zadimoghaddam. Minimizing the diameter of a network using shortcut edges. In Proc. of the 12th Scandinavian Symp. and Work. on Algorithm Theory (SWAT), volume 6139 of LNCS, pages 420–431. Springer, 2010].In this paper we focus on the undirected graph case: we show that also in this case the problem does not admit a polynomial-time approximation scheme (unless P=NP). Moreover, we show that, differently from the directed case, the greedy algorithm can have an unbounded approximation ratio. In order to test the practical performance of the greedy algorithm, we experimentally measured its efficiency in term of ranking improvement, comparing it with another algorithm that simply adds edges to the nodes that have highest betweenness. Our experiments show that the greedy algorithm adds only few edges in order to increase the betweenness of a node and to reach the top positions in the ranking. Moreover, the greedy algorithm outperforms the second approach
Two-Year Progress of Pilot Research Activities in Teaching Digital Thinking Project (TDT)
Full text linkThis article presents a progress report from the last two years of the Teaching Digital Thinking (TDT) project. This project aims to implement new concepts, didactic methods, and teaching formats for sustainable digital transformation in Austrian Universities’ curricula by introducing new digital competencies. By equipping students and teachers with 21st-century digital competencies, partner universities can contribute to solving global challenges and organizing pilot projects. In line with the overall project aims, this article presents the ongoing digital transformation activities, courses, and research in the project, which have been carried out by the five partner universities since 2020, and briefly discusses the results. This article presents a summary of the research and educational activities carried out within two parts: complementary research and pilot projects
Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network
Full text linkThe Independent Cascade Model (ICM) is a widely studied model that aims to capture the dynamics of the information diffusion in social networks and in general complex networks. In this model, we can distinguish between active nodes which spread the information and inactive ones. The process starts from a set of initially active nodes called seeds. Recursively, currently active nodes can activate their neighbours according to a probability distribution on the set of edges. After a certain number of these recursive cycles, a large number of nodes might become active. The process terminates when no further node gets activated.
Starting from the work of Domingos and Richardson [Domingos et al. 2001], several studies have been conducted with the aim of shaping a given diffusion process so as to maximize the number of activated nodes at the end of the process. One of the most studied problems has been formalized by Kempe et al. and consists in finding a set of initial seeds that maximizes the expected number of active nodes under a budget constraint [Kempe et al. 2003].
In this paper we study a generalization of the problem of Kempe et al. in which we are allowed to spend part of the budget to create new edges incident to the seeds. That is, the budget can be spent to buy seeds or edges according to a cost function. The problem does not admin a PTAS, unless P=NP. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when these costs are high; the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
