Complexity in Contract Negotiation
  Paul E. Dunne

Abstract:

A popular abstract model used in multiagent systems realisation of
e-trading envisages a collection of $m$ non-shareable resources allocated
among a society of $n$ distinct agents each of whom associates a particular
(rational) value with any given set assigned it. Two widely studied
concepts of an allocation being optimal are: Maximum Social Welfare -
the sum of the individual valuations is maximised; Pareto Optimality -
the allocation is such that any change (strictly) improving the value of some agent's
holding results in another being penalised.

An initial allocation is unlikely to be optimal in either of
these senses and thus agents must negotiate exchanges to
reach an optimum holding. Some practical restrictions, however, must
be imposed in order for the contract negotiation stages to be implementable. One such
restriction is to limit the number ($k$) of resources that may feature in a single contract and
to require that any contract entered into must strictly increase the overall Social Welfare --
so-called IR-contracts.
It is known that under these restrictions it may not be possible to reach a theoretical
optimum from a given starting allocation.

We first establish that decision variants of 2 simple optimisation problems --
  Welfare Optimisation: is there an allocation whose social welfare is >=K?
  Welfare Improvement:  is there a better allocation?
are both NP-complete;

We also show that deciding whether a given allocation is Pareto
Optimal is co-NP complete. Each of these results holding when only 2 agents are involved
and the valuation functions are monotonic.

We further prove the following results in this setting:

 I) For k=1: determining if a IR-contract sequence exists from an allocation A_1
    to another allocation A_2 is NP-hard. This holds even only 2 agents are involved
    and the resource valuation functions are monotonic.
 II) For k<=m/3 determining if a IR-contract path exists is NP-hard. This holds even
     with only 2 agents.