Mechanisms
and Algorithms for
Efficient Solutions to Matching Problems
By
Anna Bogomolnaia
Mechanisms for making joint decisions, sharing the benefits from a shared resource within networks and for the assignment problem of finding an efficient one to one matching of objects between two sets (like agents and tasks) have many practical applications. Yet, the fraction of the mechanism design literature devoted to these issues has, till recently, been small. During last several years, however, this area, has attracted considerable academic interest and the proposed research plans to extend the recent work being carried out in this area in two specific directions outlined below.
Until recently, practically all studies on this subject concentrated on deterministic mechanisms and used some version of Gale's Algorithm to provide efficient and "cheat-proof" solutions to this class of problems. There are two problems with these models that our proposed research seeks to address: Firstly, most of these models use the unrealistic assumption that the agents preferences are strict (i.e., they do not admit indifference even between two identical objects). Technical difficulties of handling indifference in deterministic mechanisms is well established with only Svensson [1995] and some ongoing work by Bogomolnaia and Deb [2001] directly addressing this subject. Secondly, most of the papers in this area confine themselves to deterministic models. The indivisibilities present in matching models imply a number of restrictions in deterministic setting, in particular if a concern for fairness or symmetry between agents is present. Introducing probabilistic mechanisms provides for much wider domain permitting more equtable solutions. But, just as with indifference, there exist only a handful of papers, namely Hylland and Zeckhauser [1979], Zhou [1990], Bogmolnaia and Moulin [1999,2000] and Abdulkadiroglu and Sonmez [1998], dealing with such mechanisms. If one looks at the recent literature in this area (Abdulkadiroglu and Sonmez [1998,1999,2000], Bogmolnaia and Moulin [1999,2000], Papai [2000], Svensson [1999], Bogomolnaia and Deb [2001]), it is clear that no work has been done on probabilistic matching mechanisms in the presence of preferences that permit indifference. Models which incorporate both indifference and the possibility of random assignments will allow us to tackle a broader range of such as those as scheduling, or time-sharing. Our proposal is to complete our ongoing research on matching problems with indifference and to look at probabilistic extensions of these models as outlined below.
We are interested in finding mechanisms which would satisfy certain normative properties. The set of such requirements varies with particular problem at hand, but the main concerns of the mechanisms design literature are efficiency, fairness (or symmetry) and incentive compatibility (inducing truth-telling).
First of the models in the project is the assignment problem with indifferences. Several indivisible objects are to be assigned to the agents, who can have arbitrary preferences over objects (each agent gets at most one object). A number of the "early" papers took an exchange-based approach to this problem, allowing for indifferences and introducing ownership rights over objects (rather than looking at joint ownership as would be the case for a shared resource within a network). Allowing for markets in which individuals exchange objects these papers discuss the weak core of such a market. The existence of a solution for this model is derived using Gale's Top Cycle Algorithm. The solution, however, is not strictly efficient.
Recent papers have viewed this problem as a problem of mechanism design and have looked for incentive compatible mechanisms, which would provide an efficient and equitable solution to the matching problem and allow for the possibility of shared or common ownership. The allocation rules that this approach has yielded while efficient, have a different normative problem: that of inequity. The mechanisms have largely turned out to be ones that define a strictly hierarchical structure over the set of individuals with an implied disadvantage for those at the bottom of the hierarchy.
With a couple of exceptions, this literature assumes strict preferences over objects. Our own study of the case where agents share ownership of resources and with the general domain of preferences permitting the possibility of agents being indifferent between some objects is limited to presenting possible modifications of hierarchical mechanisms for this setting. We analyze the Priority Rule – the full analog of hierarchical rules for the general preference domain (permitting indifference) with indivisibilities. This rule by necessity is a correspondence, instead of a function, in such a setting. A complete characterization of such rules can be provided by a set of normative axioms of incentive compatibility (truth-telling is self enforced), neutrality (objects are treated symmetrically) and non-bossiness (agents do not have excessive power over what other agents get).
Also, adapting a general domain allows us to compare and unite the two approaches - exchange based and mechanism design based – an attempt which has not been made before, and to understand better the equity-efficiency trade-off for deterministic assignment rules.
The next step in integrating the two above mentioned approaches, is to combine the assumption of general domain with the assumption of partial ownership (some objects are owned by agents, while others are belong to the group as a whole). We plan on introducing more general ownership structure, allowing for an object to "belong" to a subgroup of agents, who have a voice over how to assign it. Many traditionally used normative requirements have to be carefully modified again to apply for this new extension.
We expect to be able to characterize the only rule so far presented in the literature for the general domain and partial ownership – "school admission rule" (Abdulkadiroglu and Sonmez), and do provide its extensions for more general ownership structure.
Further extension of the current work is to consider probabilistic assignments under general preferences domain. All above mentioned rules, its extensions, and new rules will be analyzed in the light of their fairness, efficiency and incentive-compatibility properties. A further comparison of exchange based and mechanism design approaches will be carried out.
One of the first steps toward a full treatment of complete and transitive preferences in the probabilistic assignment would be considering the domain of dichotomous preferences (those containing at most two indifference classes). One important fact about dichotomous domains is that all deterministic efficient assignments have the same number of "served" agents. Accordingly, the efficiency structure of probabilistic assignment is easier to capture. In particular, a uniform average of all efficient assignments is efficient. Other interesting efficient solutions emerge as well, such as a generalization of random priority rule, or a rule which maximizes product of expected utilities.
A very appealing feature of dichotomous domain in voting model is that, unlike in the strict preference domain, the three "corner stone" mechanism design requirements of incentive compatibility, equity and efficiency are compatible. Thus, instead of impossibility results, we can expect to capture specific mechanisms by adding further normative requirements.
For instance, approval voting, which selects the public alternative with the largest support (randomizing in the case of ties), is strategy-proof, efficient and fair (symmetric). It is singled out from other such mechanisms by a consistency property.
Time-sharing of a public facility is mathematically equivalent to the model of probabilistic voting, but here fairness precludes shutting down an agent entirely like approval voting would do. The facility operates in several possible modes, and each agent finds only some subset of those modes to be acceptable and others not. Here we would wish to give everyone a "fair share" of total time. The existence of a cheat-proof and efficient rule which ensures fair sharing is conjectured.
To summarize, our proposed research will attempt to extend existing models of mechanism design dealing with the matching problem and related matching algorithms to allow for a general domain of preferences and the possibility of randomization. It is expected that this extension will provide more efficient and equitable solutions to problems of resource sharing within networks than currently implementable through existing matching models.
Projects
2002-2003
2001-2002
Technical Reports
Special Emphasis
