BibTeX for papers by David Kotz; for complete/updated list see https://www.cs.dartmouth.edu/~kotz/research/papers.html @Article{bredin:jgame, author = {Jonathan Bredin and Rajiv T. Maheswaran and {\c{C}}agri Imer and Tamer Ba{\c{s}}ar and David Kotz and Daniela Rus}, title = {{Computational Markets to Regulate Mobile-Agent Systems}}, journal = {Autonomous Agents and Multi-Agent Systems}, year = 2003, month = {May}, volume = 6, number = 3, pages = {235--263}, publisher = {Kluwer Academic Publishers}, copyright = {Kluwer Academic Publishers}, DOI = {10.1023/A:1022923422570}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-jgame/index.html}, abstract = {Mobile-agent systems allow applications to distribute their resource consumption across the network. By prioritizing applications and publishing the cost of actions, it is possible for applications to achieve faster performance than in an environment where resources are evenly shared. We enforce the costs of actions through markets where user applications bid for computation from host machines. \par We represent applications as collections of mobile agents and introduce a distributed mechanism for allocating general computational priority to mobile agents. We derive a bidding strategy for an agent that plans expenditures given a budget and a series of tasks to complete. We also show that a unique Nash equilibrium exists between the agents under our allocation policy. We present simulation results to show that the use of our resource-allocation mechanism and expenditure-planning algorithm results in shorter mean job completion times compared to traditional mobile-agent resource allocation. We also observe that our resource-allocation policy adapts favorably to allocate overloaded resources to higher priority agents, and that agents are able to effectively plan expenditures even when faced with network delay and job-size estimation error.}, } @InCollection{bredin:game-book, author = {Jonathan Bredin and David Kotz and Daniela Rus and Rajiv T. Maheswaran and {\c{C}}agri Imer and Tamer Ba{\c{s}}ar}, title = {{A Market-Based Model for Resource Allocation in Agent Systems}}, booktitle = {{Coordination of Internet Agents Models, Technologies, and Applications}}, editor = {Franco Zambonelli}, year = 2001, chapter = 17, pages = {426--441}, publisher = {Springer-Verlag}, copyright = {Springer-Verlag}, ISBN = {3-540-41613-7}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-game-book/index.html}, abstract = {In traditional computational systems, resource owners have no incentive to subject themselves to additional risk and congestion associated with providing service to arbitrary agents, but there are applications that benefit from open environments. We argue for the use of markets to regulate agent systems. With market mechanisms, agents have the abilities to assess the cost of their actions, behave responsibly, and coordinate their resource usage both temporally and spatially. \par We discuss our market structure and mechanisms we have developed to foster secure exchange between agents and hosts. Additionally, we believe that certain agent applications encourage repeated interactions that benefit both agents and hosts, giving further reason for hosts to fairly accommodate agents. We apply our ideas to create a resource-allocation policy for mobile-agent systems, from which we derive an algorithm for a mobile agent to plan its expenditure and travel. With perfect information, the algorithm guarantees the agent's optimal completion time. \par We relax the assumptions underlying our algorithm design and simulate our planning algorithm and allocation policy to show that the policy prioritizes agents by endowment, handles bursty workloads, adapts to situations where network resources are overextended, and that delaying agents' actions does not catastrophically affect agents' performance.}, } @Misc{bredin:info, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{The Role of Information in Computational-Resource Allocation, for the TASK Electronic Commerce REF}}, howpublished = {Invited paper at the DARPA TASK PI meeting}, year = 2001, month = {May}, copyright = {the authors}, location = {Santa Fe, NM}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-info/index.html}, abstract = {We examine the role of information in markets that allocate computation to software agents. The comparison of two types of markets illuminates the importance of information and the incentives for buyers and sellers to share their preferences with each other. In our comparison, the distinguishing feature of the two markets types is the alignment of agents' interests. We define a closed-interest market as one where resources are collectively owned among the agents. An open-interest market makes no assumptions on the interests of agents or resource owners. \par The incentives of agents in the two markets drastically differ. The open-interest model motivates agents to be less trusting and to not share information. This aspect stems from the model's greater applicability to resource allocation, but has a deep impact on system efficiency. In this paper, we summarize some economic theory and allegorical evidence from our models and system implementations that support the claim, and conclude with guidelines for system development. }, } @PhdThesis{bredin:thesis, author = {Jonathan L. Bredin}, title = {{Market-based Control of Mobile-agent Systems}}, school = {Dartmouth College Computer Science}, year = 2001, month = {June}, copyright = {Jonathan L. Bredin}, address = {Hanover, NH}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-thesis/index.html}, note = {Available as Dartmouth Computer Science Technical Report TR2001-408}, abstract = {Modern distributed systems scatter sensors, storage, and computation throughout the environment. Ideally these devices communicate and share resources, but there is seldom motivation for a device's owner to yield control to another user. We establish markets for computational resources to motivate principals to share resources with arbitrary users, to enforce priority in distributed systems, to provide flexible and rational limitations on the potential of an application, and to provide a lightweight structure to balance the workload over time and between devices. As proof of concept, we implement a structure software agents can use to discover and negotiate access to networked resources. The structure separates discovery, authentication, and consumption enforcement as separate orthogonal issues to give system designers flexibility. \par Mobile agents represent informational and computational flow. We develop mechanisms that distributively allocate computation among mobile agents in two settings. The first models a situation where users collectively own networked computing resources and require priority enforcement. We extend the allocation mechanism to allow resource reservation to mitigate utility volatility. The second, more general model relaxes the ownership assumption. We apply our computational market to an open setting where a principal's chief concern is revenue maximization. \par Our simulations compare the performance of market-based allocation policies to traditional policies and relate the cost of ownership and consumption separation. We observe that our markets effectively prioritize applications' performance, can operate under uncertainty and network delay, provide metrics to balance network load, and allow measurement of market-participation risk versus reservation-based computation. \par In addition to allocation problems, we investigate resource selection to optimize execution time. The problem is NP-complete if the costs and latencies are constant. Both metrics' dependence on the chosen set complicates matters. We study how a greedy approach, a novel heuristic, and a shortest-constrained-path strategy perform in mobile-agent applications. \par Market-based computational-resource allocation fertilizes applications where previously there was a dearth of motive for or means of cooperation. The rationale behind mobile-agent performance optimization is also useful for resource allocation in general distributed systems where an application has a sequence of dependent tasks or when data collection is expensive.}, } @InProceedings{bredin:game, author = {Jonathan Bredin and Rajiv T. Maheswaran and {\c{C}}agri Imer and Tamer Ba{\c{s}}ar and David Kotz and Daniela Rus}, title = {{A Game-Theoretic Formulation of Multi-Agent Resource Allocation}}, booktitle = {{Proceedings of the International Conference on Autonomous Agents}}, year = 2000, month = {June}, pages = {349--356}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/336595.337525}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-game/index.html}, abstract = {This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. From our game, we build a market-based CPU allocation policy and a strategy with which an agent may plan its expenditures for a multi-hop itinerary. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments and that our planning algorithm handles network delay gracefully.}, } @InProceedings{bredin:risk, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{Trading Risk in Mobile-Agent Computational Markets}}, booktitle = {{International Conference on Computing in Economics and Finance}}, year = 2000, month = {July}, numpages = 10, publisher = {Kluwer Academic Publishers}, copyright = {Kluwer}, address = {Barcelona, Spain}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-risk/index.html}, note = {No proceedings available}, abstract = {Mobile-agent systems allow user programs to autonomously relocate from one host site to another. This autonomy provides a powerful, flexible architecture on which to build distributed applications. The asynchronous, decentralized nature of mobile-agent systems makes them flexible, but also hinders their deployment. We argue that a market-based approach where agents buy computational resources from their hosts solves many problems faced by mobile-agent systems. \par In our earlier work, we propose a policy for allocating general computational priority among agents posed as a competitive game for which we derive a unique computable Nash equilibrium. Here we improve on our earlier approach by implementing resource guarantees where mobile-agent hosts issue call options on computational resources. Call options allow an agent to reserve and guarantee the cost and time necessary to complete its itinerary before the agent begins execution. \par We present an algorithm based upon the binomial options-pricing model that estimates future congestion to allow hosts to evaluate call options; methods for agents to measure the risk associated with their performance and compare their expected utility of competing in the computational spot market with utilizing resource options; and test our theory with simulations to show that option trade reduces variance in agent completion times.}, } @TechReport{bredin:game-tr, author = {Jonathan Bredin and Rajiv T. Maheswaran and {\c{C}}agri Imer and Tamer Ba{\c{s}}ar and David Kotz and Daniela Rus}, title = {{A Game-Theoretic Formulation of Multi-Agent Resource Allocation}}, institution = {Dartmouth Computer Science}, year = 1999, month = {October}, number = {PCS-TR99-360}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-game-tr/index.html}, abstract = {This paper considers resource allocation in a network with mobile agents competing for computational priority. We formulate this problem as a multi-agent game with the players being agents purchasing service from a common server. We show that there exists a computable Nash equilibrium when agents have perfect information into the future. We simulate a network of hosts and agents using our strategy to show that our resource-allocation mechanism effectively prioritizes agents according to their endowments.}, } @TechReport{bredin:lottery-tr, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{Mobile-Agent Planning in a Market-Oriented Environment}}, institution = {Dartmouth Computer Science}, year = 1999, month = {May}, number = {PCS-TR99-345}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-lottery-tr/index.html}, note = {Revision 1 of May 20, 1999}, abstract = {We propose a method for increasing incentives for sites to host arbitrary mobile agents in which mobile agents purchase their computing needs from host sites. We present a scalable market-based CPU allocation policy and an on-line algorithm that plans a mobile agent's expenditure over a multihop ordered itinerary. The algorithm chooses a set of sites at which to execute and computational priorities at each site to minimize execution time while preserving a prespecified budget constraint. We present simulation results of our algorithm to show that our allocation policy and planning algorithm scale well as more agents are added to the system.}, } @InProceedings{bredin:position, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{Economic Markets as a Means of Open Mobile-Agent Systems}}, booktitle = {{Proceedings of the Mobile Agents in the Context of Competition and Cooperation (MAC3) Workshop at Autonomous Agents'99}}, year = 1999, month = {May}, pages = {43--49}, publisher = {ACM}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-position/index.html}, abstract = {Mobile-agent systems have gained popularity in use because they ease the application design process by giving software engineers greater flexibility. Although the value of any network is dependent on both the number of users and the number of sites participating in the network, there is little motivation for systems to donate resources to arbitrary agents. We propose to remedy the problem by imposing an economic market on mobile-agent systems where agents purchase resources from host sites and sell services to users and other agents. Host sites accumulate revenues, which are distributed to users to be used to launch more agents. We argue for the use of markets to regulate mobile-agent systems and discuss open issues in implementing market-based mobile-agent systems.}, } @TechReport{bredin:demand-tr, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{Utility Driven Mobile-Agent Scheduling}}, institution = {Dartmouth Computer Science}, year = 1998, month = {May}, number = {PCS-TR98-331}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-demand-tr/index.html}, note = {Revised October 3, 1998}, abstract = {Mobile agents are programs capable of migrating from one host machine to another. We propose that mobile agents purchase resource access rights from host machines thereby establishing a market for computational resources and giving agents a metric to evenly distribute themselves throughout the network. Market participation requires quantitative information about resource consumption to define demand and calculate utility. \par We create a formal utility model to derive user-demand functions, allowing agents to efficiently plan expenditure and deal with price fluctuations. By quantifying demand and utility, resource owners can precisely set a value for a good. We simulate our model in a mobile agent scheduling environment and show how mobile agents may use server prices to distribute themselves evenly throughout a network.}, } @InProceedings{bredin:market, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{Market-based Resource Control for Mobile Agents}}, booktitle = {{Proceedings of the International Conference on Autonomous Agents}}, year = 1998, month = {May}, pages = {197--204}, publisher = {ACM}, copyright = {ACM}, DOI = {10.1145/280765.280801}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-market/index.html}, abstract = {Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.}, } @TechReport{bredin:market-tr, author = {Jonathan Bredin and David Kotz and Daniela Rus}, title = {{Market-based Resource Control for Mobile Agents}}, institution = {Dartmouth Computer Science}, year = 1997, month = {December}, number = {PCS-TR97-326}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/bredin-market-tr/index.html}, abstract = {Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.}, }