Blockchain Papers

Javier Contreras, Yeny E. Rodríguez

No abstract is available for this record.

Ayelet Sapirshtein, Yonatan Sompolinsky, Aviv Zohar

Bitcoin is a decentralized crypto-currency, and an accompanying protocol, created in 2008. Bitcoin nodes continuously generate and propagate blocks---collections of newly approved transactions that are added to Bitcoin's ledger. Block creation requires nodes to invest computational resources, but also carries a reward in the form of bitcoins that are paid to the creator. While the protocol requires nodes to quickly distribute newly created blocks, strong nodes can in fact gain higher payoffs by withholding blocks they create and selectively postponing their publication. The existence of such selfish mining attacks was first reported by Eyal and Sirer, who have demonstrated a specific deviation from the standard protocol (a strategy that we name SM1). In this paper we extend the underlying model for selfish mining attacks, and provide an algorithm to find $ε$-optimal policies for attackers within the model, as well as tight upper bounds on the revenue of optimal policies. As a consequence, we are able to provide lower bounds on the computational power an attacker needs in order to benefit from selfish mining. We find that the profit threshold -- the minimal fraction of resources required for a profitable attack -- is strictly lower than the one induced by the SM1 scheme. Indeed, the policies given by our algorithm dominate SM1, by better regulating attack-withdrawals. Using our algorithm, we show that Eyal and Sirer's suggested countermeasure to selfish mining is slightly less effective than previously conjectured. Next, we gain insight into selfish mining in the presence of communication delays, and show that, under a model that accounts for delays, the profit threshold vanishes, and even small attackers have incentive to occasionally deviate from the protocol. We conclude with observations regarding the combined power of selfish mining and double spending attacks.

Morten Brandvold, Péter Molnár, Kristian Vagstad, Ole Christian Andreas Valstad

No abstract is available for this record.

Nicolas Houy

When processing transactions in a block, a miner increases his reward but also decreases his probability to earn any reward because the time needed for his block to reach consensus depends on its size. We show that this leads to a game situation between miners. We analytically solve this game for two miners. Then, we show that miners do not play a Nash equilibrium in the current Bitcoin mining environment, instead, they should not process any transaction. Finally, we show that the situation where no transaction is ever processed would stop being a Nash equilibrium if the transaction fee was multiplied or, equivalently, the fixed reward divided by a factor of about 12.

Nicolas Houy

We study the economics of Bitcoin transaction fees in a simple static partial equilibrium model with the specificity that the system security is directly linked to the total computational power of miners. We show that any situation with a fixed fee is equivalent to another situation with a limited block size. In both cases, we give the optimal value of the transaction fee or of the block size. We also show that making the block size a non binding constraint and, in the same time, letting the fee be fixed as the outcome of a decentralized competitive market cannot guarantee the very existence of Bitcoin in the long-term.

Michał Polasik, Anna Piotrowska, Tomasz Piotr Wisniewski, Radosław Kotkowski · 5 authors

Over recent years, interest has been growing in Bitcoin, an innovation that has the potential to play an important role in e-commerce and beyond. The aim of our paper is to provide a comprehensive empirical study of the payment and investment features of Bitcoin, and their implications for the conduct of e-commerce. Since network externality theory suggests that the value of a network and its take-up are interlinked, we investigate both adoption and price formation. We discover that its returns are driven primarily by Bitcoin’s popularity, the sentiment expressed in newspaper reports on cryptocurrency, and total number of transactions. The paper also reports on the first global survey of merchants who have adopted this technology, and we model the share of sales paid for with this alternative currency, using both ordinary and Tobit regressions. Our analysis examines how country-, customer-, and company-specific characteristics interact with the proportion of sales attributed to Bitcoin. We find that company features, use of other payment methods, customers’ knowledge about Bitcoin, and the size of both the official and unofficial economy are significant determinants. The results will be of interest to traders who seek to understand factors driving prices and will help to inform vendors as to the most favorable circumstances for adopting the currency for online transactions.

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.

Per J. Agrell, Peter Bogetoft

Specific supply-chain investments are vital in achieving faster lead-time performance and more competitive costs. In practice, such as in the highly leveraged telecom sector, the coordinating original equipment manufacturers (OEM) often delegate the upstream coordination of suppliers to contract manufacturers. This can be justified by informational advantages or economies of scale. However, the rationale of such schemes has also been challenged by analytical work on three-stage chains, leading to open questions. In this paper, we study the organizational and contractual choice of a supply chain coordinator (say an OEM) to either control or delegate the investment decision of some shared resource (say dedicated machines, information or product standards, etc) to a contract manufacturer (CM) or to an upstream supplier in a three-stage supply chain. The analysis derives closed-form results for the economic performance of three scenarios under asymmetric information on investment cost: direct contracting with an integrated CM-supplier, decentralized contracting to tier-1 suppliers and centralized contracting to tier-1 and tier-2 suppliers. The results show that the observed practice to delegate investments to tier-1 and possibly tier-2 suppliers leads to relatively poor performance due to under-investments. The superior arrangement is the centralized conditional model, where the OEM forces coordination among upstream suppliers by offering conditional financing. We close the paper with an analogy to the Boeing 787 supply chain and some discussion about the assumptions and applicability of the model.

Torsten O. Paulussen, Armin Heinzl, Christian Becker

The health sector is a central domain in every economy. It is challenged by progressing costs and funding issues. Hospitals play a major role for the examination and treatment of patients. The sequence how patients are assigned to hospital units determines the quality of treatment, the resource utilization, as well as the patients’ overall treatment time. Thus, efficient scheduling of patients in hospitals is crucial. Current approaches disregard the decentral organization in hospitals and neglect the varying pathway of patients since they often focus on one single unit solely. We propose an agent-based coordination mechanism that overcomes these limitations. Patients and hospital resources are modeled as autonomous software agents which follow their own objectives. This reflects the decentralized structure in hospitals. Agents are coordinated by a distributed mechanism where software agents improve their situation through negotiations which moves towards an overall pareto-optimum. We show promising evaluations based on experiments.

Jannik Dreier, Jean‐Guillaume Dumas, Pascal Lafourcade

Auctions have a long history, having been recorded as early as 500 B.C. [Auction Theory, Academic Press, San Diego, USA, 2002]. Nowadays, electronic auctions have been a great success and are increasingly used in various applications, including high performance computing [Concurrency and Computatio n: Practice and Experience 14(13–15) (2002), 1507–1542]. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt [International Journal of Information Security 5 (2006), 201–216] developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the bidders, i.e. no information apart from the winner and the winning price is leaked. We first show that this protocol – when using malleable interactive zero-knowledge proofs – is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participants’ bids. We provide an efficient parallelized implementation of the protocol and the attack to show its practicality. Additionally we discuss some issues with verifiability as well as attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.

Hanieh JavadiKhasraghi, Shahriar Mohammadi

Web2 and the evolving vision of Web3 have a great effect on facilitation of information sharing, information aggregation, interoperability, user-centered design, collaboration on the World Wide Web, and crowd-centered services. New concept of Web is the intuition that drives crowdsourcing, crowd servicing, and crowd computing. With crowdsourcing emergence people get motivated to work through internet without being limited by time or geographical location. On the other hand employers could have their jobs done faster and cheaper. This paper is going to introduce an innovative approach for Amazon Mechanical Turk (AMT) crowdsourcing marketplace. In current AMT marketplace, workers especially new ones need to qualify themselves for each requester that has submitted Human Intelligence Tasks (HITs) in AMT, and there is lack of shared reputation system; some workers may cheat on tasks in order to maximize their income, as a result requesters are uncertain of the quality of results, so they offer lower rewards and consequently qualified workers leave the marketplace.

Mike Burkart, Samuel Lee

Abstract We study transactions in which sellers fear being underpaid because their outside option is better known to the buyer. We rationalize various observed contracts as solutions to such smart buyer problems. Key to these solutions is granting the seller upside participation. In contrast, the lemons problem calls for granting the buyer downside protection. But, in either case, the seller (buyer) receives a convex (concave) claim. Thus, contracts usually associated with the lemons problem, such as debt or cash-equity offers, can be equally well manifestations of the smart buyer problem, although the two information asymmetries have opposite cross-sectional implications. Received December 23, 2014; accepted May 23, 2016 by Editor Uday Rajan.

Chuan Yue, 32794

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.

Huaning Cai

Modern engineering and social systems are often too complex to be managed by a centralized agent. Instead, such systems are commonly structured with multiple decentralized agents each responsible for managing a subset of the system, but the resulting system performance depends on the aggregate of the decisions made by decentralized agents. Local agents' decision makings often exhibit selfish behavior as they seek to optimize their own objectives under their localized models, which if left uncoordinated can lead to substantial loss of efficiency compared with the system that can be optimized by a single (hypothetical) centralized agent. In this dissertation, we seek to study the fundamental issues of how to efficiently manage large-scale and multi-agent stochastic dynamic systems, especially on how to device efficient coordination mechanisms that would optimize system performance under various constraints that are unique to decentralized systems.In the first part of this dissertation we study decentralized control of a general class of stochastic dynamic resource allocation problems that have many applications. We consider a stochastic system in which multiple decentralized agents allocate shared system resources in response to customer requests that arrive stochastically over time. Each agent is responsible for a subset of the allocation decisions which it makes according to a dynamic allocation policy obtained by maximizing his own expected profit subject to a potentially mis-specified model of the way in which shared resources are consumed by other agents. We introduce the notion of a transfer contract which specifies how agents compensate one another whenever resources are consumed and establish the existence of contracts under which the decentralized system has no efficiency loss relative to centralized optimality. We also show that this property is insensitive to mis-specification by each agent of the dynamics of resource consumption by others in the system. An explicit characterization of the optimal transfer contract and an iterative decentralized algorithm for computing it is also provided. In the language of duality, contracts are analogous to shadow prices and the iterative algorithm has the favor of a dual update method, but strong duality and convergence of the iterative algorithm to the set of optimal contracts are guaranteed without assumptions of convexity.In the second part of this dissertation we study a class of related decentralized control problems but specialize to portfolio and risk management. Many financial institutions typically trade in multiple correlated markets. While centralized portfolio optimization over all trading decisions is ideal, it is generally not possible due to the complexity of each market, and firms typically adopt a decentralized setup in which trading in each market the responsibility of a particular desk. Decentralized portfolio optimization, however, is complicated by the fact that different agents are commonly only well informed about their own investment universe (proprietary research and forecasts, etc) and prefer to keep this private, and have their own incentives which they optimize on the basis of their limited models. It is well known, however, that the aggregate performance of such a system can be extremely inefficient due to the loss of diversification. In this dissertation, we formulate a multi-agent dynamic portfolio choice problem and study how to improve its efficiency. We show that an internal system of swap contracts, which define internal cash transfers between agents, can be used to facilitate risk sharing and induce agents to choose portfolios that as a collection are optimal for the firm. Conceptually using swap contracts is similar to performance benchmarking that is often employed in the finance literature for decentralized portfolio management, but our new approach offers a significant advantage in that the swap contracts can be constructed in decentralized manner without requiring an all-knowing central agent. We provide an explicit characterization of the optimal swap contracts and an iterative algorithm for computing them that can be implemented without compromising proprietary agent level data.Throughout this dissertation, we also discuss various important issues surrounding decentralized control of stochastic dynamic systems, including but not limited to approximation methods, performance attribution, sensitivity analysis, and fairness issues, etc.

Christine Brandstätt, Gert Brunekreeft, Nele Friedrichsen

Smart contracts based on voluntary participation and optionality can be a low transaction cost solution to implement locational signals in distribution networks and thereby avoid network investment. This paper examines the efficiency properties of smart contracts. Based on a three-node example network we show that cases exist in which smart contracts can achieve a pareto-improvement compared to the status-quo even with voluntary participation. With the pareto improvement at least one party is better of under a smart contract without worsening the situation for anyone else. We note that this requirement is very restrictive and leaves significant potential for efficiency improvements by smart contracts untapped. We then discuss the implementation of smart contracts with incentive regulation. There are two main tasks for the regulator: allowing network operators flexibility to offer such contracts and incentivizing network operators to do so.

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.

Michael T. Goodrich, Florian Kerschbaum

In this paper, we study methods for improving the utility and privacy of\nreputation scores for online auctions, such as used in eBay, so as to reduce\nthe effectiveness of feedback extortion. The main ideas behind our techniques\nare to use randomization and various schemes to escrow reputations scores until\nappropriate external events occur. Depending on the degree of utility and\nprivacy needed, these external techniques could depend on the number and type\nof reputation scores collected. Moreover, if additional privacy protection is\nneeded, then random sampling can be used with respect reputation scores in such\na way that reputation aggregates remain useful, but individual reputation\nscores are probabilistically hidden from users. Finally, we show that if\nprivacy is also desired with respect to the the reputation aggregator, then we\ncan use zero-knowledge proofs for reputation comparisons.\n

Michael T. Goodrich, Florian Kerschbaum

In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main ideas behind our techniques are to use randomization and various schemes to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.

Paola Adinolfi, Mita Marra, Raffaele Adinolfi

In Italy, the transformation of government procurement began in 2000 with the model developed by Consip SpA (a public company owned by the Ministry of Economy and Finance) for all public agencies across the nation. The paper is aimed to reconstruct the path taken by the public procurement reform in Italy gradually evolving from a supply-driven to a demand-driven approach. The Italian procurement transformation has co-existed with two different approaches to reform, which are working in parallel and sometimes at cross-purposes. A supply-driven approach focuses on tightening the controls on spending to tap economies of scale. A demand-driven approach focuses on decentralization and development of Electronic Public Administration MarketPlace (MEPA). The paper discusses the role Consip has played and is still playing to centrally guide the decentralization of public e-procurement, and shows the results of a sample investigation aimed at analysing the level of satisfaction of small/medium firms participating in the MEPA.

Camelia Bejan, Juan Camilo Gómez

A family of core extensions for cooperative TU-games is introduced. These solution concepts are non-empty when applied to non-balanced games yet coincide with the core whenever the core is non-empty. The extensions suggest how an exogenous regulator can sustain a stable and efficient outcome, financing a subsidy via individual taxes. Economic and geometric properties of the solution concepts are studied. When taxes are proportional, the proportional prenucleolus is proposed as a single-valued selection device. An application of these concepts to the decentralization of a public goods economy is discussed.

Aydin Behnad, Taraneh Eghlidos

A Publicly Veriable Secret Sharing (PVSS) scheme, as introduced by Stadler, has a feature where anyone, besides the participants, can verify the validity of the shares distributed by the dealer. Schoenmakers added a new feature, by providing a proof of correctness of the shares released by the players in the reconstruction process. This protocol is claimed to be an improvement on Stadler's and Fujisaki-Okamoto's, both in eciency and in the type of intractability assumptions. However, Young-Yung improved Schoenmakers' PVSS, using a Discrete-Log instead of a Decision Die-Hellman. In this paper, a new PVSS is presented, having an intrinsic dierence with its predecessors, that is, the participants can prove the validity of their given shares, implicitly, proving their membership by a zero-knowledge protocol. This feature prevents cheaters from participating in the reconstruction process to gain valid shares. Hence, the new proposed PVSS is more secure than previous ones. Besides, the dealer only sends the amount of commitments limited to the threshold value, regardless of the number of shareholders; this leads to a more dynamic protocol.

Sara Biancini

We consider the regulation of national firms in a common market. Regulators can influence the production of national firms but they incur in a positive cost of public funds. First, we show that market integration is welfare improving if and only if the efficiency gains compensate for the negative public finance effect (related to business stealing). We also show that supranational competition can have very different consequences on the rent seeking behaviour of firms, depending on cost correlation and ex-ante technological risk. Finally, we characterize the global optimum and show how it can be sustained in a decentralized bargaining solution.

Don Perugini, Dennis Jarvis, Stefan Reschke, Don Gossink

Military operations typically involve cooperation of various military, government and commercial organizations from various nations. In order to coordinate these autonomous organizations, a social mechanism is required that facilitates deliberative planning and task allocation in decentralized, open and dynamic environments, and enables agreements via a legal contracting process. In this paper, we present (a component of) such a mechanism, called the legal agreement protocol (LAP). Agents that plan using LAP must plan with partial observability that is the customer is only aware of proposals (capabilities) that suppliers choose to send. This makes it difficult for the customer to determine the (minimum/average) expected cost of any unallocated sub-tasks in its search. In this paper, we present and compare various heuristics that allow the customer to dynamically determine the expected cost for sub-tasks as proposals are received during planning. We show that different heuristics have tradeoffs in terms of quality of solution and search effort (efficiency of search and quantity of communication). The number of distributed agents involved in planning also influences the effort required to search. More agents increase communication, but provide more information (observability) about agents' capabilities to be utilized by the heuristics

Son Ku Kim, Keunkwan Ryu

This paper studies the issue of designing an optimal organizational form: design for sub-units' task allocation, decision-making structure, and incentive schemes for organizational members. Depending on the way tasks are allocated between the sub-units, and whether decision-making is centralized or not, organizations face a trade-off between coordination and information. Task allocation by production processes calls for coordination more strongly than the allocation by final products. Centralized decision-making serves for better coordination, whereas decentralization serves for better information. The coordinational benefit under centralization gets bigger as the organization's common uncertainty increases, and this benefit is magnified when the sub-units are functionally divided by production processes. The informational benefit under decentralization gets bigger as the organization's local uncertainty increases, and this benefit is magnified when the sub-units are designed autonomous. Thus, complementarily designed organizations tend to have centralized decision-making structures and fixed salary scheme, whereas less complementarily designed organizations tend to have decentralized decision-making and 'pay for performance' incentive contract.