[ Home ]
Abstract: We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. We test these algorithms on many classes of games, and show that they perform well against the state of the art-- the Lemke-Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan-Wilson for n-player games.
Abstract: For the problem of online real-time scheduling of jobs on a single processor, previous work presents matching upper and lower bounds on the competitive ratio that can be achieved by a deterministic algorithm. However, these results only apply to the non-strategic setting in which the jobs are released directly to the algorithm. Motivated by emerging areas such as grid computing, we instead consider this problem in an economic setting, in which each job is released to a separate, self-interested agent. The agent can then delay releasing the job to the algorithm, inflate its length, and declare an arbitrary value and deadline for the job, while the center determines not only the schedule, but the payment of each agent. For the resulting mechanism design problem (in which we also slightly strengthen an assumption from the non-strategic setting), we present a mechanism that addresses each incentive issue, while only increasing the competitive ratio by one. We then show a matching lower bound for deterministic mechanisms that never pay the agents.
Abstract: In many online domains, agents share goods or services that are both cheap to provide and valuable to receive. Examples include ratings in a recommender system, forwarding a message to node closer to its destination in a mobile ad-hoc network, and uploading a file in a P2P system. Existing systems in these domains often rely on agents to voluntarily provide goods. Despite the low cost of doing so, many agents instead choose to free-ride, leading to a loss in social efficiency. We present an initial step towards addressing this problem in the context of an abstract, extremely simplified model, where we identify more efficient mechanisms, including one that is provably optimal.
Abstract: We generalize the framework of non-cooperative computation (NCC), recently introduced by Shoham and Tennenholtz, to apply to cryptographic situations. We consider functions whose inputs are held by separate, self-interested agents. We consider four components of each agent's utility function: (a) the wish to know the correct value of the function, (b) the wish to prevent others from knowing it, (c) the wish to prevent others from knowing one's own private input, and (d) the wish to know other agents' private inputs. We provide an exhaustive game theoretic analysis of all 24 possible lexicographic orderings among these four considerations, for the case of Boolean functions (mercifully, these 24 cases collapse to four). In each case we identify the class of functions for which there exists an incentive-compatible mechanism for computing the function. In this article we only consider the situation in which the inputs of different agents are probabilistically independent.
Abstract: Motivated by the rise of online auctions and their relative lack of security, this paper analyzes two forms of cheating in sealed-bid auctions. The first type of cheating we consider occurs when the seller examines the bids of a second-price auction before the auction clears and then submits a shill bid in order to increase the payment of the winning bidder. In the second type, a bidder cheats in a first-price auction by examining the competing bids before submitting his own bid. In both cases, we derive equilibrium strategies when bidders are aware of the possibility of cheating. These results provide insights into sealed-bid auctions even in the absence of cheating, including some counterintuitive results on the effects of overbidding in a first-price auction.
Abstract: We introduce the notion of fault tolerant mechanism design, which extends the standard game theoretic framework of mechanism design to allow for uncertainty about execution. Specifically, we define the problem of task allocation in which the private information of the agents is not only their costs to attempt the tasks, but also their probabilities of failure. For several different instances of this setting we present technical results, including positive ones in the form of mechanisms that are incentive compatible, individually rational and efficient, and negative ones in the form of impossibility theorems.
Abstract: We introduce a new mechanism-design problem called fair imposition. In this setting a center wishes to fairly allocate tasks among a set of agents whose cost structures are known only to them, and thus will not reveal their true costs without appropriate incentives. The center, with the power to impose arbitrary tasks and payments on the agents, has the additional goal that his net payment to these agents is never positive (or, that it is tightly bounded if a loss is unavoidable). We consider two different notions of fairness that the center may wish to achieve. The central notion, which we call k-fairness, is in the spirit of max-min fairness. We present both positive results (in the form of concrete mechanisms) and negative results (in the form of impossibility theorems) concerning these criteria. We also briefly discuss an alternative, more traditional interpretation of our setting and results, in the context of auctions.
Abstract: We explore the problem of sharing network resources when users' preferences lead to temporally concentrated loads, resulting in an inefficient use of the network. In such cases external incentives can be supplied to smooth out demand, obviating the need for expensive technological mechanisms. Taking a game-theoretic approach, we consider a setting in which bandwidth or access to service is available during different time slots at a fixed cost, but all agents have a natural preference for choosing the same time slot. We present four mechanisms that motivate users to distribute the load by probabilistically waiving the cost for each time slot, and analyze the equilibria that arise under these mechanisms.