Uplink Power Control and Base Station Association in Multichannel Cellular Networks

A combined base station association and power control problem is studied for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one cell (i.e., base station). A distributed association and power update algorithm is proposed and shown to converge to a Nash equilibrium of a noncooperative game. We consider network models with discrete mobiles (yielding an atomic congestion game), as well as a continuum of mobiles (yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. It is shown that these mechanisms can be implemented in a distributed fashion.

A Fair Contract for Managing Water Scarcity

In public utilities, under supply constraints, fairness considerations lead to a market failure. This paper characterizes a two-period principal-agent contract for demand management, that mitigates this market failure in urban water systems. The contract is designed as an extensive form mechanism using subgame perfect Nash equilibrium (SPNE) as the solution concept. The contract is fair; and is shown to be economically efficient if, in case of deviation by the agent, the gain to the agent and the loss to the principal are small. It is shown that the assumption can be avoided in an infinite horizon contract.

An analytical approach to the study of cooperation in wireless ad hoc networks

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal share of service that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

Truthful and Quality Conscious Query Incentive Networks

Query incentive networks capture the role of incentives in extracting information from decentralized information networks such as a social network. Several game theoretic tilt:Kids of query incentive networks have been proposed in the literature to study and characterize the dependence, of the monetary reward required to extract the answer for a query, on various factors such as the structure of the network, the level of difficulty of the query, and the required success probability.None of the existing models, however, captures the practical andimportant factor of quality of answers. In this paper, we develop a complete mechanism design based framework to incorporate the quality of answers, in the monetization of query incentive networks. First, we extend the model of Kleinberg and Raghavan [2] to allow the nodes to modulate the incentive on the basis of the quality of the answer they receive. For this qualify conscious model. we show are existence of a unique Nash equilibrium and study the impact of quality of answers on the growth rate of the initial reward, with respect to the branching factor of the network. Next, we present two mechanisms; the direct comparison mechanism and the peer prediction mechanism, for truthful elicitation of quality from the agents. These mechanisms are based on scoring rules and cover different; scenarios which may arise in query incentive networks. We show that the proposed quality elicitation mechanisms are incentive compatible and ex-ante budget balanced. We also derive conditions under which ex-post budget balance can beachieved by these mechanisms.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

Bidding Dynamics of Rational Advertisers in Sponsored Search Auctions on the Web

In this paper, we address a key problem faced by advertisers in sponsored search auctions on the web: how much to bid, given the bids of the other advertisers, so as to maximize individual payoffs? Assuming the generalized second price auction as the auction mechanism, we formulate this problem in the framework of an infinite horizon alternative-move game of advertiser bidding behavior. For a sponsored search auction involving two advertisers, we characterize all the pure strategy and mixed strategy Nash equilibria. We also prove that the bid prices will lead to a Nash equilibrium, if the advertisers follow a myopic best response bidding strategy. Following this, we investigate the bidding behavior of the advertisers if they use Q-learning. We discover empirically an interesting trend that the Q-values converge even if both the advertisers learn simultaneously.

Incentive compatible mechanisms for group ticket allocation in software maintenance services

A customer reported problem (or Trouble Ticket) in software maintenance is typically solved by one or more maintenance engineers. The decision of allocating the ticket to one or more engineers is generally taken by the lead, based on customer delivery deadlines and a guided complexity assessment from each maintenance engineer. The key challenge in such a scenario is two folds, un-truthful (hiked up) elicitation of ticket complexity by each engineer to the lead and the decision of allocating the ticket to a group of engineers who will solve the ticket with in customer deadline. The decision of allocation should ensure Individual and Coalitional Rationality along with Coalitional Stability. In this paper we use game theory to examine the issue of truthful elicitation of ticket complexities by engineers for solving ticket as a group given a specific customer delivery deadline. We formulate this problem as strategic form game and propose two mechanisms, (1) Division of Labor (DOL) and (2) Extended Second Price (ESP). In the proposed mechanisms we show that truth telling by each engineer constitutes a Dominant Strategy Nash Equilibrium of the underlying game. Also we analyze the existence of Individual Rationality (IR) and Coalitional Rationality (CR) properties to motivate voluntary and group participation. We use Core, solution concept from co-operative game theory to analyze the stability of the proposed group based on the allocation and payments.

Fair Scheduling in Cellular Systems in the Presence of Noncooperative Mobiles

We consider the problem of ``fair'' scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric alpha-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash equilibrium (NE) that we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise nonrobust (in presence of noncooperation) alpha-fair scheduling algorithms.

Necessary and sufficient conditions for optimality in constrained general sum stochastic games

In this paper we first derive a necessary and sufficient condition for a stationary strategy to be the Nash equilibrium of discounted constrained stochastic game under certain assumptions. In this process we also develop a nonlinear (non-convex) optimization problem for a discounted constrained stochastic game. We use the linear best response functions of every player and complementary slackness theorem for linear programs to derive both the optimization problem and the equivalent condition. We then extend this result to average reward constrained stochastic games. Finally, we present a heuristic algorithm motivated by our necessary and sufficient conditions for a discounted cost constrained stochastic game. We numerically observe the convergence of this algorithm to Nash equilibrium. (C) 2015 Elsevier B.V. All rights reserved.

Interaction between a strategic mass media firm and a government

Resumen: Este artículo intenta teorizar acerca de la dinámica entre los medios masivos de comunicación y los gobiernos de los países latinoamericanos. Si bien en la última década los gobiernos atacaron públicamente a los medios de comunicación, se afirma que no se dio por las razones que dicen, sino más bien por asuntos económicos. Por lo tanto, se ha diseñado un modelo utilizando el método de “principal” vs “incumbente”, donde se alcanzará un equilibrio de Nash perfecto en subjuegos. Además de esto, se realiza un repaso por la literatura conocida, y concluye señalando las fortalezas y debilidades del modelo propuesto.

A Behavioral Foundation for Models of Evolutionary Drift

Binmore and Samuelson (1999) have shown that perturbations (drift) are crucial to study the stability properties of Nash equilibria. We contribute to this literature by providing a behavioural foundation for models of evolutionary drift. In particular, this article introduces a microeconomic model of drift based on the similarity theory developed by Tversky (1977), Kahneman and Tversky (1979) and Rubinstein (1988),(1998). An innovation with respect to those works is that we deal with similarity relations that are derived from the perception that each agent has about how well he is playing the game. In addition, the similarity relations are adapted to a dynamic setting. We obtain different models of drift depending on how we model the agent´s assessment of his behaviour in the game. The examples of the ultimatum game and the chain-store game are used to show the conditions for each model to stabilize elements in the component of Nash equilibria that are not subgame- perfect. It is also shown how some models approximate the laboratory data about those games while others match the data.

The Supercore for Normal Form Games

We study the supercore of a system derived from a normal form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore of that system coincides with the set of Nash equilibrium strategy profiles of the last game in the sequence. This result is illustrated with the characterization of the supercore for the n-person prisoners’ dilemma. With regard to the mixed extension of a normal form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria. For games with an infinite number of Nash equilibria this need not be no longer the case. Yet, it is not difficult to find a binary relation which guarantees the coincidence of these two sets.

A Model of Evolutionay Drift

Drift appears to be crucial to study the stability properties of Nash equilibria in a component specifying different out-of-equilibrium behaviour. We propose a new microeconomic model of drift to be added to the learning process by which agents find their way to equilibrium. A key feature of the model is the sensitivity of the noisy agent to the proportion of agents in his player population playing the same strategy as his current one. We show that, 1. Perturbed Payoff-Positive and PayoffMonotone selection dynamics are capable of stabilizing pure non strict Nash equilibria in either singleton or nonsingleton component of equilibria; 2. The model is relevant to understand the role of drift in the behaviour observed in the laboratory for the Ultimatum Game and for predicting outcomes that can be experimentally tested. Hence, the selection dynamics model perturbed with the proposed drift may be seen as well as a new learning tool to understand observed behaviour.

The von Neumann-Morgenstern stable sets for 2x2 games

We analyze the von Neumann and Morgenstern stable sets for the mixed extension of 2 2 games when only single profitable deviations are allowed. We show that the games without a strict Nash equilibrium have a unique vN&M stable set and otherwise they have infinite sets.

The Economics of "Why is it so hard to save a threatened Language?"

We study the language choice behavior of bilingual speakers in modern societies, such as the Basque Country, Ireland andWales. These countries have two o cial languages:A, spoken by all, and B, spoken by a minority. We think of the bilinguals in those societies as a population playing repeatedly a Bayesian game in which, they must choose strategically the language, A or B, that might be used in the interaction. The choice has to be made under imperfect information about the linguistic type of the interlocutors. We take the Nash equilibrium of the language use game as a model for real life language choice behavior. It is shown that the predictions made with this model t very well the data about the actual use, contained in the censuses, of Basque, Irish and Welsh languages. Then the question posed by Fishman (2001),which appears in the title, is answered as follows: it is hard, mainly, because bilingual speakers have reached an equilibrium which is evolutionary stable. This means that to solve fast and in a re ex manner their frequent language coordination problem, bilinguals have developed linguistic conventions based chie y on the strategy 'Use the same language as your interlocutor', which weakens the actual use of B.1