Shai Vardi

Shai Vardi

Auto-generated profile, based on publicly available information

Shai Vardi

Department of Information Systems, Muma College of Business, University of South Florida , Tampa, FL 33620

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
3 August 2016 in ACM Transactions on Economics and Computation
Verified
Journal Article
Open access
AHAvinatan Hassidim
Avinatan Hassidim
YMYishay Mansour
Yishay Mansour
SVShai Vardi
Shai Vardi
We introduce the notion of local computation mechanism design —designing game-theoretic mechanisms that run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs payments, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanism needs to maintain incentive compatibility with respect to the allocation and payments. We present local computation mechanisms for two classical game-theoretical problems: stable matching and job scheduling. For stable matching, some of our techniques may have implications to the global (non-LCA (Local Computation Algorithm)) setting. Specifically, we show that when the men’s preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.

1 January 2022 in Operations Research Letters
Verified
Journal Article
Open access
BMBenjamin Moseley
Benjamin Moseley
SVShai Vardi
Shai Vardi

1 May 2022 in Mathematics of Operations Research
Verified
Journal Article
Closed access
SVShai Vardi
Shai Vardi
APAlexandros Psomas
Alexandros Psomas
EFEric Friedman
Eric Friedman
A single homogeneous resource needs to be fairly shared between users that dynamically arrive and depart over time. Although good allocations exist for any fixed number of users, implementing these allocations dynamically is impractical: it typically entails adjustments in the allocation of every user in the system whenever a new user arrives. We introduce a dynamic fair resource division problem in which there is a limit on the number of users that can be disrupted when a new user arrives and study the trade-off between fairness and the number of allowed disruptions, using a fairness metric: the fairness ratio. We almost completely characterize this trade-off and give an algorithm for obtaining the optimal fairness for any number of allowed disruptions.

1 September 2024 in Operations Research
Verified
Journal Article
Closed access
TKThomas Kesselheim
Thomas Kesselheim
APAlexandros Psomas
Alexandros Psomas
SVShai Vardi
Shai Vardi
The paper studies generalization of the secretary problem, where decisions do not have to be made immediately upon applicants’ arrivals. After arriving, each applicant stays in the system for some (random) amount of time and then leaves, whereupon the algorithm has to decide irrevocably whether to select this applicant or not. The arrival and waiting times are drawn from known distributions, and the decision maker’s goal is to maximize the probability of selecting the best applicant overall. The paper characterizes the optimal policy for this setting, showing that when deciding whether to select an applicant, it suffices to know only the time and the number of applicants that have arrived so far. Furthermore, the policy is monotone nondecreasing in the number of applicants seen so far, and, under certain natural conditions, monotone nonincreasing in time. Furthermore, when the number of applicants is large, a single threshold policy is almost optimal.

1 November 2025 in Operations Research
Verified
Journal Article
Closed access
SVShai Vardi
Shai Vardi
WHWilliam Haskell
William Haskell
Balancing Fairness and Efficiency: The Price of Fairness in Scheduling Scarce Resources “The Price of Fairness of Scheduling a Scarce Resource” investigates the trade-offs between fairness and utility when scheduling scarce resources among multiple stakeholders. The research focuses on envy-freeness, a widely recognized fairness criterion, and explores how fairness constraints impact overall utility, quantified by the price of fairness—the ratio of attainable utility with and without fairness considerations. By analyzing various factors, including the number of agents, time horizon, discount factors, and switching costs, the authors derive tight bounds on the price of fairness. Interestingly, they discover that, whereas fairness often increases utility loss, certain parameters—such as reducing the time horizon or increasing the number of agents—can counterintuitively reduce this loss. These findings offer strategic insights for decision makers facing fairness constraints in scheduling, helping them navigate complex trade-offs between equitable resource allocation and maximizing efficiency.

13 November 2023 in Operations Research Letters
Verified
Journal Article
Closed access
YSYu Su
Yu Su
SVShai Vardi
Shai Vardi
XRXiaoqi Ren
Xiaoqi Ren
AWAdam Wierman
Adam Wierman