Search

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. We study a 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. Our first main result is a characterization of the optimal policy for this setting. We show 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. Our second main result is that when the number of applicants is large, a single threshold policy is almost optimal. Funding: A. Psomas is supported in part by the National Science Foundation [Grant CCF-2144208], a Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2476. [ABSTRACT FROM AUTHOR]

Trade-Offs in Dynamic Allocation Problems Food rescue organizations often receive donations to allocate to food pantries or families. Donations are unpredictable, and goods are often perishable; as a result, allocations have to be made within a short time frame after arrival without knowledge of future arrivals. It is important that donations go to organizations that are able to use them; at the same time, organizations that serve different communities should be treated equitably. In "Fair and Efficient Online Allocations," Benadè, Kazachkov, Procaccia, Psomas, and Zeng study fairness-efficiency trade-offs in such online allocation problems. Against adversarial arrivals, no algorithm can provide nontrivial guarantees for both these objectives simultaneously. When item values are drawn from (potentially correlated) distributions, there is no trade-off, and a simultaneously fair and efficient algorithm is presented. We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another's allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. In a slightly weaker adversary regime where item values are drawn from (potentially correlated) distributions, it is possible to achieve the best of both worlds. We give an algorithm that is Pareto efficient ex post and either envy free up to one good or envy free with high probability. Neither guarantee can be improved, even in isolation. En route, we give a constructive proof for a structural result of independent interest. Specifically, there always exists a Pareto-efficient fractional allocation that is strongly envy free with respect to pairs of agents with substantially different utilities while allocating identical bundles to agents with identical utilities (up to multiplicative factors). Funding: A. Psomas is supported in part by the National Science Foundation [Award CCF-2144208] and Google [the AI for Social Good Award and the Research Scholar Award]. This work was partially supported by the National Science Foundation [Grants IIS-2147187, IIS-2229881, and CCF-2007080] and the Office of Naval Research [Grant N00014-20-1-2488]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.0332. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Over the last few decades, the natural flow regime of most rivers has been significantly altered influencing the ecological integrity and functioning of river ecosystems. Especially in the Mediterranean region, irrigated agriculture is considered one of the most important drivers of hydro-morphological modifications in river systems. In this study we employ the Indicators of Hydrologic Alteration (IHA) methodology for the Pinios River and its tributaries, located in a Mediterranean catchment in central Greece, with the purpose to assess the natural flow regime under a simulated no-agriculture scenario and compare with the current situation. The work is based on the use of the SWAT (Soil Water Assessment Tool) model for the simulation of long time series of daily stream flows, which were analyzed under the actual conditions (baseline), and the hypothetical scenario. The key characteristics of the flow regime projected under each model run were assessed through the implementation of the IHA methodology that utilizes a number of indicators to characterize the intra- and inter-annual variability in the hydrologic conditions. The results of this study revealed that without agricultural activities in the catchment, annual and monthly flows would increase, with significant alterations in the flow characteristics of the winter months, and much smaller in summer. However, the analysis showed that the frequency of droughts and low flow summer events would be smaller. The article provides a comprehensive and easy-to-implement methodology that can facilitate the impact assessment of agricultural human activities on river flow variability under the typical Mediterranean conditions, allowing experimentation on setting river flow thresholds required for a good ecological status within the context of the European Water Framework Directive. [ABSTRACT FROM AUTHOR]