Miscomputing Ratio: The Social Cost of Selfish Computing Kate Larson and Tuomas Sandholm

AAAI Conferences

Auctions are useful mechanisms for allocating items (goods, tasks, resources, etc.) in multiagent systems. The bulk of auction theory assumes that the bidders' valuations for items are given a prior/. In many applications, however, the bidders need to expend significant effort to determine their valuations. This is the case, for example, when the bidders can gather information (Perisco 2000) when the bidders have the pertinent information in hand, but evaluating it is complex. There are a host of applications of the latter that are closely related to computer science and AI questions. For example, when a carrier company bids for a transportation task, evaluating the task requires solving the carrier's intractable vehicle routing problem (Sandholm 1993).


Using Performance Profile Trees to Improve Deliberation Control

AAAI Conferences

Performance profile trees have recently been proposed as a theoretical basis for fully normative deliberation control. In this paper we conduct the first experimental study of their feasibility and accuracy in making stopping decisions for anytime algorithms on optimization problems. Using data and algorithms from two different real-world domains, we compare performance profile trees to other well-established deliberation-control techniques. We show that performance profile trees are feasible in practice and lead to significantly better deliberation control decisions. We then conduct experiments using performance profile trees where deliberationcontrol decisions are made using conditioning on multiple features of the solution to illustrate that such an approach is feasible in practice.


Efficient Metadeliberation Auctions

AAAI Conferences

Imagine a resource allocation scenario in which the interested parties can, at a cost, individually research ways of using the resource to be allocated, potentially increasing the value they would achieve from obtaining it. Each agent has a private model of its research process and obtains a private realization of its improvement in value, if any. From a social perspective it is optimal to coordinate research in a way that strikes the right tradeoff between value and cost, ultimately allocating the resource to one party-thus this is a problem of multi-agent metadeliberation. We provide a reduction of computing the optimal deliberation-allocation policy to computing Gittins indices in multi-armed bandit worlds, and apply a modification of the dynamic-VCG mechanism to yield truthful participation in an ex post equilibrium. Our mechanism achieves equilibrium implementation of the optimal policy even when agents have the capacity to deliberate about other agents' valuations, and thus addresses the problem of strategic deliberation.


AAAI99-007.pdf

AAAI Conferences

Department of Economics University of Bristol 8 Woodland Road Bristol BS8 1TNFEngland Abstract This paper analyzes automated distributive negotiation where agents have firm deadlines that are private information. The agents are allowed to make and accept offers in any order in continuous time. We show that the only sequential equilibrium outcome is one where the agents walt until the first deadline, at which point that agent concedes everything to the other. This holds for pure and mixed strategies. So, interestingly, rational agents can never agree to a nontrivial split because offers signal enough weakness of bargaining power (early deadline) so that the recipient should never accept. Similarly, the offerer knows that it offered too much if the offer gets accepted: the offerer could have done better by out-waiting the opponent. In most cases, the deadline effect completely overrides time discounting and risk aversion: an agent's payoff does not change with its discount factor or risk attitude. Several implications for the design of negotiating agents are discussed. We also present an effective protocol that implements the equilibrium outcome in dominant strategies. 1 Introduction Multiagent systems for automated negotiation between self-interested agents are becoming increasingly important due to both technology push and application pull. The competitive pressure on the side with many agents often reduces undesirable strategic effects. On the other handFmarket mechanisms often have difficulty in "scaling down" to small numbers of agents (Osborne & Rubinstein 1990). In the limit of one-to-one negotiationFstrategic considerations become prevalent.


Valuation Uncertainty and Imperfect Introspection in Second-Price Auctions

AAAI Conferences

In auction theory, agents are typically presumed to have perfect knowledge of their valuations. In practice, though, they may face barriers to this knowledge due to transaction costs or bounded rationality. Modeling and analyzing such settings has been the focus of much recent work, though a canonical model of such domains has not yet emerged. We begin by proposing a taxonomy of auction models with valuation uncertainty and showing how it categorizes previous work. We then restrict ourselves to single-good sealed-bid auctions, in which agents have (uncertain) independent private values and can introspect about their own (but not others') valuations through possibly costly and imperfect queries. We investigate second-price auctions, performing equilibrium analysis for cases with both discrete and continuous valuation distributions. We identify cases where every equilibrium involves either randomized or asymmetric introspection. We contrast the revenue properties of different equilibria, discuss steps the seller can take to improve revenue, and identify a form of revenue equivalence across mechanisms.