Distributed quiescence detection in multiagent negotiation

In a distributed multiagent negotiation involving multiple issues, it is often desirable to finalize deals only when all related issues are resolved. However, detecting that a multiagent negotiation has reached a globally quiescent state can be a nontrivial task in a distributed, asynchronous system. We present a quiescence detection protocol based on the Dijkstra-Scholten algorithm for distributed termination detection. The protocol operates as a layer on top of an underlying mediated negotiation protocol. If agents conform to the detection protocol, the detection process terminates iff the negotiation is quiescent. We discuss agent incentives to deviate from the protocol, and describe extensions that enforce adherence with respect to the most significant potential deviations.

Probabilistic state-dependent grammars for plan recognition

Techniques for plan recognition under uncertainty require a stochastic model of the plan-generation process. We introduce Probabilistic State-Dependent Grammars (PSDGs) to represent an agent's plan-generation process. The PSDG language model extends probabilistic context-free grammars (PCFGs) by allowing production probabilities to depend on an explicit model of the planning agent's internal and external state. Given a PSDG description of the plan-generation process, we can then use inference algorithms that exploit the particular independence properties of the PSDG language to efficiently answer plan-recognition queries. The combination of the PSDG language model and inference algorithms extends the range of plan-recognition domains for which practical probabilistic inference is possible, as illustrated by applications in traffic monitoring and air combat.

Compact securities markets for Pareto optimal reallocation of risk

The securities market is the fundamental theoretical framework in economics and finance for resource allocation under uncertainty. Securities serve both to reallocate risk and to disseminate probabilistic information. Complete securities markets—which contain one security for every possible state of nature—support Pareto optimal allocations of risk. Complete markets suffer from the same exponential dependence on the number of underlying events as do joint probability distributions. We examine whether markets can be structured and “compacted” in the same manner as Bayesian network representations of joint distributions. We show that, if all agents’ risk-neutral independencies agree with the independencies encoded in the market structure, then the market is operationally complete: risk is still Pareto optimally allocated, yet the number of securities can be exponentially smaller. For collections of agents of a certain type, agreement on Markov independencies is sufficient to admit compact and operationally complete markets.

AkBA: A progressive, anonymous-price combinatorial auction

The allocation of discrete, complementary resources is a fundamental problem in economics and of direct interest to e-commerce applications. Combinatorial auctions account for complementarities by optimizing over offers expressed in terms of bundles. Progressive versions of combinatorial auctions alleviate the burden on bidders of expressing offers for all bundles of interest by providing interim feedback based on partial sets of bids. Feedback in terms of hypothetical prices is particularly useful, as it directs bidders toward those bundles potentially yielding the greatest surplus. For a general class of discrete resource allocation problems with free disposal, we establish by construction the existence of competitive equilibrium prices on bundles that support the efficient allocation. We introduce AkBA, a family of progressive auctions that use these equilibrium bundle prices. We examine a particular instance of the family, called A1BA, and present some empirical data on its performance.

Combinatorial auctions for supply chain formation

Supply chain formation presents difficult coordination issues for distributed negotiation protocols. Agents must simulatenously negotiate production relationships at multiple levels, with important interdependencies among inputs and outputs at each level. Combinatorial auctions address this problem by global optimization over expressed offers to engage in compound exchanges. A one-shot combinatorial auction that optimizes the reported value of the bids results in optimal allocations with truthful bids. But autonomous self-interested agents have an incentive to bid strategically in an attempt to gain extra surplus. We investigate a particular combinatorial protocol consisting of a one-shot auction and a strategic bidding policy. We experimentally analyze the efficiency and producer surplus obtained in five networks, and compare this performance to that of a distributed, progressive auction protocol with non-strategic bidding. We find that producers can sometimes gain significantly by bidding strategically. However, when the available surplus is small relative to the consumers' values, the producers' strategic behavior may prevent the supply chain from forming at all, resulting in zero gains for all agents. We examine the robustness of the combinatorial protocol by investigating agent incentives to deviate, identifying quasi-equilibrium behavior for an example network.