Fedor Sandomirskiy
Fedor Sandomirskiy
Game Theory & Economics & Algorithms
Thanks to a background in mathematics and physics, I enjoy the mathematical beauty of results and get inspired by realworld applications. My research usually blends microeconomic insights with ideas from algorithmic game theory and relies on the interplay of probability, convexity, and functional analysis.
Currently, I am a postdoc at the Technion Game Theory group and a member of the Mechanism Design for Data Science group. I am also affiliated with Game Theory Lab at HSE in St.Petersburg, which I was heading before joining Technion. In Spring 2021, I am joining Caltech HSS as a postdoc.
I will be on the Economic and OR job markets 2022/23.
Contacts
Technion, office 423, Cooper building, dept. IE&M
Technion, office 423, Cooper building, dept. IE&MResearch
Working papers

Feasible joint posterior beliefs (with Itai Arieli, Yakov Babichenko, and Omer Tamuz)
Journal of Political Economy (JPE), 2021 (accepted)
EC2020 Best Paper Awardabstract,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 "notrade" 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, 2021 (accepted)abstract,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.

On social networks that support learning (with Itai Arieli and Rann Smorodinsky)
Journal of Economic Theory, R&R 2021abstract,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 Bayesrational 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.

Fair Division with minimal sharing (with Erel SegalHalevi)
Operations Research, R&R 2021abstract,slides (Caltech 2021)Siblings inherited several apartments would not be satisfied by an allocation giving them an apartment with probability 50% or envyfree 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 sharingminimization among fair Paretooptimal allocations turns out to be algorithmicallytractable for almost all instances.

Algorithms for Competitive Division of Chores (with Simina Branzei)
Mathematics of Operations Research (MOR), 2021 (accepted)abstract,slides (Algorithms Seminar, TAU, March 2019)This is the first explicit algorithm for computing market equilibria of "nonconvex" exchange economies that have disconnected equilibrium set. We avoid the "blackbox" of CellEnumeration technique, used in the literature, by the novel approach based on enumeration of all the faces of the Pareto frontier via a simple 2agent reduction. The results are applied to approximately fair division of indivisible chores.

Representative Committees of Peers (with Reshef Meir and Moshe Tennenholtz)
Journal of Artificial Intelligence Research (JAIR), R&R 2020abstractA 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 issuebyissue 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.
Coming soon
 Bayesian persuasion with mediators (with Itai Arieli and Yakov Babichenko)
 Persuasion as transportation (with Itai Arieli, Yakov Babichenko, and Omer Tamuz)
 Feasible joint posterior beliefs (through examples) (with Itai Arieli, Yakov Babichenko, and Omer Tamuz)

Optimal auctions with multiple goods and buyers (with Alexander Kolesnikov, Aleh Tsyvinski, and Alexander Zimin)
Publications

Competitive division of a mixed manna (with Anna Bogomolnaia, Herve Moulin, and Elena Yanovskaya)
Econometrica, 2017, 85(6):18471871abstract,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 utilitywise by the feasible set of profiles), singlevalued and easy to compute.
We generalize the GaleEisenberg 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.

Protecting the Protected Group: Circumventing Harmful Fairness (with Omer BenPorat and Moshe Tennenholtz)
AAAI21 (The ThirtyFifth 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 polynomialtime algorithm for computing a Pareto optimal and almost proportional allocation (with Haris Aziz and Herve Moulin)
Operations Research Letters, 2020, 48(5):573578abstractIn this note, we show that Paretooptimal and almostfair (Proportional up to 1 item) allocations of a mixture of indivisible goods and bads always exist and can be computed in stronglypolynomial time. The technique is based on the tradingcycle algorithm for finding divisible Paretoimprovements from the paper "Fair division with minimal sharing" joint with Erel SegalHalevi and on an extension of BarmanKrishnamurthy rounding.

Dividing bads under additive utilities (with Anna Bogomolnaia, Herve Moulin, and Elena Yanovskaya)
Social Choice and Welfare, 2019, 52(3):395417abstractWe 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 zerosum games with incomplete information and asymptotically bounded values
Dynamic Games and Applications 2018, 8(1):180198abstractWe consider repeated zerosum games with incomplete information on the side of Player 2 with the total payoff given by the nonnormalized sum of stage gains. In the classical examples the value of such an Nstage 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 almostfair, i.e., if Player 1 forgets his private information the value becomes zero. We describe a class of almostfair games having bounded values in terms of an easycheckable property of the auxiliary nonrevealing 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 nonpiecewise almostfair games with an additional nondegeneracy condition the value is of the order of square root of N.

Repeated games of incomplete information with large sets of states
International Journal of Game Theory, 2014, 43(4):767789abstractThe famous theorem of R.Aumann and M.Maschler states that the sequence of values of an Nstage zerosum 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 countablysupported 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 entropylike family of functionals. Our approach is based on the wellknown connection between the behavior of the maximal variation of measurevalued martingales and asymptotic properties of repeated games with incomplete information.

An exact renormalization formula for the Maryland model (with Alexander Fedotov)
Communications in Mathematical Physics, 2015, 334(2):10831099abstractWe discuss the difference Schrodinger equation with the potential given by cotangent, the socalled 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.
Teaching, tutorials, and surveys

SURVEY 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, 2020Cotaught with Rann Smorodinsky.
Slides about zerosum 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, 2019Cotaught with Vasilis Gkatzelis.
My slides. Slides of Vasilis are available on the worskshop's page. 
COURSE Introduction to economic design
elective, for graduate students and undergrads, HSE, 2017Cotaught 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 rentdivision 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.