[Mnet-devel] another paper

[Jim Dixon]

On Thu, 6 May 2004 zooko at zooko.com wrote:

> http://www.cs.toronto.edu/~marbach/PUBL/adhoc.ps.gz
>
> I haven't read it, but I saw Prof. Marbach give a talk about it recently.
> Basically, he shows how, given a nice micropayment system, nodes can
> effectively choose prices for their resources such their choices fall into a
> Nash equilibrium and the result is socially optimal.

Not really.

His argument is based on a number of assumptions.  He spells them out
in detail.  The first concerns the user's utility function, the perceived
benefit from the connection.  This has a maximum transmission rate Cn.
If the amount of user data being transmitted by node n is xn, then the
utility function Un, a mapping from [0, Cn] into the real numbers, is
assumed to have the following properties:

1.1  increasing (OK - the more of your own data sent the better)
1.2  strictly concave
1.3  Un(0) = 0 (no data transmitted, no happiness)
1.4  continuously differentiable
1.5  the first derivative Un'(Cn) = 0

ASCII art representing the utility function Un(xn):

    ^                           .   x  x
    |                      x
    |                x
 Un |          x
    |     x
    |  x
    |x
    +----------------------------------+
    0     --- increasing xn --->      Cn

Properties 1.1 and 1.3 make sense.

The third property doesn't hold at all.  Most users deal in terms of
files.  If they can't transmit an entire file, then their bandwidth has
been burned for nothing, and they get irritated.  So Un is a step
function, with discontinuities spaced quite widely apart.

1.2 means that as you transmit more data, the utility (happiness)
delivered by each additional byte decreases.  This is questionable.

1.5 means that when you are transmitting at full bandwidth, the
additional utility delivered by each additional byte is zero.  That
is, when you are close to using your full bandwidth, you place little
value on any files you get.  This assumption has nothing to do with
reality; it's there to make the mathematics work.

Properties 1.2, 1.3, and 1.5 are essential to the authors' arguments.
Without them, further conclusions simply can't be proven.

> He is be commended for including a simple, feasible algorithm instead of merely
> a proof that some such algorithm could exist.  It is intriguing that his
> algorithm is both simpler than and more sophisticated than the various
> algorithms that we tried at Mojo Nation.  The only hole in the idea is that it
> isn't clear if his algorithm will adapt with sufficient alacrity to changing
> market conditions.
>
> Another minor hole is that the algorithm takes "the user's preference function"
> as one of the inputs, and it might be tricky to express that with sufficient
> accuracy, especially (again) as it changes over time.

They assume that the network can supply an initial approximation to the
preference function to each node.  As the network operates, these will
automatically adjust to circumstances and over time converge to stable
values.  In the stable state the nodes will presumably have different
preference functions -- probably very different.

However, the authors' proof of convergence depends upon their assumptions
and these assumptions very clearly do not hold in p2p networks.

It is not just the first assumption which does not apply.  In general,
wherever the authors came to a sticky point, they made assumptions to
make the problem tractable.  Given these many simplifying assumptions,
they get convergence.

> --Z
>
> P.S.  This paper is described in terms of Digital Silk Road style emergent
> transport on ad hoc wireless networks, but as far as I can tell the exact same
> conditions and the exact same solution apply to the question of how to price
> your storage space in Mojo Nation / Mnet.

The paper talks in terms of transmissions, so my comments use the same
language.  But they apply to storage as well.  Half a file is of no
value.  User happiness is quantized and the quantization is very coarse.

On the other hand, for most users, storage is effectively priced in terms
of the bandwidth necessary to fill it.

The paper is aimed at the mobile telephony market, where quantization
is much finer (a ten second conversation is often quite useful) and
their other assumptions are also a better fit to reality.

--
Jim Dixon  jdd at dixons.org   tel +44 117 982 0786  mobile +44 797 373 7881
http://jxcl.sourceforge.net                       Java unit test coverage
http://xlattice.sourceforge.net         p2p communications infrastructure