Optimization methods are used to determine equilibria of investment in cryptocurrencies. The basic assumptions involve existence of a core group (the "wealthy") that fears the loss of substantial assets through government seizure. Speculators constitute another group that tends to introduce volatility and risk for the wealthy. The wealthy must divide their assets between the home currency and the cryptocurrency, while the government decides on the probability of seizing a fraction the assets of this group. Under the assumption that each group exhibits risk aversion through a utility function, we establish the existence and uniqueness of Nash equilibrium. Also examined is the more realistic optimization problem in which the government policy cannot be reversed, while the wealthy can adjust their allocation in reaction to the government's designation of probability. The methodology leads to an understanding the equilibrium market capitalization of cryptocurrencies.
Given the parallels between game theory and consensus, it makes sense to intelligently design blockchain or DAG protocols with an incentive-compatible-first mentality. To that end, we propose a new blockchain or DAG protocol enhancement based on delayed rewards. We devise a new method for imposing slashing conditions on miner behavior, using their delayed rewards as stake in a Proof of Work system. Using fraud proofs, we can slash malicious miner behavior and reward long-lived, honest behavior.
Consensus protocols inherently rely on the notion of leader election, in which one or a subset of participants are temporarily elected to authorize and announce the network's latest state. While leader election is a well studied problem, the rise of distributed ledgers (i.e., blockchains) has led to a new perspective on how to perform large-scale leader elections via solving a computationally difficult puzzle (i.e., proof of work). In this paper, we present Caucus, a large-scale leader election protocol with minimal coordination costs that does not require the computational cost of proof-of-work. We evaluate Caucus in terms of its security, using a new model for blockchain-focused leader election, before testing an implementation of Caucus on an Ethereum private network. Our experiments highlight that one variant of Caucus costs only $0.10 per leader election if deployed on Ethereum.
We propose a design for philanthropic or publicly-funded seeding to allow (near) optimal provision of a decentralized, self-organizing ecosystem of public goods. The concept extends ideas from Quadratic Voting to a funding mechanism for endogenous community formation. Individuals make public goods contributions to projects of value to them. The amount received by the project is (proportional to) the square of the sum of the square roots of contributions received. Under the standard model this yields first best public goods provision. Variations can limit the cost, help protect against collusion and aid coordination. We discuss applications to campaign finance, open source software ecosystems, news media finance and urban public projects. More broadly, we offer a resolution to the classic liberal-communitarian debate in political philosophy by providing neutral and non-authoritarian rules that nonetheless support collective organization.
Ilaria Bertazzi, Sylvie Huet, Guillaume Deffuant, Floriana Gargiulo
Bitcoin-otc is a peer to peer (over-the-counter) marketplace for trading with bit- coin crypto-currency. To mitigate the risks of the p2p unsupervised exchanges, the establishment of a reliable reputation systems is needed: for this reason, a web of trust is implemented on the website. The availability of all the historic of the users interaction data makes this dataset a unique playground for studying reputation dynamics through others evaluations. We analyze the structure and the dynamics of this web of trust with a multilayer network approach distin- guishing the rewarding and the punitive behaviors. We show that the rewarding and the punitive behavior have similar emergent topological properties (apart from the clustering coefficient being higher for the rewarding layer) and that the resultant reputation originates from the complex interaction of the more regular behaviors on the layers. We show which are the behaviors that correlate (i.e. the rewarding activity) or not (i.e. the punitive activity) with reputation. We show that the network activity presents bursty behaviors on both the layers and that the inequality reaches a steady value (higher for the rewarding layer) with the network evolution. Finally, we characterize the reputation trajectories and we identify prototypical behaviors associated to three classes of users: trustworthy, untrusted and controversial.
We analyse the Tangle --- a DAG-valued stochastic process where new vertices get attached to the graph at Poissonian times, and the attachment's locations are chosen by means of random walks on that graph. These new vertices, also thought of as "transactions", are issued by many players (which are the nodes of the network), independently. The main application of this model is that it is used as a base for the IOTA cryptocurrency system (www.iota.org). We prove existence of "almost symmetric" Nash equilibria for the system where a part of players tries to optimize their attachment strategies. Then, we also present simulations that show that the "selfish" players will nevertheless cooperate with the network by choosing attachment strategies that are similar to the "recommended" one.
This paper presents a simple game theoretic framework, assuming complete information, to model Bitcoin mining activity. It does so by formalizing the activity as an all-pay contest: a competition where participants contend with each other to win a prize by investing in computational power, and victory is probabilistic. With at least two active miners, the unique pure strategy Nash equilibrium of the game suggests the following interesting insights on the motivation for being a miner: while the optimal amount of energy consumption depends also on the reward for solving the puzzle, as long as the reward is positive the decision to be an active miner depends only on the mining costs. Moreover, the intrinsic structure of the mining activity seems to prevent the formation of a monopoly, because in an equilibrium with two miners, both of them will have positive expected profits for any level of the opponent’s costs. A monopoly could only form if the rate of return on investment were higher outside bitcoin.
Aggelos Kiayias, Ηλίας Κουτσουπιάς, Maria Kyropoulou, Yiannis Tselekounis
We study the strategic considerations of miners participating in the bitcoin's protocol. We formulate and study the stochastic game that underlies these strategic considerations. The miners collectively build a tree of blocks, and they are paid when they create a node (mine a block) which will end up in the path of the tree that is adopted by all. Since the miners can hide newly mined nodes, they play a game with incomplete information. Here we consider two simplified forms of this game in which the miners have complete information. In the simplest game the miners release every mined block immediately, but are strategic on which blocks to mine. In the second more complicated game, when a block is mined it is announced immediately, but it may not be released so that other miners cannot continue mining from it. A miner not only decides which blocks to mine, but also when to release blocks to other miners. In both games, we show that when the computational power of each miner is relatively small, their best response matches the expected behavior of the bitcoin designer. However, when the computational power of a miner is large, he deviates from the expected behavior, and other Nash equilibria arise.
We survey recent results on the mathematical stability of Bitcoin protocol. Profitability and probability of a double spend are estimated in closed form with classical special functions. The stability of Bitcoin mining rules is analyzed and several theorems are proved using martingale and combinatorics techniques. In particular, the empirical observation of the stability of the Bitcoin protocol is proved. This survey article on the mathematics of Bitcoin is published by the Newsletter of the European Mathematical Society, vol.115, 2020, p.31-37. Continuation of arXiv:1601.05254 (EMS Newsletter, 100, 2016 p.32).
An open distributed system can be secured by requiring participants to present proof of work and rewarding them for participation. The Bitcoin digital currency introduced this mechanism, which is adopted by almost all contemporary digital currencies and related services. A natural process leads participants of such systems to form pools, where members aggregate their power and share the rewards. Experience with Bitcoin shows that the largest pools are often open, allowing anyone to join. It has long been known that a member can sabotage an open pool by seemingly joining it but never sharing its proofs of work. The pool shares its revenue with the attacker, and so each of its participants earns less. We define and analyze a game where pools use some of their participants to infiltrate other pools and perform such an attack. With any number of pools, no-pool-attacks is not a Nash equilibrium. We study the special cases where either two pools or any number of identical pools play the game and the rest of the participants are uninvolved. In both of these cases there exists an equilibrium that constitutes a “tragedy of the commons” where the participating pools attack one another and earn less than they would have if none had attacked. For two pools, the decision whether or not to attack is the miner’s dilemma, an instance of the iterative prisoner’s dilemma. The game is played daily by the active Bitcoin pools, which apparently choose not to attack. If this balance breaks, the revenue of open pools might diminish, making them unattractive to participants.
The main subject of this thesis is a paradigm of instability and stabilization in coalition forming among countries as rational actors, presented through a Statistical Physics inspired model.This is an interdisciplinary work involving the fields of applied mathematics and sociophysics, as well as the political applications in the real cases from past and present. Applied to political,economic and social problems, the models can be used to analyze a wide variety of real cases -- international alliances, economic or business alliances, coalitions of political parties, socialnetworks, and organizational structures.In the first part of this thesis we present and analyze the coalition forming and the instability among rational actors coupled with pairwise static historical propensity bonds that have evolvedindependently. Such organization leads to discordant associations into coalitions and the instability as a consequence of decentralized maximization of the individual benefits gained fromjoining or leaving the coalitions. We define Natural Model of coalition forming and address the questions of instability and stabilization among actors possessing different levels of rationality. The framework presented here allows to analytically calculate the optimal and non-optimal stable configurations of actors' coalitions. We then investigate the coalition forming and the stabilization under the influence of externally-set opposing global alliances, which are represented in Global Alliance Model. The stabilization is produced through new cooperations based on the effect of polarization of several distinct interests shared by actors, which generates interest-based propensities and enables a planned coalition forming. We then investigate the effect of dissolution of a global alliancewhich, together with the competing alliance, has previously generated stable coalitions.A special section of the thesis is devoted to investigation and illustration of coalition forming in real historical cases. This part presents the analysis of unstable coalitions in Europe - cycling in the England-Spain-France conflicting triangle and creation of the Italian state, as well as of the remarkable historical cases of the Soviet global alliance collapse, of the recent internal conflict in Syria, and of the "paradoxical stability" in the Eurozone.In the second part of this thesis, we present a simulation of the coalition forming models. The simulation allows to follow graphically the coalition forming processes. We present the methodology used in the simulation, as well as its application in the illustration of coalition forming in the prototypes of real case systems. Given exact propensity values, which is fairly consideredto be the most difficult part of coalition forming modeling, the simulation tool can be used to predict optimal and non-optimal spontaneous stabilizations and globally motivated stabilities inreal cases.An independent part of the thesis is devoted to the subject of viability correction in dynamic network of actors. The model is a finite set of autonomous actors with states that evolveindependently and connected into a network via their connection operators, which evolve independently as well. The network is defined to be viable if a joint evolution satisfies the centralized scarcity constraints set by the environment. In order to restore the viability of these decentralized dynamics, we apply to the method of correction by viability multipliers used in Viability Theory, where the multipliers play the role of decentralizing prices. Standing apart from the main course of the thesis, the subject of viability correction in dynamic network of actors suggests an interesting theoretic dynamical generalization of coalition stabilization in our models inspired from Statistical Physics.
The minmax regret problem for combinatorial optimization under uncertainty\ncan be viewed as a zero-sum game played between an optimizing player and an\nadversary, where the optimizing player selects a solution and the adversary\nselects costs with the intention of maximizing the regret of the player. The\nexisting minmax regret model considers only deterministic solutions/strategies,\nand minmax regret versions of most polynomial solvable problems are NP-hard. In\nthis paper, we consider a randomized model where the optimizing player selects\na probability distribution (corresponding to a mixed strategy) over solutions\nand the adversary selects costs with knowledge of the player's distribution,\nbut not its realization. We show that under this randomized model, the minmax\nregret version of any polynomial solvable combinatorial problem becomes\npolynomial solvable. This holds true for both the interval and discrete\nscenario representations of uncertainty. Using the randomized model, we show\nnew proofs of existing approximation algorithms for the deterministic model\nbased on primal-dual approaches. Finally, we prove that minmax regret problems\nare NP-hard under general convex uncertainty.\n
We analyze how network effects affect competition in the nascent cryptocurrency market. We do so by examining the changes over time in exchange rate data among cryptocurrencies. Specifically, we look at two aspects: (1) competition among different currencies, and (2) competition among exchanges where those currencies are traded. Our data suggest that the winner-take-all effect is dominant early in the market. During this period, when Bitcoin becomes more valuable against the U.S. dollar, it also becomes more valuable against other cryptocurrencies. This trend is reversed in the later period. The data in the later period are consistent with the use of cryptocurrencies as financial assets (popularized by Bitcoin), and not consistent with "winner-take-all" dynamics.
Marcelo Arenas, Juan L. Reutter, Etienne Toussaint, Martín Ugarte · 6 authors
In the consensus protocols used in most cryptocurrencies, participants called miners must find valid blocks of transactions and append them to a shared tree-like data structure. Ideally, the rules of the protocol should ensure that miners maximize their gains if they follow a default strategy, which consists on appending blocks only to the longest branch of the tree, called the blockchain. Our goal is to understand under which circumstances are miners encouraged to follow the default strategy. Unfortunately, most of the existing models work with simplified payoff functions, without considering the possibility that rewards decrease over time because of the game rules (like in Bitcoin), nor integrating the fact that a miner naturally prefers to be paid earlier than later (the economic concept of discount). In order to integrate these factors, we consider a more general model where issues such as economic discount and decreasing rewards can be set as parameters of an infinite stochastic game. In this model, we study the limit situation in which a miner does not receive a full reward for a block if it stops being in the blockchain. We show that if rewards are not decreasing, then miners do not have incentives to create new branches, no matter how high their computational power is. On the other hand, when working with decreasing rewards similar to those in Bitcoin, we show that miners have an incentive to create such branches. Nevertheless, this incentive only occurs when a miner controls a proportion of the computational power which is close to half of the computational power of the entire network.
Due to the explosive development of global network structure, electronic commerce is increasingly playing an important role in many organizations and individual consumer’s daily life. It offers opportunities to significantly improve the way for businesses interactions between both customers and suppliers. More and more large scale and decentralized ecommerce mechanisms have emerged in industrial and commercial domains in a wide range. In particular, among all these applications, online auctions, which are flexible pricing mechanisms over internet, make the physical limitations of traditional auctions disappear. They gain their extra popularity in the daily life and attract globally dispersed users due to having the characteristics that ”bargaining” and ”negotiation” besides all of the convenience. Thus, online auctions become one of the most widely studied and employed negotiation mechanisms today. Traditionally, in most current online auction applications, the traders are generally humans who operate all the behaviors to make transactions. These behaviors may involve observing the auctions, analyzing the auction information, and bidding the suitable price for the items. However, facing the increasingly demanding requirements and complexity of online trading, this kind of manual operation does not reveal the full potential of this new mode of commerce. Thus, in order to relieve the users and be more effective, exploring possible types and automating the behaviors in the online auction attract high interest. Now, in many studies, the agent-oriented auction mechanism, with its emphasis on autonomous actions and flexible interactions, arises as an effective and robust model for the dynamic and sensitive commerce environment. In such systems, the agent acts flexibly on behalf of its owner and is capable of local decision-making based on the environment information and pre-knowledge about the system. Among many different types of online auction, two of the most popular and studied types are Multiple Round English Auctions (MREA), which is single side auction, and Continuous Double Auction (CDA), which is double side auction. These auctions are newly emerged in e-commerce era based on the traditional auction types. They allow multiple agents to participate and one agent can deal with several auctions continuously or simultaneously, which are effective auction types to save time and relieve the users. Towards to these types, because there is no centralized system-wide control, the major challenge for automatic bidding strategies is to improve the degree of automation and optimize the agent’s bidding behavior in order to maximize the owner’s profit. Most of the related researches have been conducted by using heuristic methods and fixed mathematical functions to compute the final optimal bidding price for the items or to compute how much should bid at each time step. Nevertheless, because auction environments are complicated and highly dynamic due to have many factors affecting each other, these approaches are not flexible enough for the dynamic environment, and there is no dominant strategy. Against this background, this thesis is concerned with developing the intelligence of autonomous agent’s bidding strategy in order to make the agent to be more efficient and competitive for agent-based online auction mechanisms, especially in MREA and CDA. In order to be more flexible and better exploit the market information, Genetic Network Programming (GNP) is firstly employed to the agent’s bidding strategy since its applicability and efficiency have been clarified in complex and dynamic problems in many other fields. GNP is one of the evolutionary optimization techniques developed as an extension of Genetic Algorithm (GA) and Genetic Programming (GP), which uses compact directed graph structures as solutions. Basically speaking, in the proposed method, the GNP population represents the group of potential bidding strategies, and each individual uses the as-if/then decision-making functions to judge the auction information and guides the agent to take the suitable actions under different situations. Thus, it could be flexible and capable to adaptive to various auction situations. During the evolution, the GNP structure will be systematically organized, and finally, the individual which can obtain the highest profit is selected as the optimal bidding strategy at the end of training phase. In chapter 2, we introduced the conception of MREA and CDA in detail, which are the study environments in this thesis. The related researches are also introduced. In chapter 3, focusing on MREA, the bidding strategy for the auction agents in MREA is proposed using GNP. The performance of GNP-based agents is evaluated and studied in two situations: MREA is no time limit (NTL), and MREA is time limit (TL). Furthermore, according to the amount of the money each agent has, each situation is divided into 2 cases: general case and poorest case. All the participating agents in the simulations use GNP strategy. This chapter aims to study and analyze the capability and effectiveness of GNP for guiding bidding actions through the phenomenon of the simulations. The simulation results reveal that the agents using GNP strategy can understand various environments well through experiences and become smarter through evolution. In chapter 4, as an extension of the bidding strategy in chapter 3, in order to improving the agent’s intelligence and sensitivity, an enhanced bidding strategy for MREA is developed using GNP. Firstly, the GNP structure is modified to be able to judge more kinds of information and more situations at a time. Secondly, the strategy is improved to be able to consider the bidder’s attitude towards to each good, which makes the strategy to be more personalized for each bidder and could make the bidder more satisfied with the auction result and profit. The proposed strategy is compared with the previous GNP strategy and the other conventional strategies in the simulations. The simulation results demonstrated that the proposed method can outperform the previous one and is more competitive than the agents based on mathematical functions. In chapter 5, focusing on CDA, GNP with rectify nodes (GNP-RN) has been applied for CDA bidding strategy combined with proposed heuristic rules, which are derived based on the common believes for assisting agent’s bidding behavior. GNP-RN is developed aiming to guide the agent to be competitive under different CDA environments, and maximize the agent’s profit without losing chances for trading. Rectify Node (RN) is a newly proposed kind of nodes, which is used for bringing more flexible and various options for bidding action choices. 4 groups of simulations are designed to compare GNP-RN with conventional GNP and other strategies in CDA. In each simulation, the kinds of opponent agents are different in order to fully analyze the agents’ performance. The simulation results show that the proposed method can outperform all the other strategies and achieve high success rate as well as high profit even when the situation is highly competitive. In chapter 6, as an extension of GNP-RN, GNP with adjusting parameters (GNP-AP) for developing bidding strategy in large-scale CDAs is proposed and studied. In large-scale CDAs, much more history information can be obtained than small-scale CDAs. In order to enhance the sensitivity for large-scale CDAs and the capability of judging abundant information, the parameters used by GNP-AP decision-making functions are adjusted during the evolution instead of being fixed in GNP-RN. Moreover, the structure of GNP-AP is designed to be more comprehensive that the number of branches of some kinds of nodes is increased to adapt to the complicated environment situations. The simulation results show that GNP-AP can obtain a good guidance for the large-scale CDAs and could be very efficient for the markets. In chapter 7, after giving the objectives and motivation of each research in this thesis, some conclusions about the proposed algorithms are described based on the simulation results.
Abstract. We study the probability that two or more agents can attain common knowledge of nontrivial events when the size of the state space grows large. We adopt the standard epistemic model where the knowledge of an agent is represented by a partition of the state space. Each agent is endowed with a partition generated by a random scheme consistent with his cognitive capacity. Assuming that agents ’ partitions are independently distributed, we prove that the asymptotic probability of nontrivial common knowledge undergoes a phase transition. Regardless of the number of agents, when their cognitive capacity is sufficiently large, the probability goes to one; and when it is small, it goes to zero. Our proofs rely on a graph-theoretic characterization of common knowledge that has independent interest.
Shlomi Dolev, Panagiota N. Panagopoulou, Mikaël Rabie, Elad M. Schiller · 5 authors
Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the "best-reply" to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant's advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties' advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.
Ali Kakhbod, Joseph C. Koo, Demosthenis Teneketzis
We present a decentralized message exchange process (tatonnement process) for determining the level at which a certain public good will be provided to a set of individuals who finance the cost of attaining that level. The message exchange process we propose requires minimal coordination overhead and converges to the optimal solution of the corresponding centralized problem.
Epidemic theory has wide range of applications in computer networks, from spreading of malware to the information dissemination algorithms. Our society depends more strongly than ever on such computer networks. Many of these networks rely to a large extent on decentralization and self-organization. While decentralization removes obvious vulnerabilities related to single points of failure, it leads to a higher complexity of the system. A more complex type of vulnerability appears in such systems. For instance, computer viruses are imminent threats to all computer networks. We intend to study the interaction between malware spreading and strategies that are designed to cope with them. The main goals of this thesis are: 1. to analyze influence of network topology on infection spread 2. to determine how topology can be used for network protection 3. to formulate and study optimization of malware protection problem with respect to topology 4. to investigate non-cooperative game of security We used analytical tools from various fields to answer these questions. First of all, we have developed homogeneous and heterogeneous N-intertwined, susceptible - infected - susceptible (SIS) model for virus spread. This model is used to determine the influence of topology on the spreading process. For the N-intertwined model, we show that the largest eigenvalue of the adjacency matrix of the graph rigorously defines the epidemic threshold. The results of the model also predict the upper and lower bounds on epidemics as a function of nodal degree. The epidemic threshold is found to be a consequence of the mean field approximation. However, slow convergence to the steady-state justifies the application of the threshold concept. We used the exact 2N-state Markov chain model to explore the phase transition phenomenon for two contrasting cases, namely the line graph and the complete graph. The N-intertwined model assumes that the infection spreading over a link is a Poisson process. By introducing infection delay, we studied the influence of deviation from Poisson process assumption on epidemic threshold for the special case of a complete bi-partite graph. Due to the special structure of bi-partite graphs we were also able to derive approximate formula for the extinction probability in the first phase of the infection. In the case of SIS epidemic models, the effects of infection depend on the protection of individual nodes. We studied optimization of protection scheme for different networks. We use the results from heterogeneous N-intertwined model to determine the global optimum at the threshold. Above the threshold, the problem is a sum of ratios fractional programming problem, which is NP-complete. Therefore, we only determine the upper bound on the optimum. Contrary to the common sense, reducing the probability of infection for higher degree nodes pushes the network out of the global optimum. For the case of complete bi-partite graphs, we derive optimal threshold if only 2 fixed protection rates are available. Computer networks are generally distributed systems and protection cannot be globally optimized. The Internet is an extreme example: there is no global control center, and obtaining complete information on its global state is an illusion. To approach the issue of security over decentralized network, we derived a novel framework for network security under the presence of autonomous decision makers. The problem under the consideration is the N players non-cooperative game. We have established the existence of a Nash equilibrium point (NEP). The willingness of nodes to invest in protection depends on the price of protection. We showed that, when the price of protection is relatively high for all the nodes, the only equilibrium point is that of a completely unprotected network; while if this price is sufficiently low for a single node, it will always invest in protecting itself. We determine bounds on the Price of Anarchy (PoA), that describes how far the NEP is from the global optimum. We have also proposed two methods for steering the network equilibrium, namely by influencing the relative prices and by imposing an upper bound on infection probabilities. A quarantine is another possible measure against the epidemic. A quarantine on a set of network nodes separates them from the rest of the network by removing links. The concept of threshold and the N-intertwined model provides a tool to analyze how quarantine improves the network protection. We studied several different networks from artificially generated to real-world examples using the modularity algorithm. The real-world networks tend to show a better epidemic threshold after clustering than artificially generated graphs. The real-world networks have typically two or three big clusters and several smaller ones, while Barabasi-Albert (BA) and Erdos-Renyi (ER) graphs have several smaller clusters comparable in size. However, the number of removed links in a graph using modularity algorithm is unjustifiably high, suggesting that complete quarantine is not a viable solution for real-world networks.