Distributed Algorithmic Mechanism Design (talk at NECI)
- 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
Becomes easy if one requirement is dropped.
(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
Location: Board Room 4D09
Host: L. Fortnow
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.
- Great stuff! Thanks Lucas,
>[...] at http://www.cs.yale.edu/homes/jf/DAMD.ppt:Here are the sites that are most fascinating to me, lately.
>[...] 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.
For example, this tutorial about mesh
"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,
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
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
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,
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
> For example, this tutorial about meshWay cool!
> Generally, the presidents and founders of the CWNs do not wantLedgers are not the only tool for constructing net positive games. Open
> any economic mechanism in their networks. Matt and Adam are
> founders of Seattle and Portland CWNs. Here are a typical thread,
> 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.
source is one counter example, this list is another. In both situations
what you give and get are only loosely related.
>Ledgers are not the only tool for constructing net positive games. OpenThis is true, but, wouldn't it be more natural and efficient, if
>source is one counter example, this list is another. In both situations
>what you give and get are only loosely related.
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,
> This is true, but, wouldn't it be more natural and efficient, ifEvery node already does have one -- the person sitting behind it is
> every node had a ledger table?
keeping loose track of whether the whole thing is worth it. Keeping track
only needs to be automated when automation enables new functionality.
> Every node already does have one -- the person sitting behind it is...or when the formulae for keeping track involves large or precise
> keeping loose track of whether the whole thing is worth it. Keeping track
> only needs to be automated when automation enables new functionality.
numbers or functions, or when the nodes aren't people.
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