Time-inconsistent behavior, such as procrastination or abandonment of long-term goals, arises when agents evaluate immediate outcomes disproportionately higher than future ones. This leads to globally suboptimal behavior, where plans are frequently revised or abandoned entirely. In the influential model of Kleinberg and Oren (2014) such behavior is modeled by a present-biased agent navigating a task graph toward a goal, making locally optimal decisions at each step based on discounted future costs. As a result, the agent may repeatedly deviate from initially intended plans. Recent work by Belova et al. (2024) introduced a two-agent extension of this model, where a fully-aware principal attempts to guide the present-biased agent through a specific set of critical tasks without causing abandonment. This captures a rich class of principal–agent dynamics in behavioral settings. In this paper, we provide a comprehensive algorithmic characterization of this problem. We analyze its computational complexity through the framework of parameterized algorithms, focusing on graph parameters that naturally emerge in this setting, such as treewidth, vertex cover, and feedback vertex set. Our main result is a fixed-parameter tractable algorithm when parameterized by the treewidth of the task graph and the number of distinct (v,t)-path costs. Our algorithm encaptures several input settings, such as bounded edge costs and restricted task graph structure. We demonstrate that our main result yields efficient algorithms for a number of such configurations. We complement this with tight hardness results, that highlight the extreme difficulty of the problem even on simplest graphs with bounded number of nodes and constant parameter values, and motivate our choice of parameters. We delineate tractable and intractable regions of the problem landscape, which include answers to open questions of Belova et al. (2024).

We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX) — an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While recent results have established EFX existence for settings with at most three distinct valuations and for two types of goods, the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasiliniear time when there are two types of goods, given that the valuations are positive. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation.

The Nash Welfare (NW) objective—the geometric mean of utilities—is often considered as a good compromise between fairness and efficiency. The respective maximization problem (MNW) for indivisible goods was first proposed in [11] and has received significant attention in the recent years with the current best e1/e-approximation guarantee. A natural approach of first solving fractional MNW (i.e., where all items are divisible) and then rounding solution does not work, as the integrality gap of MNW can be unbounded [11]. However, from a practical perspective, e.g., in inheritance division, many instances are actually mixed. I.e., the instance has a significant amount of liquid assets, which can be easily converted into money and thus divided fractionally between agents. We model such instances with a set of indivisible goods and a single divisible good—money, which has the same value for every agent. We study the integrality gap of the MNW parametrized by the amount of money s in the instance. This parametrization is closely related to the literature on fair division with subsidies initiated by [17], where it is assumed that the maximum value of any agent per item is vmax = 1. We find that the IG may be non-monotone in s and could be strictly larger than 1 for a large amount of money s = O(n · m) dollars. On the positive side, we construct a polynomial scheme that with the amount of money c · n produces an integral allocation with integrality gap IG(s) ≤ maxα∈[0,1](2c/(2c – 1 + α))α, where IG(s) < 1.43 for c = 0.51, IG(s) < 1.16 for c = 1, and IG(s) < 1.07 for c = 2.

Fair division is a topic that has significant social and industrial value. In this work, we study allocations that simultaneously satisfy definitions of fairness and efficiency: EFx and PO. First, we prove that the problem of finding such allocations is NP-hard for two agents. Then, we propose a concept for an ILP-based solving algorithm, the running time of which depends on the number of EFx allocations. We generate input data and analyze algorithm's running time based on the results obtained.

The present bias is a well-documented behavioral trait that significantly influences human decision-making, with present-biased agents often prioritizing immediate rewards over long-term benefits, leading to suboptimal outcomes in various real-world scenarios. Kleinberg and Oren (2014) proposed a popular graph-theoretical model of inconsistent planning to capture the behavior of present-biased agents. In this model, a multi-step project is represented by a weighted directed acyclic task graph, where the agent traverses the graph based on present-biased preferences. We use the model of Kleinberg and Oren to address the principal-agent problem, where a principal, fully aware of the agent’s present bias, aims to modify an existing project by adding or deleting tasks. The challenge is to create a modified project that satisfies two somewhat contradictory conditions. On one hand, the present-biased agent should select specific tasks deemed important by the principal. On the other hand, if the anticipated costs in the modified project become too high for the agent, there is a risk of the agent abandoning the entire project, which is not in the principal’s interest. To tackle this issue, we leverage the tools of parameterized complexity to investigate whether the principal’s strategy can be efficiently identified. We provide algorithms and complexity bounds for this problem.