Search

This is a post-peer-review, pre-copyedit version of an article published in Optimization letters. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11590-020-01647-3 The paper provides a new characterization of weighted games within the class of simple games. It is based on a stronger form of the point-set-additive pseudoweighting property of simple games. The characterization obtained is of interest in various research fields such as game theory, coherent structures, logic gates, operations research and Boolean algebra. A (monotonic) simple game corresponds to an inequivalent (monotonic) function in Boolean algebra and a weighted game corresponds to a threshold function. The characterization obtained provides a better understanding of these mathematical structures while opening new prospects for solving numerous open problems in these areas. This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015–66818-P(MINECO/FEDER).

An influence game is a simple game represented over an influence graph (i.e., a labeled, weighted graph) on which the influence spread phenomenon is exerted. Influence games allow applying different properties and parameters coming from cooperative game theory to the contexts of social network analysis, decision-systems, voting systems, and collective behavior. The exact calculation of several of these properties and parameters is computationally hard, even for a small number of players. Two examples of these parameters are the length and the width of a game. The length of a game is the size of its smaller winning coalition, while the width of a game is the size of its larger losing coalition. Both parameters are relevant to know the levels of difficulty in reaching agreements in collective decision-making systems. Despite the above, new bio-inspired metaheuristic algorithms have recently been developed to solve the NP-hard influence maximization problem in an efficient and approximate way, being able to find small winning coalitions that maximize the influence spread within an influence graph. In this article, we apply some variations of this solution to find extreme winning and losing coalitions, and thus efficient approximate solutions for the length and the width of influence games. As a case study, we consider two real social networks, one formed by the 58 members of the European Union Council under nice voting rules, and the other formed by the 705 members of the European Parliament, connected by political affinity. Results are promising and show that it is feasible to generate approximate solutions for the length and width parameters of influence games, in reduced solving time "Funding Statement: F. Riquelme has been partially supported by Fondecyt de Iniciación 11200113, Chile, and by the SEGIB scholarship of Fundación Carolina, Spain; X. Molinero under grants PID2019-104987GB-I00 (JUVOCO); M. Serna under grants PID2020-112581GB-C21 (MOTION) and 2017-SGR-786 (ALBCOM)"

In this paper we discuss on several ways to extend power indices defined on simple games to the context of (j, 2)-games, i.e., games with 2 possible outputs and j possible input levels. The purpose of this paper is more conceptual than technical, and shows that different power indices can be obtained in (j, 2)-games depending on how the criticality of a player is measured. Some power indices for simple games, regarded as measures of power as payment, can be obtained from the selection of two items: (1) a probabilistic model, and (2) a collection of winning coalitions. The combination of two particular probabilistic models and three collections of winning coalitions lead to six well-known power indices for simple games. The Banzhaf and the Johnston power indices are among them. The main goal of the paper is to discuss the generalizations of these six power indices from (2, 2)-games to (j, 2)-games for j=3. The probabilistic model and the collection of winning coalitions are trivially extendable to (j, 2)-games. However, at least four possible ways of measuring the criticality of a player can be considered in this new context, and lead to different possible extensions of the six power indices to (j, 2)-games. We highlight two of them as being the most interesting under our point of view. The first one would be suitable for assessing sensitivity, because it measures the player’s ability to modify the output by a small change in his input level. The second one would be adequate to evaluate strength, because it measures the voter’s ability to modify the output by any change in his voting. The main conclusion is that different extensions of the considered power indices, as the Banzhaf and the Jonnston indices, are possible for j=3 and that they should be taken into account when working in a multiple input context. This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P(MINECO/FEDER).

We introduce collective decision-making models associated with influence spread under the linear threshold model in social networks. We define the oblivious and the non-oblivious influence models. We also introduce the generalized opinion leader–follower model (gOLF) as an extension of the opinion leader–follower model (OLF) proposed by van den Brink et al. (2011). In our model we allow rules for the final decision different from the simple majority used in OLF. We show that gOLF models are non-oblivious influence models on a two-layered bipartite influence digraph. Together with OLF models, the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures for the decision models introduced in the paper. We show that the problem of computing the satisfaction or the power measure is #P-hard in all the introduced models even when the subjacent social network is a bipartite graph. Complementing this result, we provide two subfamilies of decision models in which both measures can be computed in polynomial time. We show that the collective decision functions are monotone and therefore they define an associated simple game. We relate the satisfaction and the power measures with the Rae index and the Banzhaf value of an associated simple game. This will allow the use of known approximation methods for computing the Banzhaf value, or the Rae index to their practical computation.

We survey some recent work of Maria Serna concerning strategic games. We first examine some results related to the formal representation of strategic games and the complexity of problems related to both the existence of equilibria and the equivalence of games. These results provided a better understanding of how the succinctness of the game representation affects the complexity of such problems. We then describe some work dealing with the definition of new strategic games. The study of a Network Formation Game with asymmetric players, and the introduction of Celebrity Games as well as of Strategic Search Games intend to explain the natural behaviour of agents acting in some particular environments like communication networks, social networks, or even networks that contain valuable items hidden in different nodes. This work was partially supported by funds from the AGAUR, Spain of the Government of Catalonia under project ref. 2017 SGR 786 (ALBCOM), by the Spanish Ministry for Economy and Competitiveness (MINECO), Spain and by the European Union (FEDER funds), under grants ref. TIN2017-86727-C2-1-R.

This is a post-peer-review, pre-copyedit version of an article published in Group decision and negotiation. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10726-020-09718-7. The Banzhaf power index for games admits several extensions if the players have more than two ordered voting options. In this paper we prove that the most intu-itive and recognized extension of the index fails to preserve the desirability rela-tion for games with more than three ordered input levels of approval, a failure that undermines the index to be a good measure of power. This leads us to think of an alternative to the Banzhaf index for several input levels of approval. We propose a candidate for which it is proved that: (1) coincides with the Banzhaf index for sim-ple games, (2) it is proportional to its known extension for three levels of approval, and (3) preserves the desirability relation regardless of the number of input levels of approval. This new index is based on measuring the total capacity the player has to alter the outcome. In addition, it can be expressed through a very appropriate mathematical formulation that greatly facilitates its computation. Defining exten-sions of well-established notions in a wider context requires a careful analysis. Dif-ferent extensions can provide complementary nuances and, when this occurs, none of them can be considered to be ‘the’ extension. As shown in this paper, this situa-tion applies when trying to extend the Banzhaf power index from simple games to the broader context of games with several ordered input levels of approval. This research was partially supported by funds from: the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P (MINECO/FEDER), and the Spanish Ministry of Science and Innovation grant PID2019-I04987GB-I00.

This work proposes a novel data-driven distributed formation-control approach based on multi-population evolutionary games, which is structured in a leader-follower scheme. The methodology considers a time-varying communication graph that describes how the multiple agents share information to each other. We present stability guarantees for configurations given by time-varying interaction networks, making the proposed method suitable for real-world problems where communication constraints change along the time. Additionally, the proposed formation controller allows for an agent to leave or enter the group without the need to modify the behaviors of other agents in the group. This game-theoretical approach is evaluated through numerical simulations and real outdoors experimental results using a fleet of aerial autonomous vehicles, showing the control performance., J. Barreiro-Gomez acknowledges support from U.S. Air Force Office of Scientific Research under grant number FA9550-17-1-0259, and from the Research Center on Stability, Instability and Turbulence (SITE). This material is based upon work supported by Tamkeen under the NYU Abu Dhabi Research Institute grant CG002. I. Mas, J. I. Giribet, P. Moreno and R. Sanchez-Peña acknowledge the support of the W911NF-14-1-0008 grant from the USAITC (RDECOM, USA), and PICT 2014-2055 and PICT 2016-2016 from FONCYT (Argentina). C. Ocampo-Martinez acknowledges the project DEOCS Ref. DPI2016-76493-C3-3-R from the Spanish Ministry of Science and Education for partially supporting this research. N. Quijano thanks support from Air Force Office of Scientific Research. This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-19-1-0014.

This is a post-peer-review, pre-copyedit version of an article published in Soft computing. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00500-020-05422-5 Boolean functions have a fundamental role in neural networks and machine learning. Enumerating these functions and significant subclasses is a highly complex problem. Therefore, it is of interest to study subclasses that escape this limitation and can be enumerated by means of sequences depending on the number of variables. In this article, we obtain seven new formulas corresponding to enumerations of some subclasses of Boolean functions. The versatility of these functions does the problem interesting to several different fields as game theory, hypergraphs, reliability, cryptography or logic gates.

Purpose: We expand a previous discussion in this journal by proposing a new solution concept, based on game theory, for profit allocation with the aim of aligning incentives in collaborative supply chains.Design/methodology/approach: Through the Gately’s notion of propensity to disrupt, we minimize the desire of the nodes to leave the grand coalition in the search of a self-enforcing allocation mechanism.Findings: We discuss the benefits and limitations of this solution in comparison with more established alternatives (e.g. nucleolus and Shapley value). We show that it considers the bargaining power of the nodes, but it may not belong to the core.Originality/value: Finding a fair and self-enforcing scheme for incentive alignment, and specifically profit allocation, is essential to ensure the long-term sustainability of collaborative supply chains.

This paper aims to develop, for any cooperative game, a solution notion that enjoys stability and consists of a coalition structure and an associated payoff vector derived from the Shapley value. To this end, two concepts are combined: those of strong Nash equilibrium and Aumann--Dr\`{e}ze coalitional value. In particular, we are interested in conditions ensuring that the grand coalition is the best preference for all players. Monotonicity, convexity, cohesiveness and other conditions are used to provide several theoretical results that we apply to numerical examples including real--world economic situations.

We describe voting mechanisms to study voting systems. The classical power indices applied to simple games just consider parties, players or voters. Here, we also consider games with a priori unions, i.e., coalitions among parties, players or voters. We measure the power of each party, player or voter when there are coalitions among them. In particular, we study real situations of voting systems using extended Shapley–Shubik and Banzhaf indices, the so-called coalitional power indices. We also introduce a dynamic programming to compute them.

Predictive Business Process Monitoring is becoming an essential aid for organizations, providing online operational support of their processes. This paper tackles the fundamental problem of equipping predictive business process monitoring with explanation capabilities, so that not only the what but also the why is reported when predicting generic KPIs like remaining time, or activity execution. We use the game theory of Shapley Values to obtain robust explanations of the predictions. The approach has been implemented and tested on real-life benchmarks, showing for the first time how explanations can be given in the field of predictive business process monitoring., Comment: Galanti, R., Coma-Puig, B., de Leoni, M., Carmona, J., Navarin, N.: Explainable Predictive Process Monitoring, the International Conference on Process Mining (ICPM 2020), IEEE Computational Intelligence Society, 2020. Article accepted for publication

Cooperative game theory considers simple games and influence games as essential classes of games. A simple game can be viewed as a model of voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. An influence game is a cooperative game in which a team of players (or coalition) succeeds if it is able to convince sufficiently many agents to participate in a task. Furthermore, influence decision models allow to represent discrete system dynamics as graphs whose nodes are activated according to an influence spread model. It let us to depth in the social network analysis. All these concepts are applied to a wide variety of disciplines, such as social sciences, economics, marketing, cognitive sciences, political science, biology, computer science, among others. In this survey we present different advances in these topics, joint work with M. Serna. These advances include representations of simple games, the definition of influence games, and how to characterize different problems on influence games (measures, values, properties and problems for particular cases with respect to both the spread of influence and the structure of the graph). Moreover, we also present equivalent models to the simple games, the computation of satisfaction and power in collective decision-making models, and the definition of new centrality measures used for social network analysis. In addition, several interesting computational complexity results have been found.

Nowadays interactions with the World Wide Web are ubiquitous. Users interact through a number of steps consisting of site calls and handling results that can be automatized as orchestrations. Orchestration results have an inherent degree of uncertainty due to incomplete Web knowledge and orchestration semantics are characterized in terms of imprecise probabilistic choices. We consider two aspects in this imprecise semantic characterization. First, when local knowledge (even imprecise) of some part of the Web increases, this knowledge goes smoothly through the whole orchestration. We deal formally with this aspect introducing orchestration refinements. Second, we analyze refinement under uncertainty in the case of parallel composition. Uncertain knowledge is modeled by an uncertainty profile. Such profiles allow us to look at the uncertainty through a zero-sum game, called angel/daemon-game. We propose to use the structure of the Nash equilibria to refine uncertainty. In this case the information improves not through cooperation but through the angel and daemon competition.

In the area of Wireless Sensor Networks (WSNs), improving energy efficiency and network lifetime is one of the most important and challenging issues. Most of the considered WSNs are formed by nodes with limited resources, in which each node plays dual rule of both sensing the environment and relaying traffic to the sink from other nodes. On the one hand, the nodes need to stay alive as long as possible by achieving energy efficiency. On the other hand, they have to provide the required service. This conflict of interest makes game theory very useful in WSNs. Moreover, nodes usually have to make decisions with limited information about the state of the network. Game theory has been used recently in a remarkable amount of research in this area. In this survey, we review the most recent papers about using game theory in WSNs to achieve a trade-off between maximizing the network lifetime and providing the required service. The paper contains a complete taxonomy of games applied to this specific research problem. It summarizes and compares the different published proposals along with tables and statistical charts showing in which domains game theory has been applied recently. Overall, the paper will give to researchers a clear view of the newest trends in this research area, underlining its main challenges and hopefully fostering discussions and new research directions.

The envisioned smart grid aims at improving the interaction between the supply-and the demand-side of the electricity network, creating unprecedented possibilities for optimizing the energy usage at different levels of the grid. In this paper, we propose a distributed demand-side management (DSM) method intended for smart grid users with load prediction capabilities, who possibly employ dispatchable energy generation and storage devices. These users participate in the day-ahead market and are interested in deriving the bidding, production, and storage strategies that jointly minimize their expected monetary expense. The resulting day-ahead grid optimization is formulated as a generalized Nash equilibrium problem (GNEP), which includes global constraints that couple the users' strategies. Building on the theory of variational inequalities, we study the main properties of the GNEP and devise a distributed, iterative algorithm converging to the variational solutions of the GNEP. Additionally, users can exploit the reduced uncertainty about their energy consumption and renewable generation at the time of dispatch. We thus present a complementary DSM procedure that allows them to perform some unilateral adjustments on their generation and storage strategies so as to reduce the impact of their real-time deviations with respect to the amount of energy negotiated in the day-ahead. Finally, numerical results in realistic scenarios are reported to corroborate the proposed DSM technique.

The assignment game introduced by Shapley and Shubik (1972)Â? 6] is a model for a two-sided market where there is an exchange of indivisible goods for money and buyers or sellers demand or supply exactly one unit of the goods. We give a procedure to compute the nucleolus of any assignment game, based on the distribution of equal amounts to the agents, until the game is reduced to fewer agents.

In microgrids, the integration of distributed energy resources (DERs) in the residential sector can improve power reliability, and potentially reduce power demands and carbon emissions. Improving the utilization of renewable energy in households is a critical challenge for DERs. In this regard, renewable power sharing is one of the possible solutions to tackle this problem. Even though this solution has attracted significant attention recently, most of the proposed power sharing frameworks focus more on centralized schemes. In contrast, in this paper, the performance of a proposed distributed power sharing framework is investigated. The problem is formulated as a repeated game between households in a microgrid. In this game, each household decides to cooperate and borrow/lend some amount of renewable power from/to a neighboring household, or to defect and purchase the entire demands from the main grid based on a payoff function. The Nash equilibrium of this game is characterized and the effect of the strategies taken by the households on the system is analyzed. We conduct an extensive evaluation using real demand data from 12 households of different sizes and power consumption profiles in Stockholm. Numerical results indicate that cooperation is beneficial from both an economical and environmental perspective and that households can achieve cost savings up to 20 %. This work was partially supported by projects TIN2013-47272-C2-2, TEC2012-32354 and SGR-2014-881.

Videogame technology is quickly maturing and approaching levels of realism once reserved to 3D rendering applications used in architecture, in realtime and with the capacity to react in real-time to user input. This paper describes an educational experience using videogame technology in architecture education, exploring its applicability in the field in architecture compared to more traditional media. A prototype application modeling a proposed urban space was developed using Unreal Engine and a group of architecture students were asked to use the software to navigate the virtual environment. The development process of the applications is discussed as well as the design of the survey to assess the partic‐ ipants’ experience in four key areas (a) player profile, (b) experience using the beta version, (c) use of videogame technology as an educational tool, and (d) applicability of game engines in Architecture.

Cooperation among nodes is fundamental for the operation of mobile ad hoc networks(MANETs). In such networks, there could be selfish nodes that use resources from other nodes to send their packets but that do not offer their resources to forward packets for other nodes.Thus,a cooperation enforcement mechanism is necessary. Trust models have been proposed as mechanisms to incentive cooperation in MANET sand some of them are based on game theory concepts. Among game theoretic trust models, those that make nodes’ strategies evolve genetically have shown promising results for cooperation improvement. However,current approaches propose a highly centralized genetic evolution which render them unfeasible for practical purposes in MANETs. In this article, we propose a trust model based on a non-cooperative game that uses a bacterial-like algorithm to let the nodes quickly learn the appropriate cooperation behavior. Our model is completely distributed, achieves optimal cooperation values in a small fraction of time compared with centralized algorithms,and adapts effectively to environmental changes.

©2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The emerging data traffic demand has caused a massive deployment of network infrastructure, including Base Stations (BSs) and Small Cells (SCs), leading to increased energy consumption and expenditures. However, the network underutilization during low traffic periods enables the Mobile Network Operators (MNOs) to save energy by having their traffic served by third party SCs, thus being able to switch off their BSs. In this paper, we propose a novel market approach to foster the opportunistic utilization of the unexploited SCs capacity, where the MNOs, instead of requesting the maximum capacity to meet their highest traffic expectations, offer a set of bids requesting different resources from the third party SCs at lower costs. Motivated by the conflicting financial interests of the MNOs and the third party, the restricted capacity of the SCs that is not adequate to carry the whole traffic in multi-operator scenarios, and the necessity for energy efficient solutions, we introduce a combinatorial auction framework, which includes i) a bidding strategy, ii) a resource allocation scheme, and iii) a pricing rule. We propose a multiobjective framework as an energy and cost efficient solution for the resource allocation problem, and we provide extensive analytical and experimental results to estimate the potential energy and cost savings that can be achieved. In addition, we investigate the conditions under which the MNOs and the third party companies should take part in the proposed auction.

The Firefighter Problem was proposed in 1995 as a deterministic discrete-time model for the spread and containment of a fire. The problem is defined on an undirected finite graph G = (V, E), where fire breaks out initially at f nodes. In each subsequent time-step, two actions occur: a certain number b of firefighters are placed on nonburning nodes, permanently protecting them from the fire, then the fire spreads to all nondefended neighbors of the nodes on fire. Because the graph is finite, at some point each node is either on fire or saved, and thus the fire cannot spread further. One of the objectives for the problem is to place the firefighters in such a way that the number of saved nodes is maximized. The applications of the Firefighter Problem reach from real fires to the spreading of diseases and the containment of floods. Furthermore, it can be used to model the spread of computer viruses or viral marketing in communication networks. Most research on the problem considers the case in which the fire starts in a single place (i.e., f = 1), and in which the budget of available firefighters per time-step is one (i.e., b = 1). So does the work in this study. This configuration already leads to hard problems and, even in this case, the problem is known to be NP-hard. In this work, we study the problem from a game-theoretical perspective. We introduce a strategic game model for the Firefighter Problem to tackle its complexity from a different angle. We refer to it as the Firefighter Game. Such a game-based context seems very appropriate when applied to large networks where entities may act and make decisions based on their own interests, without global coordination. At every time-step of the game, a player decides whether to place a new firefighter in a nonburning node of the graph. If so, he must decide where to place it. By placing it, the player is indirectly deciding which nodes to protect at that time-step. We define different utility functions in order to model selfish and nonselfish scenarios, which lead to equivalent games. We show that the Price of Anarchy (PoA) is linear for a particular family of graphs, but it is at most two for trees. We also analyze the quality of the equilibria when coalitions among players are allowed. It turns out that it is possible to compute an equilibrium in polynomial time, even for constant-size coalitions. This yields to a polynomial time approximation algorithm for the problem and its approximation ratio equals the PoA of the corresponding game. We show that for some specific topologies, the PoA is constant when constant-size coalitions are considered.

A framework for assessing the robustness of long-duration repetitive orchestrations in uncertain evolving environments is proposed. The model assumes that service-based evaluation environments are stable over short time-frames only; over longer periods service-based environments evolve as demand fluctuates and contention for shared resources varies. The behaviour of a short-duration orchestration E in a stable environment is assessed by an uncertainty profile\(\mathcal U\) and a corresponding zero-sum angel-daemon game \(\varGamma (\mathcal U)\) [2]. Here the angel-daemon approach is extended to assess evolving environments by means of a subfamily of stochastic games. These games are called strategy oblivious because their transition probabilities are strategy independent. It is shown that the value of a strategy oblivious stochastic game is well defined and that it can be computed by solving a linear system. Finally, the proposed stochastic framework is used to assess the evolution of the Gabrmn IT system.

Some distinguished types of voters, as vetoers, passers or nulls, as well as some others, play a significant role in voting systems because they are either the most powerful or the least powerful voters in the game independently of the measure used to evaluate power. In this paper we are concerned with the design of voting systems with at least one type of these extreme voters and with few types of equivalent voters, with this purpose in mind we enumerate these special classes of games and find out that its number always follows a Fibonacci sequence with smooth polynomial variations. As a consequence we find several families of games with the same asymptotic exponential behavior excepting of a multiplicative factor which is the golden number or its square. From a more general point of view, our studies are related with the design of voting structures with a predetermined importance ranking., 24 pages

The emerging increase of the number of Base Stations causes redundant energy consumption, especially during low traffic periods, when the Base Stations capacity is underutilized. In this paper, we study energy efficiency issues in multi-operator mobile networks. Our primary goal is to save energy, without compromising the offered Quality of Service, by switching off the excessive Base Stations. To this end, we propose a novel game theoretic strategy using cost-based functions to decide the best suitable Base Stations to remain active. Mathematical analysis and simulations demonstrate that the proposed scheme can significantly reduce the energy consumption.

In lowest unique bid auctions, $N$ players bid for an item. The winner is whoever places the \emph{lowest} bid, provided that it is also unique. We use a grand canonical approach to derive an analytical expression for the equilibrium distribution of strategies. We then study the properties of the solution as a function of the mean number of players, and compare them with a large dataset of internet auctions. The theory agrees with the data with striking accuracy for small population size $N$, while for larger $N$ a qualitatively different distribution is observed. We interpret this result as the emergence of two different regimes, one in which adaptation is feasible and one in which it is not. Our results question the actual possibility of a large population to adapt and find the optimal strategy when participating in a collective game., 6 pag. - 7 figs - added Supplementary Material. Changed affiliations. Published version

The original publication is available at www.rairo-ro.org Simple games cover voting systems in which a single alter- native, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, which are desirable properties to be fulfilled for a simple game. Finally, we consider the possibility of representing a game in a more succinct and natural way and show that the corresponding recognition problem is hard.

We introduce the novel concept of coprivacy or co-operative privacy to make privacy preservation attractive. A protocol is coprivate if the best option for a player to preserve her privacy is to help another player in preserving his privacy. Coprivacy makes an individual’s privacy preservation a goal that rationally interests other individuals: it is a matter of helping oneself by helping someone else. We formally define coprivacy in terms of Nash equilibria. We then extend the concept to: i) general coprivacy, where a helping player’s utility (i.e. interest) may include earning functionality and security in addition to privacy; ii) mixed coprivacy, where mixed strategies and mixed Nash equilibria are allowed with some restrictions; iii) correlated coprivacy, in which Nash equilibria are replaced by correlated equilibria. Coprivacy can be applied to any peer-to-peer (P2P) protocol. We illustrate coprivacy in P2P anonymous keyword search, in content privacy in social networks, in vehicular network communications and in controlled content distribution and digital oblivion enforcement

In this paper we propose a new power index useful for the evaluation of each member in a committee, or democratic institution, and the degree of influence over the voting decision making system. The proposed solution is based on the observation that democratic organizations not only tend to form coalitions which can by themselves guarantee the control of the organization, but that they also do it in an extremely efficient way that avoids the inclusion of powerful members if they can be replaced by weaker ones. The mathematical foundation of the new measure is based on two different axiomatizations. A comparison with other well-known measures is also done.

We thank Ester Camiña, John Hatfield, Alejandro Manelli, and two anonymous referees for their very helpful comments and suggestions. The work of D. Jaume and A. Neme is partially supported by the Universidad Nacional de San Luis through grant 319502 and by the Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET) through grant PICT-02114. Support for the research of J. Massó was received through the prize "ICREA Acadèmia" for excellence in research, funded by the Generalitat de Catalunya. He also acknowledges the support of MOVE, where he is an a¢ liated researcher. His work is also supported by the Spanish Ministry of Science and Innovation through grants ECO2008-04756 (Grupo Consolidado-C) and CONSOLIDER-INGENIO 2010 (CDS2006-00016), and by the Generalitat de Catalunya through grant SGR2009-419 Altres ajuts: MINCYT/PICT-02114 A multiple-partners assignment game with heterogeneous sales and multi-unit demands consists of a set of sellers that own a given number of indivisible units of potentially many different goods and a set of buyers who value those units and want to buy at most an exogenously fixed number of units. We define a competitive equilibrium for this generalized assignment game and prove its existence by using only linear programming. In particular, we show how to compute equilibrium price vectors from the solutions of the dual linear program associated to the primal linear program defined to find optimal assignments. Using only linear programming tools, we also show (i) that the set of competitive equilibria (pairs of price vectors and assignments) has a Cartesian product structure: each equilibrium price vector is part of a competitive equilibrium with all optimal assignments, and vice versa; (ii) that the set of (restricted) equilibrium price vectors has a natural lattice structure; and (iii) how this structure is translated into the set of agents' utilities that are attainable at equilibrium

In traditional distributed computing the users and owners of the computational resources usually belong to the same administrative domain. Therefore all users are equally entitled to use the resources. The situation is completely different in large-scale emergent distributed computing systems, such as Grid systems, where the roles of the users are asymmetric as regards their access rights and usage of resources. Further, unlike traditional distributed computing case, Grid systems introduce hierarchical levels, which are to be taken into account for optimizing the overall system's performance. In this paper we present a Stackelberg game for modelling asymmetric users' behavior in Grid scheduling scenario. We define a two-level game with a Leader at the first level and the rest of users, called Followers, at the second one. The Leader is responsible for computing a planning of his tasks, which is usually a large fraction of the total pool of tasks in the batch. The Followers try to select the best strategy for the assignments of their tasks subject to Leader's strategy. The Stackelberg game is then translated into a hierarchical optimization problem, which is solved by Genetic Algorithm (GA) on the Leader's level and by ad hoc heuristic combined with GA on the Followers' level. We have experimentally evaluated the approach through a benchmark of static instances and report computational results for resource utilization, makespan and flowtime

In this paper, the issue of network topology control in wireless networks using a fully distributed algorithm is considered. Whereas the proposed distributed algorithm is designed applying game theory concepts to design a non-cooperative game, network connectivity is guaranteed based on asymptotic results of network connectivity. Simulations show that for a relatively low node density, the probability that the proposed algorithm leads to a connected network is close to one.

Scheduling independent tasks in Computational Grids commonly arises in many Grid-enabled large scale applications. Much of current research in this domain is focused on the improvement of the efficiency of the Grid schedulers, both at global and local levels, which is the basis for Grid systems to leverage large computing capacities. However, unlike traditional scheduling, in Grid systems security requirements are very important to scheduling tasks/applications to Grid resources. The objective is thus to achieve efficient and secure allocation of tasks to machines. In this paper we propose a new model for secure scheduling at the Grid sites by combining game-theoretic and genetic-based meta-heuristic approaches. The game-theoretic model takes into account the realistic feature that Grid users usually perform independently of each other. The scheduling problem is then formalized as a noncooperative non-zero sum game with Nash equilibria as the solutions. The game cost function is minimized, at global and user levels, by using four genetic-based hybrid meta-heuristics. We have evaluated the proposed model through a static benchmark of instances, for which we have measured two basic metrics, namely the makespan and flowtime. The obtained results suggest that it is more resilient for the Grid users (and local schedulers) to tolerate some job delays defined as additional scheduling cost due to security requirements instead of taking a risk of allocating at unreliable resources.

This work proposes to improve the tactical decision-making of a supply chain (SC) under an uncertain competition scenario through the use of different optimization criteria, which allows to manage not only the specific objectives of the SC of interest, but also the way how its clients address their selection between different potential suppliers, identifying best market share for the SC of interest and the strategy to attain it. The resulting multi-objective optimization problem has been solved using the ɛ-constraint method in order to approximate the Pareto space of non-dominated solutions while a framework based on game theory is used as a reactive decision making support tool to deal with the uncertainty of the competitive scenario. The use of the proposed system is illustrated through its application to a multi-product, multi-echelon supply chain case study, which is intended to cooperate or to compete with another SC of similar characteristics. Fil: Zamarripa, Miguel A.. Universidad Politecnica de Catalunya; España Fil: Aguirre, Adrian Marcelo. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Santa Fe. Instituto de Desarrollo Tecnológico para la Industria Química (i); Argentina Fil: Mendez, Carlos Alberto. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Santa Fe. Instituto de Desarrollo Tecnológico Para la Industria Química (i); Argentina Fil: Espuña, Antonio. Universidad Politecnica de Catalunya; España

The electric energy distribution infrastructure is undergoing a startling technological evolution with the development of the smart grid concept, which allows more interaction between the supply-and the demand-side of the network and results in a great optimization potential. In this paper, we focus on a smart grid in which the demand-side comprises traditional users as well as users owning some kind of distributed energy source and/or energy storage device. By means of a day-ahead demand-side management mechanism regulated through an independent central unit, the latter users are interested in reducing their monetary expense by producing or storing energy rather than just purchasing their energy needs from the grid. Using a general energy pricing model, we tackle the grid optimization design from two different perspectives: a user-oriented optimization and an holistic-based design. In the former case, we optimize each user individually by formulating the grid optimization problem as a noncooperative game, whose solution analysis is addressed building on the theory of variational inequalities. In the latter case, we focus instead on the joint optimization of the whole system, allowing some cooperation among the users. For both formulations, we devise distributed and iterative algorithms providing the optimal production/storage strategies of the users, along with their convergence properties. Among all, the proposed algorithms preserve the users' privacy and require very limited signaling with the central unit.

The number of portable devices capable of maintaining wireless communications has increased considerably in the last decade. Such mobile nodes may form a spontaneous self-configured network connected by wireless links to constitute a Mobile Ad Hoc Network (MANET). As the number of mobile end users grows the demand of multimedia services, such as video-streaming, in such networks is envisioned to increase as well. One of the most appropriate video coding technique for MANETs is layered MPEG-2 VBR, which used with a proper multipath routing scheme improves the distribution of video streams. In this article we introduce a proposal called g-MMDSR (game theoretic-Multipath Multimedia Dynamic Source Routing), a cross-layer multipath routing protocol which includes a game theoretic approach to achieve a dynamic selection of the forwarding paths. The proposal seeks to improve the own benefits of the users whilst using the common scarce resources efficiently. It takes into account the importance of the video frames in the decoding process, which outperforms the quality of the received video. Our scheme has proved to enhance the performance of the framework and the experience of the end users. Simulations have been carried out to show the benefits of our proposal under different situations where high interfering traffic and mobility of the nodes are present.

Electronic version of an article published as International Game Theory Review, Vol. 21, Issue 1, 1940001, 2019, p. 1-24. DOI: 10.1142/S0219198919400012] © World Scientific Publishing Company https://www-worldscientific-com.recursos.biblioteca.upc.edu/doi/abs/10.1142/S0219198919400012 The aim of this work is to give a characterization of the Shapley–Shubik and the Banzhaf power indices for (3,2)-simple games. We generalize to the set of (3,2)-simple games the classical axioms for power indices on simple games: transfer, anonymity, null player property and efficiency. However, these four axioms are not enough to uniquely characterize the Shapley–Shubik index for (3,2)-simple games. Thus, we introduce a new axiom to prove the uniqueness of the extension of the Shapley–Shubik power index in this context. Moreover, we provide an analogous characterization for the Banzhaf index for (3,2)-simple games, generalizing the four axioms for simple games and adding another property.

Energy-related costs are becoming one of the largest contributors to the overall cost of operating a data center, whereas the degree of data center utilization continues to be very low. An energy-aware dynamic provision of resources based on the consolidation of existing application instances can simultaneously address the underutilization of servers while greatly reducing energy costs. The economics behind energy costs cannot be treated separately from resource provision and allocation. However, current scheduling techniques based on market mechanisms do not specifically deal with such a scenario. To establish the upper bound of energy savings, we model the problem of minimizing energy consumption when allocating resources to networked applications as a Stackelberg leadership game. The model is applied to a proportional-share mechanism in which resource providers can maximize profit by minimizing energy costs, while users can select resources that ensure that their minimum requirements are satisfied. We show that our mechanism can determine the optimal set of resources switched on and off, while maintaining user service level agreements (SLAs) - even in realistic conditions considering incomplete information. Highlights? Energy-related costs in large-scale infrastructures are an increasing cost. ? We present a new power model for computing resources based on industry-standard benchmarks. ? We study the trade-off between powering down nodes and quality of service delivered to users. ? We model the interaction between the resource provider and users as a Stackelberg game, a game-theoretic tool.

This paper addresses the channel selection problem for Long Term Evolution Unlicensed (LTE-U). Channel selection is a frequency-domain mechanism that facilitates the coexistence of multiple networks sharing the unlicensed band. In particular, the paper considers a fully distributed approach where each small cell autonomously selects the channel to set-up an LTE-U carrier. The problem is modeled using a non-cooperative repeated game and the Iterative Trial and Error Learning - Best Action (ITEL-BA) learning algorithm is used to drive convergence towards a Nash Equilibrium. The proposed approach is evaluated by means of simulations in different situations analyzing both the throughput performance and the convergence behavior.

Els jocs simples simètrics (3, 2) serveixen de models per a sistemes de votació anònims en els quals cada votant pot votar "sí", abstenir-se, o votar "no", el resultat és "sí" o "no", i els votants juguen papers intercanviables. L'extensió a jocs simples simètrics (j,2), en els quals cada votant tria entre j nivells d'aprovació ordenats, també n'imita algunes regles naturals de decisió, com sistemes classificats passa/falla. Cada un dels jocs està determinat pel conjunt de perfils (anònims) mínims vencedors. Això fa possible comptar els sistemes possibles, i els recomptes suggereixen alguns patrons interessants. En el cas (3, 2), l'aproximació sosté una versió del Teorema de May, classificant tota les normes de votació anònima possibles amb abstenció en termes de quote functions. A diferència de la situació per jocs ordinaris simples aquests resultats revelen que la classe de jocs simples amb 3 o més nivells d'aprovació es manté ampli i variat, fins i tot després de la imposició de la simetria.

In decentralized systems, nodes often need to coordinate to access shared resources in a fair manner. One approach to perform such arbitration is to rely on auction mechanisms. Although there is an extensive literature that studies auctions, most of these works assume the existence of a central, trusted auctioneer. Unfortunately, in fully decentralized systems, where the nodes that need to cooperate operate under separate spheres of control, such central trusted entity may not exist. Notable examples of such decentralized systems include community networks, clouds of clouds, cooperative nano data centres, among others. In this paper, we make theoretical and practical contributions to distribute the role of the auctioneer. From the theoretical perspective, we propose a framework of distributed simulations of the auctioneer that are Nash equilibria resilient to coalitions and asynchrony. From the practical perspective, our protocols leverage the distributed nature of the simulations to parallelise the execution. We have implemented a prototype that instantiates the framework for bandwidth allocation in community networks, and evaluated it in a real distributed setting., 17 pages, 5 figures, 1 algorithm, published in ICDCS'16