Online Housing Market

Julien Lesca [email protected] · 2025

Read Online Housing Market by Julien Lesca [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-15916.txt.

Introduction

Julien Lesca studies an online form of the classic housing swap market where each agent owns one house and seeks a trade. In the online form agents come and go at any time, so no full market ever sits still. He stretches two famed rules to that shifting world.

The stretch aims to keep fair traits like no waste, no harm to joiners, and no gain from lying. It also aims to block games with arrival or exit timing. He proves all traits at once can not be had online. Variants trade traits off, each keeping a split subset of the ideal list.

Catalog record

CREATORJulien Lesca [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-15916

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Online Housing Market Julien Lesca [email protected] Abstract This paper studies an online variant of the celebrated housing market problem (?), where each agent owns a single house and seeks to exchange it for another based on her preferences. In this online setting, agents may arrive and depart at any time, meaning that not all agents are present on the housing market simultaneously. We extend the well-known serial dictatorship and Gale’s top trading cycle mechanisms to this online scenario, aiming to retain their desirable properties such as Pareto efficiency, individual rationality, and strategy-proofness. These extensions also seek to prevent agents from strategically delaying their arrival or advancing their departure. We demonstrate that achieving all of these properties simultaneously is impossible in the online context, and we present several variants that achieve different subsets of these properties. † † jair-heading: Vol. 1 (1993), 1-15 — sub: 6/91, pub: 9/91 1 Introduction Allocating indivisible resources to agents is a fundamental problem in computational social choice, which lies at the intersection of economics (?) and computer science (?, ?). The decision maker in such problems must consider both the preferences of the agents over the resources and their strategic behavior. In this paper, we focus on a specific problem known as the housing market in the matching theory literature (?), where each agent is endowed with a single resource that they are willing to exchange for another. Furthermore, we assume that no monetary compensation is allowed to offset any unfavorable exchanges during the process. Despite its simplicity, this problem has many applications, including the exchange of dormitory rooms for students (?), the trade of used items (?), kidney exchanges where incompatible donor/recipient pairs exchange viable organs for transplants (?), and many more (see, e.g., (?) for additional applications). In this paper, we assume that the preferences over resources are ordinal, which is a standard assumption for the housing market. By doing so, we implicitly assume that the decision maker cannot assess the magnitude of preferences between resources, either because this information is unavailable or because it is too costly to obtain through interaction with the agents. The procedure for reallocating resources among agents is centralized, and the decision maker aims to produce an allocation that is as efficient as possible Under ordinal preferences, Pareto optimality is an appropriate efficiency measure, aiming to find allocations where no agent can be made better off without harming another. In the standard offline setting, this requirement can be satisfied by the serial dictatorship (SD) procedure, sometimes called picking-sequence (?). In this procedure, agents are arranged in a specific order, and each agent, one by one, selects their most preferred resource from the pool of remaining resources. However, this process is not individually rational, as some agents may end up with resources less desirable than their initial endowments. This is undesirable because agents may be incentivized to avoid participating in the trade for fear of being worse off. The well-known Gale’s top trading cycle (TTC) procedure (?) circumvents this drawback by ensuring individual rationality while computing an allocation that is Pareto optimal. Since the procedure is centralized, the decision maker must interact with agents to gather their preferences over resources. However, during this process, agents may misreport their preferences in an attempt to manipulate the procedure and achieve a more favorable outcome. Mechanism design, a subfield of game theory, seeks to create procedures where truthfully revealing preferences is a dominant strategy for agents (?). Both serial dictatorship and TTC procedures possess this property. Moreover, it has been proven that the TTC procedure is the only mechanism that is simultaneously individually rational, Pareto efficient, and strategy-proof (?). The standard offline setting assumes that all agents participating in the exchange are available at the same time, and that the exchange procedure is conducted during this period. However, in many contexts, this requirement is unrealistic or too demanding, making it difficult to gather a larger set of agents for the exchange. In more realistic scenarios, agents are only available during restricted time periods, meaning that some may not be able to participate in the exchange simultaneously. This is the case, for example, with online exchange websites (?), where agents do not arrive at the marketplace at the same time and cannot remain indefinitely before their swaps take place. This type of scenario is referred to as online (?), or dynamic, in the context of matching (?). In this paper, we show how the standard procedures, serial dictatorship and TTC, can be adapted to fit an online environment. Outline Section 2 provides a non-exhaustive list of related works connected either to the housing market problem or to online versions of social choice problems. Section 3 presents the main definitions of the key properties that we seek to achieve for our mechanisms. Sections 4 to 6 describe online mechanisms based on the famous serial dictatorship procedure. More specifically, Section 4 first considers a static variant of this procedure, where assignments to non-leaving agents are irrevocable. Section 5 relaxes this requirement by considering a dynamic version of the serial dictatorship. Section 6 considers a safe version in which no agent can be allocated an item she prefers less than her own. Finally, Section 7 introduces multiple online variants of the TTC procedure. 2 Related Works Related works encompass studies on variants of the housing market problem and investigations into online versions of social choice problems. 2.1 Housing Market Problem Variants Multiple variants of the standard housing market have been explored in the literature. First, the extension to exchanges involving multiple items has been extensively studied. Fujita et al. (?) proposed a TTC-like procedure that selects a Pareto optimal allocation (which belongs to the core) under restricted preferences over sets of resources. This work was extended to problems where multiple copies of items exist, and similar results were found under slightly different restrictions on preferences (?). When agents can exchange multiple resources, the problem of computing an individually rational and Pareto efficient allocation is known to be NP-hard, even for additive preferences (?). A sufficient condition to achieve strategy-proofness has also been provided (?). Other extensions have considered exchange situations where agents are embedded in a social network. In some cases, the possible exchanges are constrained by the structure of the social network (?, ?, ?, ?). Others have viewed the social network as a means to advertise the exchange procedure, designing mechanisms to incentivize agents to invite their neighbors to participate (?, ?). Finally, other works have explored extensions of the preference model used to describe agents’ preferences. Standard algorithms have been adapted to handle cases with indifferences (?, ?). In another direction, the scope of the preference model can extend beyond simply considering the resource allocated to an agent. For instance, some works (?, ?) have introduced preference models that also take into account the identity of the agent receiving an individual’s initial endowment. 2.2 Online Problems in Social Choice Multiple social problems related to our exchange problem have been examined through the lens of online procedures. In fair division, which aims to allocate resources fairly, several online variants have been explored (?, ?, ?). For instance, strategy-proofness and Pareto efficiency have been studied

Read the complete text