Strategic Behavior in Two-sided Matching Markets with Prediction-enhanced Preference-formation
Authors: Stefania Ionescu
Yuhao Du
Kenneth Joseph
Aniko Hannak
Venue: NeurIPS 2023 poster (2023)
Keywords: matching markets
strategic behaviour
ML-based forecasting
recommender systems
adversarial attacks
agent-based modelling

Abstract: Two-sided matching markets have long existed to pair agents in the absence of regulated exchanges.  A common example is school choice, where a matching mechanism uses student and school preferences to assign students to schools. In such settings, forming preferences is both difficult and critical. Prior work has suggested various prediction mechanisms that help agents make decisions about their preferences. Although often deployed together, these matching and prediction mechanisms are almost always analyzed separately. The present work shows that at the intersection of the two lies a previously unexplored type of strategic behavior: agents returning to the market (e.g., schools) can attack future predictions by interacting short-term non-optimally with their matches. Here, we first introduce this type of strategic behavior, which we call an adversarial interaction attack. Next, we construct a formal economic model that captures the feedback loop between prediction mechanisms designed to assist agents and the matching mechanism used to pair them. Finally, in a simplified setting, we prove that returning agents can benefit from using adversarial interaction attacks and gain progressively more as the trust in and accuracy of predictions increases. We also show that this attack increases inequality in the student population.

Strategic Behavior in Two-sided Matching Markets with Recommendation-enhanccee Preference-formation
Stefania Ionescu Department of Informatics University of Zürich Andreasstr. 15 Zürich, 8050 ionescu@ifi uzh.
Yuhao Du Department of CS and Engineering
University Buffalo Buffalo NY, 14260
yuhaodu@buffalo. edu
Kenneth Joseph
Anikó Hannák
Department of CS and Engineering
Department of Informatics University Zürich Andreasstr. 15, Zürich, 8050 hannak@ifi uzh ch
University at Buffalo Buffalo NY, 14260
xjoseph@buffalo.cm edu
Abstract
Two-sided matching markets have long existed to pair agents the absence regulated exchanges. A common example is school choice, where matching mechanism uses student and school preferences to assign students to schools. such settings, forming preferences is both difficult and critical. Prior work has suggested various prediction mechanisms that help agents make decisions about their preferences. Although often deployed together, these matching and prediction mechanisms are almost always analyzed separately. The present work shows that at the intersection of the lies previously unexplored type of strategic behavior: agents returning to the market (e.g., schools) can attack future predictions by interacting short-term non-optimally with their matches. Here, we first introduce this type of strategic behavior, which we call an adversarial interaction attack. Next, we construct formal economic model that captures the feedback loop between prediction mechanisms designed to assist agents and the matching mechanism used pair them. Finally, in a simplified setting, we prove that returning agents can benefit from using adversarial interaction attacks and gain progressively more the trust in and accuracy of predictions increases. We also show that this attack increases inequality in the student population.
Introduction
In two-sided matching markets, agents are partitioned in two disjoint sets (e.g., students and schools) and want to get paired with agents from the other set for future bilateral exchanges (e.g., student learns at a school and the school provides instruction to the student) [26). In such markets, agents typically report their preferences over potential matches and matching mechanism uses those preferences to produce an assigument, i.e. a pairing between agents. Because forming one's preference is hard, agents benefit from external recommendations.
Since predictive models have become increasingly accessible, reliable, and trusted 117] they also became more frequently used to inform sefference-formation in matching markets. One such example school choice. After the introduction of the No Child Left Behind Act, in 2001, students from low- performing schools were allowed to transfer to better- setter-performing schools. However, initially, only few students took advantage of this opportunity, partly because it hard for parents assess which
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

school would improve their child's performance. In 2008, content-based recommender system called SmariChoice was deployed for focus group participants; its goal was help parents with the assessment by identifying the best schools based on predictions on the student's 's development at that school [27]- Another example is in refugee assignment, where refugees are matched with locations. Here, the preferences of locations over refugees are given by machine learning (ML. model that predicts the level of integration success (e.g., measured by the probability of employment within 90 days) of an individual at a given location [5]. 'The Swiss government has recently implemented randomized test to examine the performance of data-driven algorithms for outcome- nateo assignment"
3. Similar approaches have been developed for other application domains such as labor market [24 and course allocation [5].
These examples show that using predictive models to inform the preferences of agents in matching markets is not a problem of the future, but rather one of the present. However, prior work has evaluated potential vulnerabilities separately in the matching mechanisms [00 7 2 and prediction-
based recommendations [3 21. When considering the matching algorithm, one usually analyzes the incentives of individuals by. for example, asking whether the mechanism is strategy-proof (i.e. whether agents have an incentive to misreport their preferences). Similarly, there is broad literature on attacks recommendations [8 2 [I]] and predictive models which might face poisoning or evasion attacks (i.e. attacks which either inject fake data to trigger an unfaithful model or perturb the testing input trigger misclassification) [1].
In this paper, we argue that, in addition considering vulnerabilities of the matching and prediction mechanisms independently, it is critical to also look at vulnerabilities in systems that combine them together. Specifically, we consider systems similar to those described above, i.e, where: (a) agents of one side (the returning side) come back to the matching market in subsequent rounds (e.g., schools), (b) agents have post-matching objectives (e.g., schools want to be prestigious and minimize their cost), (c) agents on the returning side have the power to shape the quality of the interaction with those they are assigned to via post-matching decisions (e.g, schools can increase the performance of students through extra-curricular preparations or integration programs), and (d) these interactions impact outcomes for the non-returning side, which in turn influence future predictions (e.g.. predictions based on the outcomes of past students change the preferences of current students).
By making the feedhack loop between the matching and prediction mechanisms explicit, we uncover a new type of strategic behavior: the returning side can attack the system by changing their interactions with their matches. Even though in the short-run might be beneficial for both matched parties to have the best possible interaction (e.g.. both locations and refugees want refugees to be employed as soon as possible), the returning side (e.g., locations) might want to sacrifice their utility in the current round for different future predictions (e.g.. locations might postpone hiring difficult-to-integre so they will not be allocated similar refugees in the future). We call such post-matching strategic selavvorrwherr agents sacrifice their short-term utility to trigger different long-term predictions adversarial interaction attacks. Similarly, we call a system where agents cannot benefit from such attacks interaction-pie prooff.
refugees
In this paper, we first build a formal model for repeated two-sided matching markets with prediction- enhanced preference formation. Second, we use this model to define adversarial interaction attacks and the optimization problem faced by returning agents. Finally, we create a simplified setting (in the main text, and an agent-based model in the appendix) to analyze when and by how much agents can benefit from interaction-stratggl behavior. We show that, for some systems, (a) the returning agents have an incentive to use adversarial interaction attacks, (b) the utility gains obtained through such attacks increase as predictions become more accurate and trusted, (c) once a returning agent attacks, others have an incentive to implement more severe attacks, and (d) the non-returning agents are unevenly negatively affected by such attacks.
2 Other Related Work
Adversarial Attacks in Reconmendations. From past literature in recommender systems (RS), the most similar adversarial attacks to the one we consider are shelling attacks (i.e., attacks where fake users and ratings are created to trigger different future recommendations). These works mainly focused on crafting adversarial examples 23 21). Differently, Christakopoulou and Banerjee [8] analyzed shelling attacks from machine learning and optimization perspective by building on the

---

literature on poisoning attacks in classification tasks [16], and formulating the problem as two-player general-sum game between an RS and an Adversarial Attacker.
However, our setting has some key differences. First, the returning agents usually cannot inject fake users (e.g., because there are public records of which students attended which schools). Instead, agents attack by adapting their actions. This distinction has both social implications (the non-returning agents experience a different outcome while the attack takes place) and economic implications (the returning agent implementing the attack sacrifices their short-term utility). Second, the existence of capacity constraints entails a rivalry for available seats (if a student is accepted at a school then another student is not accepted, and vice versa). Consequently, when attacking for being matched to a specific (type of) agent, there are two intents do so: (a) rank higher in the preferences of agents who are of interest, and (b) rank lower in the preferences of agents who are not of interest. The latter different from classical recommender system applications and is increasingly important when the returning agents cannot fully and freely express their preferences. Third, also because of competition, agents do not decide to whom they are allocated (not all students can get a place to their most preferred school); instead, they report their preferences to a matching market, which produces an assignment. Therefore, attacks this setting are not only efficient if they change the most preferred option of a non-returning agent, but also if they change the ordering of options lower in the preference ranking.
Strategic Behavior in Matching Markets. As noted above, matching markets (MM) are widely used to pair agents based on their reported preferences: in such settings agents can behave strategically by. e.g., misreporting their preferences. Prior work shows that users find and implement such profitable manipulations which leads to congestion and inefficiencies 7 Thus, durateg-prroofness
a common desiderata in real-world application domains; e.g., in the Boston school choice system, this triggered a transition from the Boston to the Deferred Acceptance mechanism []. In this paper we analyse it is not an attack on the mechanism
atrateic-interaactng, which differs from strategic-reporting alone, but rather on its combination with the prediction-basee preference- formatton process. When proposing predictive modelling for refugee assignment, Bansak et al. [5] distinguished between the modeling phase (when the predictive model is built) and the matching phase (when the assignment is produced). We generalise and extend this framework by also considering the phase when the paired agents interact and new data is produced. Moreover, we build on prior litcrature in economics when creating the model (for formalising the matching phase (25 and when analyzing the system (for unilateral deviations and Nash equilibria (22))
Using Simulations to Understand Long-Term Effects. The machine learning community has seen an increasing use of simulation to study the interaction between users and recommendations, RecSim provides environment that naturally supports sequential interaction with users. Mansoury et al. proposed a method for simulating interactions between users and RSs to study the impact of the resulting feedback loop the popularity bias amplification. Bountouridis et al. [6] built framework called SIREN to study how RSs will impact users' news consumption preference in the long term. Similarly, scholarship within MM used simulations to understand the effect of different design choices. Erdil and Ergin 10 developed an experiment in order to compare the performance of two alternative matching algorithms in the school choice setting. In the context of online dating, Ionescu et al. 13 proposed an ageet-based model (ABM) to test the effects of different platform interventions in reducing racial homogamy, At the intersection of ML and two-sided markets, Malgonde al. 18 built an ABM to test the effects of introducing a two-sided RS within a complex adaptive business system. Similar to this previous work, we create simplified setting to model complex socio-technical system. We use both theoretical analysis (in the main text) and simulations (in the appendix- to confirm that the results carry to more realistic settings). We, however, have a different goal: to understand how the characteristics of the market affect the incentives to use and effects of using adversarial interaction attacks.
12
3 Problem Formulation
Our model for the system is composed of three phases: (a) modeling, (b) matching, and (c) interacting. The modeling stage builds predictive model that forecasts the interaction outcome of two agents if matched. During the matching phase, the non-returning agents use this model to inform their
3

---

Modelling
Interacting
Attributes agents;
Data
Interactions
relurning wou-returning
Matching
Assignment
Forecasting Procedure
Non-returning agents' preforences
Matching Procedure
Expected interaction stccess
Returning agents'
preferences
Figure I: Overview of the interaction between different components of system with a forecasting- based preference formation and matching procedure. The interaction predictions can be used to inform the preferences of a. the non-returning side of the market (e.g. students), or the returning side of the market (e.g. locations).
preferences next, matching algorithm pairs each agent in the non-returning side of the market (student) with an agent the returning side of the market. Finally, the interacting stage, the agents already paired according to the assignment obtained during matching interact with each other (students attend the classes at their assigned school). This interaction will produce an outcome (e.g.. SAT scores of students) that is kept record and used to inform future predictions. The entire system then repeats in a series of rounds with new non-returning agents each time, but with the same returning agents. Figure I shows overview of all the phases and the interactions between them. In the remainder of this section, we formalise each the stages and present the decision problem faced by the returning agents.
3.1 The Matching Stage
We start with the notation for the agents. Let X be the set of non-returning agents be matched time (round) f, and Y be the set of returning agents. Moreover, we denote by > the preference of the non-returning agent
X' over the returning agents, Y. In other words, = is ranking Y. Similarly, >y is the preference of E Y over X. These preferences could be either unweighted (i.e., the agent only knows the ordering of their options) weighted (i.e., the agent also knows how much more they prefer each potential match over another). the weighted case, the preference >a has an associated weight function W. Y R mapping each option y the strength æ wants be matched to
A matching is pairing of non-returning agents returning ones, i.c., 1 X [fL). Here, u(x) = signifies that x remained unassigned More generally, a matching procedure (or allocation rule) maps the preferences of agents to matching. In other words, matching procedure M is function mapping every ((>xlzex, (>glvey) to a matching μ. We denote by p the matching in round i.e. μ² a(((>=))e f> ))
3.2
The Interacting Stage
After being matched, the agents interact. For every agent pair (z. y). there is a set of possible outcomes, depending on their interaction. Since æ not returning to the market, we assume they will always prefer the best outcome for them. Therefore, the set of possible outcomes depends on actions of the returning agent, 3y. We denote the set of outcomes could choose from when interacting with by (z)..
Depending on the resulting outcome, each agent has some value, cost, and utility. If y chooses outcome when interacting with we denote by (x) their value, by cg (x:) their cost, and by
Alternatively, the predictive model could be used to inform the preferences of the returning agents. For simplicity, we chose not to extend our model to capture this alternative the main text and only include in appendix. Moreaver, here we use school choice as a running example; see the appendix for other examples.
"In simplified scenarios where each returning agent (c.g., due capacity constraints), we can express the matching function as function from More precisely, μ4(μ) x when x is matched with y and 1 if y remains unmatched. Since this refers to the same pairing, we avoid introducing additional notation and will also use μ for the mapping of returning to non-returning agents in such simplified cases.
be matched to at most non-returning agent
X U {1].

---

2g(2) = -1(2)) -j(2) their utility. We use the analogous notation for æ. We also make the simplifying assumptions that (a) the value is symmetric, i.c. ez(()) = en and (b) the cost of the non-returning side is null, i.e. that (v) = O and wg(v) = (z)
As an example, a school might have the choice set 02(2) = {80, ] since it could either invest in extracurriular preparation for (case in which scores around 100% state-administered tests) or not to invest (and I scores around 80%). If school incurs a fixed cost of 5 when preparing a student, then for the outcome 80 both the student and the school have utility of 80 while for the outcome 100 the student has a utility of 100 while the school subtracts the cost from the value, and thus has utility of 100 5 95.
3.3 The Modeling Stage
The prediction model at time t is informed by the history of interactions until that time. We denote the history up to time by H' = {(0, o, l')ly - n² (x)), interacted with æ at time 1' < I with outcome 0g(x)) (x)). The history thus records the agents matched far, together with the time and outcome of their interaction.
The prediction algorithm uses the history an input. Its output is hypothesis, i.c., function which maps a pair of agents to their expected interaction outcome. We use the usual statistical framework in learning theory and denote the hypothesis by parameterized function ho, X x Y IR. The prediction is thus based on the parameter 0g at time i, which is obtained by solving the optimization problem 8, arg ming L(0,, H. Here, L is the loss function.
The hypothesis predicts values for a potential interaction between a non-returning agent, x, and all the returning agents. Therefore, it induces a preference weight function and ranking over the returning agents. Formally, hg, (z. Y + R gives a weighted preference over Y. which we denote by > By exposing agent to this ranking, their final preference might change. To capture this change, each agent x has a prediction integration function, hū, that transforms a (weighted) preference of æ into a new preference, >'., using the hypothesis-base ranking, h
To continue the previous example, let us assume that student x initially believes schools A and B are equally good for them, i.e. >r is A ~ B with, say, a weight function (y((A) (B) = 80. Assume the hypothesis predicts ho, (ar, A) 100 and ho, (2, B) 80, which corresponds to the ranking A >/ B. The exposure of student to this prediction-based ranking changes their preference to new one which lies between their original opinion, >. and the suggested one, > For instance, the new preference could correspond to the weight profile obtained by averaging the original and the suggested ones. Then, the new preference, hi (>a) => 21 has the weight function w/ (A) 90 and w/z (B) 80 thus ranking A > B.
3.4 The Decision Problem of Returning Agents
The decision problem faced by the returning agents when they choose how to interact with their matches can be formalised as dynamic programming task over the infinite horizon. They choose the action that maximizes the sum of their utility now plus the expected discounted utility in the future if they take that action. Using the notation introduced in the previous section, the maximum utility a returning agent, y, from time onward is
Uy (1²)
(ny (1'(w) + 3E (U, (n 1(x 1,, oEO,(u (1))
max
(1)
where we make the standard assumption in economics that agents steeply discount future utility and denote the discount factor by 3. The optimal strategy of returning agent is to take, at every round, the interaction leading to the outcome that maximizes the
utility.
The straightforward interaction strategy is to always choose the outcome maximising the 1-step utility. Le. choose arg mar, (n (ug (z)). When a returning agent uses this strategy, we say interacts truthfully. Naturally, in general, the optimal strategy needs not be the truthful one. The resulting gap leaves space for strategic interactions. We refer to strategies involving non-truthful
"To achieve this succinet problem formulation, we made some simplifying assumptions and notations (details in Subsection 2.3 from the appendix).
5

---

interactions as adversarial interaction attacks and call the systems in which agents cannot benefit from such attacks interaction proof.
To give two simple examples, a system in which the preference formation is solely based on the attributes of schools (e.g., how far away the school is, what subjects are taught, what are the final examinations) and past data on interactions is not used would be interaction-proof. Similarly, a system that only uses the history of interactions before announcing the decision to introduce the ML-algorithm would also be interaction-prodt expected utility is constant with respect to the choice of interaction. Thus, the utility from now onward is maximized by choosing the outcome giving the highest utility in the current round.
This is because, in both of these cases, the future
4 Simplified Setting
While useful for formalizing the definition of adversarial interaction attacks within variety of contexts, the problem formulation proposed in the previous section is too general to allow for a tractable and insightful numerical analysis. Thus, we operationalize the framework by creating simplified model. The main goal of such model is to support both proving that returning agents can benefit from adversarial interaction attacks and understanding why and when this could be the case. The remainder of this section introduces the simplified model. To improve readability, we refer to returning agents as schools and non-returning agents as students. However, the model could be read through the lens of alternative applications (c.g., locations and refugees).
Interaction. We assume that there are two schools, Y (), and two types of students: cheap, C, and expensive, E. Moreover, each school has the capacity to accept only one student. Any interaction between school and student leads to outcome between zero and one (i.e., (x) = [0, 1] Vy E Y E {C,E)) This outcome matches its value: (x) = o. However, schools have different costs for given outcome depending on the type of student. More precisely, cheap students require negligible specialized assistance, thus having a zero cost for any outcome, i.c. og (C) 0, while expensive students require a cost of three quarters of the value of the chosen outcome, i.e. cy (E)= 3/4 o. Thus, the resulting utility for school y E Y is given by rC(C") = and ug(
o/4. 4. Note that this always leads non-negative utilities. To account for cases when returning agents incur large integration costs from accepting any match (e.g.. for refugee assignment or the allocation of under-performing students (27 5) also analyze the scenario of negative utilities. We do so by offsetting the cost by a constant q > 1, thus giving uC(C") o q and (B) = 0/4 - q. Unless otherwise specified, we consider the non-negative model for utilities (i.e.. without the offsets).
For simplicity. we assume students have a uniform random chance of preferring each school, and predictions are based on the outcome of the most recent interaction of the same-type student at the school. More precisely, a student x will have a 1/2 chance of having the preference profile A >ー B and 1 1/2 chance of having the preference profile B >> A. For the same student x, the prediction algorithm gives to each school y weight wh (2) equal to the last outcome of same-type student at school y based on the history of interactions" For example, a student type E will start with a 50% chance of thinking that A > E B; if, according to the history, the most recent student of type E who attended school A had a worse outcome than the most recent student of type E who attended school B then accurate prediction- basee hypothesis will recommend B > A.
Preferences.
Accuracy and trust. The impact of predictions depends on their accuracy and trust, two metrics on which system designers usually try to improve on 20 9. To account for this, we model the accuracy via a parameter a, which captures the probability that the recommendation the one given by the most recent outcome with same-type student. In the example above, the hypothesis will generate B >/ A with probability a and the reversed ranking (i.e., A A B) with probability 1 1 a. Similarly, the trust of students in the recommendations is given by 0. which captures the probability that students adopt the recommended ranking as opposed to maintaining their original preference over the alternatives (i.e., >/ is > with probability 9 and >~ with probability 1 - 0). The accuracy and trust are just extensions to help understand the changes in incentives to attack as the power of our
"In the absence of historical interactions between a type of student and school we assume the outcome was 1. We believe this is the most sensible assumption as prior to introducing a prediction mechanism to inform preferences there is limited impact of past outcomes on future assignments. As result, schools would likely optimize the 1-step utility and interact truthfully.

---

prediction models improves. Since the final goal of predictions is to be accurate and trustworthy, for most of the analysis we will assume both a and 0 are 1.
Matching. Matching mechanisms are complex procedures that, based on the preferences of all agents, assign students schools. Serial dictatorship, Boston, and deferred acceptance are all examples of such mechanisms which were deployed in the school choice setting (see the appendix for the definition of each). While, in theory, schools have the chance of expressing their preferences, in practice, these preferences are often given by a lottery with some priority ordering (e.g. students with siblings at the same school have a higher priority at that school) [. Thus, the true preferences of schools usually have a limited impact on the final allocation. For the theoretical analysis, we consider random serial dictatorship (RSD), which (1) picks random ordering of students and (2) assigns, in turn (according to this ordering), each student to the most preferred school that still has available places. the appendix, we use simulations to investigate the effects of using alternative mechanisms.
Analysis. To see whether schools have an incentive to interact strategically, we compare the utility of one school, y, under two scenarios: (a) when both schools interact truthfully (i.e., pick outcome for their interaction with all students) and (b) when interacts strategically at some level (i.e., picks outcome where / (0, 1] for its interaction with expensive students) while the other school interacts truthfully. If the expected utility of increases when it unilaterally interacts strategically, then y has an incentive deviate from interacting truthfully and adopt such a strategy. Using a came-theerette framework, we say that schools are agents which can choose actions corresponding to adversarial attacks at levels E {0, 1/L,2/L, always chooses the outcome 1 when interacting with expensive students and the outcome 1 with cheap students. Thus, = 0 represents a truthful interaction. With respect to this set of actions, each school has best response (i.e., an action that gives it the highest utility) given the actions of others. both schools play the best response to the other's 's actions and, thus, none of them can change their level of attack to achieve a higher expected utility, we say the action profile is Nash Equilibrium.
1 | an attack at level / means that the school
5 Results
The results section starts with three subsections. each titled based on its main takeaway. The first two focus on results under the assumption that prediction models have perfect levels of trust and accuracy. while the third subsection will investigate incentives to attack as those levels change. Since proofs are mostly mathematical formalizations of intuitive behavior, we reserve them for the appendix and solely provide the intuition within the main text. To position the results within the broader context, each of these three subsections ends with a paragraph discussing the implications of its results. We also include final subsection explaining why we opted for simple model and analysis and how it could be extended.
5.1 Not all systems are interaction-proof
We first consider scenario where, at each timestep. there is one student of cach type (i.e. X {C, E}) and schools put sufficient weight on the future expected utility (i.c., 3 is sufficiently large). In such a case, Theorem states that schools can benefit from implementing an adversarial interaction attack. The proof (see appendix) compares the expected utilities under truthful and strategic interactions and shows that attack at any level I + produces increase in expected discounted utility when 3 > 2/3.
Theorem Assume X' = (C, E). schools are sufficiently forward-looking (3 > 2/3), and predic- tions have perfect trust and accuracy (i.e., == 0 1). Then, schools have incentive to deviate from truthullyy interacting and implement adversarial interaction attacks.
It is important to note that this takeaway is heavily based on the composition of the market (i.e., the number and type of students available). For example, Theorem 2 shows that when there are only expensive students, a strategy profile where all schools interact truthfully is a Nash Equilibrium. Similarly, Theorem shows that, even when students induce a negative utility for the schools, as long
'Here L is an arbitrary large natural number. This makes the action space discrete, thus capturing the often- used assumption that agents do not have infinitesimal control over the outcomes. Instead, there is an atomic unit of change (1/L L in our case) they can make.
7

---

as they are of the same type and sufficiently many to guarantee that each school will be allocated a student, then schools still do not have an incentive implement adversarial interaction attacks. The full proofs are included in the appendix. They formalize the intuition that, in such scenarios, schools either (a) prefer being allocated a student remaining unmatched or (b) have the same type of allocated student disregarding their interaction outcomes.
Theorem 2
Assume predictions have perfect trust and accuracy (i.e., = == 1). When there are only expensive students, a strategy profile where both schools interact truthfully is a Nash Equilibrium.
Theorem 3
Assume predictions have perfect trust and accuracy (i.e., = 0 = 1). When all students induce the same negative utility for schools, and there are at least two students, a strategy profile where both schools interact truthfulyy is a Nash Equilibrium.
Yet, there are also scenarios when forward-looking schools have incentive interact strategically with all available students, disregarding their type. One such instance is when there is one student giving schools a negative utility for any choice of action. This example is covered by Theorem 4 The main intuition behind the proof is that the attacking school has the opportunity to avoid being allocated any student, which gives it a better utility than being allocated one. If the weight given to future gains (i.e., 39) is sufficiently large, then schools prefer to decrease their utility in the current round in order to maximize the chance of having null utility in subsequent rounds.
Theorem Assume predictions have perfect trust and accuracy (i.e., a - 1). If there is only one student giving schools a negative utility for any outcome and schools are sufficiently forward-looking then schools have an incentive to deviate from truthfully interacting and implement adversarial interaction attacks.
These toy examples prove that it is not sufficient to analyze the matching mechanism in isolation from the cefferencce-ormatiion process. In particular, Roth (25) proved that RSD is a strategy- proof mechanism for both sides. However, our theorems show that system containing the same mechanism is not necessarily interaction-proof, thus challenging the desirability of implementing such mechanism.
5.2
Once school implements an attack, the other school has an incentive to respond with more severe attacks
The prior analysis showed that, in some setups, schools have an incentive to interact strategically. It remains, however, unclear how school would best respond to adversarial attack of the other school. Theorem (e)oremm]ssttess the best response of a school is to attack at the smallest level that still higher than the current level of attack of the other school. The proof (see appendix) formalizes the intuition that schools want an attack that sacrifices their short-term utility the least, while still triggering the prediction mechanism not recommend them expensive students.
Theorem Assume predictions have perfect trust and accuracy (i.e., a == = {C, E and schools are sufficiently forward- (B > 4/5), the best response of school A for strategy B of attacking at a level l attack at level min 1 + 1/L..
1). When X
This has a few important implications. First, it suggests that schools would likely not attack at high levels directly, thus having limited impact on the welfare of expensive students. However, little by little, schools would attack at increasingly higher levels until both schools choose an outcome of 0 (i.e., level of attack 1) for expensive students. Corollary [ which is an immediate consequence of Theorem 5 states that the resulting strategy profile when both schools attack at a maximum level is Nash Equilibrium. This equilibrium is, however, undesirable for both schools, as it is Pareto dominated by the initial choice of actions; i.c., if both schools interact truthfully, then both of their expected utilities are higher than when the schools attack at the maximum level.
Corollary Assume predictions have perfect trust and accurucy (i.e., a 0= When X {C, E} and schools are sufficiently howard-looking the stralegy profile where both schools use adversarial interaction attacks at the highest level (iee,, 1 = 1) is Nash Equilibrium. However, this is Pareto dominated by the strategy profile where all schools interact truthfully.
8

---

Altogether, these results show the system resulting from introducing prediction-base based recommenda- tions to inform preferences within a matching market could encourage returning agents to engage in higher and higher levels of adversarial interaction attacks. This behavior ultimately leads to an equilibrium that is detrimental to all agents. For our example, lowered the welfare (i.e., the average value of outcomes) of expensive students and reduced the expected discounted utilities of both schools. At a societal level, such a system could thus result increased inequalities among the student population. Therefore, there is need for system with prediction and matching mechanisms that together lead to different interaction incentives for returning agents, As illustrated by the next two subsections, two potential solutions are to lower the impact of outcome- predictions or use matching mechanisms that let schools express their true preferences.
5.3 Increases in trust in and accuracy of recommendations lead to higher discounted expected utilities under adversarial interaction attacks
Finally, we acknowledge the general trend of increasing the accuracy of and trust in prediction 20
Before incorporating prediction mechanisms, prior outcomes have a limited impact on preferences (e.g., from anecdotal experiences of isolated past students, or advice from counselors (27]). When predictions made algorithmically, there is higher potential for personalizing them; however, due to the high level of individuality, algorithms struggle to produce accurate predictions. This affects both the trust of students in recommendations and leads challenge for designers improve accuracy. Theorem shows that improving these parameters affects the impact of adversarial interaction attacks. The proof is based on the following observation: the expected gain in utility from using a strategic interaction is strictly increasing with both trust and accuracy.
Theorem When X = [CC E), the expected utility of a school using an adversarial interaction attack is continuous function that increases monotonously in both accuracy (a)) and trust (0).
Naturally, when predictions are disregarded by students (i.e., 0 = 0) or are random (i.e., 0.5) it best for schools to interact truthfully- - see Theorem 7 When increasing the accuracy and trust, the utility under attacks increases (by Theorem 6 until adversarial attacks constitute best response (as shown by Theorem []] This means that, depending on the specifics of the system, such as the parameter B, for any given level of trust, there exists some maximum value of where truthful interaction is still the optimal strategy. The proof of this statement can be formalized using the intermediate value theorem and the three aforementioned results.
Theorem 7 When X = (C,E), the truthful strategy profile is a Nash Equilibrium under predictions with 50% accuracy (a = 0.5) or null levels of trust (8- = 0)
In short, the above analysis shows that, even adversarial interaction attacks do not currently increase the expected utility, they might if we introduce prediction mechanisms or improve their trust and accuracy. This underlines the importance of re-evaluating incentives when considering such changes. Moreover, it shows that limiting the impact of outcome-based predictions could, in turn, limit the gains of returning agents from interacting strategically.
5.4 Discussion
Our paper (1) created an economic model to allow for general definition of adversarial interaction attacks and (2) simplified the setting to prove these attacks could indeed be attractive for returning agents. We underline that our goal was to illustrate the emerging feedback loop and show the importance of considering it when prediction algorithms inform preferences. Thus, we favored simple model together with basic theoretical analysis. As such, the current analysis can be extended in various ways, such as by using more realistic prediction and matching mechanisms (MM), accounting for more diverse agents, defining and analyzing incentives for undetectable interaction attacks, and extending the space of strategies.
Perhaps the main question for future work is whether adversarial interaction attacks remain attractive in more realistic settings. As first step to address this question, we extended the simple setting presented above to more realistic agent-based model. In particular, this model uses k-Nearest Neighbors 444 to predict future outcomes, compares multiple MM (including Deferred Acceptance and Boston), and increases the number of agents. The simulation results both confirm the takeaways

---

from the theoretical analysis and provide some additional insight. First, they show that different MM are more susceptible to adversarial interaction attacks depending on the distribution of students with respect to their attributes. Second, they suggest that allowing schools to express their true preferences over students (instead of using lotteries) can, in some cases, eliminate the incentives of using adversarial attacks. The exception is when utilities are negative and there are fewer students than places at schools. Third, it illustrates the inequality between students: as suggested by the theoretical results, the welfare of students decreases when schools interact strategically, and this decrease is mostly borne by the expensive students. We provide details on the agent-based model and visualizations for the simulation results within the appendix; to ease reproducibility. the code is available on GitHut
Conclusion
Predictive models are increasingly used inform preference-formatiee formation in matching markets (MM). However, the robustness of the prediction mechanism under adversarial attacks and of MMs under strategic behavior are usually investigated separately. In the present work, we extend existing models by including the interacting stage in which agents, matched by the MM, interact with each other, thus generating new training data. Doing so makes the feedback loop between the prediction model and the MM explicit and uncovers a new type of strategic behavior: the agents that return to the market in subsequent rounds can deviate from the most profitable interactions in the current round in order to attack the predictions and matchings of future rounds.
In a simplified setting, we prove that returning agents could indeed have an incentive to interact strategically. Doing so is more effective as predictions get better in terms of accuracy (and trust). In aligmment with previous work on recommendations [20], this suggests we should look beyond accuracy when designing prediction mechanisms for such systems, Moreover, we find that, when returning agents choose to adopt this attack, it has perverse consequences for the utility of all agents. In particular, it both lowers the overall utility and increases inequality among non-returning agents (students). These issues reflect how strategic behaviors of social institutions (schools) cause social inequalities independent of individual potential. Altogether, this work indicates that both aspects of the matching and prediction mechanisms are key developing robust systems and sets the framework for dialog between the ML and MM communities.
Acknowledgments and Disclosure of Funding
The authors would like to thank Vlad Gavrila, Atri Rudra, Nicolò Pagan, and the anonymous reviewers for their valuable feedback. KJ and YD gratefully acknowledge the support by the NSF award IIS1939579, with partial support from Amazon.
References
[1] Atila Abdulkadiroglu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez. 2006. Changing the Boston school choice mechanism: Strategy-proofnee as equal access. Mimeographed. Harvard University (2006).
[2] Atila Abdulkadiroglu and Tayfum Sönmez, 2003. School choice: A mechanism design approach. American economic review 93, 3 (2003), 729-747.
[3] Avidit Acharya, Kirk Bansak, and Jens Hainmueller. 2019.
Combining Outcome-Basee and Preference-Basee Matching: The g-Constrained Priority Mechanism. arXiv preprint arXiv:1902.0735: (2019).
[4] Raheela Asif, Agathe Merceron, and Mahmood K Pathan. 2014. performance at degree level: a case study. International Journal of Intelligent Systems and Applications 7, (2014), 49.
Predicting student academic
[5] Kirk Bansak, Jeremy Ferwerda, Jens Hainmueller, Andrea Dillon, Dominik Hangartner, Duncan Lawrence, and Jeremy Weinstein. 2018. Improving refugee integration through data-driven algorithmic assignment. Science 359, 6373 (2018), 325-329.
GGitHub link: https///ggttuoooooosccca//c/ccit
10

---

[6] Dimitrios Bountouridis, Jaron Harambam, Mykola Makhortykh. Mónica Marrero, Nava Tintarev. and Claudia Hauff. 2019. SIREN: A Simulation Framework for Understanding the Effects of Recommender Systems in Online News Environments, In Proceedings of the Conference on Fairness, Accountability, and Transparency (Atlanta, GA, USA) (FAT* '19). 150-159.
[7] Eric Budish and Estelle Cantillon. 2012. The multi-unit assignment problem: Theory and evidence from course allocation at Harvard. American Economic Review 102, 5 (2012), 2237-
71.
[8] Konstantina Christakopoulou and Arindam Banerjee. 2019. Adversarial attacks on an oblivious recommender. In Proceedings of the 13th ACM Conference Recommender Systems. 322-330.
[9] Berkeley J Dietvorst, Joseph P Simmons, and Cade Massey. 2018. Overcoming algorithm aver- sion: People will use imperfect algorithms if they can (even slightly) modify them. Management Science 64, (2018), 1155-1170.
[10] Aytek Erdil and Haluk Ergin. 2008. What's the matter with tie- breakink? Improving efficiency in school choice. American Economic Review 98, 3 (2008), 669-89.
[11] Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and J Doug Tygar. 2011. Adversarial machine learning. In Proceedings of the 4th ACM workshop on Security and artificial intelligence. 43-58.
[12] Eugene Ie, Chih wei Hsu, Martin Mladenov, Vihan Jain, Sanmit Narvekar, Jing Wang, Rui Wu, and Craig Boutilier. 2019. RecSim: A Configurable Simulation Platform for Recommender [cs.LG]
Systems. (2019). arXiv: 19999.94447
[13] Stefania Ionescu, Anikó Hannák, and Kenneth Joseph. 2021. An Agent-based Model Evaluate Interventions on Online Dating Platforms to Decrease Racial Homogamy. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency. 412-423.
[14] Dorina Kabakchieva, Kamelia Stefanova, and Valentin Kisimov. 2010. Analyzing university data for determining student profiles and predicting performance. In Educational Data Mining 2011.
[15] Kurniadi, Abdurachman, HLHS Warnars, and W Suparta. 2019. A proposed framework in an intelligent recommender system for the college student. In Journal of Physics: Conference Series, Vol. 1402. IOP Publishing, 066100.
[16] Bo Li, Yining Wang. Aarti Singh, and Yevgeniy Vorobeychik. 2016. Data poisoning attacks on factorization-base collaborative filtering. arXiv preprint arXiv:/6088 08/2 (2016).
[17] Jennifer M Logg, Julia A Minson, and Don A Moore. 2019. Algorithm appreciation: People prefer algorithmic to human judgment. Organizational Behavior and Human Decision Processes 151 (2019), 90-103.
[18] Onkar Malgonde, He Zhang, Balaji Padmanabhan, and Moez Limayem. 2020. TAMING COMPLEXITY IN SEARCH MATCHING: WWDDDDDDD RECOMMENDER SYSTEMS ON DIGITAL PLATFORMS. Mis Quarterly 44, (2020).
[19] Masoud Mansoury, Himan Abdollahpouri, Mykola Pechenizkiy, Bamshad Mobasher, and Robin Burke. 2020. Feedback Loop and Bias Amplification in Recommender Systems. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management (Virtual Event, Ireland) (CIKM '20). Association for Computing Machinery, New York, NY, USA, 2145-2148.
[20] Sean M McNee, John Riedl, and Joseph A Konstan. 2006. Being accurate is not enough: how accuracy metrics have hurt recommender systems. In CHI'06 extended abstracts on Human factors in computing systems. 1097-1101.
[21] Bamshad Mobasher, Robin Burke, Runa Bhaumik, and Chad Williams. 2007. Toward trust- worthy recommender systems: An analysis of attack models and algorithm robustness. ACM Transactions on Internet Technology (TOIT) 7, 4 (2007), 23-es.
[22] Roger B Myerson. 2013. Game theory. Harvard university press.
[23] Michael O'Mahony, Neil Hurley, Nicholas Kushmerick, and Guénolé Silvestre. 2004, Collab- orative recommendation: robustness analysis. ACM Transactions on Internet Technology (TOIT) 4, 4 (2004), 344-377.
11

---

[24] Ioannis Papartizos, B Barla Cambazoglu, and Aristides Gionis. 2011. Machine learned job recommendation. In Proceedings of the fifth ACM Conference on Recommender Systems. 325-
328.
[25] Alvin E Roth. 1982. The economics of matching: Stability and incentives. Mathematics of operations research 7, 4 (1982), 617-628.
[26] Alvin E Roth and Marilda Sotomayor. 1992. Two-sided matching, Handbook of game theory with economic applications (1992), 485-541.
[27] David C Wilson, Suzanne Leland, Kenneth Godwin, Andrew Baxter, Ashley Levy, Jamie Smart, Nadia Najjar, and Jayakrishnan Andaparambil. 2009. SmartChoice: An online recommender system to support low-income families in public school choice. A/ Magazine 30, (2009), 46-46.
12


Reviews:
[{"review_id": "qX0rKyUkEA", "reviewer": "Reviewer_Zyns", "summary": "This paper introduces a fresh perspective on attacks called *adversarial interaction attacks*, which can occur in markets that involve both a returning and a non-returning side. In such markets, agents' preferences are shaped by prediction mechanisms. While previous research has examined strategic behavior separately within the realms of matching and prediction mechanisms, the authors uncover the existence of these adversarial interaction attacks by explicitly considering the feedback loop between these mechanisms.\n\nTo investigate this phenomenon, the authors create a simplified setting and make several observations. They demonstrate that agents are driven by incentives to employ these attacks for personal gain. Moreover, the authors provide evidence that when returning agents adopt these attacks, it not only reduces the overall benefit but also amplifies inequality among non-returning agents.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**Significance:** This paper provides important insights into adversarial interaction attacks in markets with returning and non-returning sides. By shedding light on the underlying incentives and repercussions associated with these attacks, the authors deepen the understanding of strategic behavior within matching and prediction mechanisms. It also emphasizes the importance of developing strategies to mitigate these attacks and promote fairness in market outcomes.\n\n**Novelty:** The attacks presented in this paper are novel. Previous studies have focused on strategic behaviors in either matching markets or prediction mechanisms individually, but this paper introduces a new perspective by examining the interplay between the two.\n\n**Clarity and Quality:** The paper is well-written and comprehensible.", "weaknesses": "The setting analyzed is a bit too simplistic, perhaps this can be improved in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Zyns for their feedback on and engagement with our manuscript! We appreciate the positive feedback on the significance and novelty of our work and the expressed concern regarding the simplicity of our model.\n\nRegarding the latter, we tried to follow the model-simplicity principle introduced by Axelrod (1997) and widely used since. More precisely, our goal was to keep the model minimal in order to highlight the source of vulnerability. This also allowed us to create a general framework and, thus, show the feedback loop could be problematic in multiple settings.\n\nThat being said, we agree that besides the advantages it provides, the simplicity of the model is also a limitation. As such, we reserved subsection 5.4 to discuss this choice and underline that a central direction for future work would be to consider more realistic models. As a first step, we used the appendix to extend the model (e.g., by considering more agents, alternative matching mechanisms, and k-NN as a more realistic recommender system) and perform simulations. This additional analysis largely confirmed our theoretical results. Most important, when there are few non-returning agents compared to available places and the utility of returning agents is always negative, adversarial interaction attacks continue to be effective for all analyzed market characteristics. While this analysis does not exclude the need for more realistic settings, we hope it provides some evidence that such attacks are worth investigating within various application domains."}, {"review_id": "sZpz7d7REQ", "reviewer": "Reviewer_EhdA", "summary": "This paper is looking at problems that arise in two sided matching markets, where preferences of the agents are being informed by various prediction mechanisms.  In particular, the paper makes an argument that the existence of a predictive model used by agents to inform their preference has interesting strategic repercussions. They argue that when thinking about market design, predictive models can not be ignored or analysed independently.\n\n", "questions": "-\tAre there qualitatively similar findings if DA was used instead? What would be the complications with analyzing DA over RSD? I looked at the results in the simulation and it seemed like DA did not always follow identical trends as RSD and was curious as to its behaviour.\n\n-\tA key driver of the results seems to be the feedback loop between the prediction model and the market.  Would simply cutting this feedback loop be enough (I will admit I am not sure how this would be done without ignoring data) or are you suggesting that an entirely new way of modelling such mechanisms is needed?\n\n\n\n", "limitations": "The authors did a very good job at discussing the implications of their work in terms of inequity. In particular, this is a key message of the paper -- that care needs to be taken in designing and deploying market mechanisms  since data generated by them and fed into predictive models might have strategic ramifications that can exaspertate inequality. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I liked this paper. It was well written and  the theoretical analysis appears to be solid. That said, I think its significance comes in clearly highlighting the arise of potentially unforeseen strategic behavior in markets due to the use of predictive models that shape users’ preferences. The argument made in the paper that there are interesting interplays between ML models and market mechanisms is an important warning to market designers AND opens up interesting theoretical questions in the mechanism design/market design space.\n\n", "weaknesses": "-\tThe theoretical analysis was focussed on the random serial dictatorship mechanism. I understand why the authors might have done so as it simplifies the analysis significantly, but theoretical results on other matching mechanisms (e.g. DA) would have also been interesting.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer EhdA for their supportive feedback and insightful questions! We are especially grateful for their engagement with both the paper and supplementary material.\n\nTo address the first question, as mentioned by the reviewer, DA poses additional challenges as we would need to consider more rounds (where students propose to schools) and potentially distinguish between different versions of DA. Since using DA changes the matching phase, the main difference comes in the probability of being allocated an undesirable student given a unilateral past strategic interaction (when histories are equal, we have symmetry and thus equal probabilities of outcomes). To take one example, under student-proposing DA with lotteries for the preferences of schools, there are two alternatives: (a) the two students prefer different schools (thus, each being allocated to the school they prefer), or (b) the two students prefer the same school (thus, using the lottery-based preference of the preferred school for the allocation). By interacting strategically, a school maximizes the chance of the undesirable student to prefer the other school (i.e., the beneficial subcase of a). This will complicate the proof of Lemma2 (within the appendix) but otherwise lead to the same conclusions. Since this analysis requires explaining DA and discussing the intuition behind a larger number of particular cases while providing a limited amount of additional insight, we reserved the discussion of DA for the simulation.\n\nAs EhdA accurately noted, by departing from the assumptions of the minimal model, we notice differences between DA and RSD. Looking at individual rounds during matching revealed this is due to the increased importance of the lottery-based preferences of schools under DA. For instance, assume there are more students than places at schools (which produced the largest gaps DA - RSD) and two schools with one place each. Then, under RSD, two students will be selected: the first will be allocated to the school they prefer the most, and the second to the other school. Being strategic under RSD is thus effective as, when the first student is undesirable, it minimizes the chance this student will be allocated to the strategic school. On the other hand, under DA, in the first round, each student proposes to the most preferred school. In the next round, all students who applied to school B and were not tentatively accepted by B would apply to school A and vice-versa. Thus, by the third round, each school would have tentatively accepted the student they (lottery-based) prefer the most out of all but one student. Therefore, the effectiveness of a strategy used by, e.g., school A is limited to maximizing the pool of undesirable students school B receives in the first round of the DA. However, since there are still many undesirable students remaining, school A will still receive proposals from many undesirable students in subsequent rounds. Thus, besides edge cases, under DA with many undesirable students, schools receive the students they (lottery-)prefer the most.\n\nOn the second question, as EhdA mentioned, cutting the feedback loop by ignoring data would be effective throughout scenarios. From the results of Section 5.3, one alternative is to maintain some noise in predictions (i.e., lower the prediction accuracy, alpha). More precisely, as discussed in lines 371-376, we want the maximum value of alpha that will introduce sufficiently much noise to make adversarial interaction attacks inefficient (under the current market parameters, e.g., beta, theta). This is, however, to some degree, a theoretical solution. While it makes sense mathematically, it is unclear how to find this optimal value of alpha in practice as many parameters (e.g., precise utility functions, how forward-looking returning agents are) are private information. Moreover, since these attacks are detrimental to social welfare, returning agents might be reluctant to share truthfully whether they would implement adversarial interaction attacks.\n\nBased on the simulation results, another solution could be giving more decision-power to returning agents. For example, by allowing them to fully express their preferences (instead of using lotteries), we might eliminate the incentive to attack when utilities are positive or all places will be filled. However, the intervention is ineffective when utilities are negative and there are fewer non-returning agents than places. We discuss this intervention in lines 401-404 but not what to do in the latter scenario (which corresponds to realistic settings, e.g., refugee assignment). As mentioned by EhdA, this might require a different mechanism design. For instance, we could use top trading cycles; start with a random allocation of, e.g., refugees to locations and redistribute refugees based on the preferences of locations. It is important to investigate, though, the resulting loss in welfare. \n\nFinally, one alternative solution could involve legislation. While detecting and punishing adversarial interactions is likely difficult to impossible, there could be a relocation of funds to counteract the undesirability of matches. For example, all locations could contribute equally to a collective account that covers the estimated costs of integrating all refugees. Then, when a refugee is matched to a location, that location also receives the paired funds for integrating the refugee. Doing so will lead to a positive utility scenario and potentially to equal desirability of all non-returning agents. \n\nAltogether, our initial analysis seems to suggest efficient interventions will likely depend on the application domain and might require input from domain experts to assess their feasibility. Thus, in order to avoid giving a hasty suggestion, we concentrated on underlining the main causes for problems and kept the discussion on potential solutions at a high level. We left this interesting and important analysis for future work."}, {"review_id": "GeUZMvNqfj", "reviewer": "Reviewer_UhQP", "summary": "This paper studies the matching market with returning agents and\nproposes an important strategic behavior that returning agents can\nattack future predictions by distort short-term interactions. The\nauthors formulate the systems as (repeated) three phases and study a\nsimplified setting to derive informative conclusions on the impact of\nthis attack behavior.", "questions": "  In line 275-276, \"the school always chooses outcome\n  1-l\", I am confused about how can the school choose\n  the outcome of interaction here.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "\n  -Novel and meaningful topic of strategic behavior in matching market\n  with returning agents.\n\n  -The description of setting and analysis of phenomenon is clear and\n  easy for readers to follow.\n", "weaknesses": "  A natural question is whether these conclusions can be extended to\n  larger matching markets. The setting used for inducing main\n  conclusions of this paper seems too simplified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer UhQP for their feedback and question. We are grateful both for their appreciation of the novelty and importance of the topic and for their concern about the simplicity of the model.\n\nRegarding the question, we apologize for the lack of clarity surrounding the link between adversarial interaction attacks and outcomes. In the interaction phase, the school interacts with the allocated student. During this interaction, the school has some choice of action (e.g., provide integration services or after-school preparation for the student transferring from a low-performing school). In practice, the student also has a choice to react to these opportunities (e.g., attend and pay attention to these services). However, as mentioned in lines 161-165, since the student is not returning, we assume they will make the most out of the provided opportunities. Thus each action of the school will have a direct connection with an (expected) outcome of the interaction. For example, the school could know, based on past experience, that by providing a fraction of (1-l) of the total hours of after-school training, the student (is expected to) get a final SAT score equal to a fraction (1-l) of the maximum one. As such, each action of the school during the interaction with the student corresponds to an outcome of their interaction. We tried to capture this intuition in the example included in lines 171-176. We will clarify this in the final version.\n\nThe level of control a returning agent has on the interaction outcome varies with the application domain. For example, in a school choice setting, there is still some variability in the performance of the student. That is, based on the performance of the student in mock exams and/or the performance of similar past students, the school can anticipate the final result of the current student, but there will still be some variability. However, in a refugee assignment problem, if a location does not provide (good) interview opportunities for one refugee in the first 90 days, the respective refugee does not have any chance of getting a (good) job. In short, in a general scenario, the returning agent chooses their action (i.e., how much support they provide to a given non-returning agent), which maps to an expected outcome (i.e., the success of the interaction, which is estimated based on past experiences).\n\nWe would also want to add a few words regarding the simplicity of the model. As mentioned in the reply for reviewer Zyns, throughout the modeling phase, we tried to follow the model-simplicity principle introduced by Robert Axelrod (1997) and used in the next decades. More precisely, our goal was to keep the model minimal in order to highlight the source of vulnerability. This also allowed us to create a general framework and , thus, show the feedback loop could be problematic in multiple settings.\n\nThat being said, we are in agreement with Reviewer UhQP that besides its advantages, the simplicity of the model is also a limitation. In particular, we underline in lines 394-395 that a central direction for future work would be to consider more realistic (and in particular larger) models. As a first step, we used the appendix to extend the model (e.g., by considering higher numbers of agents, alternative matching mechanisms, and k-NN as a more realistic recommender system) and perform simulations. This additional analysis largely confirmed our theoretical results. Most important, when there are few non-returning agents compared to available places and the utility of returning agents is always negative, adversarial interaction attacks were effective for all considered matching mechanisms. While this analysis does not exclude the need for larger and more realistic settings in future work, we hope it provides some evidence that such attacks are worth investigating within various settings and application domains."}]

Author rebuttal:
We would like to thank the organizers and reviewers for the opportunity to further discuss our work in this response phase and author-reviewer discussion! We are grateful for the extra work involved and will try to address the questions through direct responses.

Meta-review: This paper looks at a dynamic two-sided matching model where (i) one side is single-shot and the other side returns each round and (ii) agents do not know the preferences up front but instead estimate/learn them via a predictor.  They show that strategic agents on the returning side can manipulate that predictor in the short term to potentially gain in the long term.  Strategic behavior in matching markets is not a new area of study, but the attack found in this model is (to the best of my/reviewers’ knowledge) new and interesting.  We encourage the authors to take the reviewers’ comments, and the authors’ own rebuttal, seriously to address remaining issues of motivation/generality.
Decision: Accept (poster)