Fedor Sandomirskiy

Fedor Sandomirskiy

Auto-generated profile, based on publicly available information

Fedor Sandomirskiy

Princeton University, Princeton, NJ, USA

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2017 in Econometrica
Verified
Journal Article
Closed access
ABAnna Bogomolnaia
Anna Bogomolnaia
HMHervé Moulin
Hervé Moulin
FSFedor Sandomirskiy
Fedor Sandomirskiy
EYElena Yanovskaya
Elena Yanovskaya

1 February 2024 in Mathematics of Operations Research
Verified
Journal Article
Closed access
SBSimina Brânzei
Simina Brânzei
FSFedor Sandomirskiy
Fedor Sandomirskiy
We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash social welfare on the Pareto frontier of the set of feasible utilities. The Pareto frontier may contain many such points and, consequently, the outcome of the competitive rule is no longer unique. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive utility profile can be constructed via an explicit formula; each candidate can be checked for competitiveness and the allocation can be reconstructed using a maximum flow computation. Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy. Funding: This work was supported by National Science Foundation (CNS 1518941); Lady Davis Fellowship Trust, Hebrew University of Jerusalem; H2020 European Research Council (740435); Linde Institute at Caltech.

15 August 2014 in Communications in Mathematical Physics
Verified
Journal Article
Closed access
PDF file
AFAlexander Fedotov
Alexander Fedotov
FSFedor Sandomirskiy
Fedor Sandomirskiy

1 May 2022 in Operations Research
Verified
Journal Article
Closed access
FSFedor Sandomirskiy
Fedor Sandomirskiy
ESErel Segal-Halevi
Erel Segal-Halevi
When assets are to be divided among several partners, for example, a partnership split, fair division theory can be used to determine a fair allocation. The applicability of existing approaches is limited as they either treat assets as divisible resources that end up being shared among participants or deal with indivisible objects providing only approximate fairness. In practice, sharing is often possible but undesirable, and approximate fairness is not adequate, particularly for highly valuable assets. In “Efficient Fair Division with Minimal Sharing,” Sandomirskiy and Segal-Halevi introduce a novel approach offering a middle ground: the number of shared objects is minimized while maintaining exact fairness and economic efficiency. This minimization can be conducted in polynomial time for generic instances if the number of agents or objects is fixed. Experiments on real data demonstrate a substantial improvement over current methods.

1 February 2022 in Management Science
Verified
Journal Article
Closed access
ABAnna Bogomolnaia
Anna Bogomolnaia
HMHervé Moulin
Hervé Moulin
FSFedor Sandomirskiy
Fedor Sandomirskiy
Ann likes oranges much more than apples; Bob likes apples much more than oranges. Tomorrow they will receive one fruit that will be an orange or an apple with equal probability. Giving one half to each agent is fair for each realization of the fruit. However, agreeing that whatever fruit appears will go to the agent who likes it more gives a higher expected utility to each agent and is fair in the average sense: in expectation, each agent prefers the allocation to the equal division of the fruit; that is, the agent gets a fair share. We turn this familiar observation into an economic design problem: upon drawing a random object (the fruit), we learn the realized utility of each agent and can compare it to the mean of the agent’s distribution of utilities; no other statistical information about the distribution is available. We fully characterize the division rules using only this sparse information in the most efficient possible way while giving everyone a fair share. Although the probability distribution of individual utilities is arbitrary and mostly unknown to the manager, these rules perform in the same range as the best rule when the manager has full access to this distribution. This paper was accepted by Ilia Tsetlin, behavioral economics and decision analysis.

10 January 2014 in International Journal of Game Theory
Verified
Journal Article
Closed access
PDF file
FSFedor Sandomirskiy
Fedor Sandomirskiy