5 papers
Subexponential Algorithm for High Multiplicity Fair Division of Mixed Instances via Stereometry
Yuriy Dementiev, Fedor Pribytkov, Danil Sagunov
We study the problem of computing an envy-free (EF) allocation of indivisible items among agents when items come in three distinct types. Each agent holds additive valuatio…
Learning Augmented Exact Exponential Algorithms
Tatiana Belova, Yuriy Dementiev, Danil Sagunov
The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, th…
Structural Approach to Guiding a Present-Biased Agent
Tatiana Belova, Yuriy Dementiev, Artur Ignatiev +1
Time-inconsistent behavior, such as procrastination or abandonment of long-term goals, arises when agents evaluate immediate outcomes disproportionately higher than future ones. Th…
EFX and PO Allocation Exists for Two Types of Goods
Vladimir Davidiuk, Yuriy Dementiev, Artur Ignatiev +1
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 fa…
How to guide a present-biased agent through prescribed tasks?
Tatiana Belova, Yuriy Dementiev, Fedor V. Fomin +2
The present bias is a well-documented behavioral trait that significantly influences human decision-making, with present-biased agents often prioritizing immediate rewards over lon…