Schedule
|
All technical sessions on Tuesday and Wednesday will be held in Room 206 (Business School Lecture Theatre), Gilbert Scott Building. On Thursday morning, technical sessions will be held in Room G255 (Humanities Lecture Theatre), Gilbert Scott Building. Before the first technical session of each day, coffee will be served in Room 305 (MBA Suite), Gilbert Scott Building.
|
|
Tuesday, 14 April 2015
(Wednesday | Thursday)
|
14:00-14:30
|
Registration: Room 305 (MBA Suite), Gilbert Scott Building (directions); +coffee
|
|
14:30-14:45
|
Introduction to the meeting: Room 206, Gilbert Scott Building
|
|
14:45-15:30
|
Gianluigi Greco, University of Calabria, Italy (chair: Nicolas Maudet)
|
|
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.
|
|
15:30-16:15
|
Coffee break, Room 305, Gilbert Scott building
|
|
16:15-17:00
|
Scott Kominers, Harvard University, USA (chair: Nicolas Maudet)
|
|
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]
|
|
17:00-17:45
|
Julien Lesca, Paris Dauphine University, France (chair: Nicolas Maudet)
|
|
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.
|
|
Wednesday, 15 April 2015
(Tuesday | Thursday)
|
09:00-09:45
|
Simina Brânzei, Aarhus University, Denmark (chair: Haris Aziz)
|
|
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.
|
|
09:45-10:30
|
Martin Hoefer, Max-Planck-Institut für Informatik, Germany (chair: Haris Aziz)
|
|
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.
|
|
10:30-11:15
|
Coffee break, Room 305, Gilbert Scott building
|
|
11:15-12:00
|
Vangelis Markakis, Athens University of Economics and Business, Greece (chair: Sylvain Bouveret)
|
|
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.
|
|
12:00-12:45
|
Haris Aziz, NICTA and University of New South Wales, Australia (chair: Sylvain Bouveret)
|
|
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]
|
|
12:45-14:30
|
Lunch at the Glasgow University Union dining room (map and directions)
|
|
14:30-16:00
|
Rump session (chair: Ulle Endriss) [+]
|
|
The following people all presented a 5-minute talk at the rump session:
Daniel Karabekyan (Moscow), Toby Walsh (Sydney), Annick Laruelle (Bilbao), Joanna Drummond (Toronto), Vedran Podobnik (Zagreb), Sergey Kadenko (Kiev), Giulia Rotundo (Rome), Hervé Moulin (Glasgow), Christian Klamler (Graz), Baharak Rastegari (Glasgow), Tommy Andersson (Lund), Murat Ali Cengelci (Istanbul), and Tamás Fleiner (Budapest).
|
|
16:00-16:30
|
Coffee break, Room 305, Gilbert Scott building
|
|
16:30-18:15
|
Management Committee meeting (chair: Ulle Endriss)
|
|
19:30
|
Dinner in the Terrace Lounge, Hilton Glasgow Grosvenor (map and directions)
|
|
|
Thursday, 16 April 2015
(Tuesday | Wednesday)
|
08:50-09:00
|
Opening remarks: MATCH-UP 2015
|
|
09:00-09:45
|
Joana Pais, University of Lisbon, Portugal (chair: David Manlove)
|
|
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] Slides
|
|
09:45-10:30
|
Kavitha Telikepalli, Tata Institute of Fundamental Research, India (chair: David Manlove)
|
|
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.
Slides |
|
10:30-11:00
|
Coffee break, Room 305, Gilbert Scott building
|
|
11:00-11:45
|
Tommy Andersson, Lund University, Sweden (chair: David Manlove)
|
|
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]
|
|
11:45-12:45
|
Katarína Cechlárová, Pavol Jozef Šafárik University in Košice, Slovakia (chair: David Manlove)
|
|
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.
|
|
12:45-14:30
|
Lunch at the Glasgow University Union dining room (map and directions)
|