Fedor Sandomirskiy
Fedor Sandomirskiy
I am an Associate Research Scholar and Lecturer at the Department of Economics of Princeton University (2023-25). Before that, I was a Linde postdoc in Economics and PIMCO fellow in Data Science at the California Institute of Technology, a postdoc at the Technion Game Theory group, a member of the Mechanism Design for Data Science group, and worked at the Game Theory Lab of HSE University. I've been serving on the program committee of the ACM Conference on Economics and Computation: as a PC member (EC'19-22) and as an Area Chair (EC'23).
In January 2025, I will join Princeton University as an Assistant Professor of Economics.
CV RESEARCH STATEMENT TEACHING STATEMENT
Contacts
office 277, Julis Romo Rabinowitz bld.
News
- July 2024: A new WP "Narrow Framing and Risk in Games" (with Po Hyun Sung, Omer Tamuz, and Ben Wincelberg)
- April 2024: I am excited to continue at Princeton University as an Assistant Professor starting in January 2025!
- February 2024: A new WP "Stable Matching as Transportation" (with Federico Echenique and Joseph Root)
- November 2023: A new WP "Decomposable Stochastic Choice" (with Omer Tamuz)
-
July 2023:
- I joined Princeton Economics as an Associate Research Scholar and Lecturer!
- A new WP "On the Origin of the Boltzmann Distribution" (with Omer Tamuz)
- I joined Princeton Economics as an Associate Research Scholar and Lecturer!
-
June 2023: Check new versions of "Private Private Information" and "Persuasion as transportation"
-
May 2023: "Algorithms for Competitive Division of Chores" (with Simina Branzei) is published in Mathematics of Operations Research
-
December 2022: I will serve as an Area Chair at the ACM Conference on Economics and Computation EC'23.
Mind the unusually early submission deadline: January 20
- October 2022: A new WP "The geometry of consumer preference aggregation" (with Philip Ushchev)
-
September 2022:
- Automatically generated proof of the RSD conjecture for four agents
- Updated CV, Research Statement, and Teaching Statement
- Automatically generated proof of the RSD conjecture for four agents
-
July 2022:
-
Presenting at EC'22 (twice), at INFORMS Market Design Workshop, and Stony Brook Game Theory conference
See slides on Private private information, Beckmann's approach to multi-item auctions, and Persuasion as transportation
-
-
June 2022:
- Lecture notes on Economic Design for CS & Math students released. Feedback welcome!
- "Efficient Fair Division with Minimal Sharing" is published in Operations Research
- Lecture notes on Economic Design for CS & Math students released. Feedback welcome!
-
May 2022: Two papers are accepted at EC'22:
- a new WP "Persuasion as transportation" (with Itai Arieli and Yakov Babichenko)
- "Private private information" (with Omer Tamuz and Kevin He)
-
March 2022: Three new WPs:
- "Beckmann's approach to multi-item multi-bidder auctions" (with Alexander Kolesnikov, Aleh Tsyvinski, and Alexander P. Zimin)
- "Bayesian Persuasion with Mediators" (with Itai Arieli and Yakov Babichenko)
- Efficiency in Random Resource Allocation and Social Choice (with Federico Echenique and Joseph Root)
-
February 2022: "On the fair division of a random object" (with Herve Moulin and Anna Bogomolnaia) is published in Management Science
-
January 2022: I will be serving at the PC of
The Twenty-Third ACM Conference on Economics and Computation (EC'22)
Research
Working papers
-
Narrow Framing and Risk in Games (with Po Hyun Sung, Omer Tamuz, and Ben Wincelberg)
abstractWe study finite normal-form games under a narrow framing assumption: when players play several games simultaneously, they consider each one separately. We show that under mild additional assumptions, players must play either Nash equilibria, logit quantal response equilibria, or their generalizations, which capture players with various risk attitudes.
-
Stable Matching as Transportation (with Federico Echenique and Joseph Root)
abstractWe study matching markets with aligned preferences and establish a connection between common design objectives---stability, efficiency, and fairness---and the theory of optimal transport. Optimal transport gives new insights into the structural properties of matchings obtained from pursuing these objectives, and into the trade-offs between different objectives. Matching markets with aligned preferences provide a tractable stylized model capturing supply-demand imbalances in a range of settings such as partnership formation, school choice, organ donor exchange, and markets with transferable utility where bargaining over transfers happens after a match is formed.
-
Decomposable Stochastic Choice (with Omer Tamuz)
abstractWe investigate inherent stochasticity in individual choice behavior across diverse decisions. Each decision is modeled as a menu of actions with outcomes, and a stochastic choice rule assigns probabilities to actions based on the outcome profile. Outcomes can be monetary values, lotteries, or elements of an abstract outcome space. We characterize decomposable rules: those that predict independent choices across decisions not affecting each other. For monetary outcomes, such rules form the one-parametric family of multinomial logit rules. For general outcomes, there exists a universal utility function on the set of outcomes, such that choice follows multinomial logit with respect to this utility. The conclusions are robust to replacing strict decomposability with an approximate version or allowing minor dependencies on the actions' labels. Applications include choice over time, under risk, and with ambiguity.
-
On the Origin of the Boltzmann Distribution (with Omer Tamuz)
abstractThe Boltzmann distribution is used in statistical mechanics to describe the distribution of states in systems with a given temperature. We give a novel characterization of this distribution as the unique one satisfying independence for uncoupled systems. The theorem boils down to a statement about symmetries of the convolution semigroup of finitely supported probability measures on the natural numbers, or, alternatively, about symmetries of the multiplicative semigroup of polynomials with non-negative coefficients.
-
Private private information (with Omer Tamuz and Kevin He), new version from June 2023
Journal of Political Economy, R&Rextended abstract published at EC'22abstract,slides (EC'22)In a private private information structure, agents' signals contain no information about the signals of their peers. We study how informative such structures can be, and characterize those that are on the Pareto frontier, in the sense that it is impossible to give more information to any agent without violating privacy. In our main application, we show how to optimally disclose information about an unknown state under the constraint of not revealing anything about a correlated variable that contains sensitive information.
-
Persuasion as transportation (with Itai Arieli and Yakov Babichenko), new version from June 2023
extended abstract published at EC'22abstract,slides (EC'22)We consider a model of Bayesian persuasion with one informed sender and several uninformed receivers. The sender can affect receivers' beliefs via private signals and the sender's objective depends on the combination of induced beliefs. We reduce the persuasion problem to the Monge-Kantorovich problem of optimal transportation. Using insights from optimal transportation theory, we identify several classes of multi-receiver problems that admit explicit solutions, get general structural results, derive a dual representation for the value, and generalize the celebrated concavification formula for the value to multi-receiver problems.
-
The geometry of consumer preference aggregation (with Philip Ushchev)
abstract,slidesThis paper revisits a classical question in economics: how do individual preferences and incomes of consumers shape aggregate behavior? We develop a method that reduces the hard problem of aggregation to simply computing a weighted average. The method applies to populations with homothetic preferences. The key idea is to handle aggregation in the space of logarithmic expenditure functions. We demonstrate the power of this method by (i) characterizing classes of preferences invariant with respect to aggregation, i.e., such that any population of heterogeneous consumers with preferences from the class behaves as if it were a single aggregate consumer from the same class; (ii) characterizing classes of aggregate preferences generated by popular preference domains such as linear or Leontief; (iii) describing indecomposable preferences, i.e., those that do not correspond to aggregate behavior of any non-trivial population; (iv) representing any preference as an aggregation of indecomposable ones. We discuss connections and applications of our findings to robust welfare analysis, information design, stochastic discrete choice, pseudo-market mechanisms, and preference identification.
-
Beckmann's Approach to Multi-item Multi-bidder Auctions (with Alexander Kolesnikov, Aleh Tsyvinski, and Alexander P. Zimin)
abstract,slides (INFORMS Market Design Workshop'22)We consider the problem of revenue-maximizing Bayesian auction design with several i.i.d. bidders and several items. We show that the auction-design problem can be reduced to the problem of continuous optimal transportation introduced by Beckmann. We establish the strong duality between the two problems and demonstrate the existence of solutions. We then develop a new numerical approximation scheme that combines multi-to-single-agent reduction and the majorization theory insights to characterize the solution.
-
Bayesian Persuasion with Mediators (with Itai Arieli and Yakov Babichenko)
abstractA sender communicates with a receiver through a sequence of mediators. The sender is the only informed agent and the receiver is the only one taking an action. All the agents have their own utility functions, which depend on the receiver's action and the state. For any number of mediators, the sender's optimal value is characterized. For one mediator, the characterization has a clear geometric meaning of constrained concavification of the sender's utility, optimal persuasion requires the same number of signals as without mediators, and the presence of the mediator is never profitable for the sender. Surprisingly, the second mediator may improve the sender's utility; however, optimal persuasion with several mediators may require more signals.
-
Efficiency in Random Resource Allocation and Social Choice (with Federico Echenique and Joseph Root)
abstractWe study efficiency in general collective choice problems when agents have ordinal preferences and randomization is allowed. We establish the equivalence between welfare maximization and ex-ante efficiency for general domains. We relate ex-ante efficiency with ex-post efficiency, characterizing when the two notions coincide. Our results have implications for well-studied mechanisms including random serial dictatorship and a number of specific environments, including the dichotomous, single-peaked, and social choice domains.
-
On social networks that support learning (with Itai Arieli and Rann Smorodinsky)
Journal of Economic Theory, R&Rextended abstract published at EC'21abstract,slides (theory seminar at Cornell 2020), talk (Conference on Mechanism and Institution Design 2020)Whether or not a given social network aggregates information depends not only on the topology of the network and information available to agents but also on the order in which they make their decisions. We consider a model with Bayes-rational agents and identify the topological property sufficient for aggregation for most of the orders. We use this property and the insights from the theory of expander graphs to show that learning is possible without opinion leaders and that it can be robust to the elimination of large groups of agents.
-
Stable Matching as Transportation (with Federico Echenique and Joseph Root)
COMING SOON
Selected publications
-
Feasible joint posterior beliefs (with Itai Arieli, Yakov Babichenko, and Omer Tamuz)
abstract,slides (Paris School of Economics 2021), poster, talk, lightning talk (EC2020)We study the set of possible joint posterior belief distributions of a group of agents who share a common prior regarding a binary state, and who observe some information structure. For two agents we introduce a quantitative version of Aumann's Agreement Theorem and show that it is equivalent to a characterization of feasible distributions due to Dawid et al. (1995). For any number of agents, we characterize feasible distributions in terms of a "no-trade" condition. We use these characterizations to study information structures with independent posteriors. We also study persuasion problems with multiple receivers, exploring the extreme feasible distributions.
-
On the fair division of a random object (with Herve Moulin and Anna Bogomolnaia)
Management Science, 2022, 68(2):1174-1194abstract,slides (Center for the Study of Rationality 2019) with extra results on the exact Price of Fairness in bargainingAnn 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 his allocation to the equal division of the fruit, i.e., he 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 his 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.
-
Competitive division of a mixed manna (with Anna Bogomolnaia, Herve Moulin, and Elena Yanovskaya)
Econometrica, 2017, 85(6):1847-1871abstract,slides (Center for the Study of Rationality 2017)A mixed manna contains goods (that everyone likes), bads (that everyone dislikes), as well as items that are goods to some agents, but bads or satiated to others. If all items are goods and utility functions are homothetic, concave (and monotone), the Competitive Equilibrium with Equal Incomes maximizes the Nash product of utilities: hence it is welfarist (determined utility-wise by the feasible set of profiles), single-valued and easy to compute.
We generalize the Gale-Eisenberg Theorem to a mixed manna. The Competitive division is still welfarist and related to the product of utilities or disutilities. If the zero utility profile (before any manna) is Pareto dominated, the competitive profile is unique and still maximizes the product of utilities. If the zero profile is unfeasible, the competitive profiles are the critical points of the product of disutilities on the efficiency frontier, and multiplicity is pervasive. In particular the task of dividing a mixed manna is either good news for everyone, or bad news for everyone.
We refine our results in the practically important case of linear preferences, where the axiomatic comparison between the division of goods and that of bads is especially sharp. When we divide goods and the manna improves, everyone weakly benefits under the competitive rule; but no reasonable rule to divide bads can be similarly Resource Monotonic. Also, the much larger set of Non Envious and Efficient divisions of bads can be disconnected so that it will admit no continuous selection.
-
Fair Division with minimal sharing (with Erel Segal-Halevi)
Operations Research 2022abstract,slides (Caltech 2021)Siblings inherited several apartments would not be satisfied by an allocation giving them an apartment with probability 50% or envy-free up to one apartment. We suggest a new approach to fair division with valuable items, which bridges the modern "divisible" and "indivisible" literature: sharing minimization. The problem of sharing-minimization among fair Pareto-optimal allocations turns out to be algorithmically-tractable for almost all instances.
Other publications in chronological order
-
Algorithms for Competitive Division of Chores (with Simina Branzei)
Mathematics of Operations Research (MOR), 2023,abstract,slides (Algorithms Seminar, TAU, March 2019)This is the first explicit algorithm for computing market equilibria of "non-convex" exchange economies that have disconnected equilibrium set. We avoid the "black-box" of Cell-Enumeration technique, used in the literature, by the novel approach based on enumeration of all the faces of the Pareto frontier via a simple 2-agent reduction. The results are applied to approximately fair division of indivisible chores.
-
Feasible Joint Posterior Beliefs (Through Examples) (with Itai Arieli, Yakov Babichenko, and Omer Tamuz)
ACM SIGecom Exchanges, 2021, 19(1):21–29abstractThrough a sequence of examples, we survey the main results of "Feasible Joint Posterior Beliefs" [Arieli, Babichenko, Sandomirskiy, Tamuz 2021]. A group of agents share a common prior distribution regarding a binary state, and observe some information structure. What are the possible joint distributions of their posteriors? We discuss feasibility of product distributions, correlation of posteriors in feasible distributions, extreme feasible distributions and the characterization of feasibility in terms of a "no-trade" condition.
-
Representative Committees of Peers (with Reshef Meir and Moshe Tennenholtz)
Journal of Artificial Intelligence Research (JAIR), 2021, 71:401–429abstractA population of voters must elect representatives among themselves to decide on a sequence of possibly unforeseen binary issues. Voters care only about the final decision, not the elected representatives. While an issue-by-issue vote by all voters would maximize social welfare, we are interested in how well the preferences of the population can be approximated by a small committee.
-
Protecting the Protected Group: Circumventing Harmful Fairness (with Omer Ben-Porat and Moshe Tennenholtz)
AAAI-21 (The Thirty-Fifth AAAI Conference on Artificial Intelligence), 2021abstractThe recent literature on fair Machine Learning manifests that the choice of fairness constraints must be driven by the utilities of the population. However, virtually all previous work makes the unrealistic assumption that the exact underlying utilities of the population (representing private tastes of individuals) are known to the regulator that imposes the fairness constraint. In this paper we initiate the discussion of the mismatch, the unavoidable difference between the underlying utilities of the population and the utilities assumed by the regulator. We demonstrate that the mismatch can make the disadvantaged protected group worse off after imposing the fairness constraint and provide tools to design fairness constraints that help the disadvantaged group despite the mismatch.
-
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation (with Haris Aziz and Herve Moulin)
Operations Research Letters, 2020, 48(5):573-578abstractIn this note, we show that Pareto-optimal and almost-fair (Proportional up to 1 item) allocations of a mixture of indivisible goods and bads always exist and can be computed in strongly-polynomial time. The technique is based on the trading-cycle algorithm for finding divisible Pareto-improvements from the paper "Fair division with minimal sharing" joint with Erel Segal-Halevi and on an extension of Barman-Krishnamurthy rounding.
-
Dividing bads under additive utilities (with Anna Bogomolnaia, Herve Moulin, and Elena Yanovskaya)
Social Choice and Welfare, 2019, 52(3):395-417abstractWe compare the Egalitarian rule (aka Egalitarian Equivalent) and the Competitive rule (aka Comeptitive Equilibrium with Equal Incomes) to divide bads (chores). They are both welfarist: the competitive disutility profile(s) are the critical points of their Nash product on the set of efficient feasible profiles. The C rule is Envy Free, Maskin Monotonic, and has better incentives properties than the E rule. But, unlike the E rule, it can be wildly multivalued, admits no selection continuous in the utility and endowment parameters, and is harder to compute. Thus in the division of bads, unlike that of goods, no rule normatively dominates the other.
-
On repeated zero-sum games with incomplete information and asymptotically bounded values
Dynamic Games and Applications 2018, 8(1):180-198abstractWe consider repeated zero-sum games with incomplete information on the side of Player 2 with the total payoff given by the non-normalized sum of stage gains. In the classical examples the value of such an N-stage game is of the order of N or square root of N as N goes to infinity. Our aim is to find what is causing another type of asymptotic behavior of the value observed for the discrete version of the financial market model introduced by De Meyer and Saley. For this game Domansky and independently De Meyer with Marino found that the value remains bounded as N goes to infinity and converges to the limit value. This game is almost-fair, i.e., if Player 1 forgets his private information the value becomes zero. We describe a class of almost-fair games having bounded values in terms of an easy-checkable property of the auxiliary non-revealing game. We call this property the piecewise property, and it says that there exists an optimal strategy of Player 2 that is piecewise constant as a function of a prior distribution. Discrete market models have the piecewise property. We show that for non-piecewise almost-fair games with an additional non-degeneracy condition the value is of the order of square root of N.
-
An exact renormalization formula for the Maryland model (with Alexander Fedotov)
Communications in Mathematical Physics, 2015, 334(2):1083-1099abstractWe discuss the difference Schrodinger equation with the potential given by cotangent, the so-called Maryland model. We obtain explicit renormalization formulas relating its solutions for large coordinates to solutions of the same equation with renormalized parameters and bounded coordinate. These formulas are similar to the renormalization formulas from the theory of Gaussian exponential sums.
-
Repeated games of incomplete information with large sets of states
International Journal of Game Theory, 2014, 43(4):767-789abstractThe famous theorem of R.Aumann and M.Maschler states that the sequence of values of an N-stage zero-sum game with incomplete information on one side converges as N tends to infinity, and the error term is bounded by a constant divided by square root of N if the set of states K is finite. The paper deals with the case of infinite K. It turns out that for countably-supported prior distribution with heavy tails the error term can decrease arbitrarily slowly. The slowest possible speed of the decreasing for a given distribution is determined in terms of entropy-like family of functionals. Our approach is based on the well-known connection between the behavior of the maximal variation of measure-valued martingales and asymptotic properties of repeated games with incomplete information.
Teaching, tutorials, and surveys
-
COURSE Algorithmic Economics (CS/SS/EC149)
20-lecture introduction to Economic Design for grads & undergrads with CS & Math background, Caltech, Spring 2022Lecture notes cover the basics of ranking aggregation, auctions, fair division, matching markets, and information design. The focus is on the interplay of CS and Econ ideas. A few easy-to-formulate, hard-to-solve open problems are discussed along the way. Suggestions welcome! -
SURVEY TALK Methods of Optimal Transportation in Bayesian Persuasion & Auctions
seminar Stochastic Analysis and its Application in Economics, HSE 2020slides
-
MINICOURSE Information in games
for graduate students at IE&M, Technion, 2020Co-taught with Rann Smorodinsky.
slides about zero-sum games with incomplete information cover both static and dynamic cases. The discussion of the dynamic one assumes some familiarity with martingales and Blackwell's approachability.
slides about Bayesian persuasion (aka information design). -
OPEN PROBLEM One open problem in Bayesian communication
open problem session at Dynamics and Information Workshop, TAU, 2020slides
-
TUTORIAL Appeal and challenges of competitive approach to fair allocation of resources
De Aequa Divisione workshop, LUISS, 2019Co-taught with Vasilis Gkatzelis.
My slides. Slides of Vasilis are available on the workshop's page. -
COURSE Introduction to mechanism design
elective for graduate students and undergrads, HSE, 2017Co-taught with Alexander Nesterov.
Slides about voting mechanisms, classic axiomatic approach, and impossibility results.
Slides about issues of fairness via the example of fair division of divisible goods without money.
Slides about the rent-division problem (fair allocation of indivisible goods with money).
Slides about algorithmic mechanism design insights (complexity of mechanisms and bidding languages, approximate guarantees as a way to escape impossibilities) applied to combinatorial auctions and fair division of indivisible goods without money.
Miscellaneous
-
RSD conjecture
Random Serial Dictatorship (RSD) is one of the most popular and intuitive ways to allocate objects to agents: agents are ordered randomly and pick their most preferred objects sequentially.
There is a high-stake conjecture that RSD is the only non-manipulable mechanism satisfying mild requirements of fairness and efficiency; for details, see my lecture notes (Section 5.5).
Here and here, you can find automatically generated proofs of this conjecture for 3 and 4 agents. Be careful, the 4-agent proof is a bit lengthy. A program on C++ generating these proofs is available by request.
-
Postdoc at the Technion: how to
Here I collected some hints and lifehacks for international postdocs at the Technion. Some hints may be relevant for international students and other Israeli universities.
The suggestions are based on my subjective experience (2018-2021). Use at your own risk and double-check. If you find something incorrect, outdated, or there is something important to add, shoot me an email or comment in the Google doc.
-
My advisors
I've been fortunate to work with and learn from many outstanding human beings whose talents, breadth, and research & ethical standards inspire me and set a high bar.
A special role was played by Victor Domansky (1944-2014) and Victoria (Vita) Kreps (1945-2021). Vita and Victor introduced me to game theory, showed me how fascinating this field is, and offered me guidance much beyond academic supervision. I miss them a lot.
You can read about Vita here and Victor, here. Victoria Kreps Memorial Prize in Game Theory is meant to support junior Russian game theorists (link in Russian). The 2021 prize was awarded to Ivan Samoylenko. The future of the prize remains uncertain at the moment.