Loading ...
Sorry, an error occurred while loading the content.

Distributed Algorithmic Mechanism Design (talk at NECI)

Expand Messages
  • Lucas Gonze
    Forwarded not because I think there are listers in Princeton NJ with a spare hour after lunch, but because the talk is a formalization of the same topics we
    Message 1 of 6 , Apr 12 5:48 AM
    • 0 Attachment
      Forwarded not because I think there are listers in Princeton NJ with a
      spare hour after lunch, but because the talk is a formalization of the
      same topics we generally approach informally. A quote from a different
      (?) talk by the same speaker, at http://www.cs.yale.edu/homes/jf/DAMD.ppt:

      "
      Representative Hard Problem to solve on the Internet

      Hard if it must be solved:

      By a distributed algorithm
      Computationally efficiently
      Incentive compatibly

      Becomes easy if one requirement is dropped.
      "

      Talk details:
      (At NEC Research, http://www.neci.nec.com)
      Title: Foundations of Distributed Algorithmic Mechanism Design
      Speaker/Affiliation: Joan Feigenbaum, Yale University
      Date: Fri Apr 12, 2002
      Time: 1:30pm
      Location: Board Room 4D09
      Host: L. Fortnow

      Abstract:

      Despite their prominent role in some of the more applied areas
      of computer science, incentives have rarely been an important
      consideration in traditional theoretical computer science,
      where, typically, agents are assumed either to be obedient,
      i.e., to follow the prescribed algorithm, or to be adversaries
      who play against each other. In contrast, the strategic agents
      in game theory are neither obedient nor adversarial. Although
      one cannot assume that strategic agents will follow the
      prescribed algorithm, one can assume that they will respond to
      incentives. In general, the economics literature traditionally
      stressed incentives and downplayed computational complexity, and
      the theoretical computer science literature traditionally did
      the opposite. Because of the emergence of the Internet as a
      standard platform for distributed computation, this state of
      affairs is changing rapidly: Ownership, operation, and use by
      many self-interested, independent parties give the Internet the
      characteristic of an economy as well as those of a computer.
      Distributed algorithmic mechanism design (DAMD), a relatively
      new and growing area of theoretical computer science, is the
      mathematically rigorous study of scalable, multiagent protocols
      in which resources, computation, and agents are distributed.
      This talk will survey the fundamental open problems in DAMD.
      Preliminary results will be presented on interdomain routing, a
      typical DAMD task.

      ** Open to the Public.


      ===

      ...like the MIT P2P Conf, this is an instance of P2P changing hands from
      hackers to scientists. For myself I have been finding much more
      interesting and inventive stuff at citeseer.nj.nec.com, in the academic
      literature, than at slashdot.

      - Lucas
    • Todd Boyle
      Great stuff! Thanks Lucas, ... Here are the sites that are most fascinating to me, lately. http://wirelessman.org
      Message 2 of 6 , Apr 12 3:34 PM
      • 0 Attachment
        Great stuff! Thanks Lucas,

        >[...] at http://www.cs.yale.edu/homes/jf/DAMD.ppt:
        >[...] at NEC Research, http://www.neci.nec.com
        >Title: Foundations of Distributed Algorithmic Mechanism Design
        >Speaker/Affiliation: Joan Feigenbaum, Yale University
        >[..] Ownership, operation, and use by
        >many self-interested, independent parties give the Internet the
        >characteristic of an economy as well as those of a computer.
        >Distributed algorithmic mechanism design (DAMD), a relatively
        >new and growing area of theoretical computer science, is the
        >mathematically rigorous study of scalable, multiagent protocols
        >in which resources, computation, and agents are distributed.
        >This talk will survey the fundamental open problems in DAMD.
        >Preliminary results will be presented on interdomain routing, a
        >typical DAMD task.

        Here are the sites that are most fascinating to me, lately.
        http://wirelessman.org
        http://wirelessman.org/meetings/mtg18/report.html

        For example, this tutorial about mesh
        http://wirelessman.org/tga/contrib/S80216a-02_30.pdf

        "Mesh coverage & robustness improve exponentially
        as subscribers are added"

        I cannot pretend to understand the mathematics.

        Links to this site http://www.freenetworks.org is now appearing
        on the front pages of BAWUG and other community wireless
        networks. CWNs are globally, waking up and coordinating.
        Here was teh Seattle Wireless meeting in January,
        http://serv9.lly.org:8080/Summit2002Imgs/dcp00649.jpg

        These are almost totally "user groups" rather than professional
        designers of the radios, protocols etc. But P2P software
        developers will find many kindred spirits among both the CWNs
        and the companies in WirelessMAN and 802.16 workgroups,
        who are building mesh networking and other radical stuff, entirely
        outside the regulated internet. Find your tribe and like-minded
        people in the free wireless networking community.

        Let me give an example; the ebXML has been built by hundreds
        and hundreds of people who were mostly getting a salary from
        their companies but expressing their personal values and shared
        vision for interoperability. Very few investors or corp. boards who
        actually understand the economics of standards processes would
        authorize the work. Fact is, many are laid off or demoted for
        their activities.. Similarly the people from Nokia and the telcos
        etc. building the mesh networking standards, are blowing a big
        hole in the fundamental economics of Internet and the PSN.
        They're doin it on purpose after a lifetime of obedience and
        exploitation. It is an expression of our great cultural heritage,
        that networks will increasingly become a commons rather than
        a hierarchic business they are today.

        Roundabout way of saying, I STRONGLY agree with Joans basic
        observation for the need for incentive mechanisms, most
        fundamentally, that each node have a standard way of sending
        an economic event notification to any other node. (Not a
        settlement like digital cash or bank payment, but, a mechanism
        for sending an unambiguous notification that the Self has
        recognized, or booked, or recorded, a receivable or payable
        to/from the party named in the notification
        http://www.gldialtone.com/UEEN.htm

        I am talking about nothing more complicated than sending bills
        to people with the following data: DueTo, DueFrom, DateTime, Amount, WhatFor.
        Whoever wants to send a bill can send one, every 2 seconds if they want.
        The recipient can route them to the bitbucket if they want. But the
        biller presumably will maintain a total of the amounts they want to
        receive from the node and if that guy doesn't turn up with a $5 bill
        once in a while, then I suppose they will be blocked.

        Once you have this 5-column database table or ascii file, of the
        DueTo/DueFrom/Amount.. etc. you can take the whole list of ARs/APs and
        send it to somebody for clearing. Matching and settlement bots can
        offset and net the mutual balances. If you are providing something to
        the economy as well as consuming other peoples stuff, your balance will
        be netted to vanish.

        By the way, what you provide does NOT need to be anything related to the
        wireless network. Do you get it yet? This is why accounting has never
        been implemented in networking protocols until now. It enables a
        pandoras box of commercial activity outside the banking system.

        But usually, since this is all local between people, the net negative
        people will get a message from the settlement bot, telling them *one* of
        the net negative people to go and pay $20 or whatever, to net positive
        person X. Everything completely transparent and audit trail for anybody
        who is entitled to see it. There is no hub. There is no corp. There is
        no human, basically. Here, http://www.arapxml.net/arapcloud.htm and
        http://www.arapxml.net/ where we already written a submission for
        the OMG that does some of these things, and
        http://www.gldialtone.com/journalBus.htm etc.

        http://lists.bawug.org/pipermail/wireless/2001-August/002348.html
        http://lists.bawug.org/pipermail/wireless/2001-August/002366.html

        Generally, the presidents and founders of the CWNs do not want
        any economic mechanism in their networks. Matt and Adam are
        founders of Seattle and Portland CWNs. Here are a typical thread,
        http://www.seattlewireless.net/archive/ezmlm.cgi?sss:6029:bjmoilhodjgmimbhihph#b
        The people building the community networks do not understand the
        idea of a market, and assume that people will just work together for
        the spirit of it. They make all kinds of assumptions such as
        equating a billing mechanism with micropayments, and associating
        it with bandwidth metering etc. Under their managment the CWNs
        will remain like little clubs while millions of users are swept into
        commercially operated mesh networks. They will retrofit central
        control into into mesh routing nodes...Isn't that nuts?

        Todd Boyle CPA 9745-128th Ave NE Kirkland WA
        International Accounting Services, LLC www.gldialtone.com
        425-827-3107 AR/AP everywhere www.arapxml.net
      • Lucas Gonze
        ... Way cool! ... Ledgers are not the only tool for constructing net positive games. Open source is one counter example, this list is another. In both
        Message 3 of 6 , Apr 13 9:20 AM
        • 0 Attachment
          > For example, this tutorial about mesh
          > http://wirelessman.org/tga/contrib/S80216a-02_30.pdf

          Way cool!

          > Generally, the presidents and founders of the CWNs do not want
          > any economic mechanism in their networks. Matt and Adam are
          > founders of Seattle and Portland CWNs. Here are a typical thread,
          > http://www.seattlewireless.net/archive/ezmlm.cgi?sss:6029:bjmoilhodjgmimbhihph#b
          > The people building the community networks do not understand the
          > idea of a market, and assume that people will just work together for
          > the spirit of it.

          Ledgers are not the only tool for constructing net positive games. Open
          source is one counter example, this list is another. In both situations
          what you give and get are only loosely related.

          - Lucas
        • Todd Boyle
          ... This is true, but, wouldn t it be more natural and efficient, if every node had a ledger table? A list of +/- amounts of money that have been addressed
          Message 4 of 6 , Apr 13 11:51 AM
          • 0 Attachment
            >Ledgers are not the only tool for constructing net positive games. Open
            >source is one counter example, this list is another. In both situations
            >what you give and get are only loosely related.
            >
            >- Lucas

            This is true, but, wouldn't it be more natural and efficient, if
            every node had a ledger table? A list of +/- amounts of money
            that have been addressed to the node? This would tell you
            how much each of the nodes in your community have
            posted as due to/from you. Then you can blow it away anytime,
            or disable the feature.

            This piece should be built into every network interface at
            some level. It doesn't constrain anybody's modes of interacting,
            but it enables the nodes to aggregate their economic support
            for crucially important gateways, backbones and other resources.

            Everybody will configure their ledger to discard all bills except
            some known nodes they need to pay. The hard association
            between a node identity on the network layer, and the billing
            protocol, much reduces the scope of spammers or abusive
            billers, DOS attacks etc.

            The financial frauds possible in this architecture are quite
            limited if you assume the workstation itself is secure, because
            of the agreement in amounts between biller and billee. Nobody
            would be paying anything and nobody would pay or agree with
            any false liability, anymore than you would pay a bill in your
            mailbox that you do not owe.

            As long as there's no economic mechanism for the community
            network (or P2P application) they will remain irrelevant footnotes.

            There is an asymmetry of benefit in almost every interaction.

            There is game theory.

            All this stuff has been methodically considered in political
            economy for centuries,

            Todd
          • Lucas Gonze
            ... Every node already does have one -- the person sitting behind it is keeping loose track of whether the whole thing is worth it. Keeping track only needs
            Message 5 of 6 , Apr 14 10:13 AM
            • 0 Attachment
              > This is true, but, wouldn't it be more natural and efficient, if
              > every node had a ledger table?

              Every node already does have one -- the person sitting behind it is
              keeping loose track of whether the whole thing is worth it. Keeping track
              only needs to be automated when automation enables new functionality.
            • Clay Shirky
              ... ...or when the formulae for keeping track involves large or precise numbers or functions, or when the nodes aren t people. -clay -- NEC@Shirky.com -- A
              Message 6 of 6 , Apr 14 1:14 PM
              • 0 Attachment
                > Every node already does have one -- the person sitting behind it is
                > keeping loose track of whether the whole thing is worth it. Keeping track
                > only needs to be automated when automation enables new functionality.

                ...or when the formulae for keeping track involves large or precise
                numbers or functions, or when the nodes aren't people.

                -clay

                --
                NEC@... -- A low-volume list about Networks, Economics, and Culture

                Subscribe at http://shirky.com/nec.html, or send a message to
                nec-request@..., with 'subscribe' in the subject line
              Your message has been successfully submitted and would be delivered to recipients shortly.