{"id":"arxiv/2607.09953","url":"https://arxiv.org/abs/2607.09953","tags":["math.OC","cs.CC"],"score":0,"title":"Complexity of partitioned-items response problems: matchings and perfect matchings","domain":"math.OC","source":"arxiv","authors":["Christoph Buchheim","Lowig Duer","Eva Ley","Maximilian Merkert","Komal Muluk"],"reviews":0,"subject":"math.OC","summary":"We consider bilevel optimization problems in which leader and follower jointly construct a feasible solution for an underlying combinatorial optimization problem. Response problems ask whether the leader can encourage -- or, in the pessimistic setting, enforce -- a reaction of the follower that includes a set of mandatory items while excluding a set of forbidden items. Our investigation focuses on tractability results for various cases which emerge from different combinations of the total number of mandatory, forbidden, and neutral items. After providing some results for response problems…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}