09:00 - 09:30 Gathering
09:30 - 10:15 Noam Nisan (Hebrew University):
Matching for the Israeli Pre-Army-Service Gap Year: Diversity in Matching Markets
10:15 - 11:00 Kobi Gal (Ben Gurion University):
Collaborative System Design for the Human in the Loop
11:00 - 11:20 Coffee
11:20 - 12:05 Yakov Babichenko (Technion):
Communication Complexity of Local Search
12:05 - 12:50 Shahar Ovadia (Weizmann Institute of Science):
Combinatorial Cost Sharing
12:50 - 14:30 Lunch
14:30 - 15:15 Rump session: Avi Cohen, Hadassa Daltrophe, Tomer Ezra, Ophir Friedler, Kira Goldner, Moshe Mash, Oren Roth, Alon Eden
15:15 - 16:00 Michal Feldman (Tel Aviv University):
Stable Secretaries
16:00 - 16:20 Coffee
16:20 - 17:05 Moshe Babaioff (Microsoft Research):
The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade
Noam Nisan (Hebrew University): Matching for the Israeli Pre-Army-Service Gap Year: Diversity in Matching Markets
I will describe our experience of designing and running a matching market for the Israeli "mechinot", a post-high-school, pre-army-service, gap year. The matching was run during January 2018, and matched 1607 of the 2580 candidates to 35 different programs. A unique feature of this matching market is the central importance of a wide variety of diversity criteria which takes us to scenarios in which stability a'la Gale-Shapley can no longer be theoretically guaranteed or be efficiently achieved even when it exists.
Joint work with Yannai Gonczarowski, Lior Kovalio, and Assaf Romm.
Kobi Gal (Ben Gurion University): Collaborative System Design for the Human in the Loop
A significant amount of human activity involves people working together in groups. Increasingly, these groups also involve computer systems acting autonomously or as proxies for individual people or organizations. I will present work for designing effective computer agents for collaborating with people in these heterogeneous settings, drawing on artificial intelligence (knowledge representation and learning), psychology (modeling social factors) and economics (social choice). I will demonstrate this approach by presenting a methodology for extending productivity in a large scale citizen science platform, and for improving the efficiency and performance of a fair division website by reasoning about disparities in the allocation process.
Yakov Babichenko (Technion): Communication Complexity of Local Search
We show that the following communication variant of the local search problem is hard: Alice holds a function $f_A$, Bob holds a function $f_B$, and their goal is to compute a local maximum of $f_A+f_B$. We show an application of this result to combinatorial auctions with two submodular valuations: Finding an allocation such that every single item transfer weakly decreases the social welfare requires exponential (in the number of items) communication.
Joint work with Shahar Dobzinski and Noam Nisan.
Shahar Ovadia (Weizmann Institute of Science): Combinatorial Cost Sharing
We introduce a combinatorial variant of the cost sharing problem: several services can be provided to each player and each player values every combination of services differently. A publicly known cost function specifies the cost of providing every possible combination of services. A combinatorial cost sharing mechanism is a protocol that decides which services each player gets and at what price. We look for dominant strategy mechanisms that are (economically) efficient and cover the cost, ideally without overcharging (i.e., budget balanced). Note that unlike the standard cost sharing setting, combinatorial cost sharing is a multi-parameter domain. This makes designing dominant strategy mechanisms with good guarantees a challenging task.
We present the Potential Mechanism -- a combination of the VCG mechanism and a well-known tool from the theory of cooperative games: Hart and Mas-Colell's potential function. The potential mechanism is a dominant strategy mechanism that always covers the incurred cost. When the cost function is subadditive the same mechanism is also approximately efficient. Our main technical contribution shows that when the cost function is submodular the potential mechanism is approximately budget balanced in three settings: supermodular valuations, symmetric cost function and general symmetric valuations, and two players with general valuations.
Joint work with Shahar Dobzinski.
Michal Feldman (Tel Aviv University): Stable Secretaries
We define and study a new variant of the secretary problem. Whereas in the classic setting multiple secretaries compete for a single position, we study the case where the secretaries arrive one at a time and are assigned, in an on-line fashion, to one of \emph{multiple} positions. Secretaries are ranked according to talent, as in the original formulation, and in addition positions are ranked according to attractiveness. To evaluate an online matching mechanism, we use the notion of \emph{blocking pairs} from stable matching theory: our goal is to maximize the number of positions (or secretaries) that do not take part in a blocking pair. This is compared with a \emph{stable matching} in which no blocking pair exists. We consider the case where secretaries arrive randomly, as well as that of an adversarial arrival order, and provide corresponding upper and lower bounds.
Moshe Babaioff (Microsoft Research): The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade
Abstract:
The seminal impossibility result of Myerson and Satterthwaite [1983] states that for bilateral trade, there is no mechanism that is individually rational (IR), Bayesian incentive compatible (BIC), weakly budget balanced, and efficient. This has led follow-up work on two-sided trade settings to weaken the efficiency requirement and consider approximately efficient simple mechanisms, while still demanding the other properties. The current state-of-the-art of such mechanisms for two-sided markets can be categorized as giving one (but not both) of the following two types of approximation guarantees on the gains from trade: a constant ex-ante guarantee, measured with respect to the second-best efficiency benchmark, or an asymptotically optimal ex-post guarantee, measured with respect to the first-best efficiency benchmark. Here the second-best efficiency benchmark refers to the highest gains from trade attainable by any IR, BIC and weakly budget balanced mechanism, while the first-best efficiency benchmark refers to the maximum gains from trade (attainable by the VCG mechanism).
In this paper, we construct simple mechanisms for double-auction and matching markets that simultaneously achieve both types of guarantees: these are ex-post IR, BIC, and ex-post weakly budget balanced mechanisms that 1) ex-ante guarantee a constant fraction of the gains from trade of the second-best, and 2) ex-post guarantee a realization-dependent fraction of the gains from trade of the first-best, such that this realization-dependent fraction converges to 1 (full efficiency) as the market grows large.
joint work with Yang Cai, Yannai Gonczarowski and Mingfei Zhao.