Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMatching for the Israeli Mechinot Gap-Year Programs: Handling Rich Diversity Requirements
325
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We describe our experience with designing and running a matching market for the Israeli Mechinot gap-year programs. The main conceptual challenge in the design of this market was the rich set of diversity considerations, which necessitated the development of an appropriate preference-specification language along with corresponding choice-function semantics, which we also theoretically analyze. Our contribution extends the existing toolbox for two-sided matching with soft constraints. This market was run for the first time in January 2018 and matched 1,607 candidates (out of a total of 3,120 candidates) to 35 different programs, has been run twice more since, and has been adopted by the Joint Council of the Mechinot gap-year programs for the foreseeable future.
rate research
Read More
In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [Bredereck et al., 2019]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.
The classic paper of Shapley and Shubik cite{Shapley1971assignment} characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay. Whereas the core of this game is always non-empty, that of the general graph matching game can be empty. This paper salvages the situation by giving an imputation in the $2/3$-approximate core for the latter. This bound is best possible, since it is the integrality gap of the natural underlying LP. Our profit allocation method goes further: the multiplier on the profit of an agent is often better than ${2 over 3}$ and lies in the interval $[{2 over 3}, 1]$, depending on how severely constrained the agent is. Next, we provide new insights showing how discerning core imputations of an assignment games are by studying them via the lens of complementary slackness. We present a relationship between the competitiveness of individuals and teams of agents and the amount of profit they accrue in imputations that lie in the core, where by {em competitiveness} we mean whether an individual or a team is matched in every/some/no maximum matching. This also sheds light on the phenomenon of degeneracy in assignment games, i.e., when the maximum weight matching is not unique. The core is a quintessential solution concept in cooperative game theory. It contains all ways of distributing the total worth of a game among agents in such a way that no sub-coalition has incentive to secede from the grand coalition. Our imputation, in the $2/3$-approximate core, implies that a sub-coalition will gain at most a $3/2$ factor by seceding, and less in typical cases.
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the $epsilon$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $epsilon$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
When selling information products, the seller can provide some free partial information to change peoples valuations so that the overall revenue can possibly be increased. We study the general problem of advertising information products by revealing partial information. We consider buyers who are decision-makers. The outcomes of the decision problems depend on the state of the world that is unknown to the buyers. The buyers can make their own observations and thus can hold different personal beliefs about the state of the world. There is an information seller who has access to the state of the world. The seller can promote the information by revealing some partial information. We assume that the seller chooses a long-term advertising strategy and then commits to it. The sellers goal is to maximize the expected revenue. We study the problem in two settings. (1) The seller targets buyers of a certain type. In this case, we prove that finding the optimal advertising strategy is equivalent to finding the concave closure of a simple function. The function is a product of two quantities, the likelihood ratio and the cost of uncertainty. Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a finite-size convex program. The convex program will have a polynomial size if the state of the world has a constant number of possible realizations or the buyers face a decision problem with a constant number of options. For the general problem, we prove that it is NP-hard to find the optimal mechanism. (2) When the seller faces buyers of different types and only knows the distribution of their types, we provide an approximation algorithm when it is not too hard to predict the possible type of buyers who will make the purchase. For the general problem, we prove that it is NP-hard to find a constant-factor approximation.
We consider agents with non-linear preferences given by private values and private budgets. We quantify the extent to which posted pricing approximately optimizes welfare and revenue for a single agent. We give a reduction framework that extends the approximation of multi-agent pricing-based mechanisms from linear utility to nonlinear utility. This reduction framework is broadly applicable as Alaei et al. (2012) have shown that mechanisms for linear agents can generally be interpreted as pricing-based mechanisms. We give example applications of the framework to oblivious posted pricing (e.g., Chawla et al., 2010), sequential posted pricing (e.g., Yan, 2011), and virtual surplus maximization (Myerson, 1981).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
