Quantifying Inefficiency with Yannai Gonczarowski | a16z crypto Research Series

Transcript

Welcome everyone to this afternoon's uh research seminar A6Z crypto. Uh very pleased to welcome Yai Ganscarowski. Um Yianai has had more distinct chapters in his career so far than most of us I would say. Um he had a chapter as a professionally trained opera singer. Talked to him about that. Um he had a chapter as a computer scientist indeed as one of the really most visible superstars of the ECON CS area for the past decade and now he's in a chapter as an economist as a faculty member at Harvard in both the ECON and CS departments. Today he'll talk about something very near and dear to my heart quantifying and efficiency.

>> Thank you so much for this introduction. I'm not sure it's completely earned but thank you. Uh yeah, so this is joint work with Ellis Sev who's a wonderful game theorist at the Hebrew University. And I'm going to start with two slides that I'm going to ask the economists here to ignore, but this is more kind of you know making sure we we start at the same level. So let's talk about utilities for a second. So it took me quite a while to realize that computer scientists and economists actually mean two different things when they say utilities. usually, you know, giving a bit of a oversimplification of both.

Within computer science, especially within the computational social choice uh community, they think about utilities as giving additional intensity information beyond the ordinal preferences. While in economics, at least for the last 65 plus years, utilities are no more than a representation of the ordinal preferences. So you might ask, what do these numbers mean? So these numbers do not reflect intensity. They reflect risk attitudes. As an example, if my utility for alternative A is eight and for alternative B is four, it does not mean I like alternative 8 twice as much as

alternative 4. It rather means that if my utility for a third alternative C is zero, then I'm indifferent between getting B this four for sure and a 50/50 lottery between A whose utility is eight and C whose utility is zero because the expected utility here is four. So I'm a different between this four and that four. Accordingly, if my utility for A instead of eight were five, it doesn't mean that I would have liked A any less. it would still be my most preferred alternative. It would just mean that this 50/50 lottery between A and C instead of giving me expected utility 4 would have given me expected utility 2

and a half meaning that I would have strictly prefer preferred B over this lottery. So, so in economics we think about these numerical values as reflecting risk attitudes rather than so this means that I would have been more risk averse. I would have preferred the sure thing rather than the lottery. So utilities, these numbers are actually a concise representation of preferences over lotteryies via expectations. We have a number for each pure alternative. And we evaluate a lottery by taking the expected utility and comparing to the expected utilities of other lotteryies.

And you might wonder when preferences have such a nice uh concise representation. The answer is any phenoyman Morgan Stern preferences have such representation. What are these? There are four fairly standard not not um fairly standard fairly uh you know agreed upon uh in the sense that most preferences would have uh would satisfy these axioms such that if a preference uh satisfies these four axioms then we call phenomenon Morgansson preference and it has this nice representation. In particular, this representation is only unique up to an affine transformation.

If you multiply all utility values by five or you add 13 to all utility values, all of these comparisons would remain exactly the same. And this gives the next thing which is a bit of a thorn that utility numbers, utility cardinal utilities are not interpersonally comparable. If we multiply, we can multiply my utilities by 13 but not multiply Tim's utilities by anything. Either before the multiplication they were not comparable or after they weren't, but actually they never were.

You there is no way to compare my five to Tim's five, which also means that it is not particularly meaningful to sum these two fives up together. To give you one example, if you open Wikipedia under price of anarchy, the first example is of calculation of the price of anarchy. Um, so what do they say? This is a prisoner's dilemma. Uh, defect defect gives total disutility 10. Cooperate cooperate gives total disutility two. They do the ratio, they see it's five, and they say the price of anarchy of this game is five. What's the problem?

you if you add one to all these utilities you're allowed they're only unique up to an aine transformation then you need to take the ratio between four and 12 which gives [snorts] you a price of anarchy of three if you subtract one from all this utilities you need to take the ratio of 0 and 8 gives you a price of anarchy of infinity price of anarchy is the ratio between the equilibrium uh here sum of utilities and and and the uh first best And this raised the question of is the price of anarchy here high? Is it low? How do we compare this to other games? Or or you know more generally what do we learn from these numbers except that the equilibrium is

not efficient? And you know since I'm now speaking to computer scientists I'm allowed to add this slice that I usually don't add. Is it high? Is it low? Uh same text. Yeah. >> Is that literally the first example on the Wikipedia page? This is literally the first example on the Wikipedia page. Yeah. So I I should note this is not a general criticism of the concept of price of anarchy. If you read Tim's paper, you will see that he is very careful. He never talks about the sum of utilities. He talks about a cost function that is exogenously given and that is the thing that he takes the ratios of. I wish everyone were as careful as Tim. So let's >> I mean just for history like when I was first doing the price of anarchy work

twothirds of economists told me some version of your first slide. >> Yeah. So that's >> so like you're not making up a story. It's >> no no this this really is the thing that that gives the knee-jerk reaction to economists when they see these results. So today you know this is not going to be about web 3. I apologize but since we have so many wonderful interns here who are truly making a commendable effort to talk across discipline boundaries this is at the very least an example of the links that I encourage you to go to talk across these boundaries okay so really beginning of talk is now so social choice theory exists since I don't know

centuries and it usually asks how to aggregate the ordinal ordinal over lotteryies if you wish preferences of individuals over alternatives. It usually asks questions such as is alternative A society preferred to alternative B. Is alternative A society efficient meaning society most preferred among all alter alternatives? It falls short from generally answering questions such as by how much is alternative A society preferred to alternative B or how society inefficient is alternative B is it very inefficient is it 99% efficient you know there's something that's just a little bit more but really

it's it's very good so these questions are are neither attempted to be answered nor answered and what I'm going to do today I'm going to aumatically define a cardinal measure of inefficiency of alternatives that's going to allow us to ask these questions. It's going to be cardinal. It's going to be comparable across settings. Think across different games. And it's going to be cardally unique. And yet, it's going to be based solely on the ordinal over lotteryies for Morgan's certain preferences rather than the utility values. Why do this?

because I like what I call inefficiency bounding theorems and computer scientists call approximation theories theorems. These are I think an early major contribution of computer science to economics. These are not theorems that say this equilibrium or this mechanism is efficient. These are theorems that say this equilibrium or mechanism is quantifiably not far from efficient. computer scientists called the price of anarchy. Um because at some point computer scientists realized that their the input to their algorithms might be affected by incentives and they were like oh this is anarchy. So it's it's uh um you can you can like the name

you can you can not like the name but that's that's the name. Example number one of an inefficiency bounding theorem. This is my first example even when Tim is not in the audience. This is a a very rightfully celebrated paper uh from 2002 that says the commulative driving time in every equilibrium of a large class of congestion games. You know there are many cars each has an origin destination when they drive the same road they uh uh make each other slower etc. The commulative driving time in equilibrium is no greater than 4/3 the optimal commulative driving time. Right? So it means that if you could direct every single car to minimize optimal commu to

minimize the commulative driving time, if you could get it down to an hour, it means that in equilibrium it's not going to be worse than an hour and 20 minutes. This is this is interesting. It's should be compared to the you know more classic approach of you know characterizing when equilibria are inefficient or or that they might be inefficient or something like that. So this is one example. Second example is a much newer one that I also really like saying that okay so the setting is a first price auction we have independ independent biders values and we're looking at a bas equilibrium since different biders values are drawn from different distributions the

equilibrium need not be efficient but turns out that if you take the expected welfare meaning the expected value of the winner then it is no less than adequate equilibrium you do this then it is no less than 86% of the expected optimal welfare meaning meaning the expected highest value and this is regardless of the distributions that you sample from so again a very insightful inefficiency bounding theorem I should say you know 86% really is a way of saying 1 minus one over e^2 and the reason I mention this is this is tight there are actually uh uh settings meaning distribution ions for the biders

that give you 86% and no more. And I also like this example because it shows you the power of inefficiency bounding theorems not only in what they tell us but in the rapid development that they allow between papers. This started with a paper that showed 63% more than about a decade before this final result was published. that was gradually tightened over the years with more and more papers until they got to 86%. And compare this to the standard in economics which is you sit on this until you get the optimum. If it takes you 10 years, it takes you 10 years. Th this allows for much more rapid development. When your ideas stop, someone else's ideas can

start. So we have two examples. Each of them has what you might call a social inefficiency measure. One of them is the driving time. The outer one is the expected welfare. That's a social efficiency measure. And there are three properties that make these interpretable in an economic sense. One of them is that they aggregate ordinally over the individuals in a in a way that makes sense. They use minutes to sum up over different individuals or they use dollars to sum up over different individuals. And this is of course much more challenging if you don't have interpersonal comparability. This is the usual problem that has plagued social

choice for more time than any of us were alive. But there are two more problems that don't usually crop up in social choice. The first one is what we call intracontext cardinal comparability. This is the property that for each of these things 90% is twice the inefficiency loss of 95%. This is something that is challenging to do if you don't have a common unit of measure.

One example uh you can think about is uh the NAS social welfare function. If if you're familiar with that, it's it's a wellstudied well social welfare function economics going back to the 70s and before that to the 50s. You take the product of everyone's utilities normalized. So some kind of worst case is zero and there is a there are beautiful papers that show that the order induced by this is has wondrous properties.

All of these papers give axioms that show you that the order induced by this is a good order. I'm not familiar with any paper that justifies the specific numerical values. Meaning that if you apply any monotone transformation to the NAS social welfare, you take two to the power of that, you take the log of that, you take the tangent of that, you get something that is as justified by all the papers at least that I know that justify the NAS social welfare. meaning that they're talking about 90% versus 95% of the optimal NAS social welfare is much harder to interpret is much harder

to compare so this is intra context cardinal comparability and you know here I can go back to a very classic book in economics from 1957 loose and riifa and they tell us one must develop an almost inhuman self-control not to read into these numbers those properties which numbers usually enjoy. For example, one must keep in mind that it is meaningless to add two together or to compare magnitude of difference between them if they are used as indices that represent an order over certain alternatives. The only meaningful numerical property is order 1957. Next comes interontext cardinal comparability meaning the ability to compare across

different games. So for example here when we say 120% of the optimal driving time or 133% actually the optimal driving time this carries similar meaning across similar games because there is a natural reference point here. This essentially says in every driving in every um congestion game if you take instantaneous arrival as zero and you take the optimal commulative driving time and you take the difference between these two and then you take the difference between instantaneous arrival

and equilibrium. The latter is no more than 4/3 of the former. And it is this reference point that gives meaning to this measure. The same here in the auction setting what we implicitly did was normalize no trade to zero. And then we asked if you take the distance between equilibrium uh you know equilibrium efficiency and no trade versus optimal efficiency and no trade what the ratio is. And this is the thing that gives meaning to saying 86% across games.

So this is another challenge that one would have to contend with if they would want to define this in a general way. And I should note here the again from Lucen Rifa they say the non-uniqueness of the zero point is of no real concern in any of the applications of utility theory but the arbitrary unit of measure gives trouble. And I will add here that in our setting and more generally for any approximation theorem the non-uniqueness of the zero point is of a real concern as well. If you shift everything by five the optimum remains optimum the ratio between optimum and something else goes crazy.

So today the goal is to define machinery to allow us to give meaningful inefficiency bounding theorems in settings when we don't have a reference point. We don't have a common unit of measure. We don't have interpersonal comparability model. So a context is a pair. X is a finite set of alternatives and then we have n individuals and each of them has forman Morgan certain preferences over lotteryies over X. You can think about this as the set of outcomes of a mechanism or the set of strategy profiles in a game or whatever. A social inefficiency function specifies a non-

negative number. We're going to call that number an inefficiency for every pair of context and specific randomized alternative meaning uh lottery over alternatives in this context. So we can ask in this context this specific lottery over alternatives what's the inefficiency of this? I should note before the mathematicians in the audience uh uh object I know this is not a function technically there is no set of all contexts therefore this is not a function technically it's a family of functions but nothing that I'm going to do today is going to give any set theoretical issues so I'm going to call this a function and we're going to be fine with that so in this paper we aiatically define a unique social

inefficiency function it's going going to be unique up to a single multiplicative factor across all contexts. Meaning that if you multiply it by five in one context, you need to multiply it by five in all contexts. Which means that you can still compare numbers across contexts. This is going to give meaning to statements like you know you take your favorite mechanism you calculate its worst case inefficiency across a broad family of contexts and then you say no other mechanism can improve upon this worst case inefficiency by more than 28%.

For example, and we're actually going to prove this precise theorem as our application. We're going to use techniques from computer science to prove that random serial dictatorship very popular matching mechanism is approximately optimal among all truthful ordinal matching mechanisms. So no other mechanism will be able to shave more than 28% off the inefficiency of random serial dictatorship. That's going to be our application later.

>> So quick question. So yeah it's not like linear in the probabilities, right? So the function so it takes as input like a distribution. >> I'm not saying what it is yet. It takes as input a context and a rasmiz alternative and gives you a number could be linear, could be not linear or could be whatever. >> I shouldn't necessarily think of it as linear is what I'm saying as opposed to saying context, alternative with that extended to lotteryies through expectations. >> You're right. Okay. >> It's it's going to I'm going to tell you a secret. It's going to be linear, but we'll get there. So one thing that you might notice which is a cousin of Tim's question is that the inefficiency is not only of the alternative. It's of the alternative

within the context. The context matters which means that everyone's preferences over all alternatives not only this one matter. So again here we can go back to 1963. This is the second edition of Arrow's influential book. And he tells us that Gibo I'm I'm not citing Gibbo because Gibo is in French. So I'm telling you what Arrow said in English about Gibo. So Gibbo argues that a social welfare function based on individual utilities which are meaningful only up to monotonic transformations must be what is mathematically termed a functional not a function in the ordinary sense. That is each social choice must depend on the entire individual ordering. This in a sense has already foreshadowed or or

foreseen that you would need also all of the other preferences here when you talk about a specific alternative. So we have a social inefficiency function gives us a non- negative number. We call it the inefficiency. Uh lower inefficiency is better. Perhaps the most controversial thing I'm going to say today is that we allow for this inefficiency to be infinite for some context, alternative pairs. Technically, it makes life much harder for us. So, this is not a shortcut. Conceptually, I'm going to now claim that it's required to satisfy two properties that we think are mild. First one is parominicity. This is going to be one of our axioms. It says if we have

fixed some context, we have alternative A, alternative B. If everyone prefers A to B, then the inefficiency of A better be lower than that of B. If someone even strictly prefers A to B, then the inefficiency of A better be strictly lower. That is paro monotonicity. The other property, this is more of a mathful, is what we call invariance to dominated alternatives. So what's going on here? We're going to say that the social inefficiency function I satisfies IDA invariance to dominant alternatives. If whenever you take a context and now you throw out of this context some weakly dominated alternative. So everything that you thrown out is weekly

dominated by some lottery over stuff that you keep in. And then you take a look at some alternative that's a lottery over the stuff that remained. Its inefficiency in the original context and the context was stuff thrown out should be the same. The way to think about this is that usually our models model the things that we really have a trade-off between the things that we might be interested in.

They don't model points that say well the world might explode completely or you know everyone might you know uh incur some some real serious issues or whatever. So we don't want the inclusion or non-inclusion of such points to change our analysis. This is similar to the price of anarchy which takes a look at the in at the uh cost or or or gain at equilibrium and at the optimum and not at other suboptimal um inefficient points. So this is not one of our axioms. It's a desirable property than going to be implied by

them. We think it's a a property that you would want to satisfy to not depend on the choice of modeling to include irrelevant points. And I'm now going to prove to you this is going to be the only proof we're going to see today that these two together implied that you must allow for infinite inefficiency. I should note we can skip this but Arrow has already back in 1951 criticized a specific social choice function that normalizes each utility to the function to the range of 01 and then added them up that the order induced by this is sensitive to the addition or removal of alternatives that are dominated by all other alternatives and arrow says this

is extremely unsatisfactory. So this is kind of an ordinal version of our IDA. But again, the idea that this is uh undesirable goes way back. Okay. So here's the context >> intuitively just to go back to that. So just like the simple version of it, so hold some outcome fixed >> that has some inefficiency in the current context. You're saying if I throw in stuff that >> everybody likes less than this anyways, this inefficiency stays the same. Whereas if we introduce a new one that could be the new optimal then the inefficiency of this fixed alternative might go up. Right.

>> Exactly. >> Should I also think of that like monotonicity? Should I think of the inefficiency should only go up as you add more stuff. It stays the same. >> We're not requiring that. >> We're not. >> Is that going to be true for the eventual >> um if you it's it's going to be you need to say a few more words, but yes, what what you're thinking intuitively about is going to be satisfied. Here's the context. It has two alternatives, A Z and A1. I plotted arbitrary utility representations of the preferences here that only say both uh individuals prefer A Z to A1. Let's assume for contradiction that the inefficiency at A1 is finite.

Now let's add some A2. It's the least preferred and you know in these ratios that satisfy the preference over the lotteryies in by IDA the inefficiency of A1 should still be I the inefficiency of A2 therefore has to be greater than I. This is by paro monotonicity. Now let's remove A1. It is not the optimal. It is not the thing that you care about. It is something suboptimal in between. By IDA removing it shouldn't make a difference. um which means that the inefficiency of A2 here is still greater than one. Now I'd like to remind you that the utility scales are completely arbitrary. Our our

inefficiency notion only depends on the ordinal preferences. So I scale the utilities like this which means that here again you know I actually didn't change the context only the way that I draw it the inefficiency of I2 is greater than I of A2. But now take a look at this context and at this context. Um up to the change of name from A2 to A1 we see that these are the same context which means that this should have inefficiency equal I. If anyone is nervous about the last step it is by neutrality which means invariance to isomorphisms that we prove follows also from parade of monotonicity and

IDA. So we got that the inefficiency of A2 here should both be I and greater than I at the same time. So one thing we could have done is say well that's impossibility. We can have no uh social and efficiency function satisfying these two and go home. We chose to do something else. We said >> isomeorphism here is between contexts. >> It's between context. It's changing of names of alternatives within context. >> Okay. And this preferences over lottery should just be preserved under that name.

>> Yeah. Yeah. we we renamed A2 to A1. That shouldn't change anything. So what we chose to do instead is to say well let's call this inefficiency infinity which means that here we have inefficiency infinity here and infinity here even though this should be greater than this because of parto monotonicity but fine let's you know squint at it and say if both are infinity that also satisfies paro monotonicity. I should say importantly this is never an issue when individuals are not indifferent along the entire parto frontier. Here both individuals are indifferent across the entire pra frontier because the prao frontier consists of a single point.

Whenever you have a real tension a real trade-off. There is no individual that is indifferent across the entire prao frontier. You will not have this issue. you will this proof will not tell you that you need infinite inefficiency and the social inefficiency function that I'm going to define for you later will not dictate infinite inefficiency either. So it's only in this specific case of you know kind of degenerate pra preferences over the prao frontier. I think I'm going to have to skip most of the related literature. There is a lot it's beautiful goes back to the 50s.

I'll just say that to our knowledge our paper is the first that for arbitrary sets of alternatives aumatically microfounds a social welfare function that depends only on the ordinal VNM preferences over alternatives whose numeric value rather than induced order is unique and cannot be arbitrarily shifted and which can be meaningfully compared across context. We are also unaware of any paper that uses or characterizes even the order induced by our social welfare function and more related work. Okay, axioms. So we're going to have seven axioms that define our social and efficiency uh function. I know seven is a lot but you need to

pinpoint something cardally that requires work. First aim is par monotonicity. As we said, the classic version would be let this be a context for every X and Y. If X is weekly preferred to Y by everyone, then the inefficiency better be weakly smaller. If it is strictly preferred to Y by even one person in addition, then the inefficiency better be strictly smaller. And as we said the first thing, this is too strong. We need to weaken it to allow for infinite inefficiency. So we're going to say either the inefficiency is strictly weaker or they're both infinity. This turns out to be slightly too weak in the sense that strict paro monotonicity across many

many papers has the purpose of making sure the function that you're defining is not constant. And as this is defined now it allows it to be constant infinity. So we're going to slightly strengthen it's still weaker than what's written in in white here to make sure it doesn't allow for that. So we're going to say either inefficiency at X is less than at Y or they're both the same but there exists another alternative that everyone likes better than X that has finite inefficiency. So we don't allow for infinite inefficiency across maximal chains ordered by paro dominance. So

this is kind of a right in between axiom but overall I would like to still emphasize this is still weaker than what we started with. So if you like what we started with you should like this two anonymity. If we permute the identity of the players. So we permute the numbers uh whoever was individual one is now five or was five is now three etc etc. We don't change the inefficiency of any alternative. So so far for ordinal aggregation let's move on to intracontext cardinal comparability. This is to your question Tim. We have an axim we call it expected inefficiency kind of a nod to expected utility saying that if you have two

lotteryies and you randomize between them with probability alpha then the inefficiency of the lottery is the expected inefficiencies at the thing you randomize between. So this is the linearity that you were asking about. There are two ways to interpret this. One of them is saying that the social aggregation of inefficiency is riskneutral. So it's saying we don't artificially impose any risk attitudes for society when aggregating over the individuals. The other one is noting that one of our main use cases that's going to be our application is quantifying the social inefficiency of the outcome of randomized mechanisms.

And this says that the social inefficiency of a randomized outcome is the expected social inefficiency of the realized outcome. So this is our third axum. Fourth axum is you cannot not have an IIAa axiom whenever you aimatize something. So this is uh independence of irrelevant alternatives. So usually IAA looks like this. You have a context. You take a look at the context C prime with you know over a subset of the alternatives. So you drop some stuff [snorts] and you say if these share some property you know have the same indifference point have a same disagreement point whatever whoever has seen such papers

know what I'm talking about. uh if they share some property then for every two alternatives if the inefficiency of one is lower than of the other in one context it should be lower than the other in the other context as well. So we need to understand what share some property should mean here. We don't have any disagreement point here unlike you know bargaining the bargaining literature. We don't have this is a direct quote from the paper that defines the national social welfare function. We don't have a distinguished alternative which represent one of the worst states for all individuals. For example we may imagine that all member of society die.

We just said we don't want to artificially have to include this kind of writtenness in our model. So we need to do something else here. Fortunately, Al Roth before he was a matching guy, he was a bargaining guy and he looked at IAA with respect to other reference points, not the disagreement point. In particular, he looked at two endogenous points. One of them he called the ideal point. It's an imaginary alternative in which every individual receives as much utility as in her ideal alternative. So formally two contexts have the same ideal point if each individual is indifferent between their favorite alternative year and their favorite

alternative year. And he looked at the point of minimal expectations which is an imaginary alternative in which each individual receives as much utility as in her least preferred undominated alternative. So again two contexts have the same point of minimal expectations if for each individual their least preferred undominated alternative here is this. you know, they're indifferent between their least preferred uh undominated alternative here and their least preferred undominated alternative here.

>> So, are these just sort of saying like X-rime includes the right stuff basically? >> No, these are saying um >> like the ideal point I feel like you're saying in X prime should be >> if you remove stuff in a way that doesn't change the ideal point or the point of minimal expectations thing certain properties should hold. So really what we're saying here is if C and C prime have the same ideal point and same point of minimal expectations this better hold. This is going to be our axiom. And note that the more points that I put here the weaker the axum becomes because the there are less pairs CC prime for which this axiom has bite.

So I include we included everything all the endogenous points from Roth 77. The last thing >> I am a little confused because the word utility appears in these definitions. Sorry, the word utility appears in these Roth definition. >> Yeah, but but it as I now phrase it, you don't need the world the word okay >> utility. You can say indifferent between their favorite here and here or indifferent between their favorite their least favorite and dominated here and here. >> So like for example, you pick some player, you say what's your favorite in X? So you would like to see that same alternative appear in X prime >> or or something uh equivalent to that if they have several favorites. Yeah.

>> Last thing I'm going to want to turn this into a cardinal rather than ordinal axum. So instead of saying in this case X is society preferred to Y and C prime if and only if in C, we're going to say X is societally preferred to Y and C prime but the same amount that it is societally preferred sorry X is societally preferred to Y and C prime but the same amount that it is societally preferred to Y in C. So this is the cardinal version of IIA. And just to show you that I'm not cheating in any way, we're going to say whenever neither of the sides is infinite minus infinity,

if one of these is infinity minus infinity, the axum has no bite. So I'm not cheating here with infinities. So this is IA axum five almost there. Independence of irrelevant preferences. So what is this? So this is so axiom 4 was about comparison across two different contexts with the same individuals. This is going to be comparison across contexts with different individuals. So we're going to have a context C and two contexts D contexts D and D prime over the same alternatives with the same number of players but different

preferences. So you can think about M people here and M different people here. And we're going to talk about the composed context C composed D. What does this mean? It means putting the context side by side thinking about them as a single big context. So the alternative set is going to be X pure alternative set is going to be X cross Y. So each alternative is a pair of what the first context gets and what the second context gets. There's going to be n plus m alternatives individuals. So sum of individuals. The first n individuals only care about the marginal over x. The second m alter the last m alternatives only care about the marginalss over y.

This is for whomever knows the definition of phenomenon of composition of games. This is exactly the same thing but not for games for contexts. So we're going to say the following. take the same one alternative in Y and two alternatives X and X prime in X and we're going to say in C composed D if you take a look at the at the difference in inefficiencies between XY and X prime Y and in C composed D prime differentives over the Y component you take a look at the difference between XY and X prime Y these should be the Aim.

What's the idea here? The idea is that we have not changed the y component. So, preferences over the y component should not change this difference. We only changed the x component from x to x prime. And the preferences over the x component are the same. So, the change in inefficiency should be the same. And again, if one of these sides is infinity minus infinity, this axiom has no bite. So this is about comparison across contexts with the same number of different individuals.

N plus M here, N plus M here, but different M. Finally, we have duplication. This is for comparison across contexts with different numbers of alternatives. So let's take a context C and let's take a look at the kwise self-composition of C with itself. So we take K independent copies of C. We self-compose them. So we take K copies of C, put them side by side, take a look at them, treat them as a big context.

And we take some two alternatives X and X prime. And we say the difference between the inefficiencies of all X here and all X prime here should be the same as the difference between the inefficiencies of X and X prime in the original context. This is an axiom that says we don't want things to the inefficiencies to blow up artificially just because we're duplicating or to diminish just because we're duplicating. This is an axiom that says our inefficiency notion should be some sort of a per capita notion. I'm not saying if it's a uh u arithmetic average or geometric average or harmonic average or whatever

but should be some kind of per capita measurement. This is what this axum says. This will allow us to compare contexts with of different sizes and have meaningful comparison. And again if one of these is infinity minus infinity this has no bite. Final axum is the shortest axiom. It says in every context there should be some alternative that has zero inefficiency. There should be a best thing in every context not saying what it is should just exist. So these are five axioms. For ordinal aggregation we have paralom monotonicity andimity.

For intracontext cardinal comparability we have expected inefficiency. For intercontext cardinal comparability, we have IIA, IIP, duplication, and feasibility characterization. This is our main result. It says there exists a social inefficiency function I hat. I'm going to show you what it is soon enough such that the following holds. Any social inefficiency function I that satisfies our seven axioms. Or rather any social inefficiency function I satisfies our seven axioms if and only if it is a constant finite positive constant times I hat. So this means that our seven axioms uniquely characterize a

social inefficiency function up to a single multiplicative constant across all contexts at the same time. If you multiply in one context, you should multiply in all contexts. So you can sh still compare ratios of inefficiencies across different contexts. And let me show you what I hat. Oh, furthermore, and this is where we pay for having seven axioms, dropping any of these seven axioms invalidates this statement. So for every each one of these seven axioms, we have an example of a social inefficiency function that satisfies the other six but does not satisfy this theorem. So

none of our axioms is redundant. They're logically independent for people who like uh >> for that axiom where you needed to have both of the Roth notions. Can you prove can you prove you need both? You remember the >> if if you put only one it strengthens >> if if you have only one there it strengthens the aim. So that that is >> is [clears throat] an or is an and in that >> it's >> it's an and if C and C prime have the same ideal point and the same >> point of minimal expectations only then this aim says something.

>> Yeah. So so we threw in all of the endogenous you know points from the bargaining literature into that axum to make it as weak as we know. So here's our construction for iH. So let C be any context and and pick some utility representations. We're going to see that the calculation that follows does not depend on this choice denote by FC the paro frontier of C. So this is the let for each I for each individual I let UI max be their maximum utility across the paro frontier. UI min be their minimum utility across the prao

frontier. And now we're going to define what is this? This is the per capita meaning average sum of normalized utilities normalized so that each utility number is normalized to have minimum zero and maximum one along the paro frontier. So we normalize each utility function to have minimum zero maximum one along the paro frontier. And then this is a social welfare function that is utilitarian. It averages the utilities at the alternative that we're talking about.

And then we define our inefficiency as looking at this thing finding its maximum. Let's call that zero. And then our inefficiency is loss in this measure compared to optima. Let's do an illustration. So here's a context with some utility representation. We start by finding the maximum and minimum for each individual across the paro frontier. This is one's favorite point. This is one's least favorite point on the paro frontier. This is two's favorite point. This is two's least favorite point along the paro frontier.

So now this is the normalized unit of one's utility function. This is the normalized unit of two's utility function and we average them. So this is 1 zero. This is 0 1. So each of them has average half. This is V equals 0. This is V equals 1. And which means that this is the unit of V. This is the maximum of V across all alternatives in the context. So we call this IAhat equals Z.

And then we count back from zero in the units of V. So if this was the unit of V, this is the unit of Ihat. And this is the line of Ihat equals one. This is inefficiency one. This is in efficiency a bit more than one. These are between 0 and one. This is the only social inefficiency function again up to this constant. You know, you could normalize this to be a half unit and this to be a half unit. this you know this would mean multiplying everything by um by one half but that's that's the only degree of freedom you have and you need to normalize in the same way across all individuals across all contexts. So this

is the only thing that satisfies our seven axioms. Going one last time back to arrow. So arrow says as it stands the sum of individual utilities seems to be excluded by the entire nature of the present approach since we agreed to reject the idea of cardinal utility and especially of interpersonally comparable utility. However, presumably the sum utilities could be reformulated in a way which depends only on the individual orderings and not the utility indicators. The only way I can see of making the sum of utilities depend only on the indifference locai meaning the uh um the uh equivalence classes of uh utility functions is the

following. Since to each indiv each individual ordering there corresponds an infinite number of utility indicators, set up an arbitrary rule that assigns to each indifference map one of its utility indicators. arbitrarily choose consistently for every pre uh for every preferences always the same utility function then the sum of particular utility indicators chosen by the rule is a function of the individual orderings and can be used to establish a social ordering. So to some extent this is what we do except that the thing that we have that for each preference order chooses a specific utility representation is not an arbitrary rule. It is the unique rule

that follows from our axioms. I think we can skip >> go back to the construction of just the definition of the function. So just um so when you have a degenerate par frontier >> so when we have a degenerate you define by zero that's exactly when you get the infinities we talked about so so you get so this is what we have in this slide. So we can say that an individual I is frontier indifferent if they're frontier along the entire per frontier. These are exactly the individuals for which you divide by zero and you get infinite inefficiency if and only if this point is strictly less preferred than the paro frontier by a frontier indifferent

individual. This is if and only if. So along the prao frontier you always have finite inefficiency but for points that for alternatives that are strictly preferred less than the paro frontier by a frontier indifferent individual you get infinite inefficiency that's the only case >> I see. But so if you have a full paro frontier you said this earlier then everything's finite. >> Yeah. So if you if you have if no one is indifferent across the bra frontier which is usually the case because we model trade-offs we don't model you know then then then everything's fine. Okay application so for our application we go to a setting where we have no transfers no outside options

not only there are no monetary transfers but it's repugnant to compare or measure using money. If you go to some uh to city hall and you tell them I want to allocate students based on how much they would have been willing to pay to get to that school if you would have charged them they would you know throw you out very very quickly. So it's a context in which you it's repugnant to even measure using money which means that interpersonal comparison is very challenging. meaningful precise cardinal values for utilities are very challenging to justify and we're going to talk about a setting with no outside options as I said so n we're going to have n individuals n objects each person

must get an object there is no option of staying without an object meaning that you cannot say we're normalized so that being without an object is utility zero or anything like that and this is going to be our context so I think we can skip these but We're going we're going to say an ordinal mechanism is a mapping from profiles of strict rankings over the n objects to distributions to uh randomized matchings. So an ordinal mechanism is something that gets orders over objects and outputs randomized matching. We assume I skipped that in the previous slide. We assume everyone has strict rankings over objects.

An ordinal mechanism is truthful if truthfully ranking the objects is dominant in the induced game. And for a truthful mechanism mu, we're going to denote by this the outcome at the truthful ranking equilibrium. Random serial dictatorship is a truthful ordinal mechanism that's used abundantly for assigning housing units by governments, by colleges, internships, school slots, whatnot. And it works very simply in uniformly random order over individuals. It matches each individual to the not yet matched object ranked highest on her report ranking. So you know we draw an order. First is Tim. Tim

picks his favorite. Then his favorite is gone. Next is Yuval. He picks the his favorite among those that Tim has not yet taken, etc. And I don't only say that it's used abundantly in other places. This is also how we assigned offices in the new economics building at Harvard. You see that these are the people already picked and now it's Matthew's turn to pick his office among the remaining ones. By the way, we're thrilled to have uh Leonagel join us uh in the fall.

um theorem. There does not exist any truthful ordinal mechanism that whose worst case inefficiency over all matching contexts is better than about 72% of the worst case inefficiency of random serial dictatorship taken worst case overall matching contexts. So I should note that saying s worst case inefficiency across all contexts is meaningful only because we have intercontext comparability for i hat and saying this comparing this with 72%

of this is only meaningful due to the cardinal nature of ihat the correlary is that for every social inefficiency function that satis satisfies our seven axioms. There is no truthful ordinal mechanism that shaves more than 28% off the worst case guarantee of random serial dictatorship. And this should be compared to a well-known Xanti inefficiency result for random serial dictatorship. So we're kind of showing here well we know it's x anti inefficient but it's actually xanti approximately efficient which kind of you know explains why it doesn't perform very poorly and the

proof this was the easy part for us we adapt proofs from this wonderful paper that bounds the price of anarchy of random serial dictatorship. So they take a look at the asmtoic order of magnitude of the ratio between the optimal and realized sum of utilities as the number of objects go large. We take a look at the difference. We don't do asmtoics. But the hard parts of the proof are really you know the most naive translation you can think about from their paper. So we think about this as also a proof of concept that price of anarchy results can be translated with not a lot of effort into results about our social inefficiency function. Uh

they do this with the assumption that utility functions are exogenously normalized to 01. We make no assumptions about exogenous normalization. So what did we have here? We had a cardinal social inefficiency function. Its numeric values not only the order are uniquely defined. We demonstrate the applicability of the aimatic approach for microfounding economically meaningful quantitative comparisons of efficiency. You know maybe there are other axioms to do this better axioms. I would love to see follow-ups on that. Our utility is in units of the diameter of the utility functions range over the prao frontier for frontier and different individuals.

those that we talked about. We satisfy the axioms using a degree of freedom that we don't usually get in the social choice literature, but we do get with uh the cardinal approach, which is kind of saying these two are so bad that we're going to squint at them and say they're the same. They're both infinity rather than saying, you know, which is better, which is worse. Inefficiency bounding theorems allow us for gradual progress over papers. We didn't try to improve this one over two land two. what came when we translated in kind of a naive way the proof from the u price of anarchy of RSD paper. Maybe this could be improved. What about other applications? What about bargaining?

Instead of disagreement point, we have kind of an agreement region. Uh management science textbooks call talk about framing bargaining with respect to a zone of possible agreement. Maybe there's something there. I don't know. And what about micro foundation for other approximation theorems? Something like some quantity is at least a specific fraction of some other reference quantity. What about fairness? Approximate fairness. Uh you know axiomatize uh quantitative fairness in equity cardinal comparative statics. Instead of saying when this goes down this goes up say when this goes down this goes up by a certain function of what happened

here. So these are all uh exciting future directions and I'll stop here and thank you all >> just a very basic uh kind of sense check. So if I take a context and I rescale the VNM utilities of the players by an aine transformation the C that you would obtain would be distinct across just fixing the set of alternatives the set of lotteryies but what what is if as I rescale VNM index >> okay so you you you rescale these then the I hat that I calculate is going to be exactly the same. Why? Because I'm going to just put the formula back up on the

>> Yeah, I'm going to put the formula back up. >> I see. Because it's the I'm the max versus the min and in the >> Yeah, exactly. So, so then I'm going to reenormalize. >> I'm going to normalize between zero and one regardless of how you scale. I'm going to renormalize to the same thing. The the C only comes in in, you know, if you normalize so that this is half a unit and this is half a unit. And in all contexts you normalize. So this this is half a unit and this is half a unit. You also get something that satisfies our seven axioms which is exactly two times um which is exactly sorry it's exactly half um of our I hat. So so you the only degree of freedom you have is to what

what is the size of the thing you normalize to here and here. But you need to normalize to the same amount across all individuals across all contexts. So it's only a m multiplicative factor. And as we saw in the application here so you know you take any i. So you can multiply by 13 here and by 13 here. But the you know it cancels out because it's a positive finite constant. >> If you look maybe a couple related questions. So like you could you could ask about having a function for a restricted class of contexts.

>> Mhm. >> Where maybe you'd have more than just this unique one perhaps. >> Yeah. >> And then relatedly would be like if you go to your motivating examples at the beginning like the selfish routing games and >> uh you know kind of welfare maximizing mechanisms like you don't you don't recover those functions. >> No I don't recover those but th those are settings in which you have extra information that our contexts don't have. So I'm not by any way saying don't use extra information if you have it but sometimes you don't have it >> right. So what I'm saying is there may be like this rich intermediate region where >> I'm thinking of as like a restriction on the context if you like additional structure [clears throat] on the context >> where you maybe could then characterize you know the family of reasonable sort

of functions to think about. So okay >> maybe yeah this is for all contexts and we use in our proof the ability to jump between contexts and stuff like that. So yeah if if you restrict certainly you can get more would be interesting to see what you get there but but again you know I'm not saying so you know you could I think that doing price of anarchy for driving time is great. I think you know you you might want to do it with you know scaling B you know uh so that zero is instantaneous arrival like in your papers someone else might want to do it so that zero is arrival as if the roads are empty that's a different zero gives

a different thing so you know different different applications have different extra information that give you that they give you about what's what are reasonable points to ground yourself. This is a study about what if you have none of that showing that you can still do something. >> So for this two log two does that have any interpretation beyond if I proved the theorem for a smaller number that I have a tighter bound or is there some >> say say it again. >> So so for the two log two in this theorem >> does have any interpretation beyond if I prove the same theorem with like a smaller constant there that that's a tighter bound or is there an explicit interpretation of what two log 2 means?

No, two two two log two is what we got when we when we plugged in the the the proof from the um the the price of anarchy of RSD paper but uh you know we think 70% is a pretty good approximation but I I don't have any reason to think this is tight or >> or I guess like uh is there a interpretation to what 70% means here with >> I I don't have one if you have one I' I'd love to know >> to be specific here if we are able to show one by log two. It is like literally a twice improvement. That's the entire point that we're trying to make here.

>> If you're you can show one over >> log two for instance >> or one over log two is more than one. >> If you do one by four, okay, that's tighter. Okay. If if you can prove 80% instead of if you can prove uh um if you can prove 86% for example would that be a >> it will close half of the g half of the it will instead of bounding by this. Yeah, it will somehow cut by half the distance between um it will cut by half the thing you can shave off.

So this says some other mechanisms might be able to shave off 28% of of the worst case guarantee of ine of the worst case inefficiency. If you prove uh 86% it means that the you show that no other mechanism can shave off more than 40 14% off the worst case. So it will be um a sense of a of a two times improvement. Yeah. Thank you so much.