Search for: All records

We study the group-fair multi-period mobile facility location problems, where agents from different groups are located on a real line and arrive in different periods. Our goal is to locate k mobile facilities at each period to serve the arriving agents in order to minimize the maximum total group-fair cost and the maximum average group-fair cost objectives that measure the costs or distances of groups of agents to their corresponding facilities across all periods. We first consider the problems from the algorithmic perspective for both group-fair cost objectives. We then consider the problems from the mechanism design perspective, where the agents' locations and arrival periods are private. For both objectives, we design deterministic strategyproof mechanisms to elicit the agents' locations and arrival periods truthfully while optimizing the group-fair cost objectives and show that our mechanisms have almost tight bounds on the approximation ratios for certain periods and settings. Finally, we discuss the extensions of our results to the online setting where agent arrival information is only known at each period. 

We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents’ utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx). 

Algorithms for exchange of kidneys is one of the key successful applications in market design, artificial intelligence, and operations research. Potent immunosuppressant drugs suppress the body's ability to reject a transplanted organ up to the point that a transplant across blood- or tissue-type incompatibility becomes possible. In contrast to the standard kidney exchange problem, we consider a setting that also involves the decision about which recipients receive from the limited supply of immunosuppressants that make them compatible with originally incompatible kidneys. We firstly present a general computational framework to model this problem. Our main contribution is a range of efficient algorithms that provide flexibility in terms of meeting meaningful objectives. Motivated by the current reality of kidney exchanges using sophisticated mathematical-programming-based clearing algorithms, we then present a general but scalable approach to optimal clearing with immunosuppression; we validate our approach on realistic data from a large fielded exchange.