Two Case Studies for Trading Multiple Indivisible Goods with Indifferences

Akihisa Sonoda, Etsushi Fujita, Taiki Todo, Makoto YokooAAAI 2014 · DOI

Abstract

This paper investigates the feasibility of achieving individual rationality (IR), Pareto efficiency (PE), and strategy-proofness (SP) in exchange markets where agents trade multiple indivisible goods and may have indifferences. We introduce the "New Trading Family" algorithm, which utilizes atomic agents and dynamic demand updates. Our analysis focuses on two preference domains: Top-Only preferences and m-chotomous preferences. We prove that while the Top-Only domain allows for mechanisms satisfying all three properties, an impossibility result holds for m-chotomous preferences where $m \geq 3$, demonstrating that the structure of preferences is a critical factor in the stability of multi-item trading systems.

Introduction

In classic economic exchange models, such as the "housing market problem," agents seek to trade their initial endowments for more preferred items. The goal of mechanism design in these markets is to satisfy three core properties: Individual Rationality (no agent is worse off), Pareto Efficiency (no agent can be made better off without hurting another), and Strategy-Proofness (no agent can benefit from misreporting preferences). While the Top-Trading-Cycles (TTC) algorithm achieves these goals for single-item trades with strict preferences, real-world scenarios involving multiple items and indifferences—where an agent might value several items equally—present significant challenges.

Previous research by Sönmez (1999) suggested that these three properties are generally incompatible when agents own multiple items. This paper re-examines this impossibility by relaxing specific assumptions about initial endowments and exploring whether certain preference structures can restore the "holy grail" of mechanism design.

The New Trading Family Algorithm

To address the complexities of multi-item trading, the authors propose the New Trading Family (Algorithm 1). This framework introduces two key innovations:

  1. Atomic Agents: To simplify the problem, the mechanism "splits" an agent who owns multiple goods into several "atomic agents." Each atomic agent owns exactly one good but shares the original agent's preferences. This transformation allows the use of techniques developed for single-item markets.
  2. Dynamic Demand Update (UPDATE-TOPS): Unlike standard TTC where demand is static, this mechanism updates an agent's demand as they acquire goods. This reflects realistic scenarios where obtaining one item (e.g., a laptop) changes the marginal utility of others (e.g., a second laptop vs. a monitor).
Representation of atomic agents and their preference structures, illustrating how multi-item ownership is partitioned for the algorithm.

The algorithm operates on a directed graph structure, identifying trading cycles and components to determine the final allocation.

Structure of the TTC-Graph used in the New Trading Family algorithm, highlighting strongly connected components and sink structures.

Preference Domains and Key Results

The paper evaluates the New Trading Family mechanism across two distinct preference domains, yielding contrasting results.

Top-Only Preferences

In the Top-Only domain, agents primarily care about obtaining their single most preferred item, though they still prefer larger bundles of goods to smaller ones. The authors prove (Theorems 1 & 2) that for this domain, the New Trading Family algorithm successfully satisfies IR, PE, and SP. This identifies a significant "safe" zone where complex multi-item trading is stable and efficient.

m-chotomous Preferences

The m-chotomous domain represents tiered preferences, where items are grouped into $m$ levels of quality (e.g., "Excellent," "Good," "Poor"). Agents are assumed to prefer any number of items from a higher tier over any number from a lower tier. The authors prove a new impossibility theorem (Theorem 3): for $m \geq 3$, no mechanism can simultaneously satisfy IR, PE, and SP. This result demonstrates that the difficulty of multi-item trading is fundamentally tied to the structure of preferences rather than just the initial endowment assumptions.

Conclusion and Future Work

This research provides a nuanced view of the boundaries of mechanism design in multi-item markets. While Top-Only preferences offer a path to efficiency and fairness, tiered preferences remain problematic. Future work remains to be done for the $m=2$ (dichotomous) case, where it is currently unknown if a perfect mechanism exists. Additionally, the authors suggest exploring the computational complexity of manipulation; if a system is theoretically manipulable but computationally difficult to cheat, it may still be viable in practice.

Summary updated

BibTeX
@inproceedings{sonoda2014two,
  author = {Akihisa Sonoda and Etsushi Fujita and Taiki Todo and Makoto Yokoo},
  title = {{Two Case Studies for Trading Multiple Indivisible Goods with Indifferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8818},
}
Figure