Lattices and discrete methods in cooperative games and decisions

Questa tesi si pone l'obiettivo di presentare la teoria dei giochi, in particolare di quelli cooperativi, insieme alla teoria delle decisioni, inquadrandole formalmente in termini di matematica discreta. Si tratta di due campi dove l'indagine si origina idealmente da questioni applicative, e dove tuttavia sono sorti e sorgono problemi più tipicamente teorici che hanno interessato e interessano gli ambienti matematico e informatico. Anche se i contributi iniziali sono stati spesso formulati in ambito continuo e utilizzando strumenti tipici di teoria della misura, tuttavia oggi la scelta di modelli e metodi discreti appare la più idonea. L'idea generale è quindi quella di guardare fin da subito al complesso dei modelli e dei risultati che si intendono presentare attraverso la lente della teoria dei reticoli. Ciò consente di avere una visione globale più nitida e di riuscire agilmente ad intrecciare il discorso considerando congiuntamente la teoria dei giochi e quella delle decisioni. Quindi, dopo avere introdotto gli strumenti necessari, si considerano modelli e problemi con il fine preciso di analizzare dapprima risultati storici e solidi, proseguendo poi verso situazioni più recenti, più complesse e nelle quali i risultati raggiunti possono suscitare perplessità. Da ultimo, vengono presentate alcune questioni aperte ed associati spunti per la ricerca.

The Banzhaf Value in the Presence of Externalities

[eng] We propose two generalizations of the Banzhaf value for partition function form games. In both cases, our approach is based on probability distributions over the set of possible coalition structures that may arise for any given set of agents. First, we introduce a family of values, one for each collection of the latter probability distributions, defined as the Banzhaf value of an expected coalitional game. Then, we provide two characterization results for this new family of values within the framework of all partition function games. Both results rely on a property of neutrality with respect to amalgamation of players. Second, as this collusion transformation fails to be meaningful for simple games in partition function form, we propose another generalization of the Banzhaf value which also builds on probability distributions of the above type. This latter family is characterized by means of a neutrality property which uses an amalgamation transformation of players for which simple games are closed.

The Banzhaf Value in the Presence of Externalities

[eng] We propose two generalizations of the Banzhaf value for partition function form games. In both cases, our approach is based on probability distributions over the set of possible coalition structures that may arise for any given set of agents. First, we introduce a family of values, one for each collection of the latter probability distributions, defined as the Banzhaf value of an expected coalitional game. Then, we provide two characterization results for this new family of values within the framework of all partition function games. Both results rely on a property of neutrality with respect to amalgamation of players. Second, as this collusion transformation fails to be meaningful for simple games in partition function form, we propose another generalization of the Banzhaf value which also builds on probability distributions of the above type. This latter family is characterized by means of a neutrality property which uses an amalgamation transformation of players for which simple games are closed.

Az ellenzék ereje - általánosított súlyozott szavazási játékok (Minority power - generalized weighted voting games)

A hagyományos szavazási játékok speciális átruházható hasznosságú, kooperatív játékok, úgynevezett egyszerű játékok, ahol a játékosok a pártok, és az egyes koalíciók értéke 1 vagy 0 attól függően, hogy az adott koalíció elég erős-e az adott jogszabály elfogadásához, vagy sem. Ebben a cikkben bevezetjük az általánosított súlyozott szavazási játékok fogalmát, ahol a pártok mandátumainak száma a valószínűségi változó. Magyar példákon keresztül mutatjuk be az új megközelítés használhatóságát. / === / Voting games are cooperative games with transferable utility, so-called simple games, where the players are parties and the value of a coalition may be 0 or 1 depending on its ability to pass a new law. The authors introduce the concept of generalized weighted voting games where the parties' strengths are random variables. taking examples from Hungary to illustrate the use of this approach.

The Shapley value for airport and irrigation games

In this paper cost sharing problems are considered. We focus on problems given by rooted trees, we call these problems cost-tree problems, and on the induced transferable utility cooperative games, called irrigation games. A formal notion of irrigation games is introduced, and the characterization of the class of these games is provided. The well-known class of airport games Littlechild and Thompson (1977) is a subclass of irrigation games. The Shapley value Shapley (1953) is probably the most popular solution concept for transferable utility cooperative games. Dubey (1982) and Moulin and Shenker (1992) show respectively, that Shapley's Shapley (1953) and Young (1985)'s axiomatizations of the Shapley value are valid on the class of airport games. In this paper we show that Dubey (1982)'s and Moulin and Shenker (1992)'s results can be proved by applying Shapley (1953)'s and Young (1985)'s proofs, that is those results are direct consequences of Shapley (1953)'s and Young (1985)'s results. Furthermore, we extend Dubey (1982)'s and Moulin and Shenker (1992)'s results to the class of irrigation games, that is we provide two characterizations of the Shapley value for cost sharing problems given by rooted trees. We also note that for irrigation games the Shapley value is always stable, that is it is always in the core Gillies (1959).

Regression games

The solution of a TU cooperative game can be a distribution of the value of the grand coalition, i.e. it can be a distribution of the payo (utility) all the players together achieve. In a regression model, the evaluation of the explanatory variables can be a distribution of the overall t, i.e. the t of the model every regressor variable is involved. Furthermore, we can take regression models as TU cooperative games where the explanatory (regressor) variables are the players. In this paper we introduce the class of regression games, characterize it and apply the Shapley value to evaluating the explanatory variables in regression models. In order to support our approach we consider Young (1985)'s axiomatization of the Shapley value, and conclude that the Shapley value is a reasonable tool to evaluate the explanatory variables of regression models.

The kernel is in the least core for permutation games

Permutation games are totally balanced transferable utility cooperative games arising from certain sequencing and re-assignment optimization problems. It is known that for permutation games the bargaining set and the core coincide, consequently, the kernel is a subset of the core. We prove that for permutation games the kernel is contained in the least core, even if the latter is a lower dimensional subset of the core. By means of a 5-player permutation game we demonstrate that, in sense of the lexicographic center procedure leading to the nucleolus, this inclusion result can not be strengthened. Our 5-player permutation game is also an example (of minimum size) for a game with a non-convex kernel.

Sequencing games without initial order

In this note we study uncertainty sequencing situations, i.e., 1-machine sequencing situations in which no initial order is specified. We associate cooperative games with these sequencing situations, study their core, and provide links with the classic sequencing games introduced by Curiel et al. (1989). Moreover, we propose and characterize two simple cost allocation rules for uncertainty sequencing situations with equal processing times.

Non-cooperative incentives to share knowledge in competitive environments

In this paper we study a model where non-cooperative agents may exchange knowledge in a competitive environment. As a potential factor that could induce the knowledge disclosure between humans we consider the timing of the moves of players. We develop a simple model of a multistage game in which there are only three players and competition takes place only within two stages. Players can share their private knowledge with their opponents and the knowledge is modelled as in uencing their marginal cost of e¤ort. We identify two main mechanisms that work towards knowledge disclosure. One of them is that before the actual competition starts, the stronger player of the rst stage of a game may have desire to share his knowledge with the "observer", be- cause this reduces the valuation of the prize of the weaker player of that stage and as a result his e¤ort level and probability of winning in a ght. Another mechanism is that the "observer" may have sometimes desire to share knowledge with the weaker player of the rst stage, because in this way, by increasing his probability of winning in that stage, he decreases the probability of winning of the stronger player. As a result, in the second stage the "observer" may have greater chances to meet the weaker player rather than the stronger one. Keywords: knowledge sharing, strategic knowledge disclosure, multistage contest game, non-cooperative games

On some geometry and equivalence classes of normal form games

Equivalence classes of normal form games are defined using the geometryof correspondences of standard equilibiurm concepts like correlated, Nash,and robust equilibrium or risk dominance and rationalizability. Resultingequivalence classes are fully characterized and compared across differentequilibrium concepts for 2 x 2 games. It is argued that the procedure canlead to broad and game-theoretically meaningful distinctions of games aswell as to alternative ways of viewing and testing equilibrium concepts.Larger games are also briefly considered.

English grammar games in primary education

The purpose of this study was to analyse pupils’ English grammar acquisition from competitive and cooperative approaches. After searching a wide range of authors’ contribution to English language learning, grammar acquisition, classroom environment and language games. A hundred and twenty pupils from three schools; two from Ripoll and one from Campdevànol were enrolled in a specific grammar games intervention. This was imparted in three different phases: first of all, I interviewed the three teachers from the three schools, then I put into practice my competitive and cooperative games which I designed especially for this study (all the sessions were carried, assessed and registered by myself); finally, all pupils answered a questionnaire related to their experiences in my grammar games intervention. Analysis of teaching interventions showed that, in terms of English language acquisition, pupils used different strategies to show up understanding and achieve the objective of the game such as: recalling their background knowledge, expressing sentences influenced by their internal language and their mother tongue. Data collected revealed that most difficulties were founded in team work, even more in competitive games. The results also showed that team work is something which has to be developed step by step in order to achieve language learning and all pupils’ active participation successfully.

Axiomatization of the nucl eolus of assignment games

On the domain of general assignment games (with possible reservation prices) the core is axiomatized as the unique solution satisfying two consistency principles: projection consistency and derived consistency. Also, an axiomatic characterization of the nucleolus is given as the unique solution that satisfies derived consistency and equal maximum complaint between groups. As a consequence, we obtain a geometric characterization of the nucleolus. Maschler et al. (1979) provide a geometrical characterization for the intersection of the kernel and the core of a coalitional game, showing that those allocations that lie in both sets are always the midpoint of certain bargaining range between each pair of players. In the case of the assignment game, this means that the kernel can be determined as those core allocations where the maximum amount, that can be transferred without getting outside the core, from one agent to his / her optimally matched partner equals the maximum amount that he / she can receive from this partner, also remaining inside the core. We now prove that the nucleolus of the assignment game can be characterized by requiring this bisection property be satisfied not only for optimally matched pairs but also for optimally matched coalitions. Key words: cooperative games, assignment game, core, nucleolus

Cooperative VS. Non-cooperative Truels: Little Agreement, but Does that Matter?

It is well-known that non-cooperative and cooperative game theory may yield different solutions to games. These differences are particularly dramatic in the case of truels, or three-person duels, in which the players may fire sequentially or simultaneously, and the games may be one-round or n-round. Thus, it is never a Nash equilibrium for all players to hold their fire in any of these games, whereas in simultaneous one-round and n-round truels such cooperation, wherein everybody survives, is in both the a -core and ß -core. On the other hand, both cores may be empty, indicating a lack of stability, when the unique Nash equilibrium is one survivor. Conditions under which each approach seems most applicable are discussed. Although it might be desirable to subsume the two approaches within a unified framework, such unification seems unlikely since the two approaches are grounded in fundamentally different notions of stability.