1,720,965 research outputs found
New bounds for the balloon popping problem
No full textWe reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range (1.6595,2). We give a new lower bound of 1.68 and design an O(n5) algorithm for computing upper bounds as a function of the number of bidders n. Our algorithm provides an experimental evidence that the correct upper bound is a constant smaller than 2, thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to π2/6+1/4≈1.8949
Graphical Congestion Games
No full textWe consider congestion games with linear latency functions in which each
player is aware only of a subset of all the other players. This is modeled by means
of a social knowledge graph G in which nodes represent players and there is an edge
from i to j if i knows j . Under the assumption that the payoff of each player is
affected only by the strategies of the adjacent ones, we first give a complete characterization
of the games possessing pure Nash equilibria. Namely, if the social graphG
is undirected, the game is an exact potential game and thus isomorphic to a classical
congestion game. As a consequence, it always converges and possesses Nash equilibria.
On the other hand, if G is directed an equilibrium is not guaranteed to exist, but
the game is always convergent and an equilibrium can be found in polynomial time
if G is acyclic, even if finding the best equilibrium remains an intractable problem.
We then investigate the impact of the limited knowledge of the players on the
performance of the game. More precisely, given a bound on the maximum degree of
G, for the convergent cases we provide tight lower and upper bounds on the price
of stability and asymptotically tight bounds on the price of anarchy. Such results
are determined for four natural social cost functions: total and maximum presumed
latencies, that is the ones the players believe to pay due to the fact that they are only
aware of the existence of their neighbors, and total and maximum perceived latencies,
i.e. actually experienced due to all (and not only the known) players using the same
facilities.
All the results are then extended to singleton congestion games
New Bounds for the Balloon Popping Problem
No full textWe reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range [1.6595,2]. We give a new lower bound of 1.68 and design an O(n 5) algorithm for computing upper bounds as a function of the number of bidders n. Our algorithm provides an experimental evidence that the correct upper bound is smaller than 2, thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to π 2/6 + 1/4 ≈ 1.8949. © 2013 Springer-Verlag Berlin Heidelberg
Nash Stability in Fractional Hedonic Games
No full textCluster formation games are games in which self-organized groups (or clusters) are created as a result of the strategic interactions of independent and selfish players. We consider fractional hedonic games, that is, cluster formation games in which the happiness of each player in a group is the average value she ascribes to its members. We adopt Nash stable outcomes, where no player can improve her utility by unilaterally changing her own group, as the target solution concept and study their existence, complexity and performance for games played on general and specific graph topologies
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
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Schelling Games with Continuous Types
Full text linkIn most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants
Schelling Games with Continuous Types (short paper)
Full text linkIn most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socio-economic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling's model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability
- …
