Itai Ashlagi

STOC Conference 2025 Conference Paper

From Signaling to Interviews in Random Matching Markets

• Maxwell Allman
• Itai Ashlagi
• Amin Saberi
• Sophie H. Yu

In many two-sided labor markets, interviews are conducted before matches are formed. An increase in the number of interviews in the market for medical residencies raised the demand for signaling mechanisms, in which applicants can send a limited number of signals to communicate interest. We study the role of signaling mechanisms in reducing the number of interviews in centralized random matching markets with post-interview shocks. For the market to clear we focus on interim stability, which extends the notion of stability to ensure that agents do not regret not interviewing with each other. A matching is almost interim stable if it is interim stable after removing a vanishingly small fraction of agents. We first study signaling mechanisms in random matching markets with n agents when agents on the short side, long side, or both sides signal their top d preferred partners. Interviews graphs are formed by including all pairs where at least one party has signaled the other. We show that when d = ω(1), short-side signaling leads to almost interim stable matchings. Long-side signaling is only effective when the market is almost balanced. Conversely, when the interview shocks are negligible and d = o (log n ), both-side signaling fails to achieve almost interim stability. For larger d ≥ Ω(log 2 n ), short-side signaling achieves perfect interim stability, while long-side signaling fails in imbalanced markets. We build on our findings to propose a signaling mechanism for multi-tiered random markets. Our analysis identifies conditions under which signaling mechanisms are incentive compatible. A technical contribution is the analysis of a message-passing algorithm that efficiently determines interim stability and matching outcomes by leveraging local neighborhood structures.

NeurIPS Conference 2021 Conference Paper

Counterbalancing Learning and Strategic Incentives in Allocation Markets

• Jamie Kang
• Faidra Monachou
• Moran Koren
• Itai Ashlagi

Motivated by the high discard rate of donated organs in the United States, we study an allocation problem in the presence of learning and strategic incentives. We consider a setting where a benevolent social planner decides whether and how to allocate a single indivisible object to a queue of strategic agents. The object has a common true quality, good or bad, which is ex-ante unknown to everyone. Each agent holds an informative, yet noisy, private signal about the quality. To make a correct allocation decision the planner attempts to learn the object quality by truthfully eliciting agents' signals. Under the commonly applied sequential offering mechanism, we show that learning is hampered by the presence of strategic incentives as herding may emerge. This can result in incorrect allocation and welfare loss. To overcome these issues, we propose a novel class of incentive-compatible mechanisms. Our mechanism involves a batch-by-batch, dynamic voting process using a majority rule. We prove that the proposed voting mechanisms improve the probability of correct allocation whenever agents are sufficiently well informed. Particularly, we show that such an improvement can be achieved via a simple greedy algorithm. We quantify the improvement using simulations.

SODA Conference 2019 Conference Paper

Assignment Mechanisms under Distributional Constraints

• Itai Ashlagi
• Amin Saberi
• Ali Shameli

NeurIPS Conference 2019 Conference Paper

Discrimination in Online Markets: Effects of Social Bias on Learning from Reviews and Policy Design

• Faidra Georgia Monachou
• Itai Ashlagi

The increasing popularity of online two-sided markets such as ride-sharing, accommodation and freelance labor platforms, goes hand in hand with new socioeconomic challenges. One major issue remains the existence of bias and discrimination against certain social groups. We study this problem using a two-sided large market model with employers and workers mediated by a platform. Employers who seek to hire workers face uncertainty about a candidate worker's skill level. Therefore, they base their hiring decision on learning from past reviews about an individual worker as well as on their (possibly misspecified) prior beliefs about the ability level of the social group the worker belongs to. Drawing upon the social learning literature with bounded rationality and limited information, uncertainty combined with social bias leads to unequal hiring opportunities between workers of different social groups. Although the effect of social bias decreases as the number of reviews increases (consistent with empirical findings), minority workers still receive lower expected payoffs. Finally, we consider a simple directed matching policy (DM), which combines learning and matching to make better matching decisions for minority workers. Under this policy, there exists a steady-state equilibrium, in which DM reduces the discrimination gap.

SODA Conference 2015 Conference Paper

A dynamic model of barter exchange

• Ross Anderson
• Itai Ashlagi
• David Gamarnik
• Yash Kanoria

We consider the problem of efficient operation of a barter exchange platform for indivisible goods. We introduce a dynamic model of barter exchange where in each period one agent arrives with a single item she wants to exchange for a different item. We study a homogeneous and stochastic environment: an agent is interested in the item possessed by another agent with probability p, independently for all pairs of agents. We consider two settings with respect to the types of allowed exchanges: a) Only two-way cycles, in which two agents swap their items, b) Two or three-way cycles. The goal of the platform is to minimize the average waiting time of an agent. Somewhat surprisingly, we find that in each of these settings, a policy that conducts exchanges in a greedy fashion is near optimal, among a large class of policies that includes batching policies. Further, we find that for small p, allowing three-cycles can greatly improve the waiting time over the two-cycles only setting. Specifically, we find that a greedy policy achieves an average waiting time of Θ(1/ p 2 ) in setting a), and Θ(1/ p 3/2 ) in setting b). Thus, a platform can achieve the smallest waiting times by using a greedy policy, and by facilitating three cycles, if possible. Our findings are consistent with empirical and computational observations which compare batching policies in the context of kidney exchange programs.

AAAI Conference 2013 Conference Paper

Equilibria of Online Scheduling Algorithms

• Itai Ashlagi
• Brendan Lucier
• Moshe Tennenholtz

We describe a model for competitive online scheduling algorithms. Two servers, each with a single observable queue, compete for customers. Upon arrival, each customer strategically chooses the queue with minimal expected wait time. Each scheduler wishes to maximize its number of customers, and can strategically select which scheduling algorithm, such as First-Come-First-Served (FCFS), to use for its queue. This induces a game played by the servers and the customers. We consider a non-Bayesian setting, where servers and customers play to maximize worst-case payoffs. We show that there is a unique subgame perfect safety-level equilibrium and we describe the associated scheduling algorithm (which is not FCFS). The uniqueness result holds for both randomized and deterministic algorithms, with a different equilibrium algorithm in each case. When the goal of the servers is to minimize competitive ratio, we prove that it is an equilibrium for each server to apply FCFS: each server obtains the optimal competitive ratio of 2.

AAAI Conference 2010 Conference Paper

Competing Schedulers

• Itai Ashlagi
• Moshe Tennenholtz
• Aviv Zohar

Previous work on machine scheduling has considered the case of agents who control the scheduled jobs and attempt to minimize their own completion time. We argue that in cloud and grid computing settings, different machines cannot be considered to be fully cooperative as they may belong to competing economic entities, and that agents can easily move their jobs between competing providers. We therefore consider a setting in which the machines are also controlled by selfish agents, and attempt to maximize their own gains by strategically selecting their scheduling policy. We analyze the equilibria that arise due to competition in this 2-sided setting. In particular, not only do we require that the jobs will be in equilibrium with one another, but also that the schedulers’ policies will be in equilibrium. We also consider different mixtures of classic deterministic scheduling policies and random scheduling policies.

AIJ Journal 2009 Journal Article

Two-terminal routing games with unknown active players

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

We analyze 2-terminal routing games with linear cost functions and with unknown number of active players. We deal with both splittable and unsplittable models. We prove the existence and uniqueness of a symmetric safety-level equilibrium in such games and show that in many cases every player benefits from the common ignorance about the number of players. Furthermore, we prove new theorems on existence and uniqueness of equilibrium in 2-terminal convex routing games with complete information.

AAAI Conference 2007 Conference Paper

Learning Equilibrium in Resource Selection Games

• Itai Ashlagi

AAMAS Conference 2007 Conference Paper

Routing Games with an Unknown Set of Active Players

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

In many settings there exists a set of potential participants, but the set of participants who are actually active in the system, and in particular their number, is unknown. This topic has been first analyzed by Ashlagi, Monderer, and Tennenholtz [AMT] in the context of simple routing games, where the network consists of a set of parallel links, and the agents can not split their jobs among different paths. AMT used the model of pre-Bayesian games, and the concept of safetylevel equilibrium for the analysis of these games. In this paper we extend the work by AMT. We deal with splitable routing games, where each player can split his job among paths in a given network. In this context we generalize the analysis to all two-node networks, in which paths may intersect in unrestricted manner. We characterize the relationships between the number of potential participants and the number of active participants under which ignorance is beneficial to each of the active participants.

AAMAS Conference 2006 Conference Paper

Resource Selection Games with Unknown Number of Players

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

UAI Conference 2006 Conference Paper

Robust Learning Equilibrium

• Itai Ashlagi
• Moshe Tennenholtz
• Dov Monderer

We introduce robust learning equilibrium. The idea of learning equilibrium is that learning algorithms in multi-agent systems should themselves be in equilibrium rather than only lead to equilibrium. That is, learning equilibrium is immune to strategic deviations: Every agent is better off using its prescribed learning algorithm, if all other agents follow their algorithms, regardless of the unknown state of the environment. However, a learning equilibrium may not be immune to non strategic mistakes. For example, if for a certain period of time there is a failure in the monitoring devices (e.g., the correct input does not reach the agents), then it may not be in equilibrium to follow the algorithm after the devices are corrected. A robust learning equilibrium is immune also to such non-strategic mistakes. The existence of (robust) learning equilibrium is especially challenging when the monitoring devices are 'weak'. That is, the information available to each agent at each stage is limited. We initiate a study of robust learning equilibrium with general monitoring structure and apply it to the context of auctions. We prove the existence of robust learning equilibrium in repeated first-price auctions, and discuss its properties.

UAI Conference 2005 Conference Paper

On the Value of Correlation

• Itai Ashlagi
• Dov Monderer
• Moshe Tennenholtz

Correlated equilibrium (Aumann, 1974) generalizes Nash equilibrium to allow correlation devices. Aumann showed an example of a game, and of a correlated equilibrium in this game, in which the agents' surplus (expected sum of payo s) is greater than their surplus in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias & Papadimitriou, 1999;Papadimitriou, 2001) this suggests the study of two major measures for the value of correlation in a game with non-negative payoffs: 1. The ratio between the maximal surplus obtained in a correlated equilibrium to the maximal surplus obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal surplus to the maximal surplus obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games (Rosenthal,1973), a class of games that received a lot of attention in the recent literature.