1,720,971 research outputs found
Distributed Mechanisms for Multi-Agent Systems: Analysis and Design
Full text linkThere is an increasing need for multi-agent systems to operate under decentralised control regimes that support openness (individual components can enter and leave at will) and enable components representing distinct stakeholders with different aims and objectives to interact effectively. To this end, this thesis explores issues associated with using techniques from Game Theory and Mechanism Design to organise and analyse such systems. In particular, emphasis is given to distributed mechanisms in which there is distributed allocation (no single centre determines the allocation of the resources or the tasks) and distributed information (agents require information privately known by other agents in order to determine their own valuation or cost). Such mechanisms are important because, in comparison to their centralised counterparts, they are robust to a single-point failure, the computational burden can be potentially shared amongst many agents, and there is a reduction in bottlenecks since not all communication need pass through a single point. As a result, distributed mechanisms are better suited to many types of multi-agent application. To provide a grounding for the mechanisms we develop, the thesis contains a running example of a multi-sensor network scenario. In these systems, distributed allocation mechanisms are desirable since they are robust and reduce bottlenecks in the communication system. Furthermore, we show that distributed information naturally arises by deriving an information-theoretic valuation function. This scenario also gives rise to two additional requirements that are addressed within this thesis: (i) constrained capacity, whereby suppliers can only provide a limited amount of goods or services at any given time and (ii) uncertainty in task completion, whereby sensors potentially fail after they have been assigned tasks. Specifically, we focus on the \ac{vcg} mechanisms and investigate ways of extending it so as to address the requirements that arise within distributed setting in general and sensor networks. In particular, we choose the VCG as our point of departure since it is a mechanism that is efficient, individually rational and incentive compatible. Unfortunately, it is brittle in the sense that it does not conserve these desirable properties when considering the requirements that we outlined above. Therefore, we develop novel mechanisms that do. In more detail, the first part of this thesis considers two distributed allocation mechanisms --- a simultaneous auction environment and \ac{cda}. In the former, bidders place sealed bids in a number of selling auctions which are concurrently offering items. This results in a distributed allocation whereby the winner at each auction is determined by the seller conducting it. For this case, we derive the optimal strategy of the bidders using a game-theoretic approach. In the \acs{cda}, buyers and sellers, respectively, submit bids and asks continuously and the market clears when a bid is higher than an ask; meaning that the allocation is again determined in a distributed way. Furthermore, CDAs are known to yield close to efficient allocations, under certain conditions, even when utilising very simple strategies. However, in our case, we need to modify their format in order to deal with the requirement of constrained capacity. In both of these mechanisms, we study the system's loss in efficiency that ensues from distributing the allocation and find that it is in the simultaneous auction case and upto in the continuous double auction case. The second part of this thesis is concerned with designing mechanisms when agents have distributed information within the system. Such settings are more general than those more traditionally studied in that they encompass the fact that agents can potentially change their valuation or cost upon knowing a signal about the system (which they have not observed) that was hitherto unknown to them. Specifically, we first show that interdependent valuations arise naturally within a sensor network when we develop an information-theoretic valuation function. To account for this, we significantly extend the VCG mechanism in order to deal with these interdependent valuations. We then go on to develop a mechanism that can deal with uncertainty in task allocation. In both of these cases, our mechanisms are shown to be efficient, individually rational and incentive compatible. Moreover, their computational properties are studied and efficient algorithms are designed (based on linear and dynamic programming) in order to speed up the computation of the allocation problem which is generally -hard
Optimal Financially Constrained Bidding in Multiple Simultaneous Auctions
No full textWe consider optimal procedures for bidders participating in multiple simultaneous second-price auctions. Previous research has shown that, for such a setting, it is optimal to bid strictly positive in all available auctions, even if only a single item is required. In this paper, we investigate how the bidding strategy changes when the bidder is financially constrained such that its exposure (i.e. the sum of its bids) is limited. We prove (in the case of two auctions) that when the financial constraint is equal or less than the buyer’s valuation, it is typically optimal to participate in a single auction. We also find that the optimal strategy changes fundamentally if budget constraints are introduced. In particular, whereas without budget constraints in many cases the problem of finding the optimal strategy reduces to two dimensions, this is no longer the case if the bids are constrained. Finding the optimal policy thus becomes much more involved
Computational Mechanism Design: A Call to Arms
No full textGame theory has developed powerful tools for analyzing decision making in systems with multiple autonomous actors. These tools, when tailored to computational settings, provide a foundation for building multiagent software systems. This tailoring gives rise to the field of computational mechanism design, which applies economic principles to computer systems design
Optimal strategies for bidding agents participating in simultaneous Vickrey auctions with perfect substitutes
Full text linkWe derive optimal strategies for a bidding agent that participates in multiple, simultaneous second-price auctions with perfect substitutes. We prove that, if everyone else bids locally in a single auction, the global bidder should always place non-zero bids in all available auctions, provided there are no budget constraints. With a budget, however, the optimal strategy is to bid locally if this budget is equal or less than the valuation. Furthermore, for a wide range of valuation distributions, we prove that the problem of finding the optimal bids reduces to two dimensions if all auctions are identical. Finally, we address markets with both sequential and simultaneous auctions, non-identical auctions, and the allocative efficiency of the market
Overlapping Coalition Formation for Efficient Data Fusion in Multi-Sensor Networks
No full textThis paper develops new algorithms for coalition formation within multi-sensor networks tasked with performing wide-area surveillance. Specifically, we cast this application as an instance of coalition formation, with overlapping coalitions. We show that within this application area sub-additive coalition valuations are typical, and we thus use this structural property of the problem to we derive two novel algorithms (an approximate greedy one that operates in polynomial time and has a calculated bound to the optimum, and an optimal branch-and-bound one) to find the optimal coalition structure in this instance. We empirically evaluate the performance of these algorithms within a generic model of a multi-sensor network performing wide area surveillance. These results show that the polynomial algorithm typically generated solutions much closer the optimal than the theoretical bound, and prove the effectiveness of our pruning procedure
Computational Mechanism Design for Information Fusion within Sensor Networks
No full textConventional centralised information fusion and control architectures will be challenged by developments in sensor networks that allow sophisticated autonomous sensors, owned by different stakeholders with individual goals, to interact and share information. Given this, we advocate the use of tools and techniques from computational mechanism design (CMD), a field at the intersection of computer science, game theory and economics, to address the challenges posed by these networks. In particular, CMD allows us to engineer networks with desirable system-wide properties, in which sensors act as rational selfish agents, each attempting to fulfil their own individuals goals through the exchange of observations and information. In this paper, we present our work developing such networks. Specifically, we discuss our development of a generic and principled information valuation metric for sensor networks and we report our experiences applying it within a real world information fusion sensor network scenario
A utility-based adaptive sensing and multi-hop communication protocol for wireless sensor networks
No full textThis article reports on the development of a utility-based mechanism for managing sensing and communication in cooperative multisensor networks. The specific application on which we illustrate our mechanism is that of GlacsWeb. This is a deployed system that uses battery-powered sensors to collect environmental data related to glaciers which it transmits back to a base station so that it can be made available world-wide to researchers. In this context, we first develop a sensing protocol in which each sensor locally adjusts its sensing rate based on the value of the data it believes it will observe. The sensors employ a Bayesian linear model to decide their sampling rate and exploit the properties of the Kullback-Leibler divergence to place an appropriate value on the data. Then, we detail a communication protocol that finds optimal routes for relaying this data back to the base station based on the cost of communicating it (derived from the opportunity cost of using the battery power for relaying data). Finally, we empirically evaluate our protocol by examining the impact on efficiency of a static network topology, a dynamic network topology, the size of the network, the degree of dynamism of the environment, and the mobility of the nodes. In so doing, we demonstrate that the efficiency gains of our new protocol, over the currently implemented method over a 6 month period, are 78%, 133%, 100%, and 93%, respectively. Furthermore, we show that our system performs at 65%, 70%, 63%, and 70% of the theoretical optimal, respectively, despite being a distributed protocol that operates with incomplete knowledge of the environment
Constrained Bandwidth Allocation in Multi-Sensor Information Fusion: A Mechanism Design Approach
No full textSensor networks are increasingly seen as a solution for a large number of environmental, security and military monitoring tasks. Typically, in these networks, noisy data from a number of local sensors is fused to reduce the uncertainty in the global picture. A central issue in this information fusion is the decision of what data should be shared between sensors, in order to maximise the global gain in information, when the bandwidth of the communication network is limited. In this paper, we study the problem from a selfish agent perspective. We show how the uncertainty in the measurement of an event can be cast as a utility function derived from the Kalman filter. We then use the tools of mechanism design to engineer an incentive-compatible mechanism that allows rational selfish agents to individually maximise their own utility, whilst ensuring that the overall utility of the system is also maximised. We apply the mechanism to multi-sensor target detection and consider the complexity of finding an efficient solution with broadcast communication protocols
Sellers Competing for Buyers in Online Markets
Full text linkWe consider competition between sellers offering similar items in concurrent online auctions, where each seller must set its individual auction parameters (such as the reserve price) in such a way as to attract buyers. We show that there exists a pure Nash equilibrium in the case of two sellers with asymmetric production costs. In addition, we show that, rather than setting a reserve price, a seller can further improve its utility by shill bidding (i.e., pretending to be a buyer in order to bid in its own auction). But, using an evolutionary simulation, we show that this shill bidding introduces inefficiencies within the market. However, we then go on to show that these inefficiencies can be reduced when the mediating auction institution uses appropriate auction fees that deter sellers from submitting shill bids
Sellers Competing for Buyers in Online Markets: Reserve Prices, Shill Bids, and Auction Fees
No full textWe consider competition between sellers offering similar items in concurrent online auctions through a mediating auction institution, where each seller must set its individual auction parameters (such as the reserve price) in such a way as to attract buyers. We show that in the case of two sellers with asymmetric production costs, there exists a pure Nash equilibrium in which both sellers set reserve prices above their production costs. In addition, we show that, rather than setting a reserve price, a seller can further improve its utility by shill bidding (i.e., bidding as a buyer in its own auction). This shill bidding is undesirable as it introduces inefficiencies within the market. However, through the use of an evolutionary simulation, we extend the analytical results beyond the two seller case, and we then show that these inefficiencies can be effectively reduced when the mediating auction institution uses auction fees based on the difference between the auction closing and reserve prices
- …
