Characterization and Computation of Equilibria for Indivisible Goods

DOI10.1007/978-3-662-48433-3_19zbMATH Open1358.91069arXiv1503.06855OpenAlexW2158373208MaRDI QIDQ3449598FDOQ3449598

Peter Bro Miltersen, Hadi Hosseini, Simina Brânzei

Publication date: 4 November 2015

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Abstract: We consider the problem of allocating indivisible goods in a way that is fair, using one of the leading market mechanisms in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.

Full work available at URL: https://arxiv.org/abs/1503.06855

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Algorithmic Game Theory
• Consensus of Subjective Probabilities: The Pari-Mutuel Method
• Existence of an Equilibrium for a Competitive Economy
• The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
• On the complexity of price equilibria
• Competitive equilibrium with equal incomes for allocation of indivisible objects

Cited In (11)

• Competitive Equilibrium with Indivisible Goods and Generic Budgets
• Title not available (Why is that?)
• Title not available (Why is that?)
• The existence and computation of competitive equilibria in markets with an indivisible commodity
• Two-sided allocation problems, decomposability, and the impossibility of efficient trade
• Collective decision making
• Computation, Multiplicity, and Comparative Statics of Cournot Equilibria in Integers
• On the computability of equitable divisions
• When dividing mixed manna is easier than dividing goods: competitive equilibria with a constant number of chores
• On endowments and indivisibility: partial ownership in the Shapley-Scarf model
• On the Shapley-Scarf economy: The case of multiple types of indivisible goods

This page was built for publication: Characterization and Computation of Equilibria for Indivisible Goods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449598)