Nash Equilibrium and Decentralized Negotiation in Auctioning Divisible Resources

摘要

We consider the problem of software agents being used as proxies for the procurement of computational and network resources. Mechanisms such as single-good auctions and combinatorial auctions are not applicable for the management of these services, as assigning an entire resource to a single agent is often undesirable and appropriate bundle sizes are difficult to determine. We investigate a divisible auction that is proportionally fair. By introducing the notion of price and demand functions that characterize optimal response functions of the bidders, we are able to prove that this mechanism has a unique Nash equilibrium for an arbitrary number of agents with heterogeneous quasilinear utilities. We also describe decentralized negotiation strategies which, with appropriate relaxation, converge locally to the equilibrium point. Given an agent with a sequence of jobs, we show how our analysis holds for a wide variety of objectives.