ausblenden:
Schlagwörter:
Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Computational Complexity, cs.CC,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Multiagent Systems, cs.MA
Zusammenfassung:
We study the fair division problem of allocating a mixed manna under
additively separable piecewise linear concave (SPLC) utilities. A mixed manna
contains goods that everyone likes and bads that everyone dislikes, as well as
items that some like and others dislike. The seminal work of Bogomolnaia et al.
[Econometrica'17] argue why allocating a mixed manna is genuinely more
complicated than a good or a bad manna, and why competitive equilibrium is the
best mechanism. They also provide the existence of equilibrium and establish
its peculiar properties (e.g., non-convex and disconnected set of equilibria
even under linear utilities), but leave the problem of computing an equilibrium
open. This problem remained unresolved even for only bad manna under linear
utilities.
Our main result is a simplex-like algorithm based on Lemke's scheme for
computing a competitive allocation of a mixed manna under SPLC utilities, a
strict generalization of linear. Experimental results on randomly generated
instances suggest that our algorithm will be fast in practice. The problem is
known to be PPAD-hard for the case of good manna, and we also show a similar
result for the case of bad manna. Given these PPAD-hardness results, designing
such an algorithm is the only non-brute-force (non-enumerative) option known,
e.g., the classic Lemke-Howson algorithm (1964) for computing a Nash
equilibrium in a 2-player game is still one of the most widely used algorithms
in practice.
Our algorithm also yields several new structural properties as simple
corollaries. We obtain a (constructive) proof of existence for a far more
general setting, membership of the problem in PPAD, rational-valued solution,
and odd number of solutions property. The last property also settles the
conjecture of Bogomolnaia et al. in the affirmative.
