Mechanisms for hostile agents with capacity constraints

Abstract

Several key economic scenarios involve agents having limited capacities whose types change with time, e.g., service workers attending to service requests, power plants supplying to power grids, and machines connected to computing grids. Dynamic mechanisms have been proposed to address the issue of dynamic types. Also, a few mechanisms have been proposed to account for limited capacities in static settings. However, no prior work considers hostile agents having a preference for harming other competing agents by making capacity over-reports. This paper proposes two novel mechanisms that possess desired properties even when the agents are hostile. First, we extend a static mechanism with capacity constraints with (1) a novel utility function that captures the preference to harm others and (2) a marginal compensation penalty scheme that minimizes the cost of capacity misreports. Next, we extend such a mechanism to the case where both the unit cost and the capacity elements of agent types are dynamic. We show that both of our mechanisms are ex-post incentive compatible, ex-post individually rational, and socially efficient. Copyright © 2013, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.