2019/08/23 by Daniel Lehmann, Lehmann, Daniel · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.1908.08823
openalex publication_date 2019/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many-to-many matching with contracts is studied in the framework of revealed preferences. All preferences are described by choice functions that satisfy natural conditions. Under a no-externality assumption individual preferences can be aggregated into a single choice function expressing a collective preference. In this framework, a two-sided matching problem may be described as an agreement problem between two parties: the two parties must find a stable agreement, i.e., a set of contracts from which no party will want to take away any contract and to which the two parties cannot agree to add any contract. On such stable agreements each party's preference relation is a partial order and the two parties have inverse preferences. An algorithm is presented that generalizes algorithms previously proposed in less general situations. This algorithm provides a stable agreement that is preferred to all stable agreements by one of the parties and therefore less preferred than all stable agreements by the other party. The number of steps of the algorithm is linear in the size of the set of contracts, i.e., polynomial in the size of the problem. The algorithm provides a proof that stable agreements form a lattice under the two inverse preference relations. Under additional assumptions on the role of money in preferences, agreement problems can describe general two-sided markets in which goods are exchanged for money. Stable agreements provide a solution concept, including prices, that is more general than competitive equilibria. They satisfy an almost one price law for identical items.