14 ms·

The Price of Anarchy

120 points by beefman 10y ago

schoen 10y ago
That has the most math notation of anything I've seen written about anarchy in some time!
- quotemstr 10y ago
  Math is important. It tells us the shape of the possible. Game theory tells us when we're creating an unstable set of incentives. Our intuition for fairness is only a crude approximation of game theory. Societies and their moral systems (there's little difference) don't come out of nowhere. Sentiments like "game theory is just capitalistic ideology" make me sad. Math, like all sciences, is true whether you accept it or not.
  - CaptainSwing 10y ago
    it may be 'true' within the set of axioms on which it rests, but 'wrong' in that those axioms (rational self-seeking behaviour, etc) don't hold in reality. More, those axioms themselves could be reflections of capitalist ideology.
  - brbrodude 10y ago
    That does not mean it's infallible. Basically, Nassim Taleb stuff. We're wrong all the f*ing time and the more confident and blinded by our models we are, the greater are the effects of our screw ups, there IS such thing as hubris, we've known it long before but it's too abstract to constantly take it into consideration, so we just stop minding. It has happened countless times and there's little evidence we've been able to tame our cognitive blind spots at all, we're just humans, after all.
  - schoen 10y ago
    I didn't mean to disparage the math by my remark. I think it's interesting and I look forward to understanding it.
- automatwon 10y ago
  some time There was a time you've seen more math notation written about anarchy? I'm curious. It'd be great if you can link.
  - schoen 10y ago
    I think I meant that as a joke, so I've probably never seen more. Sorry to get your hopes up!
madmaniak 10y ago
"In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time" That's a wishful thinking. Central authority can and usually is selfish and corrupted but the impact of it is much bigger. So we can call this piece of math a science but voting for centralized systems based on that is super naive.
- madmaniak 10y ago
  I see my comment is not well received. Who will explain me why we assume that a single unit is selfish, but a big one contained of many selfish units is altruistic?
  - grive 10y ago
    You assume the central planner to be the same as a single unit (as in, of the same kind, the same species). Who is to say that the central planner must be the ontological equal of a single unit? Why not a more complex system? You could have for example a quorum of single-unit who will need to reach a consensus concerning their diverging self-beneficial impetus. You can also imagine, if you represent the interest of each single unit as a vector in some kind of space, that the quorum must navigate a product of those vectors. You can imagine an AI then, a machine exploring that vector space that could learn to balance the wants and needs of its single units. Et cætera. I don't know exactly why you comment was not well received, I am not able myself to downvote comments here and I did not do that, but my own opinion about yours was that it was basing itself on some assumptions that were biased by some real-world considerations that were irrelevant for the concept presented.
    - madmaniak 10y ago
      Thank you for your reply. "Who is to say that the central planner must be the ontological equal of a single unit" My impression is that's what most people here are discussing. I can see a definition of an anarchy in your quorum example, can't you? But you say we could have AI which will find a balance. Interesting concept. Does it imply obeying AI <=> obeying the law?
clydethefrog 10y ago
Already in the first line it claims that anarchy is a system wherein >a system degrades due to selfish behavior of its agents To my point of view, most game theory is just capitalistic ideology disguised in mathematical models.
- TeMPOraL 10y ago
  If anything, this sounds anti-capitalistic - capitalism is based on an assumption that selfish behaviour of individuals produces greater good for the society.
  - automatwon 10y ago
    "It is not from the benevolence of the butcher, the brewer, or the baker that we expect our dinner, but from their regard to their own interest" - Wealth of Nations, Adam Smith I tend to think of self-interest being equivalent to selfishness. Your point makes me wonder if self-interest is not equivalent to selfishness, at least to Economists.
    - TeMPOraL 10y ago
      Well, what you quote is true, but I think a lot of discussion stems from focusing on the wrong question, namely "does selfishness lead to better outcomes" as opposed to when it does, and when it does not. Too many people seem to approach economy as an ideology rather than a complex system in which a given approach produces good results here and bad results there, and everything should be subject to optimization and careful design.
      - JumpCrisscross 10y ago
        > Too many people seem to approach economy as an ideology rather than a complex system Few of these people have any decision-making authority. This mass ignorance of economics does occasionally bubble up on the policy side. But it is generally, at least in the United States, contained by more knowledgeable (and influential) parties.
wodenokoto 10y ago
Isn't libertarian thinking (put very heavily on the edge) the exact opposite? That a system will become more efficient if actors are let to do things for their own sake, and that actors are smart enough to calculate the negative impact of short term selfish action (that is, actors can help out now, with an exception of a positive roi)
- SonOfLilit 10y ago
  This assumes a theoretical optimal central planner, a superintelligent BDFL of sorts. Libertarian thinking is that in practice humans are so bad at management that every time we tried central planning it came up even worse than non-optimal Nash Equilibria (which are the failure mode of non-centrally-managed agent systems.) Libertarians would say that no dictator or government in history turned out to know better than The Market. That The Cost of Regulation is higher than The Cost of Anarchy. Of course, both costs are high for some problems and low for others, and the solution to practical problems usually lies at neither this extreme nor that one.
- adgasf 10y ago
  Some Libertarians are non-consequentialists. They argue that even if the outcome is less efficient, there are moral reasons to oppose central planning. What is interesting is that many argue both points: that markets are more efficient and morally superior. A good example of the distinction is David D. Friedman (consequentialist) vs Ayn Rand (non-consequentialist).
- em3rgent0rdr 10y ago
  Libertarian thinking actually permits multiple people to agree to not take the most immediately greedy action and to instead voluntarily agree to a mutually-beneficial optimal solution.
deleted 10y ago
[deleted]
CaptainSwing 10y ago
I think that this is a really interesting concept, but dislike the name. All social anarchists (anarchist-communists, anarchist-syndicalists, even mutualists etc) would see anarchy as a social process rather than a purely individualised "every man for himself" system. It disregards the possibility for non-coercive collective forms of decision making. but, saying this, a concept that discovers the loss in a system where each actor is purely self-interested is useful and interesting.
- ue_ 10y ago
  I talk with a lot of anarchists and perhaps the only ones of them who are truly in the spirit of "every man for himself" are an-caps and Stirnerists.
  - Proven 10y ago
    I don't think ancaps are all like that. You can't run business if you don't serve your customers well. Does that translate into pathological selfishness and other extreme behavior that goes in customers' nerves? I don't think so, because such business wouldn't last long. I agree with the GP post above, and I'd also like to point out the idiocy of the "scientific" assumption from Wikipedia that "central planners" have superior information compared to self-interested agents who follow their own optimization strategies. F. A. Hayek is one of best authors on this topic.
    - ghgfhgfhn 10y ago
      I was bracing myself for comments that either missed the point entirely or low brow attempts to dismantle the piece. I am surprised and happy to find an intelligent discussion! It's becoming rarer on hn.
    - ue_ 10y ago
      >You can't run business if you don't serve your customers well. Serving your customers well is entirely out of self interest, especially in large corporations; in fact, this is the easiest example of "every man for himself". You serve your customers well because ultimately it brings you more profit. Sure, it's not as sure sighted as screwing over every customer, but people who are selfish aren't necessarily stupid. I would argue that the very act of running a business in such a society is not only wrong due to the exploitation of workers, but also the motivation underlying (almost) every transaction in which your goal is to sell things in such a way as to get yourself the largest profit. Of course that doesn't happen in real life. People have moral standards. I think I'm just a cynical ancom with regard to how people would really behave in the absence of all regulation. Let's not forget what large companies can still get away with today, and imagine what it would be like with anti-competitive monopolies, oligarchies, and two or three organisations controlling mainstream information sources. So sure, your business doesn't last long because you were too obviously selfish. Your next plan of action is to pay a news outlet (or better yet, already be in control of one) to cover you. Or if you can't do that, there's still hope - you can band together with like minded people and start another business. Not without worker exploitation, of course. You need all the surplus value you can get. I simply do not have the hope that "serving your customers well" is enough to prevent what actors in a capitalist system are truly capable of doing. Let's not forget the sheer paradoxical nature of "anarcho-capitalism" (the inherent class system set up of the bourgeoisie and proletariat is the exact opposite of non-hierarchical relations). I'm not really a proponent of central planning myself, so I agree with you on that.
inlineint 10y ago
This submission seems to be a kind of follow-up to the one about Braess's paradox (https://news.ycombinator.com/item?id=13352513 https://news.ycombinator.com/item?id=13352513).
- cardiffspaceman 10y ago
  I have seen clusters of posts and have not had the time to study: Are they a dialog between unrelated people who share an interest in a topic, or is one person pursuing a theme?
bo1024 10y ago
I just want to mention that many commenters here are reading much more into the name politically than do the game theorists/computer scientists who actually do research on it. The research is focused on the game theory and not meant to make any sort of political points or value judgement. The main question asked is how to design systems so that even in a game-theoretic equilibrium, the total "welfare" is close to the best possible.
- throwaway729 10y ago
  What you are saying is true and crucial to understand. The same observation applies to a lot of named concepts in academia (in voting/game theory and economics especially). However, I also think that results in these fields can be useful in political discussions, as long as they're used as thinking devices rather than arguments in and of themselves. The map is not the territory, but "price of anarchy" is a suggestive name. The name suggests, purposefully or not, that this set of mathematical results about an abstract game theoretic model might be useful to hold in mind while thinking about political systems. And I don't think that's necessarily a bad suggestion.
- danharaj 10y ago
  Having no intention to be political just means they uncritically reproduce aspects of the ideology they passively go along with. Associating anarchy with Bad Things was a deliberate government program to suppress its movements(quite popular at the turn of the previous century). Now people do it reflexively and that is very much political. The political is not merely intent.
- sebastos 10y ago
  Ding ding ding. The Price of Anarchy originally described the surprising result that internet routing seems to work despite the lack of a central planner. [1] The "central planner" is a theoretical maximum for the routing problem - it represents an oracle that automatically knows and applies an optimal routing solution. It's not some kind of government. It's kind of hilarious seeing all of these people commenting about how this is "utopian" thinking, ancap-blah-blah, and "who says the central planner would be just?" People read what they want to read, I suppose. If you do want to read something interesting about the price of anarchy, check out this other paper [2], written by one of the original authors, which shows that the PoA = 1 (that is, there is no cost) when there are private "owners" of the edges in a routing network who are allowed to charge a "toll" for traversing that edge. Makes you wonder if a globally-standard-but-locally-owned electronic tolling system could replace gas taxes to fund our roads in a fairer way. This could remove the undue toll burden shouldered by certain unlucky people who have to commute across a heavily tolled bridge. (Seattlites should know what I'm talking about). [1] http://www.cs.yale.edu/homes/jf/poa.pdf http://www.cs.yale.edu/homes/jf/poa.pdf [2] https://people.eecs.berkeley.edu/~christos/papers/selfishrouters.pdf https://people.eecs.berkeley.edu/~christos/papers/selfishrou... [3] http://theory.stanford.edu/~tim/papers/routing.pdf http://theory.stanford.edu/~tim/papers/routing.pdf
tehabe 10y ago
Incomplete models are incomplete. It completely ignores the ways on which the mentioned transport should take place. It ignores that you usually don't have one place from which everybody starts but multiple places to other multiple places. And if you think about it, individual car mobility is this in practice. The ways are build by someone else but you can decide how and where to drive. And it kinda failed in many areas.
- alimw 10y ago
  It's not clear what you are referring to. The section on Selfish Routing begins with Braess's Paradox but swiftly moves on to a Generalized Routing Problem which appears to address your concerns.
wyager 10y ago
Wow, people are really running away with the political analogy used here. Calm down folks, they're not ragging on decentralized systems. If you read and comprehend the definitions in the article, you'll see that it's a fully general solution that allows for emergent organization through market systems or cooperation. You can bake those things into the strategies and utility functions of the actors. It's just a fun and descriptive name for the difference between an idealized central controller (which can force everyone into a configuration that maximizes an arbitrary global utility function) and the lack of such a controller. The outcomes could be the same, they could be different. If you factor in the negative utility of having the central authority in the first place, you can game-theoretically justify your particular favored level of anti-authoritarianism.
johngalt 10y ago
Think of it as structured vs unstructured if you can't avoid gettng hung up on the name. Basically this is talking about the net difference between what is locally optimal and globally optimal in a multi agent system.
- hyperbovine 10y ago
  an ("without") + arkhos ("ruler"). Seems like a fine name to me.
deleted 10y ago
[deleted]

120 points by beefman 10y ago

schoen 10y ago

That has the most math notation of anything I've seen written about anarchy in some time!

quotemstr 10y ago
Math is important. It tells us the shape of the possible. Game theory tells us when we're creating an unstable set of incentives. Our intuition for fairness is only a crude approximation of game theory. Societies and their moral systems (there's little difference) don't come out of nowhere. Sentiments like "game theory is just capitalistic ideology" make me sad. Math, like all sciences, is true whether you accept it or not.
- CaptainSwing 10y ago
  it may be 'true' within the set of axioms on which it rests, but 'wrong' in that those axioms (rational self-seeking behaviour, etc) don't hold in reality. More, those axioms themselves could be reflections of capitalist ideology.
- brbrodude 10y ago
  That does not mean it's infallible. Basically, Nassim Taleb stuff. We're wrong all the f*ing time and the more confident and blinded by our models we are, the greater are the effects of our screw ups, there IS such thing as hubris, we've known it long before but it's too abstract to constantly take it into consideration, so we just stop minding. It has happened countless times and there's little evidence we've been able to tame our cognitive blind spots at all, we're just humans, after all.
- schoen 10y ago
  I didn't mean to disparage the math by my remark. I think it's interesting and I look forward to understanding it.
automatwon 10y ago
some time There was a time you've seen more math notation written about anarchy? I'm curious. It'd be great if you can link.
- schoen 10y ago
  I think I meant that as a joke, so I've probably never seen more. Sorry to get your hopes up!

madmaniak 10y ago

"In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time" That's a wishful thinking. Central authority can and usually is selfish and corrupted but the impact of it is much bigger. So we can call this piece of math a science but voting for centralized systems based on that is super naive.

madmaniak 10y ago
I see my comment is not well received. Who will explain me why we assume that a single unit is selfish, but a big one contained of many selfish units is altruistic?
- grive 10y ago
  You assume the central planner to be the same as a single unit (as in, of the same kind, the same species). Who is to say that the central planner must be the ontological equal of a single unit? Why not a more complex system? You could have for example a quorum of single-unit who will need to reach a consensus concerning their diverging self-beneficial impetus. You can also imagine, if you represent the interest of each single unit as a vector in some kind of space, that the quorum must navigate a product of those vectors. You can imagine an AI then, a machine exploring that vector space that could learn to balance the wants and needs of its single units. Et cætera. I don't know exactly why you comment was not well received, I am not able myself to downvote comments here and I did not do that, but my own opinion about yours was that it was basing itself on some assumptions that were biased by some real-world considerations that were irrelevant for the concept presented.
  - madmaniak 10y ago
    Thank you for your reply. "Who is to say that the central planner must be the ontological equal of a single unit" My impression is that's what most people here are discussing. I can see a definition of an anarchy in your quorum example, can't you? But you say we could have AI which will find a balance. Interesting concept. Does it imply obeying AI <=> obeying the law?

clydethefrog 10y ago

Already in the first line it claims that anarchy is a system wherein >a system degrades due to selfish behavior of its agents To my point of view, most game theory is just capitalistic ideology disguised in mathematical models.

TeMPOraL 10y ago
If anything, this sounds anti-capitalistic - capitalism is based on an assumption that selfish behaviour of individuals produces greater good for the society.
- automatwon 10y ago
  "It is not from the benevolence of the butcher, the brewer, or the baker that we expect our dinner, but from their regard to their own interest" - Wealth of Nations, Adam Smith I tend to think of self-interest being equivalent to selfishness. Your point makes me wonder if self-interest is not equivalent to selfishness, at least to Economists.
  - TeMPOraL 10y ago
    Well, what you quote is true, but I think a lot of discussion stems from focusing on the wrong question, namely "does selfishness lead to better outcomes" as opposed to when it does, and when it does not. Too many people seem to approach economy as an ideology rather than a complex system in which a given approach produces good results here and bad results there, and everything should be subject to optimization and careful design.
    - JumpCrisscross 10y ago
      > Too many people seem to approach economy as an ideology rather than a complex system Few of these people have any decision-making authority. This mass ignorance of economics does occasionally bubble up on the policy side. But it is generally, at least in the United States, contained by more knowledgeable (and influential) parties.

wodenokoto 10y ago

Isn't libertarian thinking (put very heavily on the edge) the exact opposite? That a system will become more efficient if actors are let to do things for their own sake, and that actors are smart enough to calculate the negative impact of short term selfish action (that is, actors can help out now, with an exception of a positive roi)

SonOfLilit 10y ago
This assumes a theoretical optimal central planner, a superintelligent BDFL of sorts. Libertarian thinking is that in practice humans are so bad at management that every time we tried central planning it came up even worse than non-optimal Nash Equilibria (which are the failure mode of non-centrally-managed agent systems.) Libertarians would say that no dictator or government in history turned out to know better than The Market. That The Cost of Regulation is higher than The Cost of Anarchy. Of course, both costs are high for some problems and low for others, and the solution to practical problems usually lies at neither this extreme nor that one.
adgasf 10y ago
Some Libertarians are non-consequentialists. They argue that even if the outcome is less efficient, there are moral reasons to oppose central planning. What is interesting is that many argue both points: that markets are more efficient and morally superior. A good example of the distinction is David D. Friedman (consequentialist) vs Ayn Rand (non-consequentialist).
em3rgent0rdr 10y ago
Libertarian thinking actually permits multiple people to agree to not take the most immediately greedy action and to instead voluntarily agree to a mutually-beneficial optimal solution.

deleted 10y ago

[deleted]

CaptainSwing 10y ago

I think that this is a really interesting concept, but dislike the name. All social anarchists (anarchist-communists, anarchist-syndicalists, even mutualists etc) would see anarchy as a social process rather than a purely individualised "every man for himself" system. It disregards the possibility for non-coercive collective forms of decision making. but, saying this, a concept that discovers the loss in a system where each actor is purely self-interested is useful and interesting.

ue_ 10y ago
I talk with a lot of anarchists and perhaps the only ones of them who are truly in the spirit of "every man for himself" are an-caps and Stirnerists.
- Proven 10y ago
  I don't think ancaps are all like that. You can't run business if you don't serve your customers well. Does that translate into pathological selfishness and other extreme behavior that goes in customers' nerves? I don't think so, because such business wouldn't last long. I agree with the GP post above, and I'd also like to point out the idiocy of the "scientific" assumption from Wikipedia that "central planners" have superior information compared to self-interested agents who follow their own optimization strategies. F. A. Hayek is one of best authors on this topic.
  - ghgfhgfhn 10y ago
    I was bracing myself for comments that either missed the point entirely or low brow attempts to dismantle the piece. I am surprised and happy to find an intelligent discussion! It's becoming rarer on hn.
  - ue_ 10y ago
    >You can't run business if you don't serve your customers well. Serving your customers well is entirely out of self interest, especially in large corporations; in fact, this is the easiest example of "every man for himself". You serve your customers well because ultimately it brings you more profit. Sure, it's not as sure sighted as screwing over every customer, but people who are selfish aren't necessarily stupid. I would argue that the very act of running a business in such a society is not only wrong due to the exploitation of workers, but also the motivation underlying (almost) every transaction in which your goal is to sell things in such a way as to get yourself the largest profit. Of course that doesn't happen in real life. People have moral standards. I think I'm just a cynical ancom with regard to how people would really behave in the absence of all regulation. Let's not forget what large companies can still get away with today, and imagine what it would be like with anti-competitive monopolies, oligarchies, and two or three organisations controlling mainstream information sources. So sure, your business doesn't last long because you were too obviously selfish. Your next plan of action is to pay a news outlet (or better yet, already be in control of one) to cover you. Or if you can't do that, there's still hope - you can band together with like minded people and start another business. Not without worker exploitation, of course. You need all the surplus value you can get. I simply do not have the hope that "serving your customers well" is enough to prevent what actors in a capitalist system are truly capable of doing. Let's not forget the sheer paradoxical nature of "anarcho-capitalism" (the inherent class system set up of the bourgeoisie and proletariat is the exact opposite of non-hierarchical relations). I'm not really a proponent of central planning myself, so I agree with you on that.

inlineint 10y ago

This submission seems to be a kind of follow-up to the one about Braess's paradox (https://news.ycombinator.com/item?id=13352513 https://news.ycombinator.com/item?id=13352513).

cardiffspaceman 10y ago
I have seen clusters of posts and have not had the time to study: Are they a dialog between unrelated people who share an interest in a topic, or is one person pursuing a theme?

bo1024 10y ago

I just want to mention that many commenters here are reading much more into the name politically than do the game theorists/computer scientists who actually do research on it. The research is focused on the game theory and not meant to make any sort of political points or value judgement. The main question asked is how to design systems so that even in a game-theoretic equilibrium, the total "welfare" is close to the best possible.

throwaway729 10y ago
What you are saying is true and crucial to understand. The same observation applies to a lot of named concepts in academia (in voting/game theory and economics especially). However, I also think that results in these fields can be useful in political discussions, as long as they're used as thinking devices rather than arguments in and of themselves. The map is not the territory, but "price of anarchy" is a suggestive name. The name suggests, purposefully or not, that this set of mathematical results about an abstract game theoretic model might be useful to hold in mind while thinking about political systems. And I don't think that's necessarily a bad suggestion.
danharaj 10y ago
Having no intention to be political just means they uncritically reproduce aspects of the ideology they passively go along with. Associating anarchy with Bad Things was a deliberate government program to suppress its movements(quite popular at the turn of the previous century). Now people do it reflexively and that is very much political. The political is not merely intent.
sebastos 10y ago
Ding ding ding. The Price of Anarchy originally described the surprising result that internet routing seems to work despite the lack of a central planner. [1] The "central planner" is a theoretical maximum for the routing problem - it represents an oracle that automatically knows and applies an optimal routing solution. It's not some kind of government. It's kind of hilarious seeing all of these people commenting about how this is "utopian" thinking, ancap-blah-blah, and "who says the central planner would be just?" People read what they want to read, I suppose. If you do want to read something interesting about the price of anarchy, check out this other paper [2], written by one of the original authors, which shows that the PoA = 1 (that is, there is no cost) when there are private "owners" of the edges in a routing network who are allowed to charge a "toll" for traversing that edge. Makes you wonder if a globally-standard-but-locally-owned electronic tolling system could replace gas taxes to fund our roads in a fairer way. This could remove the undue toll burden shouldered by certain unlucky people who have to commute across a heavily tolled bridge. (Seattlites should know what I'm talking about). [1] http://www.cs.yale.edu/homes/jf/poa.pdf http://www.cs.yale.edu/homes/jf/poa.pdf [2] https://people.eecs.berkeley.edu/~christos/papers/selfishrouters.pdf https://people.eecs.berkeley.edu/~christos/papers/selfishrou... [3] http://theory.stanford.edu/~tim/papers/routing.pdf http://theory.stanford.edu/~tim/papers/routing.pdf

tehabe 10y ago

Incomplete models are incomplete. It completely ignores the ways on which the mentioned transport should take place. It ignores that you usually don't have one place from which everybody starts but multiple places to other multiple places. And if you think about it, individual car mobility is this in practice. The ways are build by someone else but you can decide how and where to drive. And it kinda failed in many areas.

alimw 10y ago
It's not clear what you are referring to. The section on Selfish Routing begins with Braess's Paradox but swiftly moves on to a Generalized Routing Problem which appears to address your concerns.

wyager 10y ago

Wow, people are really running away with the political analogy used here. Calm down folks, they're not ragging on decentralized systems. If you read and comprehend the definitions in the article, you'll see that it's a fully general solution that allows for emergent organization through market systems or cooperation. You can bake those things into the strategies and utility functions of the actors. It's just a fun and descriptive name for the difference between an idealized central controller (which can force everyone into a configuration that maximizes an arbitrary global utility function) and the lack of such a controller. The outcomes could be the same, they could be different. If you factor in the negative utility of having the central authority in the first place, you can game-theoretically justify your particular favored level of anti-authoritarianism.

johngalt 10y ago

Think of it as structured vs unstructured if you can't avoid gettng hung up on the name. Basically this is talking about the net difference between what is locally optimal and globally optimal in a multi agent system.

hyperbovine 10y ago
an ("without") + arkhos ("ruler"). Seems like a fine name to me.

deleted 10y ago

[deleted]