Open Collections

Stability in markets with power asymmetry

University of British Columbia

Two classes of widely studied markets are auctions, such as eBay, and two-sided matching markets, such as matching medical residents to hospitals. In both of these markets, it often happens that one side is in power and can influence the outcome of the market---e.g., the seller in an auction. In the fist part of this thesis we study two-sided matching markets in which participants are initially endowed with partial preference orderings. Our goal is to identify a matching that is stable and optimal for the side of the market that is in power, w.r.t. the underlying true preferences of the agents. We first investigate the extent to which we can learn about this matching given the partial information. We then provide a novel model in which the true preferences are learned through interviews. Our goal is to identify a centralized interviewing policy that returns our matching of interest while minimizing the number of interviews. We introduce three minimization criteria, of which the most desirable one is not always achievable. We provide an exponential-time algorithm for computing a policy that satisfies the other two criteria, and exhibit evidence that a more efficient computation may not be possible in general. We then show how to design a computationally efficient interview-minimizing policy for a setting in which agents on one side of the market are initially endowed with identical partial preferences, and agents must interview before getting matched. In the second part, we study combinatorial auctions (CAs), where multiple goods are for sale and buyers are allowed to place bids on bundles, i.e. sets of goods. In single-good auctions the auctioneer is at no risk of losing revenue if more bidders compete in the auction. In CAs however, an auctioneer may fi nd it pro table to disqualify bidders in order to be matched to a smaller set of bidders. We investigate the extent to which this counterintuitive phenomenon can occur under CA mechanisms that o er bidders dominant strategies. We show that a broad class of deterministic CAs exhibit non-monotonicity in revenue. However, revenue monotonic CAs exist in the broader domain of randomized mechanisms.

Text

2014-01-02

CC0 1.0 Universal

http://hdl.handle.net/2429/45695

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/publicdomain/zero/1.0/