publications
2025
- Nash Flows Over Time with TollsShaul Rosner, Marc Schröder , and Laura Vargas Koch2025Accepted to WINE 2025
We study a dynamic routing game motivated by traffic flows. The base model for an edge is the Vickrey bottleneck model. That is, edges are equipped with a free flow transit time and a capacity. When the inflow into an edge exceeds its capacity, a queue forms and the following particles experience a waiting time. In this paper, we enhance the model by introducing tolls, i.e., a cost each flow particle must pay for traversing an edge. In this setting we consider non-atomic equilibria, which means flows over time in which every particle is on a cheapest path, when summing up toll and travel time. We first show that unlike in the non-tolled version of this model, dynamic equilibria are not unique in terms of costs and do not necessarily reach a steady state. As a main result, we provide a procedure to compute steady states in the model with tolls.
@misc{RSV25, author = {Rosner, Shaul and Schr{\"o}der, Marc and Vargas Koch, Laura}, title = {Nash Flows Over Time with Tolls}, note = {Accepted to WINE 2025}, year = {2025} } - Bipartite Matching with Pair-Dependent BoundsShaul Rosner, and Tami Tamir2025Submitted to ITCS 2025
Let G=(U ∪V, E) be a bipartite graph, where U represents jobs and V represents machines. We introduce and study a new variant of the bipartite matching problem in which each job in U can be assigned to at most one machine in V, while the capacity of a machine depends on the particular set of jobs matched to it. These pair-dependent capacity constraints capture settings where different jobs exhibit varying tolerance to congestion, depending on the machine to which they are assigned. We define a \em bipartite PD-matching as a set of edges M ⊆E that respects these job-to-machine tolerance constraints. This variant of matching extends well-known matching problems, however, despite its relevance to real-world systems, it has not been studied before. We study bipartite PD-matchings with the objective of maximizing the matching size. As we show, the problem exhibits fundamental differences from previously explored matching variants. We analyze its computational complexity both in the general case and for specific restricted instances, presenting hardness results alongside optimal and approximation algorithms.
@misc{RT25itcs, author = {Rosner, Shaul and Tamir, Tami}, title = {Bipartite Matching with Pair-Dependent Bounds}, note = {Submitted to ITCS 2025}, year = {2025}, } - Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-datesShaul Rosner, and Tami Tamir2025Presented at ATMOS 2025
We consider a scheduling environment in which jobs are associated with \em machine-dependent due-dates. This natural setting arises in systems where clients’ tolerance depends on the service provider. The objective is to maximize throughput, defined as the number of non-tardy jobs. The problem exhibits significant differences from previously studied scheduling models. We analyze its computational complexity both in general and for the special case of unit-length jobs. In the unit-length setting, we provide an optimal algorithm that also extends to cases with machine-dependent release times and machine-dependent weights (i.e., rewards depending on the machine that completes the job). For jobs with different lengths, we show that even the unweighted problem without release times, with only two different lengths, specifically, for all j, p_j ∈{1,2}, is APX-hard. To isolate the role of machine-dependent due-dates in this hardness result, we present an optimal algorithm for the case where all p_j ∈1,2 and due-dates are not machine-dependent. This algorithm further extends to instances with a constant number of integer processing times.
@misc{RT25, author = {Rosner, Shaul and Tamir, Tami}, title = {Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-dates}, note = {Presented at ATMOS 2025}, year = {2025} } - Cost-sharing games with rank-based utilitiesShaul Rosner, and Tami TamirTheoretical Computer Science, 2025
Studies in behavioural science show that individuals are often concerned primarily about their relative welfare, rather than their absolute well-being.In this paper we define and study a variant of congestion game that reflects this phenomenon. In a cost-sharing game with rank-based utilities (CSRB-game, for short), the players are partitioned into competition sets, and the goal of every player is to minimize its cost relative to its competitors. Specifically, the primary goal of a player is to minimize the rank of its cost among its competitors, while minimizing the cost itself is a secondary objective. We show that CSRB-games are significantly different from classical cost-sharing games, and that competition may lead to a poor outcome. In particular, singleton CSRB-games need not have a pure Nash equilibrium, and even when a NE exists, natural dynamics may not converge to a NE, and the price of stability is linear in the number of players. We then analyze several natural restricted classes of singleton \CSRB-games, for which we present positive results. We provide tight characterization of classes for which a NE exists and can be computed efficiently, and bound the equilibrium inefficiency, based on the competition structure, the number of players and resources, the uniformity of resources’ costs, and the strategy space of competing players.
2023
- Entrepreneurship Facility-Activation GamesShaul Rosner, and Tami TamirIn International Symposium on Algorithmic Game Theory , 2023
In recent years, entrepreneurship has become a driving force for innovation and economic growth. While it has been extensively studied by economists, it has not received much attention in the AGT community. We define and study an entrepreneurship facility-activation game, played by a single entrepreneur and n users. The entrepreneur may activate and close facilities, and each user should select one active facility. This setting combines a weighted singleton congestion game played by the users, with a revenue maximization game played by the entrepreneur, who dynamically determines the set of active facilities in response to the users’ assignment. We analyze the resulting game from multiple perspectives. From the entrepreneur’s perspective, maximizing her profit, we provide an asymptotically tight O(\sqrtn)-approximation algorithm with and without stability restrictions. For the total welfare problem of minimizing the total users cost and facilities activation cost, we provide tight linear bounds for the PoA and PoS. Additionally, we analyze the computational complexity of both the social optimum and the cheapest stable solution. We distinguish between games with weighted and unweighted users, with and without symmetric strategies, and between arbitrary and uniform facility activation costs. Our results highlight the challenges of revenue maximization for entrepreneurs and the high impact of entrepreneurship on the total welfare and the equilibrium efficiency.
@inproceedings{rosner2023entrepreneurship, title = {Entrepreneurship Facility-Activation Games}, author = {Rosner, Shaul and Tamir, Tami}, booktitle = {International Symposium on Algorithmic Game Theory}, pages = {90--108}, year = {2023}, organization = {Springer}, } - Scheduling games with rank-based utilitiesShaul Rosner, and Tami TamirGames and Economic Behavior, 2023
Job scheduling on parallel machines is a well-studied singleton congestion game. We consider a variant of this game, arising in environments with strong competition. In a scheduling game with rank-based utilities (SRBG) the players are partitioned into competition sets, and the goal of every player is to perform well relative to its competitors. We show that SRBGs are significantly different from classical job-scheduling games, and that competition may lead to poor outcomes. An SRBG need not have a pure Nash equilibrium, and best-response dynamics may not converge to a NE even if one exists. We identify several classes of games for which a NE exists and can be computed efficiently, present tight bounds on the equilibrium inefficiencies, and suggest ways to modify SRBGs in order to guarantee NE existence. Our analysis provides insights for several other congestion and cost-sharing games that have a natural ‘rank-based’ variant.
@article{rosner2023scheduling, title = {Scheduling games with rank-based utilities}, author = {Rosner, Shaul and Tamir, Tami}, journal = {Games and Economic Behavior}, volume = {140}, pages = {229--252}, year = {2023}, publisher = {Elsevier}, }
2022
- Cost-Sharing Games with Rank-Based UtilitiesShaul Rosner, and Tami TamirIn Algorithmic Game Theory: 15th International Symposium, SAGT 2022 , 2022
@inproceedings{rosner2022cost, title = {Cost-Sharing Games with Rank-Based Utilities}, author = {Rosner, Shaul and Tamir, Tami}, booktitle = {Algorithmic Game Theory: 15th International Symposium, SAGT 2022}, pages = {275--292}, year = {2022}, organization = {Springer} }
2020
- Race scheduling gamesShaul Rosner, and Tami TamirIn Algorithmic Game Theory: 13th International Symposium, SAGT 2020 , 2020
@inproceedings{rosner2020race, title = {Race scheduling games}, author = {Rosner, Shaul and Tamir, Tami}, booktitle = {Algorithmic Game Theory: 13th International Symposium, SAGT 2020}, pages = {257--272}, year = {2020}, organization = {Springer} }