Les artistes dans les revues d'avant-garde (1870-1940) : quelques outils d'analyse informatique

La fin du XIX e siècle peut être considérée comme l'âge d'or des petites revues littéraires et artistiques, des organes publiés par de jeunes artistes de manière souvent éphémère et en tirage limité, en marge des courants institutionnels 1 . Ces périodiques, qui profitent des libertés nouvelles de la presse sous la Troisième République, se définissent de manière négative par opposition à la « grande presse ». Leurs créateurs conçoivent le caractère presque artisanal de leur production comme une forme de culture anti-industrielle et une manière d'échapper aux contraintes et aux pratiques de diffusion et de consommation des médias de masse de l'époque. Dans le contexte de la mise en réseau des pratiques littéraires à la fin du siècle, les écrivains d'avant-garde se distinguent de la littérature industrielle et de son système économique en instituant cercles, cénacles, en se constituant en groupes réunis autour de petites revues ; ces organes deviennent des vitrines essentielles dans une nouvelle économie de l'avantgarde 2 . Une revue comme La Plume fait partie d'un système complexe reliant une maison d'édition, des expositions, des ventes d'affiches, des galeries, des soirées littéraires ; ce système s'affiche dans les pages d'annonces de la revue elle-même (fig.

n° 1). Elles s'affichent ainsi comme des objets intermédiatiques, faisant dialoguer textes littéraires, critiques, illustrations, affiches, reproductions d'oeuvres d'art selon des modalités et des hiérarchies novatrices.

1 Évanghélia Stead et Hélène Védrine (dir.), L'Europe des revues , estampes, photographies, illustrations, Paris, Presses de l'Université Paris-Sorbonne, 2008 ;Peter Brooker et Andrew Thacker (dir.), The Oxford Critical and Cultural History of Modernist Magazines, vol. I-III, 2009-2013. 2 Alain Vaillant, L'Histoire littéraire, Armand Colin, coll. Lettres U, 2011, p. 269 et

Des numérisations problématiques

Si ces périodiques intéressent un nombre croissant de chercheurs dans le cadre de projets internationaux, les informations permettant de les étudier sont encore dispersées. Le premier objectif du projet PRELIA est la production d'une base de données en ligne de plus de 300 revues afin de présenter un tableau aussi complet que possible des périodiques de cette période ; chacune de ces revues fait l'objet d'une description qui bénéficie du format numérique, avec sommaires exhaustifs, liste des collaborateurs et classifications par genres, afin d'offrir le plus d'entrées possible aux chercheurs et d'offrir un outil mis à jour régulièrement5 . Afin de montrer que ces « petites » revues sont loin d'être isolées dans la production de périodiques de l'époque, la base ne se limite pas strictement aux revues les plus obscures, mais intègre des revues d'une audience plus large, aussi bien dans les champs littéraires qu'artistiques, afin de mettre en lumière les glissements des collaborateurs, les modes des thèmes abordés...

La place des artistes dans ces périodiques implique des questionnements particuliers :

1. On peut imaginer que les artistes occupent une place essentiellement marginale dans ce milieu livresque, même si la spécificité des revues fin de siècle est grande ; y at-il beaucoup de fondateurs, de rédacteurs parmi les artistes ? quels outils informatiques peuvent permettre de mesurer de manière fine la place des artistes dans les revues, et de corriger ou de justifier les a priori critiques ? 2. On connaît l'importance des réseaux d'artistes et d'écrivains pour comprendre la création artistique de cette époque : de quelle manière le phénomène des revues vient-il structurer ces groupes, et comment le mesurer ? 3. On voit apparaître de nouvelles formes de discours critiques sur les artistes, et de nouvelles modalités de diffusion des valeurs de la critique picturale : comment analyser d'un point de vue macro-structural la généalogie du vaste discours critique dans ces revues ?

Je ne ferai que présenter quelques outils possibles et discuter des méthodologies, l'état de la base de données, encore en chantier, ne permettant aucune conclusion d'ensemble et n'autorisant que des explorations ponctuelles.

Les artistes dans les revues : quelques outils de visualisation

La base de données PRELIA offre plusieurs outils informatiques développés spécifiquement pour l'analyse de corpus de revues, permettant des analyses statistiques, aussi bien au niveau des revues et des auteurs pris isolément que d'un point de vue sociologique (mise en relief de réseaux humains et géographiques) et lexicométrique.

Plusieurs outils de visualisation statistiques dynamiques ont déjà été développés et sont disponibles en ligne6 .

Un premier outil permet de présenter un graphique des publications mensuelles d'un auteur ou d'un artiste dans l'ensemble des périodiques de la base. En cas d'utilisation de pseudonymes, seule une requête passant par l'entrée principale renvoie l'ensemble des résultats (par exemple, la requête « Gourmont, Remy de » renvoie aussi les articles écrits sous le pseudonyme de « Bury, R. de », mais la requête « Bury, R. de » ne renvoie que les articles écrits sous ce nom). Le résultat pour le caricaturiste Louis Morin (fig.

n° 2) permet de voir que la fin de la publication de sa Revue des Quat'Saisons coïncide avec son implication dans une autre publication, L'OEuvre et l'Image. Qu'est-ce qui explique la cohésion de ces groupes ? Je ferais l'hypothèse que les hiérarchies rédactionnelles dans ces périodiques cachent souvent d'autres formes de structurations, que l'on peut repérer grâce à ces outils informatiques. Les unités de « revue » ou de « publication » ne sont pas suffisantes pour expliquer certains phénomènes, et on peut observer des formes de structuration dynamique des groupes d'artistes et d'écrivains qui excèdent les limites des périodiques. Le premier principe organisationnel des revues fin de siècle réside dans la formation de noyaux souples de collaborateurs, constituant des groupes rédactionnels informels qui participent simultanément à plusieurs publications en adaptant leurs productions aux contraintes de ces périodiques, mais en modifiant aussi en retour leurs lignes éditoriales. La formation de ces noyaux résulte le plus souvent de contraintes sociales ; les groupes se consolident par l'appartenance aux mêmes communautés (scolaires et universitaires, familiales, de convivialité), mais la participation à certaines revues vient modifier en retour ces appartenances et contribuer à la restructuration de l'espace social. Ces regroupements permettent souvent de dépasser les oppositions politiques, idéologiques ou esthétiques, ce qui peut expliquer la porosité des frontières entre des revues aux lignes politiques très variées.

Ces outils, dont les résultats ne sont pas encore complètement analysables tant que la base de données est en construction, permettront de donner une image plus fine des personnels des revues, en nous forçant à observer la présence et l'importance de certains noms oubliés ou mal connus. On peut imaginer des outils pour mettre en lumière des relations sinon difficilement visibles :

l'intégration d'un certain nombre de variables (tirage, etc.) dans le calcul de l'importance d'une revue ;

des graphes dynamiques permettant de montrer des évolutions dans le temps ;

des comparaisons avec d'autres mises en réseau : correspondances, liens maîtres-élèves, scolarisation, salons… ;

une visualisation géographique de ces relations, etc.

Ces visualisations permettent d'analyse les réseaux sociaux des revues ; pour ce qui est des réseaux intertextuels, des outils de numérisation et de lexicométrie peuvent faire apparaître d'autres phénomènes.

Analyses macro-textuelles

Le troisième objectif du projet PRELIA est la numérisation de ces revues, afin de rendre visibles certains aspects mal connus de ces périodiques (couvertures, publicités, matérialité...) et de remplir les zones d'ombre des numérisations actuelles, qui masquent des pans entiers de la culture littéraire et artistique passée à cause des difficultés de numérisation de ces documents. Ce corpus numérique offre de nouvelles perspectives de recherche par le biais d'outils d'analyse statistique et lexicométrique sur une grande échelle. Le Mercure de France est la première revue éditée de cette manière, par le biais d'un wiki dédié à l'édition de la revue d'Alfred Vallette (www.mercurewiki.fr).

Ce projet est né du constat des limites de la qualité des numérisations et de la reconnaissance optique de caractères sur Gallica et d'autres bases de données en ligne. L'analyse statistique de l'ensemble des termes du corpus permet de faire ressortir les « termes typiques » qui sont associés de manière singulière à tel ou tel critique, et qui constituent ainsi leurs « marques » critiques ou leur signature stylistique12 . Le discours critique d'Aurier est ainsi marqué par l'usage de termes comme « idée » ou « émotion » ; mais on remarque surtout l'absence signifiante de certains termes (musique, Seurat, Signac) par rapport aux autres critiques de la revue : Ces outils permettent ainsi de répondre à des questions concernant la généalogie de certaines notions critiques, leur dissémination chez différents auteurs, le poids de certains genres dans l'ensemble du contenu de la revue, en considérant l'ensemble de ces textes comme un vaste discours médiatique au sein duquel on peut mettre à jour des noeuds de création et de redistribution des idées, validant l'idée de considérer ces revues comme un « réseau intertextuel ».

Beaucoup de volumes du

Fig

  Fig. n° 1 a, b, c, d. Couverture et catalogue dans La Plume, n° 136, 15 décembre 1895, n. p.

L

  'accès aux revues elles-mêmes reste singulièrement limité : la plupart sont en effet extrêmement fragiles et mal conservées, les collections sont incomplètes et font souvent partie de fonds faisant l'objet d'un accès restreint. Les revues numérisées sont le plus souvent les revues les plus connues, et même dans ce cas, leur présentation est souvent incomplète (numérisation des reprints et non des originaux, perte d'informationscouvertures, images, couleurs, papiers…). Un autre grand écueil de ces projets de numérisation est leur absence de normalisation : si de nombreuses bases de données textuelles et iconographiques incluant des revues sont consultables à distance, grâce à des initiatives privées (Google Books…) ou publiques (Gallica, Europeana, INHA…), leurs modalités d'accès sont loin d'être parfaites : on constate la multiplication des standards de fichiers, la privatisation de certains chantiers, l'absence d'outils permettant d'accéder simultanément à plusieurs bases, le manque de visibilité des résultats engrangés. Les entreprises privées proposent des numérisations produites selon une logique commerciale et sans culture bibliothéconomique ; l'idée de collection est absente de leurs préoccupations, ce qui génère des bases de données non structurées dont certains documents sont quasiment invisibles pour les usagers. La présentation de ces résultats rend impossible toute forme de recherche statistique valide. Le projet des Petites REvues de LIttérature et d'Art (PRELIA) Le projet PRELIA (www.prelia.fr) cherche à résoudre ces difficultés en proposant une plateforme permettant d'unifier les données sur ces objets et d'effectuer de véritables investigations scientifiques ; l'équipe du projet est composée d'un groupe de jeunes chercheurs spécialisés dans l'étude des périodiques et de la période concernée 4 .

Fig. n° 2 .

 2 Fig. n° 2. Publications mensuelles de Louis Morin dans les revues de la base PRELIA.

Fig. n° 3

 3 Fig. n° 3 a et b. Contributeurs de Lutèce entre janvier et juin 1883.

Fig. n° 4

 4 Fig. n° 4 a et b. Part des textes et des images dans La Plume et L'Almanach du Bibliophile.

Fig. n° 6 .

 6 Fig. n° 6. Réseaux d'écrivains et d'artistes dans les revues.

Fig. n° 7 .

 7 Fig. n° 7. Exemples de repérages de communautés par regroupement d'auteurs.

  Mercure n'y sont accessibles qu'en mode image (une simple image de la page, sans recherche de texte possible), et lorsque le texte d'un volume a été reconnu, le résultat est souvent inutilisable, car le taux de fiabilité du texte est très faible (entre 70 et 99 %, ce qui représente encore près de 25 fautes par page). Le projet MercureWiki doit permettre au contraire d'obtenir un corpus cohérent, exhaustif et corrigé des textes du Mercure de France, afin d'autoriser des recherches et des interrogations pertinentes. Construit à partir du logiciel libre MediaWiki 10 adapté grâce à différentes extensions, il est conçu comme un site pédagogique et scientifique destiné à former les étudiants à l'édition de texte en ligne et à proposer un outil utile aux chercheurs. Le texte fait l'objet de plusieurs vérifications, afin de reproduire au plus près les choix typographiques originaux. Ces pages isolées sont ensuite réunies article par article afin de permettre une lecture suivie de chaque texte, accessible à partir d'un sommaire des textes édités. Chaque entrée donne accès au texte intégral de l'article en question, précédé d'une description bibliographique. Chaque texte est par ailleurs indexé par le biais de mots-clefs qui permettent de rechercher rapidement tous les textes d'un auteur ou d'un genre particulier. Un moteur de recherche intégré facilite en outre la recherche dans l'ensemble des textes édités. Cette édition plein texte peut ensuite être utilisée pour des analyses lexicométriques : en isolant de ce corpus l'ensemble des textes de critique picturale écrits entre 1890 et 1892 dans le Mercure (ce qui représente un corpus d'environ 280 000 signes), et avec l'aide d'outils d'analyse lexicométrique comme R.Temis 11 , on peut faire apparaître divers phénomènes. En analysant simplement le nombre d'articles écrit par chaque auteur des critiques picturales du Mercure de France, on fait apparaître la surreprésentation d'Aurier, l'un des découvreurs de Van Gogh et le plus grand défenseur des néo-impressionnistes et des artistes du groupe de Pont-Aven dans les revues d'avant-garde, avec près de 30 articles écrits dans cette période. Ceci permet d'expliquer que sa mort prématurée en 1892 ait été tellement préjudiciable aux artistes qu'il défendait dans la revue et ailleurs, et que des peintres comme Gauguin ne trouvent plus de voix favorables pour leurs travaux après son décès (fig. n° 8).

Fig. n° 8 .

 8 Fig. n° 8. Nombre d'articles de critique picturale par auteur dans le Mercure de France entre janvier 1890 et mai 1892.

Fig. n° 9 .

 9 Fig. n° 9. Pourcentages d'occurrences des termes « Gauguin », « Courbet » et « Gogh » par auteur dans le Mercure de France entre janvier 1890 et mai 1892.

Fig. n° 10 .

 10 Fig. n° 10. Nombre d'occurrences mensuelles du terme « Gauguin » dans le Mercure de France entre janvier 1890 et mai 1892.

  'analyse des corrélations entre certains termes chez chaque auteur (des termes associés avec une fréquence pertinente 13 ) permet d'analyser de manière globale la manière dont tel ou tel peintre est considéré par un critique. En mettant en lumière les termes qui apparaissent en cooccurrence avec le nom de Gauguin chez Aurier, on retrouve les notions clefs de son analyse de l'oeuvre du peintre : l'importance de l'anachronisme, de la combinaison du matériel et du spirituel (« idéographie »), de la spiritualité :La prise en compte de la date de publication de chaque texte permet de faire apparaître des évolutions. Les mentions du nom de Gauguin connaissent ainsi un pic en décembre 1890, pic qui mériterait une analyse historique (fig. n° 10).

		%		%	%	Modalité Global	Valeur	Proba.
		terme/mod.	mod./terme	global			t
	point	0,4117		87,2881	0,2817 103,0000 118,0000 6,4809	0,0000
	de	8,7846		64,9144	8,0827 2198,0000 3386,0000 6,4467	0,0000
	etc	0,1639		93,1818	0,1050 41,0000	44,0000	4,8446	0,0000
	objet Terme	0,1279		94,1176 vestibule	0,0812 32,0000 glorification anachronique confondre disposition 34,0000 4,3502 0,0000
	science Coefficient 0,1079	de	96,4286 5,0	0,0668 27,0000 6,5 6,7	28,0000 6,7	4,2499 6,7	0,0000
	muse corrélation 0,1239		93,9394	0,0788 31,0000	33,0000	4,2487	0,0000
	et Terme	3,2173		65,1822 idéographie matérialisme paradisiaque paupière 2,9481 805,0000 1235,0000 3,9685 spiritualiste 0,0000
	combien 0,1039 Coefficient	de	92,8571 6,7	0,0668 26,0000 6,7 6,7	28,0000 6,7	3,7110 6,7	0,0001
	idée corrélation 0,2118		81,5385	0,1552 53,0000	65,0000	3,6233	0,0001
	vient	0,1119		90,3226	0,0740 28,0000	31,0000	3,5609	0,0002
	émotion 0,0639		100,0000	0,0382 16,0000	16,0000	3,4684	0,0003
	russe	0,0000		0,0000	0,1528 0,0000	64,0000	-	0,0000
								10,4882
	pas	0,2558		33,5079	0,4559 64,0000	191,0000 -7,2503 0,0000
	musique 0,0000		0,0000	0,0454 0,0000	19,0000	-5,4124 0,0000
	nous	0,3637		42,3256	0,5132 91,0000	215,0000 -5,0842 0,0000
	envoi	0,0000		0,0000	0,0358 0,0000	15,0000	-4,7191 0,0000
	an	0,0120		15,0000	0,0477 3,0000	20,0000	-3,8797 0,0001
	marin	0,0080		12,5000	0,0382 2,0000	16,0000	-3,6371 0,0001
	mérite	0,0040		7,6923	0,0310 1,0000	13,0000	-3,6182 0,0001
	xx	0,0040		7,6923	0,0310 1,0000	13,0000	-3,6182 0,0001
	signac	0,0160		19,0476	0,0501 4,0000	21,0000	-3,5815 0,0002
	sans	0,2558		44,7552	0,3414 64,0000	143,0000 -3,5321 0,0002
	aux	0,1918		42,8571	0,2674 48,0000	112,0000 -3,5081 0,0002
	seurat	0,0120		16,6667	0,0430 3,0000	18,0000	-3,4981 0,0002
	est	1,2030		52,5305	1,3678 301,0000 573,0000 -3,4697 0,0003

L

Julien Schuh, « La relève critique d'Albert Aurier », communication au Colloque international « Les revues, laboratoires de la critique (1880-1920) », Le Mans, 2007, URL : <http://hal.archivesouvertes.fr/hal-00987276>

<http://prelia.hypotheses.org/equipe>

La base est accessible à cette adresse : <http://prelia.fr/base/opac_css/>

<http://prelia.hypotheses.org/66>

<http://www.mediawiki.org/>

Outil d'analyse statistique sous R développé par Milan Bouchet-Valat (LSQ-CREST, OSC, INED) et Gilles Bastin (Sciences Po Grenoble, Pacte). URL : http://rtemis.hypotheses.org/

« Liste de termes ayant le plus fort Khi2 par cellule dans la matrice document-termes ou dans une matrice modalités-termes. Ce khi 2 est affecté d'un signe négatif dans le cas des termes les plus significativement absents. » URL : http://rtemis.hypotheses.org/r-temis-pas-a-pas On se reportera à ce site pour l'analyse des données des tableaux.

« Un terme et un coefficient de corrélation minimum sont indiqués par l'utilisateur. R.TeMiS retourne tous les termes ayant un coefficient de corrélation supérieur (la coprésence est mesurée à l'échelle du document). » URL : http://rtemis.hypotheses.org/r-temis-pas-a-pas


Keywords: SOA, reengineering, migration, reverse engineering, Object-Oriented, service identification, quality, software reuse, legacy system. I

Migrating towards Service Oriented Architecture SOA has become a major topic of interest during the recent years. Since emerging service technologies have forced non-service based software systems to become legacy, many efforts and researches have been carried out to enable these legacy systems to survive. In this context, several service identification solutions have been proposed. These approaches are either manual, thus considered expensive, or rely on ad-hoc criteria that fail to identify relevant services. In this paper, within the big picture of migrating object-oriented legacy systems towards SOA, we address automatic service identification from source code based on service quality characteristics. To achieve this, we propose a quality measurement model where characteristics of services are refined to measurable metrics.

Service Identification Based on Quality Metrics

Object-Oriented Legacy System Migration Towards SOA Seza Adjoyan * , Abdelhak-Djamel Seriai * , Anas Shatnawi * INTRODUCTION Service Oriented Architecture SOA, whose main bricks are services [START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF], has become a trend [START_REF] Chen | Feature analysis for service-oriented reengineering[END_REF][START_REF] Zhang | Service identification and packaging in service oriented reengineering[END_REF] of computing paradigm to describe business functionalities and application logics. In SOA, a system is structured into a set of loosely coupled [START_REF] Chen | Service Identification via Ontology Mapping[END_REF][START_REF] Nakamura | Extracting service candidates from procedural programs based on process dependency analysis[END_REF][START_REF] Papazoglou | Service oriented architectures: approaches, technologies and research issues[END_REF] and interoperable business services that can be easily composed [START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF], reused [START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF] and shared [START_REF]2.0: Business transformation or train wreck? Oracle Corporation[END_REF] regardless of their physical location. Services could either be all implemented on a single machine, residing on several machines of company's internal network, or even distributed on several systems over internet [START_REF] Brown | Using Service-Oriented Architecture and Component-Based Development to Build Web Service Applications[END_REF]. Moreover, having solid service oriented architecture in place will provide the infrastructure needed to successfully deploy services in cloud environment.

The evolution of service technologies in recent years has led non-service based software systems to become legacy software [START_REF] Chen | Feature analysis for service-oriented reengineering[END_REF][START_REF] Zhang | Service identification and packaging in service oriented reengineering[END_REF]. Any software which has been developed using outdated technology [START_REF] Sneed | Integrating legacy software into a service oriented architecture[END_REF], but still brings great value to the organization that uses it, is considered as a legacy software [START_REF] Stehle | Migration of Legacy Software to Service Oriented Architecture[END_REF][START_REF] Sneed | Integrating legacy software into a service oriented architecture[END_REF]. In order to follow new technological advances and yet to conserve existing business value of current systems, a migration, which is considered as a variation of wrapping methodology [START_REF] Stehle | Migration of Legacy Software to Service Oriented Architecture[END_REF], of legacy system should be carried out. Several approaches for legacy system migration towards SOA have been reported in literature [START_REF] Sneed | Integrating legacy software into a service oriented architecture[END_REF][START_REF] Brown | Using Service-Oriented Architecture and Component-Based Development to Build Web Service Applications[END_REF][START_REF] Chen | Feature analysis for service-oriented reengineering[END_REF][START_REF] Khadka | A structured legacy to SOA migration process and its evaluation in practice[END_REF][START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF][START_REF] Khadka | A method engineering based legacy to SOA migration method[END_REF][START_REF] Cetin | Legacy Migration to Service-Oriented Computing with Mashups[END_REF][START_REF] Channabasavaiah | Migrating to a service-oriented architecture[END_REF][START_REF] Stehle | Migration of Legacy Software to Service Oriented Architecture[END_REF][START_REF] Matos | Migrating Legacy Systems to Service-Oriented Architectures[END_REF][START_REF] O'brien | Supporting Migration to Services using Software Architecture Reconstruction[END_REF]. SOA migration is achieved through two major phases: (1) legacy analysis, where available software artifacts are analyzed to identify provided services and (2) service implementation, that leverages extracted legacy code as usable services, wraps them by interfaces and orchestrates their operations. The first phase (i.e. service identification) is crucial in this process, especially with the unavailability of certain resources (e.g. developers, architects) and poor documentation [START_REF] Khadka | A structured legacy to SOA migration process and its evaluation in practice[END_REF][START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF]. Even more, it is a challenging task, since legacy systems are not necessarily built with the vision of service. Therefore many approaches have been proposed to identify services by analyzing legacy software artifacts. The majority of them are carried out manually [START_REF] Sneed | Integrating legacy software into a service oriented architecture[END_REF][START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF][START_REF] Khadka | A method engineering based legacy to SOA migration method[END_REF]. These solutions are considered as expensive in terms of expertise. Thus, some automatic or quasi-automatic approaches were proposed [START_REF] Chen | Feature analysis for service-oriented reengineering[END_REF][START_REF] Zhang | Service identification and packaging in service oriented reengineering[END_REF][START_REF] Chen | Service Identification via Ontology Mapping[END_REF][START_REF] Matos | Migrating Legacy Systems to Service-Oriented Architectures[END_REF][START_REF] O'brien | Supporting Migration to Services using Software Architecture Reconstruction[END_REF]. Most of these approaches assume the existence of large range of information about legacy systems such as their documentation, architecture and design documents [START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF][START_REF] O'brien | Supporting Migration to Services using Software Architecture Reconstruction[END_REF]. Therefore they are specific to systems where such information is available. They cannot be applied to a large number of systems where only the source code is available [START_REF] Nakamura | Extracting service candidates from procedural programs based on process dependency analysis[END_REF]. In addition, these approaches rely on ad-hoc criteria for evaluating candidate services, hence a gap between identified services and expected ones.

Our contribution in this paper is to automatically identify services from object-oriented source code. Unlike existing approaches, our service identification process is based on a quality function that measures the semantic correctness of identified services. We introduce a semantic correctness model in order to refine well-known service characteristics to measurable metrics.

The rest of the paper is structured as follows: In section 2, we outline the related works for service identification within migration towards SOA approaches. In section 3, we present our approach of service identification from object-oriented source code by defining quality metrics to evaluate services. In section 4, we evaluate our approach on two case studies. Finally, section 5 concludes the paper and provides some future directions.

II. RELATED WORK

Most of the approaches proposing migration of legacy systems to service-based ones offer only guidelines to identify services [START_REF] Khadka | A structured legacy to SOA migration process and its evaluation in practice[END_REF][START_REF] Khadka | A method engineering based legacy to SOA migration method[END_REF][START_REF] Cetin | Legacy Migration to Service-Oriented Computing with Mashups[END_REF][START_REF] Channabasavaiah | Migrating to a service-oriented architecture[END_REF]. Few of them propose technical steps. In [START_REF] Lewis | Smart: The service-oriented migration and reuse technique[END_REF], authors present a migration approach called Service-Oriented Migration and Reuse Technique (SMART). It defines five steps to achieve the migration of legacy system towards SOA. However, the proposed approach requires several sources of information (e.g. documentation) to support the analysis of the legacy system. Besides, the approach largely relies on human interaction (e.g. system analyst, maintenance programmer, etc.) that gathers information through interviewing stakeholders in order to fill the gap between existing legacy system and target architecture. In [START_REF] Zhang | Service identification and packaging in service oriented reengineering[END_REF], an architecture-based and requirement-driven service-oriented reengineering method is discussed. Services are identified by domain analysis and business function identification. The approach is based on both requirements abstraction and source code levels. This approach needs architectural and requirement information to be avalaible. [START_REF] Sneed | Integrating legacy software into a service oriented architecture[END_REF] proposes an automatic approach to evaluate candidate services. Candidate services are considered as groups of object-oriented classes evaluated in terms of development, maintenance and estimated replacement costs. Other approaches propose to evaluate services either by code pattern matching and graph transformation [START_REF] Matos | Migrating Legacy Systems to Service-Oriented Architectures[END_REF], feature location [START_REF] Chen | Feature analysis for service-oriented reengineering[END_REF] or formal concept analysis [START_REF] Chen | Service Identification via Ontology Mapping[END_REF]. A detailed survey of all service identification methods is discussed in [START_REF] Khadka | Migrating Legacy Applications: Challenges in Service Oriented Architecture and Cloud Computing Environments[END_REF].

Services and software components have several characteristics in common, in particular, those related to their quality, nature, structure and behavior. For that obvious reason, component identification techniques from object oriented legacy system could be considered as related to this paper. One of the previous works in our team identifies components from object-oriented source code based on quality-centric metrics [START_REF] Kebir | Quality-Centric Approach for Software Component Identification from Object-Oriented Code[END_REF].

As to SOA quality metrics, diverse studies have been proposed in literature for measuring qualitative properties of SOA systems. Most of these works either assess systems that are already service based or evaluate systems only after their implementation. Unfortunately, such researches are not adapted to the context of reengineering an object-oriented system towards service oriented system. [START_REF] Aldris | Measuring the Degree of Service Orientation in Proprietary SOA Systems[END_REF] proposes a framework to measure the degree of service orientation in SOA systems. It focuses on the internal SOA attribute, decomposes selected attribute to a set of factors and maps each factor to a set of measurable criteria. Each criterion is typically evaluated by a set of software metrics, though no dedicated metrics are defined for each criterion in the paper.

III. PROPOSED APPROACH

We propose a migration technique that identifies services as groups of classes in the legacy software source code. We base our legacy system analysis on the source code, since it is the only resource that is always available, while other resources such as documentation or architecture could often be missing. Unlike other approaches that identify candidate services in source code manually, we propose an automatic identification method of candidate services. Our approach is based on the definition of a fitness function that measures semantic correctness of each group of source code elements to be considered as a service.

A. Object-to-service mapping model

In order to be capable to identify services from objectoriented source code, we define a mapping between object oriented and SOA concepts (see Figure 1). We consider a service as a group of classes defined in object-oriented source code. Among these classes, some define the operations provided by the service, whereas others are inner classes. Inner classes are those which only have internal connections to other classes of the same service. Classes that define the operations provided by the service are the classes that define its interface. Inner classes do not define operations provided by the service. Operations provided by the service are class's public methods.

B. Quality Measurement Model of Services

As we have mentioned earlier, a service is identified from a group of object-oriented classes. Initially, each group of classes is considered as a candidate service. A qualified service is selected from candidate ones based on a function that measures its quality. Similar to the standard for the evaluation of software quality ISO/IEC 25010:2011 [START_REF]Systems and software engineering -Systems and software Quality Requirements and Evaluation (SQuaRE) -System and software quality models[END_REF], we define this quality function of services based on a set of characteristics that are mapped to a set of properties. Each property is later measured using a set of metrics.

1) Characteristics of Services

We deduct the quality characteristics of services based on the analysis of the most commonly used definitions of services in literature.

In literature, there are several definitions of services [START_REF] Brown | Using Service-Oriented Architecture and Component-Based Development to Build Web Service Applications[END_REF][START_REF] Zhang | Service identification and packaging in service oriented reengineering[END_REF][START_REF] Nakamura | Extracting service candidates from procedural programs based on process dependency analysis[END_REF]. According to [START_REF] Zhang | Service identification and packaging in service oriented reengineering[END_REF], a service is an abstract resource that performs a coherent and functional task. [START_REF] Nakamura | Extracting service candidates from procedural programs based on process dependency analysis[END_REF] considers a service as a process that has an open interface, selfcontainedness and coarse granularity. It can be easily composed and decomposed to implement various business workflows. [START_REF] Brown | Using Service-Oriented Architecture and Component-Based Development to Build Web Service Applications[END_REF] defines the service in terms of its characteristics: A service is a coarse-grained and discoverable software entity that interacts with applications and other services through a loosely coupled, often asynchronous, message-based communication model. Coarse-grained means that services implement more than one functionality and operate on larger data sets. Discoverable means that services can be found at both design time and run time, not only by unique identity but also by interface identity and by service kind. Self-contained refers to the self-sufficiency a service has, where context or state information is not required from other services. For loosely coupled, services are connected to other services and clients using standard, dependency-reducing, decoupled message-based methods such as XML document exchanges.

Table I lists the characteristics of services as mentioned in the definitions above. We have categorized them into two categories: those related to the structure and behavior of services and others related to the SOA platform. In order to measure the semantic correctness of candidate services, we select from the aforementioned characteristics the ones that define service structure and behavior: self-containment, composability and coarse-grained (functionality).

2) Refinement of Service Characteristics

The former selected characteristics are refined to measurable quality properties.  A service can be completely self-contained if it does not require any interface, i.e. it can be deployed as a single unit without depending on other services [START_REF] Nakamura | Extracting service candidates from procedural programs based on process dependency analysis[END_REF]. Thus, the property number of interfaces the service requires gives us a good indication on the self-containment of the service.

The higher the number of required interfaces is, the less the service is self-contained.

 A service is subject to composition with other services. This composition is realized without internal modifications but through service interface. A decomposition of the legacy system will be effective with the principle of composing those services with high cohesion and loose coupling, i.e. two services are composed with each other if their interfaces are cohesive. Thus, the average of services' cohesion within an interface gives us a good indication on the composability of the service.

 A service is more likely to be coarse-grained and hence represent complex, rich and high-level business functionality. However, it may sometimes be fine-grained and hence represent low-level primitive functionality [START_REF] Channabasavaiah | Migrating to a service-oriented architecture[END_REF].

Choosing the right level of granularity is the key for a successful service reuse. The bigger the service grains are, the less the service becomes reusable. It is relatively difficult to determine from source code the exact number of functionalities that the service provides. However, several factors can help measuring the functionality of a service. (1) A service that provides several interfaces may provide numerous functionalities, thus the higher the number of interfaces is, the more the service provides functionalities. (2) An interface whose services are highly cohesive probably provide single functionality. (3) A group of interfaces with high cohesion are most favorable to provide single or limited number of functionalities. (4) When the extracted code of candidate service is highly coupled, this means that the service probably provides very few or single functionality. ( 5) When the extracted code of candidate service is highly cohesive, this means that the service probably provides very few or single functionality. Thus, we suggest binding the functionality characteristic to properties as indicated in Table II.

3) The Quality Metrics

In our approach, according to the characteristics and properties of services we have chosen above, we build our quality metrics to evaluate the quality of candidate services. This quality will be the factor in distinguishing the extracted candidate services. The property functionality requires coupling and cohesion measurements, while composability only requires a cohesion measurement (see Figure 2). As to [START_REF] Patidar | Coupling and Cohesion Measures in Object Oriented Programming[END_REF], cohesion of a service measures how strong the elements within this service are related to each other. A service is considered as highly cohesive, if it performs a set of closely related functions and cannot be split into finer elements. The metric LCC Loose Class Cohesion proposed by [START_REF] Bieman | Cohesion and Reuse in an Object-Oriented System[END_REF] measures the overall connectedness of the class. It is calculated by: Coupling means the degree of direct and indirect dependence of a class on other classes in the system. Here, two measures are counted: method calls and parameter use, i.e. two classes are considered coupled to each other if the methods of one class use the methods or attributes of the other class. In our approach, measures the internal coupling of the

Functionality Characteristic Property

A service that provides several interfaces may provide numerous functionalities, thus the higher the number of interfaces is, the more the service provides functionality.

Number of provided interfaces

An interface whose services are highly cohesive probably provide single functionality.

Average of service's interface cohesion within the interface

A group of interfaces with high cohesion are most favorable to provide single or limited number of functionality.

Cohesion between interfaces

When the extracted code of candidate service is highly coupled, this means that the service probably provides very few or single functionality.

Coupling inside a service

When the extracted code of candidate service is highly cohesive, this means that the service probably provides very few or single functionality. candidate service and is calculated by the ratio between number of classes inside the service that are internally called to the total number of classes within the candidate service . measures the coupling of the candidate service with other services. It is calculated as .

Cohesion inside a service

4) Fitness Function Definition

We define a fitness function for an identified candidate service as a linear combination between the 3 characteristics of services previously defined, for functionality, for composability and for selfcontainment as follows:

Where are coefficient weights for each characteristic that are determined by software architect and .

The characteristics functionality , composability and self-containment are measured according to their definition as follows:

Where refers to number of provided interfaces, refers to the average of service's interface cohesion within the interface, refers to the cohesion between interfaces, refers to the coupling inside a service, and refers to the cohesion inside a service.

; where i refers to interface

C. Clustering Process

In order to recover services from OO legacy code, we group classes based on their dependencies. For that purpose, we propose a hierarchical agglomerative clustering algorithm. This algorithm groups together the classes with the maximized value of the fitness function. At the outset, every class is considered as a single cluster. Next, we measure the fitness function between all pairs of clusters. The algorithm merges the pair of clusters with the highest fitness function value into a new cluster. Then, we measure the fitness function between the new formed cluster and all other clusters and successively merge the pair with the highest fitness function value. These steps are repeated as long as the number of clusters is bigger than one, as illustrated in Pseudo code 1. As a result, the legacy system is expressed in hierarchical view presented in a dendrogram, as illustrated in Figure 3.

To obtain a partition of disjoint clusters, the resulting hierarchy needs to be cut at some point. To determine the best cutting point we employ the standard depth first search (DFS) algorithm. Initially on the root node, we compare the similarity of the current node to the similarity of it child nodes. If the current node's similarity value exceeds the average of similarity value of its children, then the current node is a cutting point, otherwise, the algorithm continues recursively through its children.

By applying the aforementioned clustering algorithm, we evaluate the legacy system and represent its classes in coarsegrained and loose-coupled disjoint set of services. An example of partitioning legacy system's classes to services is illustrated in Figure 3.

IV. EVALUATION

The proposed approach has been evaluated on two realistic case studies: Java Calculator Suite 1 which is a small system with 17 classes and MobileMedia 2 which is a medium sized system with 51 classes. Table III gives the number of classes and LOC (Line of Code) of these two case studies. Java Calculator Suite is an open-source calculator implemented in Java. It performs basic mathematical operations, has a graphic interface and supports Booleans, large numbers, machine numbers, and about 25 different operations.

MobileMedia is an open-source Java application used for managing media (photo, music, and video) on mobile devices.

A. Service Identification 1) Results

In this phase, we partition the source code of each case study into a set of clusters. Each cluster is composed of one or more classes. Each resulting cluster corresponds to one service. Table IV shows the results in terms of number of obtained services for each case study and the corresponding average service quality value for each of the three characteristics: functionality, composability and self-containment. The distribution rate of classes to services is 17/7= 2.4 classes per service for Java Calculator Suite and 3.9 for MobileMedia. Even more, we notice that almost all classes of same service are grouped to offer single functionality. For example, "Entries", "GuiCommandLine" and "ResultList" handle I/O issues.

2) Validation and Discussion

We validate the consistency of our proposed approach either by comparing resulting services with the known architectural design or by analyzing the relevance of the identified services.

In Java Calculator Suite, we notice that lexically relevant classes were grouped in one cluster. We document the resulting components by assigning a name based on the most frequent tokens in their classes' names. In Table V, we display service identification results in terms of clusters' names and their composing classes. MobileMedia has a known architecture model. In [START_REF] Figueiredo | Evolving software product lines with aspects: an empirical study on design stability[END_REF], the authors presented aspect oriented architecture for MobileMedia. We manually compare our extracted services with the modules of this design, after excluding aspect modules. We have found out that some services were directly mapped to one corresponding module in the architecture, such as the service that includes two classes "MediaListScreen" and "MediaData" was mapped to the module named "MediaListScreen". In total, 5 services were successfully mapped to 5 modules. Some other extracted services could be mapped to more than one module. This category can be divided to two types. The first type is one module with closely related functionalities such as the service named "Video Media Util Screen Play Capture Music" was mapped to three modules "PlayMediaScreen", "VideoAccessor" and "VideoAlbumData". These three modules are in fact functionally related and the resulted service was more coarsegrained than the architecture design. The second type is modules that are weakly related. For this case, we have found two services that each of them was mapped to respectively 3 and 4 modules of the architecture. Some services that are functionally closely related (in our case study, 4 services related to the functionality of transferring media via SMS) were mapped to many modules of the architecture (in our case study, 2 modules related to media transfer functionality). These extracted services were finer-grained than their corresponding modules. Finally, one service that groups exception classes is missing from the architectural design since in the architecture, non-functional modules are not represented.

The results show that 77% (10/13) of extracted services were successfully mapped in the architectural design.

B. Example of Service Deployment

We deployed identified services as Web services using Apache Axis2 on Apache Tomcat Web server and then wrapped these Web services by generating their WSDL interfaces. For example, in MobileMedia case study, the configuration file services.xml (Figure . 4) describes the "mapping" between Web service "Video Media Util Screen

V. CONCLUSION

The main contribution of the work presented in this paper is the extraction of services from legacy source code based on service quality characteristics. For this purpose, we first set a mapping model between object and service concepts. Then, unlike most ad-hoc identification approaches, we introduced a fitness function that measures the quality of identified services. The measurement metrics of fitness function are based on a refinement model of service's semantic characteristics. It is worthy to note that this approach is especially applicable to modernize legacy systems for which no software assets but the source code is available. Finally, to demonstrate the applicability of our proposed approach, we have applied it on two Java OO applications and obtained satisfying results. As a part of future work, we plan to apply our proposed on more complex case studies.

Figure 1 .

 1 Figure 1. Object-service mapping model.

Figure 2 .

 2 Figure 2. Refinement model of service characteristics.

Figure 3 .

 3 Figure 3. Dendrogram with set of services.

PSEUDO CODE 1 :

 1 AGGLOMERATIVE HIERARCHICAL CLUSTERINGInput: OO source code classes;Output: A hierarchy of clusters (dendrogram); 1: let each class be a cluster; 2: compute fitness function of pair classes;

  1 http://sourceforge.net/projects/bfegler/ 2 http://homepages.dcc.ufmg.br/~figueiredo/spl/icse08/

Figure 4 .

 4 Figure 4. Services.xml file.

TABLE I

 I

	.	CHARACTERISTICS OF SERVICES
		Type
	Characteristic	Structural and Behavioral	SOA platform
	coarse-grained
	=	
	functionality
	discoverable		
	self-contained
	=	
	loosely-coupled
	dynamic-binding		
	composable		TABLE II.	BINDING FUNCTIONALITY CHARACTERISTIC TO
	message-based			PROPERTIES
	asynchronous		

TABLE III

 III

	Play Capture Music" and the Java classes composing this service.	TABLE V. SERVICE IDENTIFICATION RESULTS
						Cluster	Cluster Name	Composing Classes
	<service name="VideoMediaUtilScreenPlayCaptureMusic"	Number
	scope="application"> <description>				1	Calc Machine Number	CalcMachineNumber
	Video Media Util Screen Play Capture Music	2	Operator Center Control	OperatorControlCenter
	. <messageReceivers> </description> <messageReceiver CASE STUDIES INFORMATION		3	Calculator jcalc_applet Gui Results jcalc Entries	Calculator CalculatorException,
	mep="http://www.w3.org/2004/08/wsdl/in-only"	Command	CalculatorTester
	Case study class="org.apache.axis2.rpc.receivers.RPCInOnlyMessageReceiv Number of classes LOC	Jcalc
	Java Calculator Suite er"/> MobileMedia <messageReceiver 17 51 mep="http://www.w3.org/2004/08/wsdl/in-out" 2360 3016 class="org.apache.axis2.rpc.receivers.RPCMessageReceiver"/>	4	E jcalc_math jcalc_trig variable_interface	jcalc_applet E jcalc_math
	</messageReceivers>				jcalc_trig
	<parameter name="ServiceClass">			variable_interface
	sample.pojo.service.VideoMediaUtilScreenPlayCapture </parameter> Music	5	Variable Checker Table	operator	VariableTable, operatorChecker
	</service>					6	PI	PI
						7	Gui Line Results Entries	Entries
						Command List	GuiCommandLine
						ResultsList
	TABLE IV.	SERVICE IDENTIFICATION RESULTS
	Case study	Number	Functionality Composability Self-
		of			containment
		services
	Java Calculator	7	0.73	0.88	0.41
	Suite
	MobileMedia	13	0.60	0.79	0.59


Jonathan Ben-Naim
email: bennaim@irit.fr

Emiliano Lorini
email: lorini@irit.fr

Evaluating Power of Agents from Dependence Relations in Boolean Games

Keywords: Boolean games, dependence, power

In this paper we propose a new methodology for evaluating the relative power of agents in a strategic situation formally represented by a boolean game. The methodology consists in extracting a power ranking from the dependence relation induced by a certain boolean game. Our approach is axiomatic. We provide a number of desirable postulates that a notion of dependence is expected to satisfy and we compare competing notions of dependence, included a notion based on the concept of veto player, with respect to them. Similarly, we provide a set of postulates for power functions (i.e., the family of functions mapping dependence graphs to power rankings) and evaluate some new methods as well as existing ones (e.g., Pagerank) with respect to this set of postulates.

INTRODUCTION

A game-based power evaluation consists in assessing the social power of the agents interacting in a given situation, formally represented by a game. It can be represented mathematically as a function that takes a game as an input and returns a ranking of the agents as output, reflecting the relative power of the agents in the game. Such an evaluation is useful, because the agents typically need to choose the peers to interact with. The agents can also represent potential partners for external users, who then will find this evaluation useful as well. Moreover, information about the relative power of the agents in a society may be useful for policy makers in order to reduce inequalities and to promote fairness. Examples of applications for game-based power evaluations include web services, recommender systems and, more generally, the design and analysis of social procedures (e.g., for resource allocation, task distribution, etc.).

The goal of the present paper is to construct and analyze game-based power evaluations whose notion of power is based on the concept of social dependence. The idea that social power and social dependence are tightly related concepts is not new, as it has been widely explored in social sciences and philosophy [START_REF] Castelfranchi | The micro-macro constitution of power[END_REF][START_REF] Goldman | Toward a theory of social power[END_REF] as well as in the area of multi-agent systems [START_REF] Sichman | A social reasoning mechanism based on dependence networks[END_REF][START_REF] Boella | From social power to social importance[END_REF]. According to [START_REF] Castelfranchi | The micro-macro constitution of power[END_REF] for instance, the power of an agent i over another agent j is based on the fact that j depends on i for the achievement of her goals. For example, Bill (who is the only mechanic in town), has power over Mary because Mary depends on Bill for achieving the goal of having her car repaired.

The input of the game-based power evaluations studied in this paper are boolean games [START_REF] Harrenstein | Boolean games[END_REF], in which each player wants to achieve a certain goal represented by a propositional formula. The interesting aspect of boolean games is that they correspond to the specific subclass of normal-form games in which agents have binary preferences (i.e., payoffs can be either 0 or 1). Since the task of assessing the relative power of the agents in a boolean game is rather complex, the strategy we follow consists in decomposing it into two sub-tasks: construct and analyze dependence functions (that determine dependence relations in a boolean game) first, and then power functions (that evaluate power from dependencies). 1Our approach is axiomatic. We first establish postulates (or axioms) that dependence and power functions may satisfy. Such postulates can be seen as criteria useful to judge and compare different methods. Then, we analyze existing functions (e.g., Pagerank [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF] and van den Brink & Gilles's power function [START_REF] Van Den | Measuring domination in directed graphs[END_REF]) on the basis of these criteria, and show that they fail to satisfy interesting postulates. So, we build new dependence and power functions and show that they satisfy such postulates. Finally, we show that game-based power evaluations can be obtained by combining dependence and power functions. The crucial point is that such combinations are synergic, in the sense that the combination of our two "local" methods (dependence functions and power functions) produces a "global" method (game-based power evaluation) that satisfies interesting properties.

The paper is organized as follows. Section 2 focuses on the problem of extracting a dependence relation from a boolean game by means of a dependence function. Section 3 is devoted to the axiomatic analysis of power functions. First some existing methods are critically investigated, then four new ones are proposed. Section 4 bridges the gap between the first part and the second part of the paper. By means of the results obtained in Sections 2 and 3, we briefly show how certain structural properties of the boolean game determine specific properties of the power ranking of the agents.

DETERMINING DEPENDENCIES

We start by introducing the concept of boolean game as well as some related notions such as the concept of capability (Section 2.1). Then, we introduce the general concept of dependence function and propose a list of intuitively reasonable postulates that any dependence function is expected to satisfy (Section 2.2). Section 2.3 provides a critical discussion of an existing dependence function proposed by [START_REF] Bonzon | Dependencies between players in boolean games[END_REF]: we show that it violates all postulates given in Section 2.2. In Section 2.4 a new dependence function based on the concept of veto player is proposed. We show that this dependence function satisfies all postulates of Section 2.2. Finally, in Section 2.5 we explore the relationship between this notion of dependence based on veto player and the concept of Nash equilibrium.

Boolean games and related notions

First of all, we shall introduce the concept of boolean game that has been proposed for the first time by [START_REF] Harrenstein | Boolean games[END_REF] and further developed by [START_REF] Dunne | Cooperative boolean games[END_REF]. Definition 1. A boolean game is a quadruple B = A, Φ, {γa}a∈A, {Φa}a∈A , where:

• A is a non-empty finite set of agents (or players);

• Φ is a non-empty finite set of propositional atoms;

• γa is a formula of the language LΦ (i.e., the propositional language constructed on Φ) denoting the goal of agent a;

• Φa ⊆ Φ is the set of all atoms controlled by agent a. As standard [START_REF] Van Der Hoek | On the logic of cooperation and propositional control[END_REF], we assume that for all a, b ∈ A, Φa∩Φ b = ∅ and that a∈A Φa = Φ (i.e., the controlled atoms form a partitition of the set Φ). Moreover, we assume that each γa is a satisfiable formula of LΦ.

The following definition introduces the notion of strategy in a boolean game. Definition 2. Given a boolean game B and a coalition C ⊆ A, a strategy of coalition C is a function sC : a∈C Φa -→ {⊤, ⊥} which consists in setting the truth value of each atom controlled by some agent in C either to ⊤ (true) or ⊥ (false). The set of all strategies of coalition C is denoted by SC .

For notational convenience, strategies of the grand coalition A are denoted by s, s ′ , . . . instead of sA, s ′ A , . . . and strategies for single-agent coalitions are denoted by sa, s b , . . . instead of s {a} , s {b} , . . . Moreover, we write S instead of SA and Sa instead S {a} .

In addition, we write s |= ϕ to mean that the valuation defined by the strategy s satisfies formula ϕ ∈ LΦ. We write |= ϕ to mean that the propositional formula ϕ is valid in propositional logic, i.e., we have s |= ϕ for all valuations s.

Finally, given a strategy sC of the coalition C and a strategy s ′ A\C of the coalition A \ C, we let sC • s ′ A\C denote the strategy in S such that:

• (i) for all p ∈ a∈C Φa, sC • s ′ A\C (p) = sC (p); • (ii) for all p ∈ a∈A\C Φa, sC • s ′ A\C (p) = s ′ A\C (p).
It is worth noting that, since each formula γa is satisfiable in propositional logic, all agents together have the capability of making an agent satisfied. That is, for every goal formula γa, there exists s ∈ S such that s |= γa.

As a last concept for this section, we introduce the wellknown concept of capability that is studied in the context of Coalition Logic (CL) [START_REF] Pauly | A modal logic for coalitional power in games[END_REF] and Coalition Logic of Propositional Control (CL-PC) [START_REF] Van Der Hoek | On the logic of cooperation and propositional control[END_REF]. This is also called α-ability. Definition 3. Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game and let ϕ ∈ LΦ. We say that coalition C has the capability of making formula ϕ true regardless of what the agents outside C do (or, C is an effective coalition for ϕ for short), denoted by CanB(C, ϕ), iff there exists sC ∈ SC such that for all s A\C ∈ S A\C , sC • s A\C |= ϕ.

The following definition introduces the notion of minimal effective coalition for a given outcome ϕ that will be used in next section for our axiomatic analysis of dependence functions.

Definition 4. Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game and let ϕ ∈ LΦ. We say that coalition C is a minimal coalition having the capability of of making formula ϕ true regardless of what the agents outside C do (or, C is a minimal effective coalition for ϕ for short), denoted by MinCanB(C, ϕ), iff CanB(C, ϕ) holds and there is no B ⊂ C such that CanB(B, ϕ) holds.

Postulates for dependence functions

A dependence function is a function that takes a boolean game as an input and transforms it into a dependence relation between the agents in the game. In particular: Intuitively, aRb means that a depends on b, or equivalently that b has power over a.

Here we adopt an axiomatic approach to the analysis of dependence functions. Specifically, we propose four intuitively reasonable postulates for this family of functions. Our first postulate says the following: if agent a can achieve her goal γa regardless of what the other agents do then a does not depend on anybody, except perhaps on herself. More formally: Postulate 1. A dependence function ∆ satisfies sensitivity to agent capability (Cap) iff for every boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A and ∀a, b ∈ A, the following holds: if CanB({a}, γa) and a = b then a, b ∈ ∆(B).

Our second postulate says the following: if b does not belong to any minimal effective coalition that can make a's goal satisfied then a does not depend on b. In order to formally state our third postulate we need to define first the following notion of agent dominance. The idea is that agent a dominates agent b with respect to agent c if and only if, for every minimal effective coalition that can make c's goal satisfied, if b belongs to this coalition then a belongs to it as well. Finally, our last postulate for dependence function says that if agent b's goal implies agent a's goal (i.e., b's goal is achieved only if a's goal is also achieved), then all agents who have power over a also have power over b. As a side note, we observe that transitivity does not seem to be a reasonable postulate for a notion of dependence based on boolean games. This is the reason why we do not consider it here. A counterexample to transitivity for dependence is the following. Suppose Mary depends on Bill, since Bill is the only mechanic in town and Mary has the goal of having her car repaired. Moreover, suppose Bill depends on Alice, since Alice is the only baker in town and Bill wants to buy bread. This does not imply that Mary depends on Alice, as it might be the case that Mary does not want to buy bread.

An existing dependence function

Bonzon et al. [START_REF] Bonzon | Dependencies between players in boolean games[END_REF] have introduced a dependence function based on the concept of relevance. Let us call it relevancebased function and denote it by Rbf. This dependence function is also used by [START_REF] Sauro | Dependency in cooperative boolean games[END_REF]. A propositional atom p is said to be relevant for a boolean formula ϕ if and only if there is no equivalent boolean formula ψ where p does not occur. Given a boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A , let RV B(a) be the set of all variables p ∈ Φ that are relevant for a's goal γa and let RAB(a) be the set of all agents b ∈ A such that b controls at least one variable that is relevant for a (i.e., there is p ∈ Φ b such that p ∈ RV B(a)).

According to Bonzon et al.: Proof (Sketch). We only prove that Rbf violates (Cap) by means of the following counterexample. Consider any boolean game B in which Φ1 = {p}, Φ2 = {q} and γ1 = p ∨ q. Clearly, 2 ∈ RAB(1). Thus, 1, 2 ∈ Rbf(B). But, CanB({1}, γ1).

In the next section we consider a new dependence function, called veto-based dependence function, which is stronger than Bonzon et al.'s relevance-based dependence function and which satisfies the four postulates given in Section 2.2.

A new dependence function

The veto-based dependence function, denoted by Vbf, is based on the concept of veto player as defined by [START_REF] Wooldridge | On the computational complexity of qualitative coalitional games[END_REF] and, more generally, in the context of cooperative game theory [START_REF] Osborne | A course in game theory[END_REF].

According to Vbf, agent a depends on agent b, if the intervention of b is necessary to ensure that a will achieve her goal γa. Specifically, a depends on b if and only if the coalition A \ {b} is not capable of making a's goal The following theorem highlights that the four postulates of Section 2.2 are all sound with respect to Vbf.

Theorem 2. Vbf satisfies (Cap), (AP), (Dom), and (Imp).

Proof (Sketch). We only provide the sketch of proof for (AP) and (Dom) as an example.

Suppose that a, b ∈ Vbf(B). By the definitions of Vbf and of the notion of capability, we have that:

(A) a, b ∈ Vbf(B) iff, for all C ⊆ A, if CanB(C, γa) then b ∈ C.
Furthermore, the following property holds for all a ∈ A:

(C) if (for all C ⊆ A, if MinCanB(C, γc) then a ∈ C) then (for all C ⊆ A, if CanB(C, γc) then a ∈ C).
Hence, we have that for all C ⊆ A, if CanB(C, γc) then a ∈ C. By the previous item (A), this is equivalent to c, a ∈ Vbf(B). This shows that Vbf satisfies (Dom).

Dependencies and Nash equilibria

In this final section we explore the connection between Vbf and Nash equilibria.

Clearly boolean games correspond to a specific subclass of games in normal form, namely games in normal form with binary utility functions ua : S -→ {0, 1} defined by: (i) ua(s) = 0 if s |= ¬γa, and (ii) ua(s) = 1 if s |= γa. Purestrategy Nash equilibria and strict Nash equilibria are defined exactly as in standard game theory. Definition 9. Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game. Moreover, let sa ∈ Sa, s A\{a} ∈ S A\{a} and s = sa • s A\{a} . Strategy s ∈ S is a Nash equilibrium iff, for all a ∈ A and for all s ′ a ∈ Sa, ua(sa • s A\{a} ) ≥ ua(s ′ a • s A\{a} ). Strategy s ∈ S is a strict Nash equilibrium iff, for all a ∈ A and for all s ′ a ∈ Sa \ {sa}, ua(sa

• s A\{a} ) > ua(s ′ a • s A\{a} ).
The following definition captures the concept of k-resilient Nash equilibrium by Abraham et al. [START_REF] Abraham | Lower bounds on implementing robust and resilient mediators[END_REF]: 2 a strategy profile s is said to be a k-resilient Nash equilibrium if no coalition of size at most k, taking the actions of its complements as given, can cooperatively deviate in a way that benefits some of its members. We also introduce the new concept of strict k-resilient Nash equilibrium.

′ C ∈ SC , ua(sC • s A\C ) ≥ ua(s ′ C • s A\C ) for all a ∈ C. Strategy s ∈ S is a strict k-resilient Nash equilibrium iff for all C ⊆ A with |C| ≤ k and for all s ′ C ∈ SC \ {sC }, ua(sC • s A\C ) > ua(s ′ C • s A\C ) for all a ∈ C.
Note that strategy s is a 1-resilient Nash equilibrium if and only if it is a Nash equilibrium, and it is a strict 1resilient Nash equilibrium if and only if it is a strict Nash equilibrium. Furthermore, if |A| = k then strategy s ∈ S is a strict k-resilient Nash equilibrium if and only if s is the unique strategy profile that makes all agents happy (i.e., s |= γa for all a ∈ A and, s ′ |= ¬γa for all s ′ = s and for all a ∈ A). This implies that, for every boolean game B with k players, there is at most one strict k-resilient Nash equilibrium.

Our first result concerning the link between Vbf and Nash equilibria is that the dependence relation extracted by means of Vbf from a k-player boolean game with one strict kresilient Nash equilibrium and in which each agent controls at least one propositional atom is complete. More formally: Theorem 3. Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game with k players. If B has one strict k-resilient Nash equilibrium and Φa = ∅ for all a ∈ A, then Vbf(B) = A × A.

Proof (Sketch). As observed above, if |A| = k and s is a strict k-resilient Nash equilibrium then, s is the only strategy profile that makes all agents happy, while all other strategy profiles s ′ make all agents unhappy. Therefore, for all a ∈ A, a can achieve his goal γa only if every agent b in A chooses the component s b in s. Hence, for all a ∈ A, a depends on all other agents. The condition Φa = ∅ for all a ∈ A guarantees that every agent b in A has more than one choice available. Therefore, b can indeed deviate from the strategy profile s by playing something different from s b and making all agents unhappy.

A more interesting result concerns the family of two-player boolean games with more than one strict Nash equilibrium. A typical example of games belonging to this family are pure coordination games [START_REF] Schelling | The strategy of conflict[END_REF] in which the two players in the 2 Abraham et al. uses the term 'strongly k-resilient Nash equilibrium' but, in order simplify exposition, we simply call it 'k-resilient Nash equilibrium'. game achieve their common goal only if they together play one of the many strict Nash equilibria. We can prove that every two-player boolean game with more than one strict Nash equilibrium induces a complete dependence relation. Intuitively, this means that in a two-player game with more than one strict Nash equilibrium (e.g., a two-player pure coordination game) the agents depend on each other. Proof (Sketch). We give the general idea of the proof with the aid of Figure 1. Let B be any boolean game such that A = {a, b}. Moreover, let SN B be the set of strict Nash equilibria in B with |SN B| > 1. The first thing to observe is that two different strict Nash equilibria in SN B necessarily differ in all their components: for all s, s ′ ∈ SN B, if s = s ′ then sa = s ′ a for all a ∈ A. From this fact, one can prove that every row in the boolean game matrix contains at least one 0 for the row player (i.e., player a) and that every column in the boolean game matrix contains at least one 0 for the column player (i.e., player b). This is clearly shown by Figure 1 Note that Theorem 4 cannot be generalized to one-player games. Indeed, as observed above, if a game has k players, then it has at most one strict k-resilient Nash equilibrium. Thus, a one-player game has at most one strict Nash equilibrium.

The following theorem provides a generalization of the preceding Theorem 4 to boolean games with k players that exploits the concept of strict k-resilient Nash equilibrium.

Theorem 5. Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game with k players. If B has more than one strict (k -1)-resilient Nash equilibrium, then Vbf(B) = A × A.

EVALUATING POWER

We turn to the second part of the paper, that is, the construction and analysis of power functions. The input of such a function is a dependence graph. Note that a ≺ b can equivalently be read as a takes precedence over b with respect to power, or a is ranked above b with respect to power. So, it is natural to put the more powerful agent on the left-hand side of the ≺ symbol. Note also that a b may be written as a, b ∈ , if it is more convenient. Similarly, a ≺ b may be written as b, a ∈ .

We are ready to define the main concept of Section 3.

Definition 13. A power function Π transforms any dependence graph D = A, R into a ranking on A.

Note that such functions have been efficiently investigated in particular in [START_REF] Altman | Axiomatic Foundations for Ranking Systems[END_REF], where it is essentially shown that no function can satisfy certain postulates all together.

Postulates for power functions

In the present section, we establish postulates (or axioms) for power functions. The first group of axioms captures the notion of transitivity studied in e.g. [START_REF] Altman | Axiomatic Foundations for Ranking Systems[END_REF]. The principle of transitivity consists of two ideas: more dependents means more power; more powerful dependents means more power as well.

As a preliminary, we need a notation for the dependents of an agent a. Throughout Section 3, when the context is clear, we may omit certain subscripts, e.g., we may write Dep(a) for short.

Next, we need to construct 3 relations between groups of agents from a relation between agents. More precisely, A, B ∈ G1( ) iff the agents of A are at least as numerous and powerful as those of B. The other relations G2 and G3 correspond to the same idea plus an advantage for A in cardinality or quality, respectively. Definition 15. Let be a ranking on a set A. We denote by G1A( ), G2A( ), and G3A( ) the binary relations on the power set of A such that ∀ A, B ⊆ A:

•

A, B ∈ G1( ) iff ∃ f : B inj -→ A (i.e., there exists an injective function f from B to A) s.t. ∀ b ∈ B, f (b) b; • A, B ∈ G2( ) iff |B| < |A| and ∃ f : B inj -→ A s.t. ∀ b ∈ B, f (b) b; • A, B ∈ G3( ) iff ∃ f : B inj -→ A s.t. ∀ b ∈ B, f (b) b and ∃ b ∈ B, f (b) ≺ b.
We are ready to define the axioms of transitivity. We turn to the second group of axioms, which captures the notion of transitivity with dilution studied in e.g. [START_REF] Altman | Axiomatic Foundations for Ranking Systems[END_REF]. By dilution, we mean that the power a gives to certain agents has to be evenly shared between them.

Again, we need preliminaries. First, we need a notation for the agents having power over a: Definition 16. Let D = A, R be a dependence graph and a ∈ A. We denote by PowD(a) the set of all agents having power over a in D, i.e., PowD(a) = {b ∈ A | aRb}.

Next, we need four relations between groups of agents. Intuitively, A, B ∈ GD1( ) iff the agents of A are at least as numerous and powerful as those of B and they do not depend on more agents, i.e., there is no more power dilution. The other relations GD2, GD3, and GD4 capture the same idea plus an advantage for A in cardinality, quality, or dilution, respectively. Definition 17. Let D = A, R be a dependence graph and a ranking on A. We denote by GD1D( ), GD2D( ), GD3D( ), and GD4D( ) the binary relations on the power set of A such that ∀ A, B ⊆ A:

• We can define the axioms of transitivity with dilution. Finally, we introduce a last group of axioms capturing the notion of transitivity with redundancy. Intuitively, there is redundancy in the power of an agent a iff a depends on herself (possibly indirectly) or two direct dependents of a overlap, i.e., at least one depends on the other (possibly indirectly) or they have (possibly indirect) dependents in common. As far as we know, this group of axioms is new.

First, we need to define the extended dependents of a, i.e., the agents depending, directly or indirectly, on a.

Definition 5 .

 5 A dependence function is a function ∆ transforming every boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A into a binary relation R on A, called a dependence relation.

Postulate 2 .

 2 A dependence function ∆ satisfies Absence of power (AP) iff for every boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A and ∀a, b ∈ A, the following holds: if there is no C ⊆ A such that MinCanB(C, γa) and b ∈ C then a, b ∈ ∆(B).

Definition 6 .

 6 Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game and let a, b, c ∈ A. We say that a dominates b with respect to c in B, denoted by DomB(a, b, c), iff ∀C ⊆ A, if MinCanB(C, γc) and b ∈ C then a ∈ C. Our third postulate says that if agent a dominates agent b with respect to agent c then b has power over c only if b has power over c. Postulate 3. A dependence function ∆ satisfies Agent Dominance (Dom) iff for every boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A and ∀a, b, c ∈ A the following holds: if DomB(a, b, c) and c, b ∈ ∆(B) then c, a ∈ ∆(B).

Postulate 4 .

 4 A dependence function ∆ satisfies Implication (Imp) iff for every boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A and ∀a, b, c ∈ A, the following holds: if |= γ b → γa and a, c ∈ ∆(B) then b, c ∈ ∆(B).

Definition 7 . 2 : 1 .

 721 Agent a has a relevance-based dependence on agent b in the boolean game B, i.e., a, b ∈ Rbf(B), if and only if b ∈ RAB(a).As the following theorem highlights Rbf does not satisfy any postulate given in the previous Section 2.Theorem Rbf violates (Cap), (AP), (Dom) and (Imp).

  true, independent of what agent b chooses. More formally: Definition 8. Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game. We say that agent a has a veto-based dependence on agent b in B, or simply, agent a depends on agent b in B, i.e., a, b ∈ Vbf(B), iff there is no s A\{b} ∈ S A\{b} such that for all s b ∈ S b , s A\{b} • s b |= γa.

(

  B) there exists C ⊆ A such that MinCanB(C, γa). Thus, from the previous items (A) and (B), it follows that there exists C ⊆ A such that MinCanB(C, γa) and b ∈ C. This shows that Vbf satisfies (AP). Let us prove that Vbf satisfies (Dom). Suppose that DomB(a, b, c) and c, b ∈ Vbf(B). As shown above, we have c, b ∈ Vbf(B) iff for all C ⊆ A, if CanB(C, γc) then b ∈ C. Thus, for all C ⊆ A, if CanB(C, γc) then b ∈ C. Thus, since DomB(a, b, c) holds, we have that for all C ⊆ A, if MinCanB(C, γc) then a ∈ C. The following property holds:

Definition 10 .

 10 Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a boolean game. Strategy s ∈ S is a k-resilient Nash equilibrium iff for all C ⊆ A with |C| ≤ k and for all s

Figure 1 :

 1 Figure 1: Boolean game with two strict Nash equilibria. Symbol * means that the value is irrelevant.

Theorem 4 .

 4 Let B = A, Φ, {γa}a∈A, {Φa}a∈A be a twoplayer boolean game. If B has more than one strict Nash equilibrium, then Vbf(B) = A × A.

1 a • s 1 b and s 3 a • s 3 b

 133 in which a boolean game with two strict Nash equilibria s is represented. Hence, it follows that Vbf(B) = {a, b} × {a, b}, since there is no sa ∈ Sa such that for all s b ∈ S b , sa • s b |= γa, and there is no s b ∈ S b such that for all sa ∈ Sa, s b • sa |= γ b .

Definition 11 .

 11 A dependence graph is an ordered pair D = A, R , where A is a finite set of agents and R a binary relation on A, called a dependence relation. The output of a power function is a ranking of the agents. Definition 12. A ranking on a set of agents A is a total and transitive binary relation on A. Intuitively, a b means that a is at least as powerful as b. So, a ≺ b (i.e., b a) means that a is strictly more powerful than b.

Definition 14 .

 14 Let D = A, R be a dependence graph and a ∈ A. We denote by Dep D (a) the set of all dependents of a in D, i.e., Dep D (a) = {b ∈ A | bRa}.

Postulate 5 .

 5 A power function Π satisfies the first, second, or third form of transitivity, denoted by (T1), (T2), or (T3), respectively, iff for every dependence graph D = A, R , ∀ a, b ∈ A: (T1) if Dep(a), Dep(b) ∈ G1[Π(D)], then a, b ∈ Π(D); (T2) if Dep(a), Dep(b) ∈ G2[Π(D)], then b, a ∈ Π(D); (T3) if Dep(a), Dep(b) ∈ G3[Π(D)], then b, a ∈ Π(D).

  A, B ∈ GD1( ) iff ∃ f : B inj -→ A s.t. ∀ b ∈ B, f (b) b and ∀ b ∈ B, |Pow[f (b)]| ≤ |Pow(b)|; • A, B ∈ GD2( ) iff |B| < |A| and ∃ f : B inj -→ A s.t. ∀ b ∈ B, f (b) b and ∀ b ∈ B, |Pow[f (b)]| ≤ |Pow(b)|; • A, B ∈ GD3( ) iff ∃ f : B inj -→ A s.t. ∀ b ∈ B, f (b) b, ∀ b ∈ B, |Pow[f (b)]| ≤ |Pow(b)|, and ∃ b ∈ B, f (b) ≺ b; • A, B ∈ GD4( ) iff ∃ f : B inj -→ A s.t. ∀ b ∈ B, f (b) b, ∀ b ∈ B, |Pow[f (b)]| ≤ |Pow(b)|,and ∃ b ∈ B, |Pow[f (b)]| < |Pow(b)|.

Postulate 6 .

 6 A power function Π satisfies the first, second, third, or fourth form of transitivity with dilution, denoted by (TD1), (TD2), (TD3), or (TD4), respectively, iff for every dependence graph D = A, R , ∀ a, b ∈ A: (TD1) if Dep(a), Dep(b) ∈ GD1[Π(D)], then a, b ∈ Π(D); (TD2) if Dep(a), Dep(b) ∈ GD2[Π(D)], then b, a ∈ Π(D); (TD3) if Dep(a), Dep(b) ∈ GD3[Π(D)], then b, a ∈ Π(D); (TD4) if Dep(a), Dep(b) ∈ GD4[Π(D)], then b, a ∈ Π(D).

Definition 18 .

 18 Let D = A, R be a dependence graph. We denote by ExatD the function on {1, 2, . . .} × A such that ∀ i ∈ {1, 2, . . .}, ∀ a ∈ A, ExatD(i, a) is the set of all extended dependents of a in D at distance i, i.e.,Exat(i, a) = Dep(a) if i = 1; b∈Exat(i-1,a) Dep(b) if 1 < i.We define that ExtD(a) = i∈{1,2,...} ExatD(i, a). Next, we need to formalize the notion of overlapping agents: Definition 19. Let D = A, R be a dependence graph and A ⊆ A. We denote by OvrD(A) the fact that two agents of A overlap in D, i.e., ∃ a, b ∈ A, a = b and (a ∈ Ext(b) or b ∈ Ext(a) or Ext(a) ∩ Ext(b) = ∅).

The issue of extracting a dependence relation from a game has also been investigated by Bonzon et al.[START_REF] Bonzon | Dependencies between players in boolean games[END_REF] for the class of boolean games (see Section

for more on this) and by Grossi & Turrini[START_REF] Grossi | Dependence in games and dependence games[END_REF] for the entire class of normal-form games.

As a last preliminary, we need four relations between groups of agents to represent equivalence or advantage in cardinality, quality, and redundancy. Definition 20. Let D = A, R be a dependence graph and a ranking on A. We denote by GR1D( ), GR2D( ), GR3D( ), and GR4D( ) the binary relations on the power set of A such that ∀ A, B ⊆ A:

• A, B ∈ GR1( ) iff ¬Ovr(A) and ∃ f : We can define the axioms of transitivity with redundancy. We conclude this section with dependencies and incompatibilities between the twelve postulates we have defined. We analyze Sbf through the postulates of Section 3.1.

Three existing power functions

Theorem 8. Sbf satisfies (T1), (T2), (TD1), (TD2), (TR1), (TR2), but violates (T3), (TD3), (TD4), (TR3)-(TR5). Another power function studied in the literature is the van den Brink-Gilles function [START_REF] Van Den | Measuring domination in directed graphs[END_REF], which consists in adding power dilution in Sbf.

Definition 22. The power function BGf transforms any dependence graph

Note that, in Theorem 4.2 of [START_REF] Van Den | Measuring domination in directed graphs[END_REF], it is shown that BGf is equivalent to the well-known Shapley power function, if the "worth" of a coalition is naturally defined as the number of dependents of that coalition. A study of the Shapley function can be found in e.g. [START_REF] Ågotnes | Power in normative systems[END_REF].

We turn to the postulate-based analysis of BGf.

Theorem 9. BGf satisfies (TD1), (TD2), (TD4), but violates (T1)-(T3), (TD3), (TR1)-(TR5).

), (TD3), and (TR3) all imply b, a ∈ BGf(D), impossible. Theorem 7 deals with the remaining postulates.

We turn to Pagerank [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF], which is an important and more recent power function, as well as one of the main constituents of the Google search engine. In Pagerank, every agent a transfers credit to every agent b. The main idea is the following: if a depends on b, then more credit is transferred. Such an increase is determined by a fixed damping factor δ.

Definition 23. Let D = A, R be a dependence graph, a, b ∈ A, and δ ∈ (0, 1). We denote by Per Dδ (a, b) the percentage of credit transferred from a to b in D with damping δ, i.e.:

Definition 24. Let D = A, R be a dependence graph and let δ ∈ (0, 1). We denote by Cre Dδ the function on

is the quantity of credit a possesses in D in step i with damping δ, i.e.:

Definition 25. Let D = A, R be a dependence graph, a ∈ A, and δ ∈ (0, 1). We denote by Pr Dδ (a) the final quantity of credit a possesses in D with damping δ, i.e.:

Note that a characterisation of the final quantities of credit in Pagerank can be found in e.g. [START_REF] Page | The PageRank Citation Ranking: Bringing Order to the Web[END_REF]. Proof (Sketch). The satisfaction part follows from (Sum) and (Norm). The violation part holds, either because of Theorem 7 or because a disadvantage in dilution can overcome any advantage in cardinality or quality.

To summarize, there are three families of axioms capturing the notions of transitivity, transitivity-with-dilution, and transitivity-with-redundancy, respectively. The function Sbf satisfies an even part of each family, BGf is more oriented to transitivity-with-dilution, and Prf fully satisfies it.

Three new power functions

In the present section, we construct three new power functions fully satisfying transitivity, transitivity-with-dilution, and transitivity-with-redundancy, respectively. Those three families of axioms have been defined in Section 3.1.

Our first power function is based on the three following ideas: the agents have accounts on which points can be added or removed; the more the dependents of a are numerous and have points on their accounts, the more a has points as well; the more rapidly an agent gets a great number of points, the higher she is ranked.

Definition 27. Let D = A, R be a dependence graph. We denote by AcD the function on {0, 1, . . .} × A such that ∀ i ∈ {0, 1, . . .}, ∀ a ∈ A, AcD(i, a) is the account of a in D in the step i, i.e.: We are ready to axiomatically analyze Abf.

Theorem 12. Abf satisfies (T1)-(T3), (TD1)-(TD3), (TR1)-(TR3), but violates (TD4), (TR4), (TR5).

Proof (Sketch). We begin with (T1). Case A: the dependents of b have the same accounts as the corresponding dependents of a, in any step. Then, the account of a is at least as big as that of b, in any step. Case B: on the contrary, there is a difference, in some step. Let i be the smallest step where there is a difference. Then, the account of a is greater than that of b in step i + 1 (and at least as big below i + 1). The axiom (T3) holds, because of the same proof, except that Case A is impossible. Concerning (T2), it follows from the top priority of Step 0. The other axioms are satisfied or violated because of Theorems 6 and 7.

Our second power function consists in introducing the notion of power dilution in Abf.

Definition 29. Let D = A, R be a dependence graph. We denote by DacD the function on {0, 1, . . .} × A such that ∀ i ∈ {0, 1, . . .}, ∀ a ∈ A, DacD(i, a) is the dilution-based account of a in D in the step i, i.e.:

Definition 30. The power function Daf transforms any dependence graph D = A, R into the ranking s.t. ∀ a, b ∈ A, a, b ∈ Daf(D) iff one of the two following cases holds:

We axiomatically analyze Daf.

COMBINING FUNCTIONS

As emphasized in the introduction, dependence functions and power functions can be combined to produce gamebased power evaluations that satisfy interesting properties.

Definition 32. A game-based power evaluation is a function Γ transforming any boolean game B = A, Φ, {γa}a∈A, {Φa}a∈A into a ranking on A.

A first postulate for game-based power evaluation is the following: if a dominates b with respect to every agent in the game, then a should be at least as powerful as b. More formally: Postulate 8. A game-based power evaluation Γ satisfies Universal Dominance (UDom) iff, for every boolean game

The second postulate says the following: if an agent a does not appear in any minimal effective coalition for the goal of a player in the game, then each agent in the game is at least as powerful as a. More formally:

CONCLUSION

Let's take stock. The main contributions of the paper are the following:

• a postulate-based analysis of the new dependence function Vbf and of the existing dependence function Rbf, with special emphasis on the advantages of the former compared to the latter;

• a descriptive analysis of the relationship between Vbf and the concepts of Nash equilibrium and k-resilient Nash equilibrium;

• a postulate-based analysis of three existing power functions Sbf, BGf, and Prf and four new power functions Abf, Daf, Cbf, and Dbf, with special emphasis on the fact that most of our new functions satisfy postulates that are violated by the existing ones.

As future work, we plan to characterize our dependence and power functions, that is, to find enough postulates so that only one method satisfies them all together. We also plan to provide an axiomatic analysis of a weaker notion of dependence, which consists in generalizing the concept of veto to coalitions. The idea is that an agent a depends on another agent b if and only if, there exists a coalition of which b is a member such that its intervention is necessary to ensure that a will achieve her goal.