On Member-Driven, Efficient and Fair Timeshare Exchanges

Vacation Timeshare is a form of ownership or "right to use" of a resort property for a specific time period (typically a week) each year. Timeshare exchange refers to the non-monetary trading of timeshare weeks among owners, so that they can interchange their vacation homes to experience new destinations. The need for member participation during the exchange process has been well-recognized for a variety of practical reasons, including the reluctance of members to accept an authoritarian solution that does not provide any information about the exchange process and their desire to experience some control over the process. Another important need is to ensure that, given the members' preferences, an exchange solution offers collectively the best-possible improvement over their currently-owned weeks, while being "fair" to all participants. We suggest two objectives to capture the efficiency and fairness of an exchange solution. For the resulting bi-criteria problem, we show that a solution that is simultaneously near-optimal on both objectives may not exist. Our main contribution is an efficient algorithm in which (i) each member uses her private preference list to communicate with other members, and the members, through such communications, collectively achieve an individually rational allocation, and (ii) for any desired approximation bounds alpha and beta on, respectively, efficiency and fairness, the following property holds: if an (alpha, beta)-approximate solution exists, then the solution provided by the algorithm satisfies this approximation guarantee; otherwise, the solution is an alpha-approximation on the efficiency measure and, among all such allocations, has the best fairness measure.