3 August 2016 in ACM Transactions on Economics and Computation
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
1 May 2022 in Mathematics of Operations Research
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
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
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