Computing exact optimal covers for cover function games with approximate ordinal input

Abstract For cover function games (CoFGs), we address the problem of organising agents into possibly overlapping coalitions so as to maximise social welfare. We introduce a subclass of CoFGs called probabilistically monotone CoFGs. Monotonicity means that the closer a cover is to an optimum, the higher its welfare. Probabilistic monotonicity means that monotonicity is satisfied with some probability, i.e., some violations of monotonicity are permitted as long as the number of violations is bounded. In addition, externalities are permitted and social welfare is not restricted to the sum function. For such games, we obtain a bound on the number of monotonicity violations that can be permitted for computing an exact optimum. For probabilistically monotone CoFGs with a bound on the number of monotonicity violations, we devise algorithms for computing an exact optimum and analyze their time complexities. We also provide constructive proofs which form the basis for our algorithms. Placing our algorithms in the context of the existing literature, we note that a key unique feature of our algorithms is that they do not require the numeric welfare values of covers as input, rather, only an ordering over these values is required. Moreover, the ordering that is required as input does not have to be the actual ordering over the welfare values, it can be an approximate anticipated version of the actual ordering. The anticipated ordering is allowed to differ from the actual ordering in that anticipation errors, captured by monotonicity violations, are permitted in the anticipated ordering as long as the number of errors is bounded. Our algorithms are therefore highly relevant for practical applications like multi-agent task allocation where welfare values are only revealed after coalition formation although an ordering over the values can be approximately anticipated in advance of coalition formation.