|
|
|
|
|
|
|
University of Glasgow, 14-16 April 2015 |
| The COST Action IC1205 meeting on Fair Division and Matching takes place at the University of Glasgow, Glasgow, UK, from 14-16 April 2015. This meeting is followed by, and is partially overlapped with, the 3rd International Workshop on Matching Under Preferences (MATCH-UP 2015) that takes place from 16-18 April 2015. |
Speakers
- Tommy Andersson
Lund University, Sweden [+]Transferring Ownership of Public Housing to Existing Tenants: A Mechanism Design Approach
This paper explores the situation when tenants in public houses, in a specific neighborhood, are given the legislated right to buy the houses they live in but can choose to remain in their houses and pay the regulated rent. This type of legislation has been passed in many European countries in the last 30-35 years (U.K. Housing Act 1980 is a leading example). The main objective with this type of legislation is to transfer the ownership of the houses from the public authority to the tenants. To achieve this goal, the selling prices of the public houses are typically heavily subsidized. The legislating body then faces a trade-off between achieving the goals of the legislation and allocating the houses efficiently. This paper investigates this specific trade-off and identifies an allocation rule that is individual rational, equilibrium selecting, and group non-manipulable in a restricted preference domain that contains "almost all" preference profiles. In this restricted domain, the identified rule is the equilibrium selecting rule that transfers the maximum number of ownerships from the public authority to the tenants. This rule is also weakly preferred to the current U.K. system by both the existing tenants and the public authority. Finally, a dynamic process that finds the outcome of the identified rule, in a finite number of steps, is provided.
[Joint work with Lars Ehlers and Lars-Gunner Svensson]
- Haris Aziz
NICTA and University of New South Wales, Australia [+]Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations
Cake cutting is one of the most fundamental settings in fair division and mechanism design without money. It has applications in scheduling and multi-agent resource allocation. We focus on cake cutting with piecewise constant valuations and consider different levels of three fundamental goals in cake cutting: fairness, Pareto optimality, and strategyproofness. We present three desirable algorithms which have their relative merits in achieving these goals.
[Joint work with Chun Ye, Columbia University]
- Simina Brânzei
Aarhus University, Denmark [+]A Dictatorship Theorem for Cake Cutting
We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol for two agents in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. For n > 2 agents, a similar impossibility holds, namely there always exists an agent that gets the empty piece (i.e. no cake). In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.
- Katarína Cechlárová
Pavol Jozef Šafárik University in Košice, Slovakia [+]Assignment of teachers to schools - a new variation on an old theme
Several countries more or less successfully use centralized matching schemes for assigning teachers to vacant positions at schools. We explore combinatorial and computational aspects of a possible similar scheme motivated by the situation characteristic for Slovak and Czech education system where each teacher specializes in two subjects. We present a model that takes into consideration that schools may have different capacities for each subject and show that its combinatorial structure leads to intractable problems even under several strong restrictions concerning the total number of subjects, partial capacities of schools and the number of acceptable schools each teacher is allowed to list. We propose several approximation algorithms. Finally, we present integer programming models and their application to real data.
- Gianluigi Greco
University of Calabria, Italy [+]Mechanisms for Fair Allocation Problems in Verifiable Settings
Mechanism design is considered in the context of fair allocations of indivisible goods with monetary compensation, by focusing on problems where declarations on allocated goods can be verified before payments are performed. A setting is discussed where verification might be subject to errors, so that payments have to be awarded under the presumption of innocence, as incorrect declared values do not necessarily mean manipulation attempts by the agents. Within this setting, a mechanism is illustrated that is truthful, efficient, and budget-balanced. Moreover, utilities for the agents are fairly determined by the Shapley value of suitable coalitional games. The computational complexity of the proposed mechanism is also discussed.
- Martin Hoefer
Max-Planck-Institut für Informatik, Germany [+]Dynamic Matching with Preferences
This talk surveys our recent work on dynamic aspects of the matching problems with preferences. On the one hand, we consider dynamics in variants of stable matching where agents repeatedly deviate to blocking pairs. We present some answers to natural questions for convergence -- can convergence to stable matchings can be guaranteed? Are paths to stability short, and can they be found efficiently? On the other hand, we consider dynamic matching scenarios, where agents arrive and depart iteratively over time. The goal here is to maintain in each round a matching that is (to some extent) preferred by the agents using a small amortized number changes over time. We consider approximate versions of stable and popular matchings and quantify the tension between approximation and number of changes.
- Scott Kominers
Harvard University, USA [+]Strategy-Proofness, Investment Efficiency, and Marginal Returns: An Equivalence
We show that a mechanism induces an agent to make efficient ex ante investment choices if and only if it rewards the agent with his marginal surplus; additionally, for an ex post efficient mechanism, these properties are equivalent to strategy-proofness for the agent. Our results extend to settings with uncertainty; moreover, they have analogs for mechanisms that are only approximately efficient and approximately incentive compatible. Among other applications, our results imply both that under the worker-optimal stable mechanism, workers are incentivized to make efficient human capital investments before entering the labor market, and that second-price auctions induce efficient bidder participation.
[Joint work with J. W. Hatfield and F. Kojima]
- Julien Lesca
Paris Dauphine University, France [+]A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences
Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents' preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.
- Vangelis Markakis
Athens University of Economics and Business, Greece [+]Approximation Algorithms for Computing Maximin Share Allocations
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of a single agent is the best that he can guarantee to himself, if he partitions the goods into n bundles and receives his least desirable bundle. The objective then is to find a partition, so that each player is guaranteed his maximin share. In the presence of indivisible goods, such allocations are not guaranteed to exist, hence, we resort to approximation algorithms. Our main result is a 2/3-approximation algorithm, which runs in polynomial time for any number of agents and goods, improving upon previous results in the literature. We also investigate some special cases and provide better approximation guarantees. Finally, we provide a probabilistic analysis, showing that maximin share allocations exist in most cases (i.e., with probability 1-o(1) on randomly generated instances). This is in accordance with the apparent difficulty reported in previous works, for obtaining impossibility results.
- Joana Pais
University of Lisbon, Portugal [+]Affirmative Action through Minority Reserves: An Experimental Study on School Choice
Minority reserves are an affirmative action policy proposed by Hafalir et al. in the context of school choice. We study in the laboratory the effect of minority reserves on the outcomes of two prominent matching mechanisms, the Gale-Shapley and the Top Trading Cycles mechanisms. Our first experimental result is that the introduction of minority reserves enhances truth-telling of some minority students under the Gale-Shapley but not under the Top Trading Cycles mechanism. Secondly, for the Gale-Shapley mechanism we also find that the stable matchings that are more beneficial to students are obtained more often relative to the other stable matchings when minority reserves are introduced. Finally, the overall expected payoff increases under the Gale-Shapley but decreases under the Top Trading Cycles mechanism if minority reserves are introduced. However, the minority group benefits and the majority group is harmed under both mechanisms.
[Joint work with Flip Klijn and Marc Vorsatz]
- Kavitha Telikepalli
Tata Institute of Fundamental Research, India [+]Popular Matchings
This talk deals with finding certain optimal matchings in bipartite graphs where each vertex has a strict preference list ranking its neighbors in an order of preference. This is the same as an instance of the stable marriage problem with incomplete lists, however the notion of optimality considered here is popularity, which is weaker than the notion of stability. The advantage that we gain by replacing stability with popularity is the improvement in the size of the resulting matching. In fact, stable matchings are minimum size popular matchings and a maximum size popular matching can be twice larger. This talk is on some efficient algorithms to compute maximum size popular matchings.
The structure of popular matchings is well-understood when vertices on only one side have preferences (with possible ties) over their neighbors while vertices on the other side do not care whether they are matched or to whom they get matched. Popular matchings need not always exist in such instances. Interestingly, in the stable marriage problem with ties, the problem of determining if a popular matching exists is NP-hard.
COST is supported by the
EU Framework Programme Horizon 2020