More Like this

1. Graphical House Allocation

   Hosseini, Hadi; Payan, Justin; Sengupta, Rik; Vaish, Rohit; Viswanathan, Vignesh (May 2023, AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems)

   The classical house allocation problem involves assigning n houses (or items) to n agents according to their preferences. A key criteria in such problems is satisfying some fairness constraints such as envy-freeness. We consider a generalization of this problem wherein the agents are placed along the vertices of a graph (corresponding to a social network), and each agent can only experience envy towards its neighbors. Our goal is to minimize the aggregate envy among the agents as a natural fairness objective, i.e., the sum of the envy value over all edges in a social graph. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied problem of linear arrangements. For identical valuations with possibly uneven spacing, we show a number of deep and surprising ways in which our setting is a departure from this classical problem. More broadly, we contribute several structural and computational results for various classes of graphs, including NP-hardness results for disjoint unions of paths, cycles, stars, or cliques; we also obtain fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call separability which results in efficient parameterized algorithms for finding optimal allocations. 

   more » « less
2. Graphical House Allocation

   Hosseini, Hadi; Payan, Justin; Sengupta, Rik; Vaish Rohit; Viswanathan, Vignesh (May 2023, ACM 2023)
3. Differentially Private Resource Allocation

   https://doi.org/10.1145/3627106.3627181  

   Chen, Joann Qiongna; Wang, Tianhao; Zhang, Zhikun; Zhang, Yang; Jha, Somesh; Li, Zhou (December 2023, ACM)
4. Past energy allocation overwhelms current energy stresses in determining energy allocation trade‐offs

   https://doi.org/10.1002/ece3.10402  

   Griffen, Blaine D.; Bolander, Mikayla; Blakeslee, April; Crane, Laura C.; Repetto, Michele F.; Tepolt, Carolyn K.; Toscano, Benjamin J. (August 2023, Ecology and Evolution)

   Abstract Regeneration of lost appendages is a gradual process in many species, spreading energetic costs of regeneration through time. Energy allocated to the regeneration of lost appendages cannot be used for other purposes and, therefore, commonly elicits energetic trade‐offs in biological processes. We used limb loss in the Asian shore crabHemigrapsus sanguineusto compare the strength of energetic trade‐offs resulting from historic limb losses that have been partially regenerated versus current injuries that have not yet been repaired. Consistent with previous studies, we show that limb loss and regeneration results in trade‐offs that reduce reproduction, energy storage, and growth. As may be expected, we show that trade‐offs in these metrics from historic limb losses far outweigh trade‐offs from current limb losses, and correlate directly with the degree of historic limb loss that has been regenerated. As regenerating limbs get closer to their normal size, these historical injuries get harder to detect, despite the continued allocation of additional resources to limb development. Our results demonstrate the importance of and a method for identifying historic appendage losses and of quantifying the amount of regeneration that has already occurred, as opposed to assessing only current injury, to accurately assess the strength of energetic trade‐offs in animals recovering from nonlethal injury. 

   more » « less
5. Editorial: Carbon allocation, volume II

   https://doi.org/10.3389/fpls.2023.1342494  

   Tanvir, Rezwan; Gibson, Susan I.; Wurtele, Eve Syrkin; Li, Ling (November 2023, Frontiers in Plant Science)