Search

We consider a distributed computing setting wherein a central entity seeks power from computational providers by offering a certain reward in return. The computational providers are classified into long-term stakeholders that invest a constant amount of power over time and players that can strategize on their computational investment. In this paper, we model and analyze a stochastic game in such a distributed computing setting, wherein players arrive and depart over time. While our model is formulated with a focus on volunteer computing, it equally applies to certain other distributed computing applications such as mining in blockchain. We prove that, in Markov perfect equilibrium, only players with cost parameters in a relatively low range which collectively satisfy a certain constraint in a given state, invest. We infer that players need not have knowledge about the system state and other players' parameters, if the total power that is being received by the central entity is communicated to the players as part of the system's protocol. If players are homogeneous and the system consists of a reasonably large number of players, we observe that the total power received by the central entity is proportional to the offered reward and does not vary significantly despite the players' arrivals and departures, thus resulting in a robust and reliable system. We then study by way of simulations and mean field approximation, how the players' utilities are influenced by their arrival and departure rates as well as the system parameters such as the reward's amount and dispensing rate. We observe that the players' expected utilities are maximized when their arrival and departure rates are such that the average number of players present in the system is typically between 1 and 2, since this leads to the system being in the condition of least competition with high probability. Further, their expected utilities increase almost linearly with the offered reward and converge to a constant value with respect to its dispensing rate. We conclude by studying a Stackelberg game, where the central entity decides the amount of reward to offer, and the computational providers decide how much power to invest based on the offered reward. [ABSTRACT FROM AUTHOR]

Using a dynamic preferential trade agreement (PTA) formation model, we show that political biases in exporting and import‐competing sectors substantially impact the extent of PTA formation. While both exclusion and free riding incentives constrain the expansion to global free trade in a free trade agreement (FTA) game, only the former incentive arises in a customs union (CU) game. When we endogenize the choice between FTAs and CUs, the tension between the flexibility benefit of FTAs and the coordination benefit of CUs reveals that FTAs always serve as PTA building blocks while CUs may serve as PTA building or stumbling blocks. [ABSTRACT FROM AUTHOR]

Similar to the role of Markov decision processes in reinforcement learning, Markov games (also called stochastic games) lay down the foundation for the study of multi-agent reinforcement learning and sequential agent interactions. We introduce approximate Markov perfect equilibrium as a solution to the computational problem of finite-state stochastic games repeated in the infinite horizon and prove its PPAD -completeness. This solution concept preserves the Markov perfect property and opens up the possibility for the success of multi-agent reinforcement learning algorithms on static two-player games to be extended to multi-agent dynamic games, expanding the reign of the PPAD -complete class. [ABSTRACT FROM AUTHOR]

We study a stochastic game with a dynamic set of players, for modeling and analyzing their computational investment strategies in distributed computing. Players obtain a certain reward for solving a problem, while incurring a certain cost based on the invested time and computational power. We present our framework while considering a contemporary application of blockchain mining, and show that the framework is applicable to certain other distributed computing settings as well. For an in-depth analysis, we consider a particular yet natural scenario where the rate of solving the problem is proportional to the total computational power invested by the players. We show that, in Markov perfect equilibrium, players with cost parameters exceeding a certain threshold, do not invest; while those with cost parameters less than this threshold, invest maximal power. We arrive at an interesting conclusion that the players need not have information about the system state as well as each others' parameters, namely, cost parameters and arrival/departure rates. With extensive simulations and insights through mean field approximation, we study the effects of players' arrival/departure rates and the system parameters on the players' utilities. • Stochastic game framework for distributed computing with application to block mining. • Players can arrive and depart over time and strategize on their power investments. • Markov perfect equilibrium follows a threshold policy. • Sensitivity analysis and insights into results using a mean field approach. [ABSTRACT FROM AUTHOR]

The game of resource extraction/capital accumulation is a stochastic infinitehorizon game, which models a joint utilization of a productive asset over time. The paper complements the available results on pure Markov perfect equilibrium existence in the non-symmetric game setting with an arbitrary number of agents. Moreover, we allow that the players have unbounded utilities and relax the assumption that the stochastic kernels of the transition probability must depend only on the amount of resource before consumption. This class of the game has not been examined beforehand. However, we could prove the Markov perfect equilibrium existence only in the specific case of interest. Namely, when the players have constant relative risk aversion (CRRA) power utilities and the transition law follows a geometric random walk in relation to the joint investment. The setup with the chosen characteristics is moti-vated by economic considerations, which makes it relevant to a certain range of real-word problems. [ABSTRACT FROM AUTHOR]

In many domains, committees bargain over a sequence of policies and a policy remains in effect until a new agreement is reached. In this paper, I argue that, in order to assess the consequences of veto power, it is important to take into account this dynamic aspect. I analyze an infinitely repeated divide-the-dollar game with an endogenous status quo policy. I show that full appropriation by the veto player is the only stable policy when legislators are sufficiently impatient; and that, irrespective of legislators' patience and the initial division of resources, there is always an equilibrium where policy eventually gets arbitrarily close to full appropriation by the veto player. In this equilibrium, increasing legislators' patience or decreasing the veto player's proposal power makes convergence to this outcome slower and the veto player supports reforms that decrease his allocation. The main predictions of the theory find support in controlled laboratory experiments. [ABSTRACT FROM AUTHOR]

We analyze undiscounted continuous-time games of strategic experimentation with two-armed bandits. The risky arm generates payoffs according to a Lévy process with an unknown average payoff per unit of time which nature draws from an arbitrary finite set. Observing all actions and realized payoffs, plus a free background signal, players use Markov strategies with the common posterior belief about the unknown parameter as the state variable. We show that the unique symmetric Markov perfect equilibrium can be computed in a simple closed form involving only the payoff of the safe arm, the expected current payoff of the risky arm, and the expected full-information payoff, given the current belief. In particular, the equilibrium does not depend on the precise specification of the payoff-generating processes. [ABSTRACT FROM AUTHOR]

This paper examines the execution problems of large traders with a generalized price impact. Constructing two related models in a discrete-time setting, we solve these problems by applying the backward induction method of dynamic programming. In the first problem, we formulate the expected utility maximization problem of a single large trader as a Markov decision process and derive an optimal execution strategy. Then, in the second model, we formulate the expected utility maximization problem of two large traders as a Markov game and derive an equilibrium execution strategy at a Markov perfect equilibrium. Both of these two models enable us to investigate how the execution strategies and trade performances of a large trader are affected by the existence of other traders. Moreover, we find that these optimal and equilibrium execution strategies become deterministic when the total execution volumes of non-large traders are deterministic. We also show, by some numerical examples, the comparative statics results with respect to several problem parameters. [ABSTRACT FROM AUTHOR]

We study a discrete-time non-stationary decision model in which the preferences of the decision maker change over time and are described by quasi-hyperbolic discounting. A time-consistent optimal solution in this model corresponds with a Markov perfect equilibrium in a stochastic game with uncountable state space played by countably many short-lived players. We show that Markov perfect equilibria may be constructed using a generalized policy iteration algorithm. This method is in part inspired by the fundamental works of Mertens and Parthasarathy (in: Raghavan, Ferguson, Parthasarathy, Vrieze (eds) Stochastic games and related topics, Kluwer Academic Publishers, Dordrecht, 1991; in: Neyman, Sorin (eds) Stochastic games and applications, Academic Publishers, Dordrecht, 2003) devoted to subgame perfect equilibria in standard n-person discounted stochastic games. If the one-period utilities and transition probabilities are independent of time, we obtain on new existence results on stationary Markov perfect equilibria in the models with unbounded from above utilities. [ABSTRACT FROM AUTHOR]

We study consumer strategy, vendor strategy and their equilibrium in a duopoly market where vendors bear the costs in the production process. If consumers have an identical preference that is unknown, we obtain the equations satisfied by the total social surplus and the profit of each vendor. Moreover, we prove that the second derivatives of the total social surplus function and the profit function are continuous at the cutoff by the well-known conditions of value matching and smooth pasting. In a duopoly market, vendors can increase the total social surplus by adjusting their output, which causes fewer profits for vendors. However, rational vendors usually do not make such concessions, which implies that it is almost impossible to maximize total social surplus in a duopoly market. Thus, the planner needs to control vendors' output to maximize the total social surplus. We obtain the planner's optimal strategy and the socially efficient allocation. When vendors and consumers maximize their value, we find that the price of goods may be less than their costs due to price competition. By Bayesian learning and price competition model, we discuss a Markov perfect equilibrium and the relationship between the socially efficient allocation and the Markov perfect equilibrium. [ABSTRACT FROM AUTHOR]

In this paper, we investigate non-cooperative radio resource management in a vehicle-to-vehicle communication network. The technical challenges lie in high-vehicle mobility and data traffic variations. Over the discrete scheduling slots, each vehicle user equipment (VUE)-pair competes with other VUE-pairs in the coverage of a road side unit (RSU) for the limited frequency to transmit queued data packets, aiming to optimize the expected long-term performance. The frequency allocation at the beginning of each slot at the RSU is regulated by a sealed second-price auction. Such interactions among VUE-pairs are modeled as a stochastic game with a semi-continuous global network state space. By defining a partitioned control policy, we transform the original game into an equivalent stochastic game with a global queue state space of finite size. We adopt an oblivious equilibrium (OE) to approximate the Markov perfect equilibrium, which characterizes the optimal solution to the equivalent game. The OE solution is theoretically proven to be with an asymptotic Markov equilibrium property. Due to the lack of a priori knowledge of network dynamics, we derive an online algorithm to learn the OE solution. Numerical simulations validate the theoretical analysis and show the effectiveness of the proposed online learning algorithm. [ABSTRACT FROM AUTHOR]

In this note, we prove the existence of a Markov perfect equilibrium in a non-stationary version of a paternalistic bequest game. The method we advocate is general and allows to study models with unbounded state space and unbounded utility functions. We cover both, the stochastic and deterministic cases. We provide a characterization of the set of all Markov perfect equilibria by means of a set-valued recursive equation involving the best response operator. In the stationary case, we show that there exists a set of strategies that is invariant under the best response mapping. [ABSTRACT FROM AUTHOR]

This note examines the structure of stationary bargaining equilibria in the finite framework of Anesi (2010) . The main result establishes a tight connection between the set of equilibrium absorbing points and the von Neumann–Morgenstern solutions: assuming that players are patient, that the voting rule is oligarchical, and that there is at least one veto player with positive recognition probability, a set of alternatives corresponds to the absorbing points of an equilibrium if and only if it is a von Neumann–Morgenstern solution. We also apply our analysis of ergodic properties of equilibria to the persistent agenda setter environment of Diermeier and Fong (2012) . We show that all equilibria are essentially pure, and we extend their characterization of absorbing sets to allow an arbitrary voting rule and by removing the restriction to pure strategy equilibria. [ABSTRACT FROM AUTHOR]

Public-private partnerships have seen the daylight in response to the adagio that project responsibilities and risks should be efficiently allocated between the public and the private sector. Nevertheless, the considerable bidding costs inhibit the competition in the market. A trustworthy project agenda, also called a project pipeline, could substantiate the PPP market's attractiveness in the belief that a current success results in a knowledge and cost advantage in future tenders. This paper builds a sequential PPP procurement model and heuristically approximates the Markov perfect equilibrium in which contractors determine how much money they are willing to invest in the bid preparation and which mark-up is appropriate for each project in the pipeline. A pipeline of projects pushes down the mark-ups and the government procurement cost. Nonetheless, according to the experiments, only players with an initial experiential advantage tend to make higher investment efforts so that additional governmental policies, like a fractional reimbursement of the bid preparation efforts, might be required to level the playing field. [ABSTRACT FROM AUTHOR]

We examine project selection decisions of firms constrained in the number of projects they can handle at once. A new project opportunity arises every period. Taking on a project requires a commitment of uncertain duration, preventing the firm from selecting another project in subsequent periods until the commitment ends. In our dynamic game, when two firms are free of commitment, they move sequentially in random order. Symmetric pure strategy Markov perfect equilibria always exist. In equilibrium, the first mover strategically rejects some projects that are then selected by the second mover, even when the value of the project is the same for both firms. A monopolist rejects more projects, and adopts ones of higher average quality compared to the duopolist. Duopolists select too few projects compared to their jointly optimal behavior. We extend the model to allow for externalities, asymmetry, and n > 2 firms. [ABSTRACT FROM AUTHOR]

We study the influence of switching cost and compatibility in a network industry. A dynamic model which includes both network effect and switching cost is constructed, and its Markov perfect equilibrium is computed. The numerical experiments discover a new kind of equilibrium, named the mixed equilibrium, in which both market sharing and tipping could occur. Furthermore, we find that, in network industry, switching cost has a non-monotony influence on market dominance. High switching cost will lead to locked-in, and reduce the possibility of market dominance, while moderate switching cost tend to increase the possibility of market tipping. In some circumstance, regulation policies for reducing switching cost will worsen the market competition. The leveling effects of compatibility dominate the un-differentiating effects, if switching cost reducing policies are incorporated with pro-compatibility policies, market dominance could be avoided. These findings provide an explanation of the slow process of mobile number portability (MNP) in China, that it is partly due to insufficient interconnection and price discrimination in the market. [ABSTRACT FROM AUTHOR]

We study an altruistic growth model with production uncertainty viewed as an intergenerational stochastic game. The existence of stationary Markov perfect equilibria is proved under general assumptions on utility functions for the generations and for non-atomic transition probabilities. This paper answers some issues that arose from the literature in the 1980s decade. [ABSTRACT FROM AUTHOR]

Abstract: We analyze dynamic price competition in a homogeneous goods duopoly, where consumers exchange information via word-of-mouth communication. A fraction of consumers, who do not learn any new information, remain locked-in at their previous supplier in each period. We analyze Markov perfect equilibria in which firms use mixed pricing strategies. Market share dynamics are driven by the endogenous price dispersion. Depending on the parameters, we obtain different ‘classes’ of dynamics. When firms are impatient, there is a tendency towards equal market shares. When firms are patient, there are extended intervals of market dominance, interrupted by sudden changes in the leadership position. [Copyright &y& Elsevier]

Abstract: This paper analyzes a two-player game of strategic experimentation with three-armed exponential bandits in continuous time. Players play bandits of identical types, with one arm that is safe in that it generates a known payoff, whereas the likelihood of the risky armsʼ yielding a positive payoff is initially unknown. When the types of the two risky arms are perfectly negatively correlated, the efficient policy is an equilibrium if and only if the stakes are high enough. If the negative correlation is imperfect and stakes are high, there exists an equilibrium that leads to efficiency for optimistic enough prior beliefs. [Copyright &y& Elsevier]

Abstract: We generalize the dynamic bargaining game of to arbitrary quota rules to provide a non-cooperative characterization of the von Neumann–Morgenstern stable set. Assuming that players are sufficiently patient and have strict preferences, a pure-strategy stationary equilibrium exists and in any such equilibrium, a policy is a steady state if and only if it is in the stable set. The result provides a non-cooperative foundation of stable sets in settings with dynamic policy-making and a persistent agenda setter. [Copyright &y& Elsevier]

Abstract: We study the Markov perfect equilibria (MPEs) of an infinite horizon game in which pairs of players connected in a network are randomly matched to bargain. Players who reach agreement are removed from the network without replacement. We establish the existence of MPEs and show that MPE payoffs are not necessarily unique. A method for constructing pure strategy MPEs for high discount factors is developed. For some networks, we find that all MPEs are asymptotically inefficient as players become patient. [Copyright &y& Elsevier]

I develop a dynamic model of social conflict whereby manifest grievances of the poor generate the incentive of taking over political power violently. Rebellion can be an equilibrium outcome depending on the level of preexisting inequality between the poor and the ruling elite, the relative military capabilities of the two groups and the destructiveness of conflict. Once a technology of repression is introduced, widespread fear reduces the parameter space for which rebellion is an equilibrium outcome. However, I show that repression-driven peace comes at a cost as it produces a welfare loss to society. [ABSTRACT FROM PUBLISHER]

Abstract: This paper presents an extension of a static model of economic conflict analyzed by and to an infinite horizon differential game. Our aim is to highlight the strategic role of appropriation among a smaller group of agents in an intertemporal context. The model yields the conclusion that there exists a unique linear/nonlinear Markov perfect equilibrium strategy, even when strategies are defined over the entire state space. We demonstrate that “partial cooperation” can be seen as a long-run response to conflict. Moreover, a decrease in the effectiveness of appropriation, the depreciation rate of a common-pool stock, the rate of time preferences or an increase in the “degree of noise” improves the degree of “partial cooperation” and thus welfare in an anarchic society. [Copyright &y& Elsevier]

Time consistent policies and reforms of intergenerational transfers are analyzed in an overlapping generation model. Governments have preferences, which give much weight to the living generations, and they cannot commit themselves to future taxes and transfers, which will be decided by future governments with different objectives. The economy follows one of two equilibrium paths with perfect foresight. On one path, governments finance the costs of their transfers to the living by increasing public debt recklessly. Consumers pay more and more taxes to finance the cost of this debt, and the successive generations will enter a process of impoverishment. On the other path, in spite of their preference bias, governments borrow less and put the economy on a path of egalitarian consumption flows for the successive generations, with a constant ratio of public debt to national income. The mechanisms, which put an economy on one or the other equilibrium paths, are unconnected to the fundamentals of the model. [ABSTRACT FROM AUTHOR]

Abstract: We consider an economy with a single capital stock that two agents strategically exploit by choosing a consumption profile over an infinite time horizon. We analyze two different games and their corresponding equilibria. In one game firms are able to pre-commit and choose simple time functions as their strategies. In the other game agents are assumed to employ Markov strategies. It turns out that in the case of pre-commitment there exists a threshold level of the capital stock such that if the initial stock is above this threshold, equilibrium consumption converges to the efficient steady state while if the initial condition is below it, the capital stock converges to zero. In case of the Markov equilibrium there exists a unique interior steady state that is globally stable. [Copyright &y& Elsevier]

This paper examines how inequality in access to credit affects the strategic behavior of users of a common resource in their investment and extraction decisions. A dynamic two-stage game is developed in which agents choose the level of sunk investment in capacity and the consequent extraction path. The results show that agents invest in excess capacity, except when inequality is very high. The relation between inequality and efficiency in resource extraction is found to be non-monotonic, with the steady-state resource stock being closest to the optimal level when either inequality is very high or very low. [Copyright &y& Elsevier]