Distributed Resource Management with
Monetary Incentives
vorgelegt von
Diplom-Mathematiker
Andreas Tanner
aus Potsdam
von der Fakultät IV – Elektrotechnik und Informatik –
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
Dr. rer. nat.
genehmigte Dissertation
Promotionsausschuß:
Vorsitzender: Prof. Dr.-Ing. Adam Wolisz
Betreuer: Prof. Dr. Hans-Ulrich Heiß
Gutachter: Prof. Dr. Kurt Geihs
Gutachter: Prof. Giuseppe Persiano, Ph.D.
Tag der wissenschaftlichen Aussprache: 7. Juli 2005
Berlin 2005
D 83
2
Zusammenfassung
Moderne Kommunikationsnetzwerke erlauben die gleichzeitige Ausführung einer
Vielzahl von Anwendungen. So ist es nicht verwunderlich, dass Mechanismen zur
Ressourcenvergabe, seien es Übertragungsbandbreite oder Rechenkapazität, in der
Informatik seit langer Zeit erforscht werden. Jedoch gehen die klassischen Mecha-
nismen von
kooperierenden Nutzern
, die nicht versuchen, das System zu ihrem
Vorteil zu manipulieren, aus. Andererseits wird die informationstechnische Infra-
struktur schon aufgrund der hohen Installationskosten von Nutzern ohne gemein-
same Interessen und über Firmengrenzen hinweg genutzt. Stehen nun Ressourcen
in begrenzter Menge zur Verfügung, ist die Entstehung von Allokationskonflikten
unvermeidlich. Ein natürlicher Ansatz zur Lösung solcher Konflikte ist die Etablie-
rung eines
Marktes
für die Ressourcenvergabe.
Diese Arbeit schlägt Marktmechanismen für die Ressourcenvergabe in verteilten
Computersystemen vor. Wir präsentieren ein neues, budgetausgeglichenes Preis-
bildungsschema für kombinatorische Tauschmärkte, welches die Berechnung der
Akzeptanz von Geboten unabhängig agierender Handelspartner erlaubt. Ebenso
haben wir eine neue Methode zur Synchronisierung der Gebote entwickelt und
zeigen, dass sie einer periodischen oder zufälligen Marktbereinigung überlegen ist.
Die neu entwickelten Mechanismen wenden wir auf die Bandbreitenvergabe für
Punkt-zu-Punkt-Kommunikation an und zeigen mittels einer Simulationsrechnung,
dass die Auktionierung der Bandbreite für einen großen Teil des Parameterraumes
zu höherer Effizienz als ein Fixpreisverkauf führt, obwohl die Auktionierung – im
Unterschied zur Wahl eines optimalen Fixpreises – keine Informationen über die
statistische Verteilung der Gebote der Nutzer benötigt.
Die Situation für Gruppenkommunikation erweist sich als schwieriger. Kellys klas-
sischer Equlibriums-Mechanismus für die Bandbreitenvergabe verliert bei der An-
wendung auf Gruppenkommunikation seine Effizienz. Wir präsentieren eine – nicht
budgetausgeglichene – Verallgemeinerung von Feigenbaums Grenzkostenmechanis-
mus auf ein Gruppenkommunikationsszenario mit Publish/Subscribe-Struktur, und
entwickeln einen Algorithmus zur effizienten, verteilten Preisberechnung.
3
Abstract
Modern communication networks handle millions of applications simultaneously,
and mechanisms of resource sharing, most prominently sharing of data transmission
bandwidth and processing power, between competing jobs have been considered
in computer science since its beginning. Classical mechanisms, however, balance
claims of
cooperating
users that do not try to manipulate the system to their advan-
tage. Due to their cost of installation, information technology infrastructure has to
be used by clients with no joint interest: by individual users and accross borders of
companies. With resources available only in a limited quantity, allocation conflicts
do arise. It is natural to apply the classical remedy for conflict resolution and install
a
market
for the system’s resources.
This thesis proposes market mechanisms for resource allocation in distributed
computer systems. We define a new budget-balanced pricing scheme for combina-
torial exchanges that allows matching of bids of autonomous buyers and sellers. We
suggets a new bid synchronization rule and prove that it performs superior to peri-
odic and random bid clearing. We give an application of a combinatorial exchange
to unicast bandwidth allocation. We demonstrate by a simulation that, for a large
part of the parameter space, auctioning bandwidth performs superior to fixed price
bandwidth sale, while not requiring prior information on the distribution of bids.
The situation for unicast cost sharing is more complicated. After proving that
the classical equilibrium mechanism of Kelly can’t looses much efficiency if applied
to group communication, we present a generalization of Feigenbaum’s adoption of
marginal cost pricing to publish/subscribe settings. We also develop an algorithm
for efficient distributed price computation.
4
Danksagung
Diese Arbeit entstand während meiner Tätigkeit als wissenschaftlicher Mitarbeiter
am
Institut für Intelligente Netze und Management Verteilter Systeme
an der TU
Berlin.
Ich habe Herrn Prof. Dr. Kurt Geihs zu danken, der in seiner Zeit an der TU Berlin
für eine stimulierende Arbeitsumgebung sorgte, die mir eigenständige Forschung
ermöglicht hat, und der mich in der Wahl meines Forschungsthemas bestärkte.
Herr Prof. Dr. Hans-Ulrich Heiss stellte sich freundlicherweise als Gutachter zur
Verfügung und gab mir wertvolle Kritik und Anregungen in der Phase der Fertig-
stellung der Arbeit.
Gero Mühl ermutigte mich nachdrücklich, meine Ergebnisse zu Papier zu bringen.
Er und Michael A. Jaeger waren außerordentlich hilfreiche Koautoren und haben
mich durch unbeirrtes Insistieren zu größerer Präzision gezwungen. All meinen
Kollegen bin ich für die vielen anregenden Diskussionen, die mir halfen, die prak-
tische Anwendbarkeit meiner Ideen nicht aus den Augen zu verlieren, zutiefst zu
Dank verpflichtet.
Meiner Familie, und besonders meiner lieben Frau Ximena, danke ich für die
Ermutigung, sich auf das Wagnis Forschung einzulassen, und für die Geduld und
Nachsicht in der langen Zeit bis zur Fertigstellung der Arbeit.
5
6
Contents
1 Introduction 10
1.1 Applicability of economic theory . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.1 Computer networks as markets . . . . . . . . . . . . . . . . . . . 15
1.2.2 Network industries . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.3 Auction theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.4 Characteristics of protocol design . . . . . . . . . . . . . . . . . . 21
1.2.5 What are good protocols? . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4 Our work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Background: Game theory and mechanism design 25
2.1 Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Mixed strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.3 Efficiency of equilibria . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.3.1 Dominant strategies . . . . . . . . . . . . . . . . . . . . . 28
2.1.3.2 Coordination ratio . . . . . . . . . . . . . . . . . . . . . . 29
2.1.4 Existence of Nash equilibria . . . . . . . . . . . . . . . . . . . . . 30
2.1.4.1 Existence of Nash equilibria for given mechanisms . . . 30
2.1.4.2 Bayesian Nash equilibria and implementable choice func-
tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.5 Existence of dominant strategies . . . . . . . . . . . . . . . . . . 32
2.1.5.1 Choice functions that are implementable in dominant strate-
gies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.1.5.2 Vickrey Groves Clarke mechanisms . . . . . . . . . . . . 33
2.1.5.3 Budget balance . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Application of VGC mechanisms to allocation problems . . . . . . . . . 33
2.3 Example: A public project . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Example: Auctioning a divisible good . . . . . . . . . . . . . . . . . . . . 37
7
3 A combinatorial exchange for autonomous traders 38
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 A combinatorial exchange model for an auction platform application . 40
3.3 Pricing properties required by autonomous traders . . . . . . . . . . . 42
3.3.1 Respecting single item bids. . . . . . . . . . . . . . . . . . . . . . 43
3.3.2 No loss from a bid. . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 A new pricing scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5 Bid synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5.1 A new clearing policy . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.2 A lower bound for the revenue . . . . . . . . . . . . . . . . . . . . 48
3.5.3 Comparison between periodic and commit window clearing . . . 50
3.5.3.1 Side conditions for the comparison . . . . . . . . . . . . 50
3.5.3.2 Simulation results . . . . . . . . . . . . . . . . . . . . . . 51
3.5.3.3 An analytic approach for offline winner determination . 51
3.5.3.4 Further research on the performance of commit window
clearing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.6 Extending SBNL to multiple item auctions . . . . . . . . . . . . . . . . . 54
4 Application to network management: Advanced resource reservation
in networks 56
4.1 Background: The RSVP protocol . . . . . . . . . . . . . . . . . . . . . . 60
4.2 An auction market for advanced reservations with well-known duration 61
4.3 Unknown reservation duration: Extensions to the admission control al-
gorithm of Greenberg et al. for a single link . . . . . . . . . . . . . . . . 62
4.3.1 Bidding for paths in the admission protocol of Greenberg et al. . 64
4.3.2 Mechanism design for reservations with unknown duration. . . . 64
4.3.2.1 Non-existence of efficient two-dimensional mechanisms. 68
4.3.2.2 Mapping two-dimensional types to one-dimensional ones. 68
4.3.2.3 The empirical interrupt probability. . . . . . . . . . . . . 69
4.4 Is there an advantage in auctioning bandwidth ? . . . . . . . . . . . . . 70
4.4.1 Fixed price mechanism . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4.2 Vickrey price mechanism . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.3 Comparing the revenue . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.3.1 No global inequality. . . . . . . . . . . . . . . . . . . . . . 74
4.4.3.2 Simulation results. . . . . . . . . . . . . . . . . . . . . . . 74
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5 Indirect mechanisms for multicast pricing 76
5.1 Linear utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.1.1 Comparison with VGC mechanisms . . . . . . . . . . . . . . . . . 80
5.1.2 Approximativity of the Nash equilibrium . . . . . . . . . . . . . . 80
5.1.3 Multicast with linear utilities . . . . . . . . . . . . . . . . . . . . . 82
8
5.1.3.1 Example with 3 users in 2 groups. . . . . . . . . . . . . . 83
5.1.3.1.1 Comparison with group agent. . . . . . . . . . . . 83
5.1.3.1.2 Remark. . . . . . . . . . . . . . . . . . . . . . . . 84
5.1.3.2 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2 Logarithmic utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Numerical simulation for unicast . . . . . . . . . . . . . . . . . . 86
5.2.2 Approximativity of the Nash equilibrium . . . . . . . . . . . . . . 88
5.2.3 Multicast with logarithmic utilities . . . . . . . . . . . . . . . . . 91
5.3 General case for multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6 Publish/subscribe systems 94
6.1 Publish/Subscribe Systems . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.1.2 Importance for mobile applications . . . . . . . . . . . . . . . . . 94
6.1.3 Why formalization? . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.2 Formal specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2.1 Propositional temporal logic and traces . . . . . . . . . . . . . . . 96
6.2.2 Formalising publish/subscribe systems . . . . . . . . . . . . . . . 98
6.2.2.1 State variables and Interface . . . . . . . . . . . . . . . . 98
6.2.2.2 Axioms of liveness and safety. . . . . . . . . . . . . . . . . 100
6.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3.1 Specifying module interfaces . . . . . . . . . . . . . . . . . . . . . 102
6.3.2 State variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.3.3 The Framework Algorithms . . . . . . . . . . . . . . . . . . . . . 105
6.3.3.1 The procedure
processNotification
. . . . . . . . . . . . . 105
6.3.3.2 The procedure
processAdminMessage
. . . . . . . . . . . 105
6.3.4 Valid routing algorithms . . . . . . . . . . . . . . . . . . . . . . . 107
6.3.4.1 Correctness proofs by decomposition . . . . . . . . . . . 108
6.4 Pricing in publish/subscribe systems . . . . . . . . . . . . . . . . . . . . 111
6.4.1 Publish/Subscribe pricing as special multicast pricing . . . . . . 111
6.4.2 Notation and General Facts . . . . . . . . . . . . . . . . . . . . . 112
6.4.3 Marginal Cost Mechanism for Publish/Subscribe Setting:
The Static Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4.4 Dynamic Aspects: Changing Utilities and Publishers in the Tree 116
6.4.5 Shapley Value Mechanism . . . . . . . . . . . . . . . . . . . . . . 120
6.4.6 Extension to Multiple Rates . . . . . . . . . . . . . . . . . . . . . 121
6.4.7 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . 122
7 Conclusion and outlook 124
9
1 Introduction
This thesis is about resource allocation in distributed systems by applying tech-
niques from applied game theory and economic theory. While resource management
has experienced extensive treatment since distributed systems have gained popular-
ity, the economic perspective is still a non-traditional one. Traditional resource man-
agement and resource management with economic incentives have a common goal:
efficient use of the resources - typically memory, computational power and, prob-
ably most importantly, bandwidth consumption for data transfer - in a distributed
system.
But what is
efficiency
? Classical resource management has a simple answer to
that: given some set of tasks, efficiency means to solve them as quickly and ac-
curately as possible, preferably while consuming little resources. The tasks are
assumed to be known, sometimes deterministically, sometimes they are assumed to
be drawn from some random distribution of possible tasks. A prominent example of
resource management in that sense is
task scheduling
.
It is a natural approach to build this negotiation on monetary incentives, and
precisely this is what our research is about.
Microeconomic theory describes economic interactions between self-interested
individuals:
A distinctive feature of microeconomic theory is that it aims to model
economic activity as an interaction of individual economic agents pursu-
ing their private interests. [48, p.3]
Mechanism design develops market mechanisms like pricing and allocation rules
that produce optimal outcomes if market participants are self-interested and there is
incomplete information. Mechanism design has been applied to analyze traditional
auction markets, as well as to suggest new pricing and allocation rules, for instance
for auctioning frequency spectrums for mobile communication and broadcast and
for electrical power markets.
We raise the following questions:
• Computers are not humans. Economic theory is, in large parts, an empiric sci-
ence about behaviour of humans. How can one transfer results from economic
theory to a setting where only computers interact?
• Moreover, even among economists, it is not undisputed under which circum-
stances market equilibria produce an efficient outcome. Is
economization
of
10
infrastructural resources actually desirable?
• Even if computer scientists are per se interested and involved in modern com-
munication technologies, it is nevertheless a plausible questions what they can
contribute to a theory developed by economists and mathematicians.
The purpose of this introduction is to discuss these points and to formulate
theses
that we claim to be proved by the remaining chapters of this work.
1.1 Applicability of economic theory
In a modern distributed system with an open architecture, the set of tasks to be done
is to be negotiated. Similarly, there has to be an agreement about the consumable
resources. The economist Paul Samuelson1defines economic science as follows:
Economic is the study of how men and society end up
choosing
, with
or without the use of money, to employ
scarce
productive resources that
could have alternative uses, to produce various commodities and dis-
tribute them for consumption, now or in the future, among various peo-
ple and groups in society. It analyzes the costs and benefits of improcing
patterns of resource allocation.[65, p.3]
Note that our resource management setup shows almost all characteristics Samuel-
son associates with economic science: only
scarce
resources need management,
and management essentially takes place by some kind of task priorization: if there
is only one unsplittable task at a time, there is no point in resource management.
Samuelson states that economy studies behaviour of “men and society”. It is
therefore an
empirical
science, and the truth of an economic theory is lastly mea-
sured by its consistency with observation. This is in clear contrast with computer
science which develops techniques to program a computer. A computer program
(we here understand this term in a very general sense, including for example com-
munication protocols) is not “observed” in its behaviour. Rather, computer science
aims to understand the “behaviour”, that is, the execution, of the program com-
pletely. Even if computer scientists sometimes also use
simulations
to analyze a pro-
gram execution in some particular context, results that solely depend on observed
behaviour in simulations are generally judged as not as satisfactory compared with
results that are proven with mathematical rigour.
This rigour does hold, however, for Microeconomics and in particular, Mechanism
design. The
private interests
mentioned above are understood as the
maximization
of individual, real-valued utility
, where the maximization is a mathematical optimiza-
tion problem with constraints and incomplete information on the side of the agents
1Nobel laureate of 1970
11
as well as the control instance. The “approximation” of homo sapiens by
homo oe-
conomicus
is the conditio sine qua non of microeconomics which is thus embedded
in the
neoclassical
branch of economic theory. Neoclassics and the assumptions it
is built upon have been, and still are, fiercly disputed among economists.
Here are a couple of objections posed by the criticists2
• The theory has a lot of paradoxical results. For instance, the classical theory
predicts (Bertrand’s paradoxon, see [81, p.116]) that under perfect competi-
tion, producers will sell their commodities at marginal cost. Clearly fixed costs
are thus not covered, and consequently, all producers run losses.
• More generally, there are many situation where at equilibrium, no market par-
ticipant earns a profit. One might argue that this yields a contradiction for a
theory which is built on the very assumption that everybody should maximize
his surplus.
• What are the implications of negative results? Many theorems, like the theo-
rems of Gibbard-Satterthwaite and of Green-Laffont3, prove the non-existence
of mechanisms with desirable properties. The theory says little about what
happens if these properties are relaxed.
• The most obvious argument against utility-maximization is probably that it is
questionable how a consumer would quantify his utility, say, for watching a
movie in a certain quality. The theory relies on that input variable, not distin-
guishing between “true utility” ( the
gain
of the consumer in comparison with
non-purchase, measured in money), and
substitutional value
, that is, the value
the consumer assigns to the commodity, given the possibilities of alternative
purchases. While the monetary gain is simply non-measurable for most con-
sumer goods4, the substitutional value is problematic since alternatives may
have a different cost structure, and long-term effects of switching commodities
may be hard to anticipate.
• In a broader sense, the assumption of human
rationality
has been very much
under discussion. This discussion was opened by Simon5[72].
2M. Burchardt [13] gives a (partly a little outdated) critical review of microeconomic theory. Even if
he omits game theory and mechanism design, he discusses most of the following points.
3See the next chapter for details.
4or may be unknown in advance, as Simon [72, p.113] remarks:
The consequences that the organism experiences may change its pay-off function – it
doesn’t know how well it likes cheese until it has eaten cheese.
We may add: Similarly, a computer user may not know which quality of service is necessary prior to
using that service.
5Simon was awarded ACM’s Turing award in 1975, and the Nobel price for economics in 1978.
12
Because of the psychological limits if the organism (particularly
with respect to computational and predictive ability), actual human
rationality-striving can at best be an extremely crude and simplified
approximation to the kind of global rationality that is implied, for ex-
ample, by game-theoretic models. While the approximation that the
organism employ may not be the best – even at the levels of com-
putational complexity they are able to handle – it is probable that at
great deal can be learnt about possible mechanisms from an exam-
ination of the schemes of approximation that are actually employed
by human or other organisms.[72, p.101]
In detail, Simon considers the following obstacles that prevent humans from
using a “globally rational” decision strategy:
1. Partially ordered utilities: Simon suggests that human perception of pay-
offs is represented by
vector functions
better than by scalars: because
preferences of different people involved in a decision may be contradic-
tive, because an individual may have more than one concern, and because
there is uncertainty about the
possible consequences
of a decision.
2. Limited “computing power”: Against the proposition of uncertain dynam-
ics, “classicists” may hold that this can be modelled with probabilities. Si-
mons replies are twofold: first, the humans have no knowledge about the
applicable probability functions. Second, humans are incapable6of ac-
tually performing the required calculations for computing an optimal ex-
pected outcome.
Probability theory is not a substitute for missing knowl-
edge,
and the fact that the distribution of some variable is unknown does
not per se justify the claim that it is randomly distributed.7The argument
of limited computing power has been intensively addressed by computer
science’s contributions to mechanism design. We will discuss details in
the next chapter.
6We add: or sceptical on the relevance of the computation’s output
7We do note that we are in contradiction with Laplace [44] here. For this outspoken believer in
determinism, randomness is in all cases just a consequence of lacking knowledge rather than an
objective state. Given two possible outcomes
success
and
failure
of some variable that has been
observed ntimes before, the
Laplace principle (rule of succession)
stipulates that the probability
that
success
occurs at the n+ 1st instance is P(
success
at n+ 1) = s+1
n+2 where sis the number
of successes observed during the first nobservations. In particular, with no prior observation, the
probability of
success
is 1
2. More generally, Laplace suggests that given that no other information
is available, all possible alternatives should be assumed to be of equal probability, that is, a uniform
distribution should be assumed. We raise three points challenging this principle: First, it is an a
priori assumption and can’t be proven. Second, to be applicable, there must be a unique decompo-
sition of the set of all states into elementary alternatives. Third, it does not help at all in the case
of continuous alternatives within an unknown range.
13
Simon introduces a new model of human decision making which has later been
associated with the terms of
bounded8rationality
or
satisficing
. He suggests
that rather than trying to maximize utility, humans set for themselves an
as-
piration level
9which may change over time. Alternatives that meat this aspi-
ration level are considered equally valued in the corresponding category, and
other categories are used to define a preference.10
Cyert and March [17], see [70, p.469f] propose a model for the behavioural dy-
namics of managers, owners, employees, customers and creditors of firms which
is based on Simon’s satisficing. According to them, there is a complex interplay
of the interests of the different parties. In particular, while classic theory assumes
that firms follow a profit-maximizing strategies, Cyert and March suggest that the
company managers (which, after all, implement the company’s strategies) try to
satisfice
goals set to them by the owners while otherwise being mainly interested
in the well-being of their organizatorial unit. Additional surplus generated in “good
times” is buffered in
organisational slacks
which may be used for conflict-mediation
when revenues fall.
8in [72, p.113], “limited”
9[72, p. 111]
10Interestingly, the concept of an “aspired profit” has been adopted in catholic economical ethics. John
Paul II writes in
Centesimus annus
[36, par.35]:
When a firm makes a profit, this means that productive factors have been properly em-
ployed and corresponding human needs have been duly satisfied. But profitability is not
the only indicator of a firm’s condition. It is possible for the financial accounts to be in
order, and yet for the people ˚
U who make up the firm’s most valuable asset ˚
U to be humil-
iated and their dignity offended. Besides being morally inadmissible, this will eventually
have negative repercussions on the firm’s economic efficiency. In fact, the purpose of a
business firm is not simply to make a profit, but is to be found in its very existence as a
community of persons who in various ways are endeavouring to satisfy their basic needs,
and who form a particular group at the service of the whole of society. Profit is a regulator
of the life of a business, but it is not the only one; other human and moral factors must
also be considered which, in the long term, are at least equally important for the life of a
business.
The pope’s argument of
long term
consequences closely resembles Simon’s
uncertainty
of the dy-
namics. However, the Pope argues
normatively
as opposed to Simon who suggests bounded ratio-
nality as a
descriptive model
of human decision-making.
Satisficing as a normative, of course, has been at all times a constant in philosophical-ethical
thinking. Aristotle (Nicomachean Ethics, ch. 6-9 [6]) defines
eudaimonia
(perfect and complete
happiness) as the state where a human assumes the highest virtues (most notably, contemplation),
given that material needs are met
. Aristotle emphasizes (par. 1179a) that eudaimonia, being a
state of perfection, requires that these needs must be fulfilled to a degree such that additional
commodities would not increase happiness.
14
1.2 Networks
The transformation of the
internet
that connected essentially academic, government
or public institutions, to nowadays
world wide web
with millions of users, many of
them private individuals, others members of companies as well as academic and
other institutions, is a challenge to the designers of the communication protocols.
Traditional protocol design tries to optimize under the assumption that all parties in-
volved faithfully honour protocol intentions. Clearly, this can’t be taken for granted
in open systems where cooperation competes with self-interested action, and the
idea of introducing monetary incentives is a compelling one from the first thought.
In this section, we will outline three approaches that analyze the interconnec-
tion of information networks and economics. First, we adopt the narrow view of
the computer scientists incorporating monetary payments into network protocols in
order to give self-interested clients incentives to coordinate their demand and use
the network efficiently. A second line of research is subsumized under the term of
network industries
used by economists to describe industries with
network effects
.
Telecommunication companies and internet service providers are typical examples.
The “computer scientist’s” research line confines to “classical” strategyproof (or
weaker) mechanisms. However, the last decade has seen a lot of development of
game-theory based
auction theory
. Inspiration for most of the theory comes from
government-run spectrum auctions, and some from electronic markets like ebay or
electrical power markets. It is interesting to ask which of the “modern” results
are relevant for the protocol designer. The third subsection gives a – very biased –
overview of modern auction theory.
1.2.1 Computer networks as markets
As computer scientist looking through the economist’s glasses, we will interpret
network resources as scarce
commodities
and network clients as utility-maximizing
agents
. We then can directly apply microeconomic theory to model the dynamics
of the system. The most prominent examples for this paradigm of thinking concern
bandwidth allocation. Nisan and Ronen [57] give a simple model of
shortest path
routing
that allows application of Vickrey-Grove-Clarke mechanism. In their model,
the network is modelled by a directed graph Gwhose
nodes
represent the self-
interested agents with whom their is associated a privately known
cost of routing
a package
. The standard Vickrey-Grove-Clarke mechanism11 yields a cost-covering,
incentive-compatible mechanism that always finds the shortest (measured in costs)
path between any two nodes in the network.
There are many refinements of that model, including ones that consider conges-
tion costs, multicast and multiple service levels.
11see next chapter for details
15
The markets described in these papers are closed subsystems of the economy.
There are no external effects, no competition from outside, no dynamics of cost
structures or customer behaviour and no roles in the economy besides “consumer”
and “producers” of resources. The market rules are “axioms” that, in the best case,
are closely modelled along with “reality”; however, there is no interest in empirical
confirmation of the results. Since the markets are formally and rigorously described,
results have intrinsic value independent from empirical evidence.
Of course, the authors of these papers are well aware of the fact that their mech-
anisms are little used in practice, and do occasionally offer some speculations on
why this is so:
Our approach of using an existing network12 protocol as a substrate for
realistic distributed computations may prove useful generally in Internet-
algorithm design, not only in routing or pricing problems. Algorithm de-
sign for the internet has the extra subtlety that adoption is not a decision
by a systems manager, concerned only with performance and efficiency,
but rather a careful compromise by a web of autonomous entities, each
with its own interests and legacies.[23]
In [23], authors model the network and the cost structure as a graph. They then
prove that a certain Vickrey-Groves-Clarke pricing scheme has nice properties (most
notably, strategyproofness), and is unique with that property. They propose dis-
tributed algorithms for payment computations and analyze its complexity. They
note that having a strategyproof pricing scheme (which is useful if peers possibly
try to manipulate), and letting peers compute payments may be problematic and
formulate an open problem addressing that issue. They also note that the Vickrey
mechanism has a problem of overcharging in comparison with the actual costs, and,
for a rare example, offer an argument based on empiric observation of real internet
providers, that states that for the observed graph, Vickrey pricing would not lead to
extensive overcharging.13
Even if the model could be extended to cover these points, the question whether
it would be advisable for a service provider to adopt the mechanism wouldn’t be
answered. Allowing interdomain routing means opening a new market, and the
model can’t in principle foretell which consequences thus arise:
• Erosion of prices (if total traffic does not grow, but competition between AS
increases), or
12The authors present a pricing scheme for interdomain routing that can be embedded in the existing
Border Gateway protocol.
13We note that there are some more directions the model could be extended: the paper does not model
capacity constraints, it rather assumes that payments grow linearly with the traffic ad infinitum.
Moreover, it is assumed that all packages travelling between a fixed pair of sender and receiver,
take identical routes.
16
• an increase in efficiency which could trigger a larger demand?
• Increased fixed costs or need for investing into new hardware, if traffic does
increase significantly, or
• a larger revenue with only little marginal costs?
It is obvious that these questions cannot be answered by methods of mechanism
design only. In a similar fashion, even if participation in the model is precipated, the
model offers no guidance on how to compute the utilities given as bids. Rather, to
derive statements on these points, the model needs to be embedded into a complete
model of the economy, or at least a sufficiently closed subset of it. But this means
that a discussion of the foundations of economy, as outlined above, can’t be avoided.
1.2.2 Network industries
The economist interested in information technology will find the computer scien-
tist’s perspective far to “technology-centred”. He would prefer establishing a mar-
ket for commodities that make use of resources, rather than trying to price the
resources themselves. Instead of deriving market rules from the technical system,
he would ask his “technology experts” to implement market rules of his choice. The
economist comes with his rich tradition of market analysis, and will gladly apply
what he has discovered about markets for bread or railway tickets or oil to new
“products” like internet access or mobile communication.
The economist, however, will notice that a theory that works well with markets
for bread won’t necessarily work for mobile communication. Oz Shy defines four
main characteristics that distinguish markets for
network products
from classical
markets [71, p.1]:
•
complementarity, compatibility and standards:
Network products are not used
standalone. Computer hardware and software can be purchased indepen-
dently and are produced by different manufacturers, but only together they are
useful to the consumer. Manufacturers have to meet strategic decisions about
which products they design to cooperate, be it hardware architectures, op-
erating systems and applications, or mobile phones and wireless networks. If
compatibility is chosen, firms, even competing ones, must find a modus vivendi
to develop standards that enable interoperability.
•
consumption externalities:
Utility of network product greatly depends on the
size of the network. Trivial examples are communication devices like fax ma-
chines that are useful only if they enjoy some degree of popularity.
•
switching costs:
Network products are complex. While it is easy to substitute
corn for wheat, it is not easy for a company to switch the operating system of
all their computers.
17
•
“Significant economies of scale in production”
, that is, production costs are
highly non-linear in the production amount. Typically, marginal cost – like
“producing” one more software licence, or routing one more IP package – are
low in comparison to the “fixed” costs, say, of developing a new application, or
setting up a new telephone line.
Clearly, the picture the economist looks at is much more complex. He is deeply
involved in the disputes that concern economic behaviour of humans. Although we
are not aware of any example, we maintain that it is quit possible to develop an
economic theory of network industries that builds on individuals that are not utility-
maximizing.
Let us consider how the AS interdomain routing problem described in the previ-
ous section looks from a “network industry” point of view. Admitting interdomain
transit traffic adds complexity to the market of data routing. In addition to offering
a service to end consumers, a provider can now try to establish itself as a backbone
transit “hub” that routes traffic from other providers. From an economic point of
view, this is equivalent to
outsourcing
the traffic routing from the service offered to
consumers, and can be compared with a railway company renting its tracks to other
carriers. Adopting the extended business plan requires an extension of the Border
Gateway protocol (BGP). Clearly, the amount and structure of competition will de-
pend on mutual compatibility, and establishing one or multiple industry standards
needs a lot of strategic consideration. Marginal routing costs are low in comparison
with the cost of the infrastructure and the costs of changing an established protocol.
1.2.3 Auction theory
There has been extensive work in auction theory in the last fifteen years. Most
of the game-theoretic analysis was inspired by the need for efficient allocation of
spectrum licenses for broadcast and telecommunication. While auctions have tradi-
tionally been used by governments for property, eg land, sale and for procurement,
the task of distributing these licenses pose a couple of new challenges: Most no-
tably, the value of these licenses is difficult to estimate. On one hand, spectra are
clearly a
scarce
resource with no production costs. In that sense, they compare
with treasures of the soil. Explanation for market prices for treasures of the soil
was a challenge to economists in the 18th and 19th century and lead to a refutation
(at least partial) of the labour theory of value and the establishment of the marginal
value theory. This theory estimates the per-unit price of a commodity to equal the
additional utility generated if one more unit of the commodity is available, thus solv-
ing the “paradoxon” that while water has a higher utility than diamonds, the price
for diamonds is nevertheless much higher.
In order to apply marginal value theory to spectrum licenses, one would need to
forecast the revenue that companies can generate from the licenses. This, however,
18
is difficult since governments don’t know business plans of private firms. For some
time, mobile phone licenses in the US were assigned by lottery, and it was hoped
that an efficient allocation would evolve from secondary trade. The result was a
fragmented and rather inefficient market, and US agencies became ready to adopt
other schemes.
Auctions
were seen as a tool to take advantage of the competition
between interested firms to extract a maximum of willingness to pay. Indeed auc-
tions have performed, in some cases, very successful, while producing disappointing
results in others.
The work of Vickrey on second price auctions [78] has served as inspiration for
a tremendous amount of papers that generalized his results to many settings. Nev-
ertheless, the few examples were pure second price auctions have been used for
spectrum license sale have ended with extremely pure results. Vickrey auctions
have a couple of disadvantages that make them unusable in some settings.
In 2004, two leading auction theorists, both involved in the design of spectrum
and other government-run auctions in various countries, have published books [43,
50] on the modern economy of auctions. According to them, the following problems
have to be addressed:
• Vickrey auctions, while stragegyproof, are not
groupwise
strategyproof: they
are very sensitive to colluding bidders. Sellers can submit shill bids to increase
prices. If the Vickrey mechanism is applied to combinatorial auctions, the
resulting allocation is efficient but the payments can be low even if there are
many high bids. Revenue may even shrink when more bids are submitted.
Milgrom presents the following example[50, p.57f]:
–Let there be two goods Aand B, and four bidders b1, b2, b3, b4. Suppose
that b1values the package of Aand Bwith 10 and b2with 9. Suppose b3
values Awith 10 and b4values Bwith 10. b1and b2have no utility from
a single item, while b3and b4have no additional utility from the second
item.
The efficient allocation, and thus the Vickrey-Grove-Clarke mechanism,
gives Ato b3and Bto b4. However, the Vickrey mechanism lets b3and b4
pay nothing. If only b1and b2were present, b1would pay 9 for the package
of Aand B.
In this example, the coalition consisting of the seller, b1and b2would prefer to
trade among themselves. Milgrom [50, p.303] defines the
core
of an auction
to be the set of all outcomes cwith the property that there is no coalition
which could find another outcome by trading only among themselves, such
that all members of that coalition are better off with that outcome, than with
c. Outcomes of Vickrey-Grove-Clarke mechanisms for combinatorial auctions
are not generally in the core.
19
Even without this pathology of the Vickrey auction, bidders can collude by
agreeing on some kind of “desirable” auction outcome. Klemperer [43, p.104]
presents a couple of examples where competing bidder try to send signals
through their bids to their competitors to persuade them to stop bidding on
some items in exchange for others.
• Vickrey auctions are not even efficient if there is a potential of
mergers
[50,
p.60]: in the above example, even if a merger between b3and b4would in-
crease the valuation by a certain amount, say, 25%, the merged company would
have to pay 10, thus suffering from a reduced total profit. In general, in the
presence of complementary values, Vickrey auctions discourage mergers. The
opposite is the case if goods are substitutes.
•
Attracting a sufficient number of bidders
is often more decisive for a success-
ful auction than pricing rules. Klemperer and Milgrom quote the results of
the New Zealand spectrum auctions as an example where, due to a large num-
ber of auctioned licenses for rather small areas, there were some licenses for
which only one or very few bidders placed a bid at all. Since Vickrey pricing
was used, some licenses went away for almost no payment, even if there was
a single bid with a proper amount. The results lead to the demission of some
of the politicians who could not advocate these results to the public, even if
the question whether more revenue could have been generated with modified
rules could not obviously be answered.
Klemperer [43, p.42] formulates the
revenue equivalence theorem
which states
that in auctions where every buyer wants to acquire at most one good, and
buyer’s types are independent private values, and supposed that bidders with
the lowest possible type have zero gain from the auction, the seller’s expected
revenue does
only depend on the allocation rule
. In particular, an efficient
auction would always make the seller either to retain the good, or to give it
to the bidder with the highest valuation. The theorem states that the revenue
is independent from the pricing rule. Consequently, in the case of a single
item auction, the only way to make an auction efficient is to set an optimal
reserve price
, that is, the minimum bid that a seller would possibly accept.
Indeed one can compute the optimal reserve price for various settings. How-
ever, Bulow and Klemperer have shown ([11], see [43, p.27]) that, under some
weak assumptions, attracting a single additional bidder increases the expected
seller’s revenue more than setting an optimal reserve price ever could.
Klemperer[43, p.113] states:
The fact that collusion and entry deterrence and, more generally, buyer
market power is the key to auction problems suggests that auction design
may not matter very much when there is a large number of potential
20
bidders for whom entry to the auction is easy. For example, though much
ink has been spilt on the subject of government security sales, auction
design may not matter much for either price or efficiency in this case.
Continuing, Klemperer cautions that empirical literature on that topic, e.g. various
analysis of US treasury auctions, is inconclusive, and irrelevance of auction design
is not proven. We note that most theoretical results are proven only for single
item auctions. In particular, there is no known revenue equivalence theorem for
combinatorial auctions.
1.2.4 Characteristics of protocol design
This thesis proposes usage of monetary transfers as a tool for resource management
whose intention is
an efficient usage of the available resources
. Economic theory
is interesting to us as long as it says something about the behaviour of the system
clients. This is a narrow focus: for instance, we do not pursuit the question whether
it is advisable for the resource’s owner to invest into producing additional resources.
On the other hand, if a protocol would allow users to gain a better service, say, by
forming a coalition with other users, then this would be relevant for the protocol
designer.
The “market” of a communication network has a structure different from the mar-
ket for spectrum licences or electric power generation. In the following, we will
give some characteristics of the resource management market.
•
Large number of users.
Internet service providers typically have thousands
of users accessing their network at any given time, and similar numbers hold
for telecommunication providers. A news publishing service may easily have
hundreds of subscribers.
•
Anonymity of usage.
Users may know some other network users, but do not
generally know the resources they use at any given time. Due to the large
number of users, they have little chance to know a significant portion of the
usage profiles.
•
Interdependence of resources.
The level of service quality desired can only be
provided by a
bundle
of resources. In a communication network, typically a
chain of links is used. More generally, other resources besides bandwidth, like
memory or computational power, have to be combined.
•
Impossibility of demand coordination.
In the case of the spectrum auctions,
we had the phenomenon that some companies tried to coordinate demand in
the sense that they proposed “splits” of the market, for example, by bidding
aggressively for some bundle of licenses and leaving other bundles to competi-
tors. We hold that this type of coordination is not possible for communication
21
markets. There is no price differentiation in internet data traffic based on
geographic realities, and it seems very improbable that users would accept
one.
•
Large number of transactions.
A typical transaction for us is
sending some IP
packages along a link
, or
connecting to some multicast stream for a duration
of some seconds or minutes
. We expect that within an hour, thousands if not
millions such transactions take place.
•
Automated bidding.
Bidding in this context will often be performed by au-
tomatized
agents
. Strategic bidding, therefore, is only feasible if it can be
automatized, too. A consequence of that is, for example, that spontaneous
“signalling” between agents is not possible.
•
Complexity is important.
Due to the large number of transactions, the amount
of computation and communication required for placing bids, performing and
communicating the matching is an important issue, particularly so because all
of that has to take place in real time.
1.2.5 What are good protocols?
We are now ready to formulate the main results of this introduction: the criterions
by whom we judge whether a given mechanism14 is a good one.
•
Existence of dominant strategies or equilibria for single players.
Equilibria al-
low forecasting how the system state will develop. If collusion between players
is not possible, it is safe to assume that players will follow dominant strategies
if they exist. In view of the negative theoretical results, often there won’t be
good mechanisms with dominant strategies, and therefore, weaker equilibria
like Bayes-Nash equilibria can be considered.
•
Efficiency at the equilibrium.
It would be desirable to have equilibria with
maximized efficiency with respect to the accumulated utility. Often, selfish
behaviour will lead to a suboptimal equilibrium.
•
Acceptable complexity (for users and owners) in the targeted usage scenario.
Combinatorial optimization problems are often NP-hard in the worst case.
Avarage case complexity may be more encouraging, and acceptable approx-
imations (though not with constant bound) may exist. A mechanism’s com-
plexity is acceptable if for the intended usage, the required optimization can
be computed with sufficient quality.
14By mechanism, we mean here the part of a communication protocol that deals with monetary trans-
fers.
22
•
Infeasibility of groupwise strategizing in the targeted usage scenario.
Even
mechanisms with dominant strategies are not generally groupwise strategy-
proof. The risks of collusion have to be analyzed with respect to the specific
usage scenario.
In a subsequent step, it may be of interest how the protocol interacts with the cur-
rent business model of the network owners. This, however, is not strictly a question
for computer scientists and not in the focus of this work.
1.3 Related work
We give detailed account of related work in the relevant chapters. Here we men-
tion only authors and works that opened major lines of research that we consider
important for this thesis.
Distributed network resource sharing can be seen as a cooperation problem be-
tween selfish agents. Such problems were described first by Rosenschein and
Zlotkin [86].
The paper of Nisan and Ronen [57] was the first to transfer mechanism design
theory from microeconomic theory to computer science. The paper contains appli-
cation scenarios for task scheduling and unicast end-to-end path-finding and trig-
gered a huge amount of follow-up work. Nisan and Ronen’s goal is the development
of efficient mechanisms with dominant strategies. Nisan and Ronen’s shortest-path
scenario was developed further by Feigenbaum et al. in [57] and Hershberger et
al. [32, 35]. Many settings involve the use of combinatorial auctions. In chapter 3,
related work on combinatorial auctions and exchanges is presented.
Generalizations for multicast setting are treated in [54, 26, 25, 1, 7, 8]. The
economical problem behind multicast settings is that of splitting the costs of a
public
project
which is extensively treated in the literature, see [48] for a start. A general
overview on applications of mechanism design with dominant strategies to computer
science is given in [24].
Kelly et al. [42, 40, 41] focus on indirect mechanisms where network users con-
trol the flow via parameters that can be interpreted as monetary payment or pay-
ment in form of service degradation like increased latency. Their mechanisms don’t
have dominant strategies but often unique Nash equilibria which are approached
in tatonnement processes. Roughgarden and Tardos [63] take a similar approach
and analyze how network usage is affected by users that are selfish and sensible to
latency.
23
1.4 Our work
This thesis tackles the problems posed above from different sides. After present-
ing relevant definitions and classic results and giving some general examples for
applications in chapter 2, we motivate and develop a market type that is a spe-
cialized combinatorial exchange. We develop a new pricing scheme that satisfies
budget-balance while preserving some of the useful properties of Vickrey-Grove-
Clarke mechanisms. Furthermore we introduce a new clearing rule, the
commit
window clearing
, and prove - empirically and partly analytically- its superiority to
the well-known periodic and random clearing rules. In chapter 4, we give an appli-
cation of the newly developed market to some unicast network resource managing
scenarios with advanced reservations.
The following chapters consider multicast scenarios. Chapter 5 contains results
of somewhat pessimistic nature: we show that mechanisms for multicast pricing im-
plement generally quite inefficient equilibria: we show that the coordination ratio
performs poorly for quite a couple of different utility functions. Finally, chapter 6
deals with publish/subscribe systems that we understand as special multicast sys-
tems. After giving a formal treatment that implements some message completeness
guarantees, we develop a pricing mechanism with dominant strategies for these
systems.
Thesis 1.
It is possible to implement a combinatorial exchange with budget-balanced
pricing that guarantees sellers additional revenue compared to non-combinatorial
markets.
Thesis 2.
The efficiency of a combinatorial exchange market with autonomous
traders depends on the used clearing policy. Commit window clearing generates
a higher revenue compared with periodic and random clearing.
Thesis 3.
Network bandwidth reservation with fixed reservation length can effi-
ciently be built on a combinatorial exchange market that uses commit window clear-
ing. Using a simple stochastic model that takes advantage of publicly known infor-
mation on call characteristics, one can also implement reservations with unknown
in advance length.
Thesis 4.
If a network splits available (inelastic) supply in proportion with the
user’s willingness to pay, and users have linear utility, the allocation at the equi-
librium has a coordination ratio of at least
3
4
, while for users with logarithmic utility
functions, the coordination ratio is unbounded. In the corresponding multicast sce-
nario, the coordination ratio is always unbounded.
Thesis 5.
Marginal cost pricing is an efficient pricing for publish/subscribe scenar-
ios if budget-balance is not required. Otherwise, the budget-balanced Shapley value
pricing guarantees a minimal efficiency loss.
24
2 Background: Game theory and
mechanism design
This chapter presents definition and classical results from game theory, microeco-
nomics, mechanism design and auction theory that is used in the later chapters.
Main references are [48] for game theory, microeconomics and mechanism design,
and [43, 50] for auction theory. We don’t give proofs for well-known results, but do
give detailed references.
2.1 Mechanisms
Let Ia set of
players
or
agents
i∈I. Let Xbe a set of
alternatives
, or
outcomes
.
Every i∈Ihas a
utility profile
ui:X7→ R. Let Ui⊆XRbe the set of all possible
strategy profiles for agent i.
For a vector ~u = (ui:i∈I), let us write ~u|uj=xfor the vector (vi:i∈I)with
vj=(ujif j6=i
xif j=i(2.1)
For a vector ~u = (uj:j∈I), let ~u−idenote ~u−i= (uj:i6=j∈I).
Definition 1 (Mechanism).
A
(direct) mechanism M
is a tuple
M= (oM, pM)
such
that
•
oM
is a
social choice
function that maps every
profile vector ~u = (ui:i∈I)
to
some outcome
oM(~u)∈X
, and
•
pM
is a
payment function
mapping every
~u = (ui:i∈I)
to some
payment
vector pM(~u) = (pM
i:i∈I)
with
pM
i∈R
.
M
• is
deficit-free
if
(∀~u)X
i∈I
pM
i(~u)≥0,(2.2)
• is
budget-balanced
if
(∀~u)X
i∈I
pM
i(~u) = 0,(2.3)
25
• satisfies
voluntary participation
if
(∀~u = (ui:i∈I)) (∀i)uioM(~u)−pM
i(~u)≥0,(2.4)
• satisfies
consumer sovereignty
if for all
i∈I
, all
x∈X
and all
~u = (ui:i∈I)
,
there is
u0
i∈Ui
such that
oM~u|ui=u0
i=x
.
Example 2.
Consider the following scheduling problem:
Let there be
n
jobs and
m
processors such that
ti
j
are processor
i
’s cost for pro-
cessing job
j
. The vector
(ti
j: 1 ≤j≤n)
is processor
i
’s
type
. Let
X
, the set of
outcomes, be the set of all possible functions
x:{1,...,n} 7→ {1,...,m}
that assign
to every job
j
(
1≤j≤n
) a processor
i
(
1≤i≤m
).
Define
M= (o, p)
by
oti
j: 1 ≤i≤m, 1≤j≤n∈arg min
x∈X
X
i,j:x(j)=i
ti
j
(2.5)
pti
j: 1 ≤i≤m, 1≤j≤n=X
i,j:o(j)=i
ti
j(2.6)
Then
M
is a direct mechanism for
X
that is not deficit-free (since it makes only
payments but does not generate any income). It does satisfy voluntary participation
(since it compensates a processor for processing a job exactly with the amount of
the claimed costs). It does not satisfy consumer sovereignty since a processor can’t
force to get a job assigned, even if he claims that he has zero costs of processing:
there could be another processor with no costs either.
2.1.1 Strategies
Definition 3 (Strategy).
A
(pure) strategy
of agent
i
for mechanism
M
is a mapping
s:ui7→ s(ui)
from the set of utility profiles of
i
to itself.
Definition 4 (Dominant strategy).
A strategy
s
is
dominant
if for all profiles
~u =
(ui:i∈I)
and for all
u0
i6=ui
,
uioM(~u|ui=u0
i)−pM
i~u|ui=u0
i≤uioM(~u)−pM
i(~u)(2.7)
A strategy is
strictly dominant
, if strict inequality holds in (2.7) for at least one
profile vector
~u
.
Definition 5 (Truthful mechanism).
A mechanism
M
is
(strictly) truthful
if for ev-
ery agent
i
, the
truth-telling strategy
, that is, the strategy
s(ui) = ui
, is (strictly)
dominant.
26
Definition 6 (Implementable social choice function).
A social choice function
o
is
implementable in dominant strategies
if there is a mechanism
M= (oM, pM)
such
that there is a strategy vector
~s
of dominant strategies in
M
such that for all profiles
~u
,
o(~u) = oM(s1(u1),...,sn(un)) (2.8)
In this case, we say that
Mimplements o
.
Remark 7.
If
M= (oM, pM)
is truthful, then
M
implements
oM
.
Example 8.
The mechanism in example 2 is
not
truthful. Agents are compensated
with an amount equal to their claim. Therefore, increasing a claim such that the
social choice function remains unchanged is more favourable to a processor than
truth-telling.
Note that this shows also that while the
o
minimizes total cost based on the costs
claimed by the processors
, the social choice function that
M
implements does not
minimize social total costs (since the processors won’t reveal their true costs).
The notions of
dominant strategy
and
truthfulness
are strong ones: a dominant
strategy has optimal performance, no matter which strategies are used by other
players. The notion of
Nash equilibrium
is weaker: a stragegy vector is a Nash
equilibrium if no single player can gain from unilateraly changing his strategy.
Definition 9 (Nash equilibrium).
Let
~
S= (si:i∈I)
be a vector of strategies and
let
~u = (s(ui) : i∈I)
. We say that
~
S
is a
(pure) Nash equilibrium
, if for all
i∈I
and
u0
i6=s(ui)
,
uioM(~u|ui=u0
i)−pioM(~u|ui=s(ui))≤uioM(~u)−pM
i(~u)(2.9)
We say that
~
S
is a
strict Nash equilibrium
if strict inequality holds in (2.9).
So if ~
Sis a Nash equilibrium, then no agent ihas an incentive to divert from his
strategy
provided that the others don’t divert from theirs
.
2.1.2 Mixed strategies
Instead of following a deterministic strategy, an agent can
randomize
over his op-
tions.
Definition 10 (Mixed strategy).
A
mixed strategy s
for agent
i
is a probability
distribution over the set of all possible strategies of
i
.
Let
o
be a social choice function. For a vector
~s = (si:i∈I)
of mixed strategies
agents
i∈I
, we write
ui(o(~s))
and
pi(o(~s))
as a shortcut for the
expected value
of the random variables
ui(o(s1,...,sn))
and
pi(o(s1,...,sn))
, where
si
are random
variables with distribution according to
si
.
27
The generalization of definitions 4 and 9 is straightforward:
Definition 11 (Dominant mixed strategy).
A mixed strategy
s
is
dominant
if for all
profiles
~u = (ui:i∈I)
and for all
u0
i6=ui
,
uioM(~u|ui=u0
i)−pM
i~u|ui=u0
i≤uioM(~u)−pM
i(~u)(2.10)
with the expected value interpretation of definition 10. Similarly, a mixed strategy
is
strictly dominant
, if strict inequality holds in (2.7) for at least one profile vector
~u
.
Definition 12 (Mixed Nash equilibrium).
Let
~
S= (si:i∈I)
be a vector of strate-
gies and let
~u = (s(ui) : i∈I)
. We say that
~
S
is a
Nash equilibrium
, if for all
i∈I
and
u0
i6=s(ui)
,
uioM(~u|ui=u0
i)−pioM(~u|ui=s(ui))≤uioM(~u)−pM
i(~u),(2.11)
again with the expected value interpretation of definition 10. We say that
~
S
is a
strict Nash equilibrium
if strict inequality holds in (2.9).
The following is obvious:
Fact 13.
If for
i∈I
,
si
is a dominant (mixed) strategy for agent
i
, then
(si:i∈I)
is
a (mixed) Nash equilibrium.
2.1.3 Efficiency of equilibria
A “good” mechanism will maximize total welfare. This leads to the following defini-
tions:
2.1.3.1 Dominant strategies
Definition 14 (Efficient social choice function).
A social choice function
o
is
effi-
cient
, if
X
i∈I
ui(o(~u)) ≥X
i∈I
uio0(~u)(2.12)
for all social choice functions
o06=o
and profile vectors
~u = (ui:i∈I)
.
Definition 15 (Efficient mechanism).
A mechanism
M= (oM, pM)
is
efficient
(in
dominant strategies), if there is a strategy vector
(si:i∈I)
such that for all user
profile vectors
(ui:i∈I)
,
• for every
i∈I
,
si
is a dominant strategy for
i
, and
28
•
X
i∈I
uioM(s1(u1),...,sn(un))≥X
i∈I
uio0(s1(u1),...,sn(un))(2.13)
for all
o0
.
M
is
strictly efficient
if for all
i∈I
,
si
is strictly dominant.
Note that
• although equation (2.13) does not depend on pM, nevertheless Mbeing effi-
cient
does
depend on pM, since it depends on the payment function whether a
given strategy is dominant, and
• it is neither necessary nor sufficient for Mbeing efficient that oMis efficient.
However, the following fact is a consequence of the
revelation principle
(see [48],
proposition 23.C.1):
Fact 16.
If
M
is efficient, then there is
M0
such that
M0
is equivalent to
M
in
the sense that for any vector
~s
of dominant strategies in
M
, there is a vector
~s0
of
dominant strategies for
M0
such that for any profile vector
~u
,
oM(s1(u1),...,sn(un)) = oM
0s0
1(u1),...,s0
n(un)(2.14)
and
pM(s1(u1),...,sn(un)) = pM
0s0
1(u1),...,s0
n(un)(2.15)
2.1.3.2 Coordination ratio
It is safe to assume that “rational” (that is, utility maximizing) agents will play ac-
cording to a dominant strategy equilibrium. Thus, a strictly efficient mechanism will
yield an efficient outcome. This, however, is not generally true for Nash equilibria
since games can have multiple Nash equilibria with different social surplus. There-
fore, the definition of the coordination ratio contains a reference to a specific Nash
equilibrium that can be dropped only if it is unique.
Definition 17 (Coordination ratio).
Let
~s
be a Nash equilibrium for
M
. The
coordi-
nation ratio
of
~s
is defined to be
rM
~s = inf
~u=(ui:i∈I)P
i∈I
uioM(s1(u1),...,sn(un))
max
x∈XP
i∈I
ui(x)(2.16)
If
~s
is the unique Nash equilibrium, we write
rM
for
rM
~s
.
29
2.1.4 Existence of Nash equilibria
2.1.4.1 Existence of Nash equilibria for given mechanisms
Not every mechanism has a mixed Nash equilibrium:
Example 18.
Let
X={1,2}
and let the profiles of agents 1 and 2 be given by
u1(1) = 1 u1(2) = 0 (2.17)
u2(1) = 0 u2(2) = 1 (2.18)
Now let the social choice function
o
be defined by
o(u1, u2) = (1
if
u1(1) ≥u2(1)
2
if
u1(1) < u2(1) (2.19)
and let the payment function
p
be the zero function. That means, “winner” in this
game is the agent who reports the higher utility. Clearly, there is no Nash equi-
librium for
(o, p)
(not even for a mixed strategy), since the agent that reported the
smaller utility could always have won the game by reporting a higher one.
However, mixed Nash equilibria do exist under quite general assumptions:
Theorem 19 (see [48], proposition 8.D.3).
Assume that
Ui
are compact and convex
subspaces of some Euclidian space for
i∈I
, and the
ui(u1,...,un) := ui(o(u1,...,un))
and
pi(u1,...,un) := pi(o(u1,...,un))
are continuous in
(u1,...,un)
and quasi-concave1
in every
ui
. Then there is a mixed strategy Nash equilibrium for the mechanism
(o, p)
.
A mixed Nash equilibrium does also exist if there are finitely many agents with
finitely many strategies:
Theorem 20 (see [48], proposition 8.D.2).
Let
I
be finite and suppose that for every
i∈I
,
Ui
is finite. Then any mechanism has a mixed Nash equilibrium.
Example 21.
Suppose that there are users
1,...,n
of some link of capacity
1
. Sup-
pose that the link’s bandwidth is split in proportion with the
bid amounts b1,...,bn
that the users attach to their bids. Users pay an amoutn on money equal to their
bids. User
i
’s surplus then is
si=ui bi
Pn
j=1 bj!−bi(2.20)
The above theorem implies that there is a Nash equilibrium for the associated game
if all
ui
are quasi-concave. Chapter 5 gives more results for this scenario.
1f:R⊇D7→ Ris
quasi-concave
if for all y∈R,{x∈D:f(x)≥y}is convex.
30
Note that even in the finite case, pure Nash equilibria do not generally exist:
Example 22 (Matching pennies).
Let
X
and the utility profiles be as in example 18
and let
o
be given by
o(u1, u2) = (1
if
u1(1) = u2(1)
2
if
u1(1) 6=u2(1) (2.21)
and let
p
be the zero function. Then there is no pure Nash equilibrium for
(o, p)
(since the “looser” of the game would win if he (and only he) changed his value of
ui(1)
). There is, however, a mixed Nash equilibrium that lets every player randomly
choose between his two possible choices for
ui(1)
. In fact, even if only one of the
agents chooses
ui(1)
randomly and the other agent follows any strategy, the yielded
strategy set is a mixed Nash equilibrium. This shows that Nash equilibria are not
unique in general.
2.1.4.2 Bayesian Nash equilibria and implementable choice functions
Definition 9 of Nash equilibrium required that for every iwith type uiand
any
vector
of the “remaining” types ~u−i, agent iis better off playing according to his equilib-
rium strategy provided that the remaining agents do.
If we assume that the agent’s types uiare
random variables
drawn from Uiac-
cording to some statistical distribution, we can weaken the notion of Nash equilibria
even further:
Definition 23 (Bayesian Nash equilibrium).
Suppose that
~u ∈ ×i∈IUi
are drawn
according to some probability distribution
F
. Let
M= (oM, pM)
. A strategy vector
~s
is a
Bayesian Nash equilibrium
if for all
i
and all
ui, u0
i∈Ui
,
E~u−ihuioM(u0
i, ~u−i)−pioM(u0
i, ~u−i)i≤E~u−ihuioM(ui, ~u−i)−pM
i(ui, ~u−i)i
(2.22)
where the expected value E is taken over all possible
~u−i
subject to
F
conditioned
on
ui
.
Definition 24 (Expected externality mechanism).
Let
o
be a social choice function.
The
expected externality mechanism
for
o
is the mechanism
M= (o, p)
, where for
~u = (ui:i∈I)
pi(~u) = −E~v0
−i
X
j6=i
vj(o(ui,~v−i))
+1
n−1X
j6=i
E~v−i
X
k6=j
vk(o(uj,~v−j))
(2.23)
The following is well-known (see [48, p.886f]):
31
Theorem 25.
If
o
is efficient and the agent’s types are independently from each
other, then the expected externality mechanism for
o
is budget balanced and imple-
ments
o
in Bayesian Nash equilibria.
While the expected externality mechanism is efficient and budget balanced, it
will not generally satisfy the condition of voluntary participation. The Myerson-
Satterthwaite theorem ([56], see [48], proposition 23.E.12) states that for a specific
setting, there are no budget-balanced mechanisms that implement an efficient social
choice function in Bayesian Nash equilibria with voluntary participation.
Theorem 26 (Myerson-Satterthwaite theorem).
Let there be two agents 1,2 and let
X={1,2}
and
ui(x) = (ui
if
x=i
0
otherwise
(2.24)
for
i= 1,2
. Suppose that the
ui
are independently drawn from intervals
[u
min
i, u
max
i]
with strictly positive densities, and
(u
min
1, u
max
1)∩(u
min
2, u
max
2)6=∅
. Then there is no
efficient social choice function
o
that is implementable in Bayesian Nash equilibria
with voluntary participation and budget-balanced payment rule.
2.1.5 Existence of dominant strategies
2.1.5.1 Choice functions that are implementable in dominant strategies
While the existence of mixed Nash equilibria is assured in many cases, far less
mechanisms have dominant strategies for their participants. Roberts [61] (Theorem
3.1) has given a characterization of social choice functions that are implementable
in dominant strategies:
Theorem 27.
Let
o
be a social choice function implemented by
M
in dominant
strategies. Assume that for all
x∈X
, there is
~u
with
o(~u) = x
. Then there is a
weight vector ~
k= (ki:i∈I)
with
ki≥0
and some
i
with
ki>0
, and a function
F:X7→ R
, such that for all
~u
,
o(~u)∈arg max
x∈X(X
i∈I
ki·ui(x) + F(x))(2.25)
If we take Fas the utility function of some “additional” agent i0, Theorem 27 can
be interpreted as saying that exactly those choice functions are implementable in
dominant strategies that maximize
weighted total surplus
for some weight vector ~
k.
2Note that the condition of budget-balance is not explicitly mentioned there but derived from the
context.
32
2.1.5.2 Vickrey Groves Clarke mechanisms
Definition 28 (Vickrey-Groves-Clarke mechanism).
A mechanism
M= (oM, pM)
is
a
Vickrey-Groves-Clarke (VGC) mechanism
if
1.
oM
is efficient, and
2.
pM
has the form
(pM
i:i∈I)
with
pM
i(~u) = −
X
j6=i
ujoM(~u)
+hi(~u−i)(2.26)
for some function
hi
which does not depend on
ui
.
A classic result (see e.g. [48], proposition 23.C.4) is
Theorem 29.
If
M
is a Vickrey-Groves-Clarke mechanism, then
M
is truthful and
efficient.
Green and Laffont [30] proved that
Theorem 30.
If for every
i∈I
and every function
f:X7→ R
, there is
ui∈Ui
with
ui(x) = f(x)
for all
x∈X
, then every truthful efficient mechanism is a Vickrey-
Groves-Clarke mechanism.
2.1.5.3 Budget balance
VGC mechanism are in general not budget balanced. In fact, Green and Laffont [30]
showed that they are never, under the prerequisites of Theorem 30:
Theorem 31.
If for every
i∈I
and every function
f:X7→ R
, there is
ui∈Ui
with
ui(x) = f(x)
for all
x∈X
, then there is no truthful efficient budget-balanced
mechanism.
2.2 Application of VGC mechanisms to allocation
problems
Definition 32 (Allocation problem).
An
allocation problem
for agents
i∈I
and a
set of goods
J
is a set of social choices
X⊆ {(ki
j:i∈I, j ∈J, ki
j∈R)}
with a set of
utility profiles
(Ui:i∈I)
such that for all
i
and
ui∈Ui
,
∀~
k,~
k0∈X"(∀j∈J)~
k−i
j=~
k0−i
j⇒ui(~
k) = ui(~
k0)#(2.27)
and for all agents
i
,
(∀j)ki
j= 0⇒ui(ki0
j:i0∈I, j ∈J) = 0 (2.28)
The set
J
is called
set of goods
.
33
ki
jcan be understood as the quantity of good jthat is allocated to agent i. Equa-
tion (2.27) says that an agent is indifferent between two social choices if the quan-
tity of goods awarded to him is identical in both choices. Equation (2.28) says that
agents have zero utility if they don’t get any good.
Example 33 (Task scheduling).
Let there be agents
1,...,n
and a set of
tasks
each
of whome can be processed by any of the agents. Suppose that processing task
j
by
agent
i
induces cost
ci,j
to agent
i
. A function
f:J7→ I
that assigns to every task
j
some agent
i
can be interpreted as an allocation function by setting
ki
j= 1
iff
f(j) = i
and 0 otherwise. Agent
i
’s utility from function
f
then is
ui(f) = −P{j∈J:f(j)=i}ci,j
.
Example 34 (Combinatorial auction).
Fix a set
I
of agents and a set
J
of goods.
Define
X=(ki
j:i∈I, j ∈J, ki
j∈ {0,1},X
i∈I
ki
j≤1
for all
j∈J)(2.29)
This models a market where agents
i
compete about goods
j
each available in
exactly one copy. Retaining goods is allowed (it would not if we would require
Piki
j= 1
for
j∈J
).
Equation (2.27) allows us to write
ui(G)
as a shortcut for
ui(ki
j:i∈I, j ∈J)
where
G={j∈J:ki
j= 1}
.
Let
o
be a social choice function for
X
. For a profile vector
~u
, write
oi(~u) = {j∈J:ki
j= 1,(ki
j:i∈I, j ∈J) = o(~u)}(2.30)
and
Vo(~u) = X
i
ui(oi(~u)) (2.31)
So
oi(~u)
is the set of goods allocated to agent
i
by
o
if the utility profile is
~u
.
Now let
M= (oM, pM)
be a VGC mechanism for
X
that satisfies voluntary partici-
pation and the
no positive transfers condition pM≥0
. This implies
pM
i(~u|ui≡0) = 0
.
The efficiency condition (2.12) can now be written as
oM(~u)∈argo:×iUi7→Xmax X
i
ui(oi(~u)) (2.32)
For the payment rule, we get according to (2.26) (and dropping the superscript
M
of
oM
for notational convenience)
pM
i(~u) = −
X
i06=i
ui0oi0(~u)
+hi(~u−i)(2.33)
=−Vo(~u) + ui(oi(~u)) + hi(~u−i)(2.34)
34
So
0 = pM
i(~u|ui≡0) = −Vo(~u|ui≡0) + 0 + hi(~u−i)(2.35)
and consequently
hi(~u−i) = Vo(~u|ui≡0)(2.36)
Finally we get
pM
i(~u) = Vo(~u|ui≡0)−Vo(~u) + ui(oi(~u)) (2.37)
The term
Vo(~u)−Vo(~u|ui≡0)
is called
Vickrey discount ∆o
vic
(~u)
. So
pM
i(~u) = ui(oi(~u)) −∆o
vic
(~u)(2.38)
The value of the Vickrey discount is exactly
the marginal social surplus contributed
by agent i
. Agent
i
pays his utility discounted by this contribution.
Note that
M
is not budget balanced. Rather, if the utilities that the agents draw
from the goods are nonnegative, the mechanism generates a surplus, the “revenue”
of the auction.
Example 35 (Combinatorial exchange).
In a combinatorial auction, the seller is not
represented by an agent. It is assumed that the generated revenue is absorbed
externally. Including the sellers into the agent set yields a
combinatorial exchange
:
Fix a set
I
of agents, a set
J
of goods and for every good
j∈J
, an agent seller
(j)
.
Define
X=(ki
j:i∈I, j ∈J, ki
j∈ {−1,0}
for
i=
seller
(j), ki
j∈ {0,1}
for
i6=
seller
(j),
X
i∈I
ki
j≤0
for all
j∈J)(2.39)
This models an exchange market with unique goods that are offered by one seller
each (with possibly one seller selling different goods), and buyers that purchase a
combination of goods. The restriction
Pi∈Iki
j≤0)
says that no more goods can be
purchased than are sold, while it is allowed that goods are “left over”.
Note that the Myerson-Satterthwaite theorem (Theorem 26) implies that there
is no budget-balanced efficient mechanism with voluntary participation for X. In
particular, the VGC mechanism is not budget balanced. In chapter 3 we will develop
an adoption of VGC that is budget-balanced and satisfies voluntary participation
(but is not efficient). In chapter 4, we will apply this mechanism to a setting were
users submit competetive bids for a overlapping pathes through a network of links
with limited capacity.
35
2.3 Example: A public project
Suppose there is a project that can be implemented on different levels. Given level x,
let c(x)be the cost incurred by the implementation of that level, where c:X7→ R+
is strictly monotonously increasing, and c(0) = 0. Now let there be agents ithat
benefit from the project, day, ui(x)is the utility of agent ifrom project level x.
Suppose that ui(0) = 0, and the uiare monotonously increasing. Let Pbe the set of
user profiles
, that is, of all vectors (ui:i∈I).
Consider first the case that X={0,1}, that is, either the project is implemented,
or not. A mechanism Mfor that problem is a tuple M= (x, p), where
•x:P 7→ Xis the decision function (the project is implemented if agents submit
a profile ~u with x(~u) = 1), and
•pis a payment function with the property that if x(~u) = 0, then p(~u) = ~
0.
We claim that
Theorem 36.
Let
M= (x, p)
be individual rational mechanism with truthtelling as
dominant strategy for all players. Then there is a price vector
~p = (pi:i∈I)
with
pi∈R+∪{∞}
such that for all user profiles
~u = (ui)
,
•
x(~u) = 1
if and only if for all
i
,
ui≥pi
, and
•
p(~u) = (0
if
x(~u) = 0,
(pi:i∈I)
otherwise
.(2.40)
Proof.
Let us write, for any iand ~v = (vi:i∈I)and pi,
P+
i(~v, pi) = {(v1,...,vi−1, qi, vi−1,...,vn) : qi≥pi}(2.41)
P−
i(~v, pi) = {(v1,...,vi−1, qi, vi−1,...,vn) : qi< pi}.(2.42)
Let M= (x, p)be truthful and individual rational. Let X={~v :xM(~v) = 1}.
Suppose that x(~v) = 1 and let p(~v) = ~p = (pi). Then for any i,
P+
i(~v, pi)⊆X(2.43)
P−
i(~v, pi) = ∅.(2.44)
Let ~u ≥v. Then ~u ∈X. We claim that p(~u) = ~p. Suppose not.
Case 1: for some
i
,
(p(~u))i> pi
.
But then for pi< p∗
i<(p(~u))i, we have
(v1,...,vi−1, p∗
i, vi+1,...nn)∈P+
i(2.45)
but this point is not in X, a contradiction.
Case 2: for all
i
,
(p(~u))i≤pi
, and for some
i
strict
<
holds.
Let ~p∗=p(~u). Now on the one hand, P−
i(~v, pi)∩P+
i(~u, p∗
i)6=∅, but on the other
hand, P+
i(~v, p∗
i)⊆X, a contradiction. This finishes the proof.
36
Let us also note that
• the mechanism that
always
implements the project and splits the costs by an
arbitrary rule is budget balanced but not individually rational, and
• the mechanism that
always
implements the project and lets no one pay any-
thing is individual rational but not budget balanced, and that
• for both these mechanisms, truth-telling is weakly dominant.
2.4 Example: Auctioning a divisible good
Suppose there is a resource of quantity 1 that can be split arbitrarily between dif-
ferent clients (agents). Let there be clients i∈I, then the set of possible allocations
is X={(xi:i∈I) : xi≥0,Pi∈Ixi≤1}. Assume that the utility functions
ui: [0,1] 7→ R+of the clients are monotonously increasing. Let M= (oM, pM)be
a mechanism for Xand (ui:i∈I)and write for a vector ~u of utility functions,
xM
i(~u) = oM(~u)iand ~xM(~u) = (xM
i(~u) : i∈I), dropping the superscript Mif no
ambiguity arises. The efficiency condition (2.12) from definition 14 then takes the
form
(∀~u)~xM(~u)∈arg max
(xi:i∈I)∈XX
i∈I
ui(xi)(2.46)
We write VM(~u) = Pi∈Iui(xM
i(~u)). As in the previous section, if Msatisfies volun-
tary participation and the no positive transfers condition, the payment function has
to be
pM
i(~u) = VM(~u|ui≡0)−VM(~u) + ui(xM
i(~u)) (2.47)
which we write as
pM
i(~u) = ui(xM
i(~u)) −∆M
vic(~u)(2.48)
37
3 A combinatorial exchange for
autonomous traders
3.1 Introduction
Part of the work presented in this chapter was published in [76] and [74].
Internet auctions are one of the success stories of electronic commerce. Retro-
spectively, this is altogether not surprising, as modern economy produces a large
turnover of goods; and a large quantity of high value goods is not allocated effi-
ciently by traditional retail commerce but rather sold for giveaway prices. Appar-
ently, there is a demand for a highly efficient secondary retail market, which spe-
cializes in transactions between partners that participate in the exchange market
spontaneously. Auctions are an elegant way to tackle the problem of pricing and,
properly used, can lead to efficient allocation of goods.
Bidding on single goods reflects utilities without interdependencies. If bundling
goods increases utility (
complementary utility
), or goods can substitute each other,
bidding on single goods involves a risk of incomplete or redundant purchases. Com-
binatorial auctions allow bidders to express more complex utility functions. Winner
determination and payment allocation for one-sided combinatorial auctions is pos-
sible using the Vickrey-Grove-Clarke (VGC) mechanism. There is much work about
complexity issues of VGC mechanism [21, 62, 66, 67]. While the exact problem
is computationally intractable, there are approximation algorithms [87] with good
stochastic performance and accuracy whose availability encourages us to leave com-
plexity issues aside in this chapter. VGC leads to efficient, budget-balanced, individ-
ual rational, and even incentive compatible goods and payment distributions [62].
However, revealing true utilities looses much attractivity if bids under false names
are possible. Sakurai et al. [64] and Yokoo et al. [83] show that there is no pro-
tocol with the properties stated above that is robust against false name bids. With
these results in mind, Yokoo et al. [84] present a protocol which is budget-balanced,
individual rational, and robust against false name bids, giving up on efficiency.
One-sided combinatorial auctions allocate goods from
one seller
to
many bidders
.
For Internet auctions, we need to model a market with
many sellers
and
many bid-
ders
. This is a special case of a
combinatorial exchange
or
double auction
[82]. The
Vickrey-Groves-Clarke mechanism (VGC) when applied to combinatorial exchanges
preserves all above properties except budget balance. Unfortunately, there is a
grave negative result [56, 58] about protocols for combinatorial exchanges stating
38
that there is no protocol for double auctions that is efficient, budget-balanced, and
individual rational.
Internet auctions have a couple of peculiarities that are so far rarely considered
in connection with double sided auctions:
• Both sellers and buyers enter their bids continuously.
• Sellers specify auction clearing times; there is no market inherent clearing
rhythm.
• There is virtually no mean against false name bids.
• Sellers may wish to leave the pricing completely to the buyer’s side, i.e., offer
their goods without asking any specific price.
• Winner determination and payment allocation should benefit all individual
traders.
We present protocols and algorithms for clearing, winner determination, and pricing
double auctions in this setting which exhibit the following properties:
• They allow auctioneers to start auctions at any time and determine their life
span.
• Bids can be aggregated, including combinatorial ones, over some time.
• A price for every successful auction is based solely on the collected bids.
• Bidding under false names is possible only with a risk of forfeiting trade.
• Pricing is budget-balanced and individual rational.
The rest of this chapter is structured as follows: Sect. 3.2 develops a combinato-
rial exchange model tailored for our application scenario. In section 3.3 we suggest
some properties of payment allocation we consider necessary in the context of auc-
tions with autonomous traders. In section 3.4, we present a new pricing algorithm
that incorporates these properties. Section 3.5 presents a new bid clearing policy
that we then show to perform superior in comparison with the “traditional” clearing
policies.
Section 3.6 extends our pricing scheme to multiple item auctions – an extension
that we will use in chapter 4 where we apply SBNL and commit window clearing to
bandwidth reservation in networks.
39
3.2 A combinatorial exchange model for an auction
platform application
We now introduce the notation used by our model which is a special type of al-
location problem as in definition 32 and example 35. More precisely, our model
describes a variant of a
clearing house
or
periodic double auction
that admits com-
binatorial bids. However, we impose a number of additional constraints that reduce
the complexity of the model to make it more feasible in practice:
• Uniqueness of goods: exactly one copy of every good is being auctioned. This
means that for every j, there is exactly one i(nameley, i=seller(j)) such that
ki
j=−1, and for all other i,ki
j= 0 for (ki
j:i∈I, j ∈J)∈X.
• Only pure offers and pure buying bids. This implies that every agent iis either
a
buyer
with ki
j≥0for all j, or a
seller
with ki
j≤0for all j. There are no
agents that want to “exchange” one good for another.
• Only buying bids can be combinatorial, that is, for every seller i, there is ex-
actly one good jwith ki
j=−1, and for all other all other j, we have ki
j= 0.
• No substitutions – no OR-connected bids. This means that the buyer’s valua-
tion functions are
convex
, that is, for every buyer iand sets of goods J1, J2⊆J
with J1∩J2=∅, we have
ui(J1∪J2)≥ui(J1) + ui(J2)(3.1)
• Free disposal is possible (i.e., the seller can keep his good), as modelled in
equation 2.39.
• Price is computed only from buying bids, i.e., sellers do not specify any reser-
vation price. This means that the seller’s valuation function is identical to 0.
We do not consider OR-connected bids because it is hard to mediate between inter-
est conflicts arising between auctioneers when there are not enough bids to sell all
items.
Our market trades with ngoods (so |J|=n). Convexity of the valuation function
and the assumption that free disposal is possible allows us to assume without loss of
generality that every buyer
bids for exactly one bundle of goods
, that is, that there is
for every buyer ia set J(i)⊆Jsuch that ui(J)>0and for all J06=J,ui(J0) = 0. (So
iwould not appreciate “additional” goods even “for free”: we can use free disposal
to avoid such “gifts”.)
We identify now agent iwith his “bid” band write b= (kb
1, . . . , kb
n, pb)with kb
i∈
{−1,0,1}and pb∈R. We distinguish between
auction bids
(or
auctions
) and
buying
bids
, respectively:
40
Auction bids represent the offered goods. For auction bids all kb
i’s are 0except
one, and this one has value −1. An auction bid bis
offering good
iif kb
i= 1. Further-
more, we impose pb= 0 for auction bids as any pricing is left to the buyers. This
means that bis auctioning the good “with no price limits”. As goods are unique, we
assume that for any good i, there is exactly one auction bid aioffering i.
Buying bids represent the demanded goods. For buying bids all kb
i’s have ei-
ther value 0or 1. A buying bid bis
bidding for goods
{i1,...,ix}if kb
i= 1 for all
i∈ {i1,...,ix}and kb
i= 0 otherwise. Here, pbis always positive (due to the free
disposal requirement negative bids are not reasonable) and represents the amount
the buyer is willing to pay for the goods he is bidding for. For example, the buying
bid (0,1,1,20) means that a buyer is willing to pay a maximum of 20 for goods 2and
3.
Let Aand Bbe the sets of auction and buying bids in the market, respectively.
Definition 37 (Winner determination algorithm).
A
winner determination algo-
rithm
takes as input a set
A
of auction bids and a set
B
of buying bids. From this, it
computes an
acceptance function χ:B 7→ {0,1}
with
X
b=(kb
1,...,kb
n,pb)∈B
χ(b)·kb
i≤1(3.2)
for all
i= 1,...,n
. A bid
b∈ B
is
accepted
by the algorithm if
χ(b) = 1
, and
rejected
otherwise.
Informally spoken, a winner determination algorithm determines for each offered
good at most one buying bid that is accepted.
Definition 38 (Payment allocation algorithm).
A
payment allocation algorithm
takes
as input a set
A
of auction bids, a set
B
of buying bids, and an acceptance function
χ
. From this, the algorithm computes a
payment allocation function p:A∪B 7→ R
.
A payment allocation function
p
satisfies
budget-balance
if
X
c∈A∪B
p(c)≥0
It is
individual rational
, iff for all bids
b
with
χ(b) = 1
we have
p(b)≤pb
, and for
all
b
with
χ(b) = 0
we have
p(b) = 0
.
Hence, a payment allocation algorithm assigns to each accepted bid its corre-
sponding revenue which is positive for a buying bid and negative for an auction bid.
The following example describes the two-sided VGC mechanism from example 35 in
our simplified notation:
Example 39 (Two-sided Vickrey-Groves-Clarke).
Let
χ
be maximizing the sum of
revenues
V∗=X
b∈B
χ(b)·pb(3.3)
41
subject to condition (3.2). Let for
c∈ A ∪ B
be
(V−c)∗
be the maximized sum of
revenues for auctions and bids
A∪B\{c}
, and let
∆
vick
,c =V∗−(V−c)∗(3.4)
be the
Vickrey discount
for
c
. Let the payment function
p
be defined by
p(a) = −∆
vick
,a
for
a∈ A (3.5)
p(b) = pb−∆
vick
,b
for
b∈ B
.
(3.6)
The resulting mechanism
(χ, p)
is the Two-sided Vickrey-Groves-Clarke mechanism
for combinatorial exchanges.
The last constraint implies that sellers cannot specify a minimum price as pre-
condition for selling their good. Note that while two-sided VGC does allow sellers
to specify a negative utility for the sale of a good, this is not really a
minimum
price condition
because specification of negative utility from a sale changes pay-
ment allocation even when more than the lost utility is given to the seller anyway,
as demonstrated by the following example:
Example 40.
Let there be two auctions and one bid of
10
for both items together.
Suppose first that the auctions are without minimum price.
According to VGC, all auctions and bids would be matched, the following pay-
ments would be allocated: the auctioneers would receive a payment of 10 each,
while the bidder’s payment would be
0
.
Suppose now that the first auctioneer would demand a minimum price of
7
. VGC
would then allocate a payment of
10
to this auctioneer, while the other one’s pay-
ment would shrink to
7
.
This contrasts with one-sided Vickrey payment or plain pay-your-bid payment for
single item auctions where specifying a minimum price does not change payment
allocation once the payment surpasses the minimum price.
In many settings, specification of minimum prices is not required by the sellers.
In particular, this holds when the market has sufficient liquidity,
or when the fixed - variable cost ratio is high. We therefore refrain from con-
sidering minimum prices. We nevertheless acknowledge the problem of respecting
minimum prices in the above sense, while preserving other desired properties of the
payment allocation algorithm, an interesting question for further research.
3.3 Pricing properties required by autonomous traders
Pricing in a combinatorial exchange is far from being trivial. Following [58] and
[39], we take individual rationality and budget-balance as hard constraints that our
payment allocation algorithm must satisfy. Besides these two constraints, we con-
sider a couple of other properties being useful which are discussed in the following.
42
3.3.1 Respecting single item bids.
By accepting combinatorial bids, we expect more willingness from the bidders to
bid and therefore an increased total revenue. Thus, a reasonable constraint for the
payment allocation is that no bidder looses from combinatorial bids:
Definition 41.
A payment allocation function
prespects single item bids
, if for all
auctions
a
and for all buying bids
b
that bid only for
a
, we have
p(a)≥pb
.
Proposition 42.
VGC respects single item bids.
Proof.
Let abe an auction bid, and babe a bid bidding for aonly. Let V−abe the
maximized revenue of all auctions except a. By accepting bid ba, the revenue in-
creased by pba. So aincreases the total revenue by at least pba, and therefore a’s
Vickrey discount is at least pba.
Parkes et al. [58] present some VGC-based budget-balanced payment rules. The
rules are generated by minimizing the deviation from the Vickrey payments mea-
sured in various distance function. Practically, they divide the available revenue1
between all traders, using various division rules:
• The
Equal
payment rule splits the available surplus equally among all sellers
and buyers.
• The
Fractional
payment rule splits the available surplus according to the frac-
tional share from the total Vickrey discount of every agent
•
Small
starts awarding discounts to the traders with small ∆vick and proceeds
until the available discount is used up.
While VGC does respect single item bids, these variants of VGC do not as is illus-
trated in the following example:
Example 43.
Let there be auctions and bids
a1: (−1,0,0)
a2: (0,−1,0)
b1: (1,1,60)
b2: (1,0,50)
b3: (1,0,49)
a1, a2
and
b1
are accepted. The available surplus is 60. The Vickrey discounts for
the agents are:
a1: 60
a2: 10
b1: 10
1Remember that we have no minimum prices in our setting
43
The
Equal
payment rule splits the available surplus equally, so
a1
and
a2
receive
20 each, and
b1
pay 40. However,
a1
would prefer to accept bid
b2
with a surplus
of
50
, leaving
a1
with a share of
25
under the
Equal
payment rule. The
Fractional
payment rule leads to the following payments:
a1
receives
60·60/80 = 45
,
a2
receives
10 ·60/80 = 7.5
,
b1
pays
60 −10 ·60/80 = 52.5
. If however
a1
accepts bid
b2
, a surplus
of 50 results. The Vickrey discount of
a1
is 50, of
b2
is only 1, and
a1
receives
a payment of
50 ·49/50 = 49
under the
Fractional
rule. Similarly, examples for
the other payment rules (
Threshold
,
Small
,
Large
, and
Reverse
payment) can be
constructed showing that they do not respect single item bids.
We are tempted to generalize single item bid respect to “all bids respect” by
demanding that for all bids b
X
1≤i≤n
kb
i·p(ai)≥pb(3.7)
where aiis the auctioning bid of the auction offering good i. Basically, this would
mean that every auction can choose its favourite bid to be accepted. However, we
can easily see that this is incompatible with budget-balance:
Example 44.
Let there be three auctions, and let there be bids as follows:
b1: (1,1,0,10)
b2: (1,0,1,10)
b3: (0,1,1,10)
The maximal revenue is 10 as only one bid can be accepted. To satisfy the three
inequalities resulting from (3.7), we would need a revenue of 15, however.
3.3.2 No loss from a bid.
Next, we desire that no auctioneer ever looses from a bid for his good. Formally,
that means:
Definition 45.
A payment allocation algorithm has the
no loss from a bid
property
if the following holds: Let
A
be a set of auctions and let
B
be a set of bids. Let
a∈ A
be an auction offering good
i
and let
b= (kb
1,...,kb
n, pb)
be a bid with
kb
i= 1
. Let
p
be the payment allocation function for
(A,B)
and let
p0
be the payment allocation
function of
(A,B∪{b})
. Then
p0(a)≥p(a)
.
Note that VGC does satisfy the no loss from a bid property. However, the
Small
rule of [58] does not:
44
Example 46.
Let there be two auctions
a1
and
a2
, and bids as follows:
b1: (1,1,100)
b2: (1,1,99)
b3: (1,0,1)
Then bid
b1
is accepted,
V∗= 100
, and
∆
vick
,a1= 100
∆
vick
,a2= 99
∆
vick
,b1= 1
and the
Small
rule allocated discounts to
b1
and
a2
, leaving
a2
with a payment of
99
and
a1
with no payment. Suppose now that there is an additional bid
b4: (0,1,2)
Now the discount goes to
b1
and
a1
, leaving
a2
with no payment. So
a2
suffered from
an additional bid.
3.4 A new pricing scheme
Now, we present a budget-balanced, individual rational, single item bid respecting
payment allocation algorithm with the no loss from a bid property.
Algorithm SBNL
Input: A– a set of auctions, B– a set of bids
Output: a payment allocation function p:A 7→ R.
•
Step 1.
Compute the item allocation that maximizes revenue. Let Vbe the
maximized revenue.
•
Step 2.
For an auction aoffering good i, let ba= (0,...,0,1,...,0, pba)be the
highest bid bidding for good ionly. If there is no such a bid, define pba= 0. Let
Vsingle =Pa∈A pba.
•
Step 3.
Solve the linear programming problem
Minimize Y=X
1≤i≤n
yi
such that
(∀b∈B)X
1≤i≤n
kb
i·yi≥pb
Among all optimal (yi: 1 ≤i≤n), choose the one that minimizes Pi(yi)2.
45
•
Step 4.
Let Q=V−Vsingle
Y−Vsingle .
•
Step 5.
For all auctions a∈ A, let p(a) = pba+ (yi−pba)·Q, where ais offering
good i.
Our pricing mechanism let successful buyers pay exactly the amount of their bid.
Winner determination takes place subject to maximizing total revenue. The pricing
mechanism distributes this revenue among the sellers.
Proposition 47.
Algorithm SBNL satisfies budget-balance and individual rational-
ity, respects single item bids, and has the no loss from a bid property.
Proof.
Obviously the algorithm is individual rational. The sum of the payments is
X
a
p(a) = X
a
pba+Q· X
i
yi−X
a
pba!=Vsingle +Q·(Y−Vsingle) = V
and this proves budget-balance. Step 2 ensures single item bid respect. For the
no loss from a bid property, note that we always have Y≥V, and this implies
Q < 1. Thus an additional single item bid for acan only increase a’s payment. The
argument for an additional combinatorial bid is similar.
3.5 Bid synchronization
After developing a pricing scheme, we will now turn our attention to the
clearing
policy
of an auction protocol which defines at what times auction and buying bids
are being matched.
Our market model allows continuous publication of new auctions. There are vari-
ous clearing strategies in use for continuous double auction markets [19, 20]:
•
Continuous clearing.
The trade occurs as soon matching bids and asks arrive.
•
Periodic or random clearing.
The trade occurs at certain times (periodic, ran-
dom, or a combination of both), bids and asks are matched subject to certain
optimality conditions (e.g. maximizing surplus or throughput).
All three policies have serious drawbacks in our scenario. Periodic clearing of bids
that are submitted continuously results in auctions whose live span is very short
when they are entered shortly before the end of an aggregation slot. A similar
effect occurs with random clearing: some auctions will close after a short time, and
little value is generated, while others may run longer than the auctioneer desires
to wait. Continuous clearing can’t be used when sell-bids have no minimum price,
since otherwise, sell-bids would always be matched with the first bid that asks for
the offered good.
We find it desirable to allow the auctioneer to control the live span of his auction.
Therefore, we use another clearing policy that we now describe.
46
3.5.1 A new clearing policy
Definition 48 (Commit window clearing).
Every auction announcement
a= (aa, ta
earliest
, ta
latest
)(3.8)
contains the following information:
• the auction bid
aa
, i.e. identity of the good
• the earliest commit time
ta
earliest
• the latest commit time
ta
latest
Every auction goes through the following sequential phases:
•
Pre-commit.
Bids for this auction can be submitted. The auction will not com-
mit to accepting any of them.
•
Allow-commit.
Bids for this auction can be submitted. The auction house can
request that the auction commits to a bid if that bid wins by the winner deter-
mination algorithm applied by the auction house. In this case, all unsuccessful
bids for this auction are uncommitted, and the auction transits into Expired
state.
•
Force-commit.
No bids can be submitted anymore for this auction. The winner
determination algorithm determines the winner among all bids that bid for
auctions in Allow-commit or Force-commit stage. Non-accepted bids for this
auction are uncommitted. Transit into Expired state.
•
Expired.
The auction is finished, the winner was determined and the payment
computed.
A bid is
committable
if all auctions the bid is bidding for are in Allow-commit
or Force-commit state. Pre-commit for an auction
a
is the time before
ta
earliest. The
Allow-commit phase lasts from
ta
earliest to
ta
latest and are followed by the Force-commit
and Expired phases.
This policy lets the auctioneer control the live span of his auction. A combinatorial
bid can be accepted if the commit phases of all auctions bidden for do overlap.
The larger the Allow-commit phase, the more inviting his auction will be toward
combinatorial bids.
47
3.5.2 A lower bound for the revenue
In this section, we give a lower bound of the revenue assuming that the set of auc-
tions open for bidding does not change. In this case, it is reasonable to assume that
the set of items bidden for and the amount of the bids submitted within that interval
are independently, but identically distributed.
Let us fix a set Aof open auctions A={A1, ..., An}and assume that bids are
independent random variables b(p, A,#2)for fixed p∈[0,1].
Consequently, the number of items a bid bis bidding for follows binomial distribu-
tion with parameters nand p:
#items(b)∼Binomial(n, p)
and the amount distribution is a squared binomial distribution.
Let us compute the expected value of the revenue generated by one bid.
E[amount(b)] =
n
X
k=0 n
kpk(1 −p)n−kk2
=n(1 −p)np(1 −p+np)(1 + p
1−p)n(3.9)
The cumulative distribution function is
P(amount(b)≤x) =
√x
X
k=0 n
kpk(1 −p)n−k,
and thus
P(max{amount(b1), ..., amount(bg)} ≤ x)
= (P(amount(b)≤x))g
=
√x
X
k=0 n
kpk(1 −p)n−k
g(3.10)
Now we can give a
lower bound
Emax(g, n, p)on the expected value Eg(n, p)of the
revenue of the auctions with gbids
Eg(n, p) = E(revenue of gbids)
≥E(max{amount(b1), ..., amount(bg)})
=
n2
X
x=0 1−Xn
kpk(1 −p)n−kg
=Emax(g, n, p)
(3.11)
48
Figure 3.1: Maximal revenue of one bid over number of bids.
Figure 3.1 is a plot of values for Emax(g, n, p)with n=10, p=0.1, 0≤g≤200.
Now if
0
<
p
<
1,
P(amount(b)≤x) = 1 for x≥n2and P(amount(b)≤x)<1for
x < n2and therefore,
lim
g→∞E(max{amount(b1), ..., amount(bg)}) = n2
On the other hand, the revenue of the nth auctions is bounded from above by n2.
Thus we conclude that lim
g→∞Eg(n, p) = n2for all
0
<
p
<
1
.
The lower bound we gave is not tight at all. We are not aware of a closed-form
representation of the precise expected revenue Eg(n, p). Figure 3.2 shows results
of a numeric simulation of Eg(10,0.1) with 1000 iterations per g(0 ≤g≤20), plotted
over the lower bound Emax(g, n, p).
Figure 3.2: Simulated revenue and lower bound over number of bids.
49
3.5.3 Comparison between periodic and commit window clearing
3.5.3.1 Side conditions for the comparison
We wish to evaluate efficiency in connection with the surplus-maximizing good al-
location of two of the three mentioned clearing policies: the new commit window
clearing policy, and periodic clearing. We will measure efficiency in terms of the
generated revenue2
per auction
, for a fixed set of auctions the timing of which we
adjust to the used clearing policy.
For periodic and random clearing, the time when bids and offers are matched is
determined by the clearing policy parameters - neither auctions nor bids have to
state anything about that time. Let ∆periodic be the length of the interval between
two clearings for the periodic clearing policy. Then the length of an auction is be-
tween 0 and ∆periodic.
For commit window clearing, the length of an auction is between tearliest and tlatest.
Its precise value will be determined during the life of the auction and will depend
on the submitted bids.
We will model behaviour of market participants as follows:
• Sellers initiate new auctions according to a Poisson process with parameter
λa. Sellers require that these auctions must terminate within a specified time
tMaxAuctionDuration which is constant for all auctions. For a given auction, let tstart
be its start time.
• Sellers have no fixed costs and therefore, wish to auction their goods without
minimum price.
• For the periodic auction, we set ∆periodic =tMaxAuctionDuration. The auction lives
from tstart to the end of the current clearing period, that is to min{n∆periodic :
n∈N, n∆periodic ≥tstart}.
• For the commit window clearing, we set tlatest =tstart +tMaxAuctionDuration. The
size of the commit window swindow can vary from 0 to tMaxAuctionDuration and
therefore, tearliest varies from tstart to tstart +tMaxAuctionDuration. For our study, we
fix the commit window size to its maximal value swindow =tMaxAuctionDuration.
• Buyers submit bids for combinations of goods. A Poisson process with param-
eter λbdetermines the times when a bid is submitted. A bid, submitted at time
tbid, will be a random variable b(p, A,#2+δ)where Ais the set of auctions
open for bidding at the time when the bid is submitted, and
δ∼N(0,#−1)(3.12)
2social surplus
50
In the choice of the amount distribution, we follow [9] who suggests as an
acceptable distribution of the bid amount a normal distribution with expected
value equaling the “fair” value of the item combination bidding for.
We claim that commit window clearing generates, under the side conditions de-
scribed above and for swindow properly chosen, a higher revenue than periodic clear-
ing. We support this claim by some simulations whose parameters are derived from
mentioned side conditions.
3.5.3.2 Simulation results
Figure 3.3 shows a comparison of revenues of auctions with periodic and commit
window clearing. The parameter pvaries in 100 steps between 0and 1. The Poisson
parameters λaand λbare constants with value 0.1. The auction duration is set to
100. The average total revenue of 50 iterations for all auctions generated within a
period of 10000 was measured.
0.2 0.4 0.6 0.8 1 p
100
200
300
400
500
revenue
period
cwc
Figure 3.3: Comparison of periodic and commit window clearing
We conclude that this simulation supports our claim.
3.5.3.3 An analytic approach for offline winner determination
Bids in the stochastic model from above are generated on the fly with a target cho-
sen from all auctions that are open for bidding at the time when a bid is submitted.
In this section, we will modify bid generation slightly: the target of a bid submitted
at time tbid is chosen from all auctions awith tearliest ≤tbid ≤tlatest. Winner deter-
mination takes place offline, that is, among
all
bids that were submitted during the
total run. For this scenario, we can show analytically that commit window clearing
generates a higher surplus, then periodic clearing.
For a set Bof bids bidding for subsets of the auction set A, define
c(B) = 1if all bids is χare compatible
0 otherwise. (3.13)
51
and let revenue(B)be the maximized revenue possible to generate from B, that is,
revenue(B) = max
B0⊆Bc(B0)X
b∈B0
amount(b).(3.14)
The following is easy:
Lemma 49.
Let there be given two finite sets of bids,
B={Bi:i∈I}
, and
B0=
{B0
i:i∈I}
, with the property that for every
i, j ∈I
,
• amount
(si) =
amount
(s0
i)
, and
• if
si
and
sj
are compatible, so are
s0
i
and
s0
j
.
Then
revenue
(B)≤
revenue
(B0)(3.15)
This implies
Lemma 50.
Let
S={bi:i∈I}
be a set of independently identically distributed
variables
bi∼b(p, A,#2)(3.16)
and let
S0={b0
i:i∈I}
be a set of independently identically distributed variables
b0
i∼b(p, Ai,#2)(3.17)
for some
Ai
with
|Ai|=|A|
.
Then
E(
revenue
(S)) ≤E(
revenue
(S0)) (3.18)
Suppose auctions are started with constant rate raduring time Tand bids sub-
mitted with constant rate rb(number per second). For simplicity, let rbbe a multiple
of ra. Furthermore, assume tMaxAuctionDuration is constant, and the size of the commit
window swindow =tMaxAuctionDuration = ∆periodic.
Figure 3.4 illustrates the situation with commit window clearing: auctions A1to
A11 are subsequently started. Auctions Aiand Ajoverlap if |i−j| ≤ MaxAuctionDuration
ra.
For three bids B1, B2and B3, vertical lines show the auctions the bid target is drawn
from.
The situation for the periodic clearing is shown in figure 3.5. The target of all
bids is contained in the set of auctions started within one clearing interval.
Now let the bper
ibe, for 1≤i≤rbT, independent, identically distributed random
variables with distribution b(p, {A[i
rb∆periodic ]+1,...,A[i
rb∆periodic ]+ra∆periodic },#2), and let
52
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A2
A1
A4
A5
A6
A8
A9
A10
A11
A3
A7
B1
B3
B2
Figure 3.4: Overlapping auctions for commit window clearing
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A2
A1
A11
A3
B3
A5
A4
A10
B1B2
A7
A6
A9
A8
clearing
Figure 3.5: Auctions for periodic clearing
53
bcwc
ibe, accordingly, independent, identically distributed random variables with dis-
tribution b(p, {Aira
rb
,...,Aira
rb+MaxAuctionDuration·ra,#2). We compute
E(revenue of periodic clearing)
=revenue({bper
i: 1 ≤i≤rbT})) (3.19)
≤revenue({bcwc
i: 1 ≤i≤rbT})) (3.20)
where the last inequality follows from lemma 50.
We conclude
Corollary 51.
The expected revenue of a commit window auction with maximal
auction duration
t
MaxAuctionDuration, auction start rate
ra
and bid submission rate
rb
is
greater or equal to the expected revenue of a periodic auction with
rat
MaxAuctionDuration
auctions running in parallel and
rbt
MaxAuctionDuration bids.
3.5.3.4 Further research on the performance of commit window clearing
Here we presented a first analysis on the efficiency of a new clearing policy suit-
able for combinatorial exchanges with multiple sellers and buyers. The policy was
compared with the classical periodic clearing policy, and it was found that commit
window clearing yields a higher mean revenue when auction and bid submission
rates, bid distribution and maximal auction duration are fixed.
Some estimates on the expected revenue for periodic and commit window clearing
were presented.
Undoubtedly, further analysis of the policies in regard of their generated rev-
enue, particularly under the side conditions used for the simulation, would be quite
interesting. The same should apply to analyzing more clearing policies like random
clearing, and generalizing the results to more amount distribution functions.
3.6 Extending SBNL to multiple item auctions
Remember that bids are of the form b= (kb
1,...,kb
n, pb), where we defined above that
kb
i∈ {−1,0,1}. For buying bids, we have kb
i∈ {0,1}, while for auction bids, kb
i≤0.
We now generalize the notion of auction bids by allowing kb
i∈Z−, the set of non-
positive integers. We keep the assumption that auction bids are non-combinatorial,
that is, that for every bid b, there is only one iwith kb
i6= 0. Now we can generalize
definition 37.
Definition 52 (Multiple item winner determination algorithm).
A
multiple item win-
ner determination algorithm
takes as input a set
A
of auction bids
A=nba= (kba
1,...,kba
n, pba) : ba∈ Ao(3.21)
54
such that for every
i
, there is exactly one
ba
with
kba
i6= 0
, and a set
B
of buying bids.
From this, it computes an
acceptance function χ:B 7→ {0,1}
with
X
b=(kb
1,...,kb
n,pb)∈B
χ(b)·kb
i≤ −kba
i(3.22)
for all
i= 1,...,n
, where
ba
is the unique bid in
A
with
kba
i6= 0
. A bid
b∈ B
is
accepted
by the algorithm if
χ(b) = 1
, and
rejected
otherwise.
Definition 38 remains unchanged. It is easy to see that the two-sided Vickrey-
Groves-Clarke mechanism of definition 39 can be generalized to multiple item auc-
tions:
Definition 53 (Two-sided Vickrey-Groves-Clarke for multiple item auctions).
Let
χ
be maximizing the sum of revenues
V∗=X
b∈B
χ(b)·pb(3.23)
subject to condition (3.22). Let for
c∈ A∪B
be
(V−c)∗
be the maximized sum
of revenues for auctions and bids
A∪B \{c}
, and let
∆
vick
,c =V∗−(V−c)∗(3.24)
be the
Vickrey discount
for
c
. Let the payment function
p
be defined by
p(a) = −∆
vick
,a
for
a∈ A (3.25)
p(b) = pb−∆
vick
,b
for
b∈ B
.
(3.26)
The resulting mechanism
(χ, p)
is the
Two-sided Vickrey-Groves-Clarke mechanism
for combinatorial exchanges with multiple items.
It follows that the mechanism SBNL generalizes to the multiple item case as well.
55
4 Application to network management:
Advanced resource reservation in
networks
Nisan and Ronen define in [57, p.13] a scenario of a network that consists of a di-
rected graph Gwhose nodes are connected by edges that represent links with asso-
ciated costs for usage. In this setting, they define the natural shortest path problem
that now corresponds to fining the cost-minimizing path between two nodes. A Vick-
rey mechanism in which the link costs are treated as bids, gives the “owners” of the
links incentive to bid according to their true costs. Nisan and Ronen’s results are
extended by Hershberger and Suri [32] and Archer and Tardos [5]. Hershberger
and Suri proved that the Vickrey pricing can be computed in the same time as the
solution of a single-source shortest path problem, if the graph is undirected1. For
results on directed graphs, see the follow-up paper [35].
The Vickrey mechanism pays more than the actual costs to the link owners (thus
buying truthfulness). Archer and Tardos note that the additional
premium
can be
a multiple of the actual costs. They prove that for a large class of graphs, every
truthful mechanism has in some instances to pay a high premium even if there is a
choice between multiple paths of essentially the same cost.
We have argued above that the fact that marginal usage costs are neglectible
compared to fixed costs makes it disputable whether there is a meaningful definition
of “costs” associated with usage of a link. Similar to the application scenario for
transport logistics, it seems much more natural to leave the pricing to the
network
users
that compete for resources. Users, however, would bid for
paths
rather than
for single links. The resulting market would be precisely the combinatorial exchange
that this chapter deals with.
Are the
pricing rules
of SBNL suitable for such a scenario?
• The requirement of
budget balance
may be obsolete if payments are small
compared with fixed “basic fees” users pay to the network owners independent
from usage. A pricing structure that is split into fixed fees and per-usage fees
is appropriate if the basic fee users pay is mirrored by a
basic utility
users
1Beware of the conference version [33] of that paper, which erroneously claims that that holds for
directed graphs, too (see also the erratum [34] of the authors).
56
have from being “connected” to the network. The amount of the fixed fee
would then be determined independently from the exchange pricing. The bids
of the users would be based on the
marginal utility
users have from using a
certain path. Of course, there would be then a question on the acceptance
of the fixed fee by the user. Thus, there would be no clear separation of the
analysis of the mechanism, and the analysis of the economical context.
In the absence of basic fees, however, budget balance of the exchange market
would be strictly required. This would hold true even if there is a basic fee but
per-usage fees may be of comparable size.
•
Respecting single item bids
and
no loss from a bid
are clearly desirable prop-
erties from the point of view of the link owners.
We conclude that if budget balance is required, SBNL’s pricing rules are reasonable
choice for network linkage pricing.
The definition of good synchronization rules seems more challenging. We have so
far not yet stated whether the bid amount refer to a payment per package or per
time interval. Nisan and Ronen have left that question unconsidered.
• One approach is to introduce
time slots
and auction them each to one bidder
exclusively. This makes sense if the link’s capacity can’t be split between bid-
ders. If this is not the case, we could divide the link’s capacity into smaller
portions and auction them either as independent goods, or as a good with
quantity more than one. But from the bidder’s point of view, the portions are
substitutes, so if they are auctioned independently, we would have to allow
bidders to submit OR-connected bids. In the second case, the auction would
be a multi-item auction.
• Alternatively, we can auction the right to
send a package over the link within a
time slot
. The link’s capacity will most probably allow more than one package
per time slot. This means that the
uniqueness of goods
condition defined above
is violated.
Table 4.1 gives a summary of the possible market types.
How do the second and third lines of the table relate to each other?
Proposition 54.
AND-of-OR-connected bids have strictly greater expressive power
than selling bids for identical copies: That is, let there be a combinatorial exchange
market AND-OR with
•
selling bids
of the form
bs= (
slot
,
link
,
portion
)
where
–
slot is a time slot,
57
Unsplittable link capacity Combinatorial exchange with AND-
connected buying bids and non-
combinatorial selling bids
Link capacity portions as distinct
goods
Combinatorial exchange with AND-
of-OR-connected buying bids and
non-combinatorial selling bids
Link capacity portions as identical
copies of the same good
Combinatorial exchange with AND-
connected buying bids and selling
bids with quantity
Package in a timeslot auction Combinatorial exchange with AND-
connected buying bids and selling
bids with quantity
Table 4.1: Possible market types for network bandwidth auctions
–
link is a network link, and
–
portion is a capacity portion of link for slot,
•
buying bids
of the form
by=
id
,V
link
W
portion
(
slot
,
link
,
portion
), p
, where
–
id is the buyer’s identity,
–
slot,link and portion are as above, and
–p
is the bid amount,
and a combinatorial exchange market AND-MULT with
•
selling bids
of the form
bs= (
slot
,
link
,
q
)
where
–
slot is a time slot,
–
link is a network link, and
–
qis a quantity (that is, a positive integer),
•
buying bids
of the form
by= (
id
,V
link
(
slot
,
link
), p)
, where the variable’s in-
terpretations are as above.
Then there are mappings
Tb
resp.
Ts
that map any any buying bid
by
of AND-MULT
to a set of buying bids
Tb(by)
of AND-OR, and any selling bid
bs
of AND-MULT to a
set of selling bids
Ts(bs)
of AND-MULT, such that for any bid acceptance function
χ
AND-MULT for AND-MULT, there is a bid acceptance function
χ
AND-OR for AND-OR,
such that for any given sets of buying and selling bids for AND-MULT,
By
and
Bs
, a
buying bid
by∈By
is accepted by
χ
AND-MULT if and only if all buying bids in
Tb(by)
are
accepted by
χ
AND-OR, and similarly, selling bids
bs∈Bs
are accepted by
χ
AND-MULT if
and only if all selling bids in
Ts(bs)
are accepted by
χ
AND-OR.
58
Proof.
Define Tsand Tbas
bs= (slot,link,q)7→ Ts(bs) = {(slot,link,portion) : portion = 1,...,q}
(4.1)
by= id,^
link
(slot,link), p!7→ Tb(by) =
id,^
link
n
_
portion=1
(slot,link,portion), p
(4.2)
Define χAND-OR as
χAND-OR(bAND-OR
y) = 1 (4.3)
iff
bAND-OR
y∈Tb(bAND-MULT
y)and χAND-MULT(bAND-MULT
y) = 1.(4.4)
We have to show that if χAND-MULT is a valid bid acceptance function, then so is
χAND-OR. The first means that if for all slots slot0and links link0and selling bids
bs= (slot,link,q),
(by= (slot0,link0)∧^
link
(slot0,link)!:χAND-MULT(by) = 1)≤q. (4.5)
The latter means that there is an allocation function φthat allocates triples
(slot,link,portion)(4.6)
to bidders such that every triple is allocated at most once, and that if
χAND-OR
id,^
link _
portion
(slot,link,portion), p
= 1,(4.7)
then there is a triple (slot,link,portion)with φ((slot,link,portion)) = id. But
clearly, equations (4.1) and (4.5) imply such a φexists.
If two selling bids offer portions in the same spot and are of the same size, we
can safely assume that buyers are indifferent between the two bids. This means
that rational buyers that wish to acquire one portion for a certain slot will always
submit bids that OR-connect all selling bids for the same slot. But this means that
the additional expressive power that AND-OR provides more than AND-MULT, is
not being used by the bidders. Consequently,
a market that sells link capacities
as multiple copies of identical goods will always be preferred over a market that
sells link capacity portions as individual goods
. We are therefore interested in the
extension of SBNL that admits selling bids with multiple copies of the same good.
59
4.1 Background: The RSVP protocol
Reservation protocols for network resources, most prominently bandwidth, have
been suggested for a long time now. While many applications, like file transfer or
email, rarely create short-term bandwidth shortages, multimedia applications like
video streaming are more demanding. If both
real time transmission
and
high band-
width
are required, even generously designed networks quickly run into temporary
capacity deficits.
One of the most popular resource reservation protocols is the
Resource Reserva-
tion Setup Protocol (RSVP)
([10], see [79]) which was designed with its application
to multicast videoconferencing in mind. RSVP uses
PATH
messages that are sent
by the stream source to the potential receivers, and
RESV
messages that travel the
opposite way and carry reservation requests from the receiver to the source. Reser-
vation requests are processed hop-by-hop by the routers which are responsible for
acceptance or rejection of reservations. A rejected reservation is not propagated
further upstream, and an error messages is sent in reply to the issuer of the re-
quest. Two aspects of RSVP are of interest here:
• RSVP reservation messages can either request
controlled load
service, or
guaranteed
service. Controlled load requests are specified by
traffic specifica-
tions (TSpecs)
which contain parameters that describe the anticipated traffic,
like average and peak rate, package size, etc. Guaranteed service is character-
ized by
service rate
(the bandwidth in bytes/second), and
slack
(the additional
delay that the hop may add, in microseconds).
• Reservation messages are for
immediate
resource usage, there is no advanced
reservation for time slots in the future.
RSVP does not specify how RESV messages are processed. Clearly, the protocol
was designed with the intention that bandwidth is reserved at a first-come first-
served base. It is, however, conceivable that monetary bids are added to RESV
messages, and that reservation requests are aggregated at intermediate hops in
order to implement an allocation based on monetary bids. Reservations in RSVP
expire unless renewed within a given time (specified in the TIME_VALUE field), but
if they are renewed, they remain valid.
If bid amounts refer to a reservation whose duration is indefinite, any bid accep-
tance mechanism obviously leads to inefficiencies of arbitrary degree. There are
only two ways out of that: either reservations are for a bounded time, or reser-
vations are unbounded but it is accepted that possibly, flows will be interrupted.
Among others, Burchard [12] uses the first approach: reservations apply to certain
time slots well-known in advance. Extensions to RSVP that support reservations
for given time slots have been suggested e.g. in [69]. While indefinite reservations
are not considered in [69], it is possible to re-negotiate the duration of reservations,
60
albeit without a guarantee of success. An overview about advance resource reserva-
tion is given in [80], but in respect to reservation with unknown in advance duration,
the authors note only that they are “difficult to implement”.
4.2 An auction market for advanced reservations with
well-known duration
In this scenario, we have
•
selling bids
of the type bs= (slot,link,q), and
•
buying bids
of type
by= id,^
slot∈slotset ^
link∈linkset
(slot,link), p!,(4.8)
where slotset is the set of slots that define the time period that the reservation
request refers to2, and linkset is the set of links that flow travels through.
It is easy to see that this yields an instance of the market from definition 52; one just
needs some enumeration of {(slot,link) : slot ∈slotset,link ∈linkset}that maps
slot-link pairs of byto the corresponding is in (kby
1,...,kby
i, . . . , kby
n, p)of equation
(3.21).
Let
By=(by= id,^
slot∈slotset ^
link∈linkset
(slot,link), p!:by∈By)(4.9)
be a set of reservation request bids. For a slot-link-pair sl = (slot,link), let Bsl
ybe
the set of all bids in Bythat bid for sl. Condition 3.22, applied to our market, then
says for any valid bid acceptance function χ, for any slot-link-pair sl = (slot,link),
the condition
X
by∈Bsl
y
χ(by)≤1(4.10)
holds.
How is the matching of buying and selling bids to be timed? An advantage of
commit window clearing (see definition 48) is that auctions don’t have to be syn-
chronized exactly, it is enough if the time windows (tearliest, tlatest)where a com-
mit is possible do overlap. For a slot slot = (tslot
start, tslot
end ), clearly we should have
tlatest ≤tslot
start, and there is no need for a stricter condition. But what should be
the earliest time that a bid is accepted? If uniformly for all slots, the slot length is
lslot and ∆slot is such that we allow commit for a slot slot = (tslot
start, tslot
end )from time
2We do not formally require slotset to be a contiguous set of time slots.
61
tslot
start −∆slot, for reservation request that requests resources between tres
start and tres
end,
to be granted it is necessary that
tres
end ≤tres
start + ∆slot +lslot (4.11)
or
spanres ≤∆slot +lslot (4.12)
with spanres =tres
end −tres
start is the reservation’s time span.
4.3 Unknown reservation duration: Extensions to the
admission control algorithm of Greenberg et al. for a
single link
If reservation duration is unknown (and with no known bounds) but accepted reser-
vations
must
be honoured, then a link that has accepted a reservation for a slot slot
can’t accept reservations for any slot after slot until the given reservation has been
released.
Greenberg et al. [31] 3proposes the parallel use of
book-ahead
requests (BA)
with known duration, and
instantaneous requests
(IR) which are of unlimited valid-
ity. While book-ahead requests are guaranteed once accepted, it is admissible that
service based on instantaneous requests is interrupted or downgraded with a suffi-
ciently small probability. Greenberg et al. assume that BA and IR requests arrivals
are given as independent Poisson processes with rates λB, λIand that BA and IR
holding times (known in advance for BA and unknown for IR) are independent and
exponentially distributed with means 1
µB,1
µI. Furthermore it is assumed that total
link capacity is s, that IR requests are for capacity 1 and BA requests are (uniformly)
for capacity b. Let rBand rIbe the per time unit rates paid for completed BA and
IR requests, and let CIbe the “penalty” (cost) for an interrupted IR request4. Then
there are three variables that control the total generated revenue:
• the probability PIthat an incoming IR request is rejected,
• the probability PBthat an incoming BA request is rejected, and
• the probability pIthat an admitted IR request is interrupted while in progress.
3A similar approach was presented in [68].
4There is no penalty if the request was rejected or if the reservation was released by the user.
62
Parameter Definition Known
to
net-
work
Known
to
user
Depends on
slink capacity yes no
rlink capacity put aside for IR re-
quests
yes no s, b, λB,
λI, µI, µB
bcapacity of BA requests yes yes
λBBA arrival rate yes no
λIIR arrival rate yes no
µIIR holding parameter yes yes
µBBA holding parameter yes yes
pemp
Iempirical interruption probability yes yes s, b, λB,
λI, µI, µB
pIinterruption probability with
known existing IR and BA reser-
vations
yes no existing IR and
BA reservations
pmax
Imaximal interruption probability
such that IR request is accepted
yes no s, b, λB,
λI, µI, µB
µemp
int P(tint < t) = 1 −e−µemp
int t, where
tint is the time when a (never re-
leased) reservation is interrupted
yes yes pemp
I, µI
raper-time utility of user ano yes
Cainterruption cost for user ano yes
rppayable rate for some reservation yes yes pI
Cpcompensation for interrupting
some reservation
yes yes pI
txtime when user stops usage of re-
source reservation
no yes
t0
xtime when resource reservation is
released
yes yes rp, Cp, µint
Table 4.2: Parameters in the Greenberg et al. model
63
With these variables, we can write the revenue rate per time unit
R= (1 −PI) (1 −pI)rI
µ0
I
λI+ (1 −PB)rB
µB
λB−pI(1 −PI)CIλI(4.13)
Here µ0
Iis the mean holding time for IR request
conditioned upon that the request
is not interrupted
. If pIis small, then we can approximate µ0
Iby µI.
• With the assumption that BA requests are far into the future, the admission
control for BA requests can take place without consideration of the IR calls
in progress. A BA request will be admitted if, including that request, at no
time more that s−rcapacity is reserved by BA reservation. The parameter r
defines an amount of capacity that is “put aside” for IR calls.
• On the other hand, the admission control for IR request must take into consid-
eration the IR calls in progress as well as the pending BA reservation. From
that information, the probability pIis computed, and the IR request is granted
if and only if the interruption probability for this request is less than pmax
I, with
pmax
Ibeing the “threshold probability” parameter.
Thus, the variables PI, PBand pIthat control the revenue all depend on the param-
eters rand pmax
I. The maximization of Rin (4.13) takes place by variation of rand
pmax
I.
Greenberg et al. sketch how pIcan be computed and point out that the com-
putation is somewhat cumbersome. They suggest different approximations whose
precision they evaluate in simulations. Greenberg et al.’s simulations also showed
that allowing BA and IR requests can significantly increase generated revenue even
if the probability threshold for service interruption is small.
4.3.1 Bidding for paths in the admission protocol of Greenberg et al.
Greenberg et al.’s admission control mechanism can easily be extended to the case
that a reservation request asks for a combination of resources: the admission con-
trol algorithm is run separately for every link, and the request is granted if and only
if
all
links are available. Figure 4.1 shows a summary of the extended algorithm.
The procedures AdmitBA and AdmitIR are called when requests arrive. They use
the global variables AdmittedBA and ASdmittedIR whose keeping up-to-date we
have omitted in the pseudocode. The procedure InterruptProbability performs
the (approximate) computation of pIas in [31]. The parameters pmax
Iand rare either
constants fixed in advance, or could also be dynamically adopted to maximize Rin
(4.13).
4.3.2 Mechanism design for reservations with unknown duration.
Greenberg et al. assume that the pay rates rIand rBand the “penalty” for inter-
rupted IR reservations CIare constants for all requests (which than can be set to 1
64
1globals AdmittedBA(link) // set of admitted BAs per link
AdmittedIR(link) // set of IR calls in progress per link
procedure AdmitBAperLink(slotset,link)
forall (slot in slotset) do
n=0
6forall ( (islotset,ilinkset) in AdmittedBA(link) ) do
if (slot is in islotset)
n++
endif
end
11 i f (n*b>c−r)
return false
endif
end
return true
16 end procedure
procedure AdmitIRperLink(link)
pir=InterruptProbability(AdmittedIR(link),AdmittedBA(link))
if (pir < pmax
I)
21 return true
else
return false
endif
end procedure
26
procedure AdmitBA(slotset,linkset)
forall (link in linkset) do
if (AdmitBAperLink(slotset,link) == false)
return false
31 endif
end
return true
end procedure
36 procedure AdmitIR(linkset)
forall (link in linkset) do
if (AdmitIRperLink(link) == false)
return false
endif
41 end
return true
end procedure
Figure 4.1: Admission control for combinatorial requests.
65
without loss of generality).
We now consider a market where users submit buying bids
by=
idby,^
slot∈slotsetby^
link∈linksetby
(slot,link), rby, Cby
(4.14)
and selling bids bs= (slot,link,q).
How would a good mechanism for this market look like?
First note that if the per-time rate is payable only for completed calls, there is
no incentive for a user ever to finish a call. Therefore, this approach is unfeasible.
We thus modify the revenue Rof (4.13) such that the rate rIis payable even for
interrupted calls5. This yields
R= (1 −PI)rI
µI
λI+ (1 −PB)rB
µB
λB−pI(1 −PI)CIλI(4.15)
A first glance may suggest a mechanism that pays a (per-time usage) price payable
if the request is accepted, and a “penalty” that is paid to the bidder in case that the
request is accepted but the service is interrupted. The problem with that approach
is that if the duration of the request is controlled by the bidder, he may manipulate
by intentionally not terminating the service to be entitled to the penalty payment.
So a user a’s
type
is a tuple (ra, Ca)where rais the
utility rate
and Cais the
cost of interrupt
. Furthermore, we assume that the
duration
of a reservation is
a random variable txwith exponential distribution. The value of tx, is unknown
even to aitself at the time when he places his bid. We assume that after txhas
expired, the user has no further utility from his reservation. However, he can keep
up the reservation to speculate on the interruption penalty CI. The utility of athus
depends on a parameter t0
xthat achooses and that defines the time
that
a
releases
his reservation, provided that it hasn’t been cancelled before
. This decision has to
be made only after txis known, so t0
xcan be dependent on tx.awill choose t0
xin
such a way that his expected utility is maximized.
Let is compute the expected utility that agains from the call
after
tx
has expired
,
conditioned on txand the assumption that the call was not interrupted so far. Let tint
be the time when the reservation is interrupted. Greenberg et al. give a computation
of the interruption probability for a call, depending on the currently existing BA
reservation. While the reservation owner does indeed have this information, adoes
not. Therefore, it is safe for ato assume that the interruption probability time for
any given call (of infinite duration) is also exponentially distributed with parameter
5One might argue that this is quite a realistic model anyway: the “interruption cost” CIcould then
be interpreted as the cost of the inconvenience to re-build the connection, while the utility already
gained by the service before the interruption is not lost.
66
µint. Then
ua(t0
x|tx, tint > tx) =
t0
x
Z
tx
µinte−µint(t−tx)(Cp−(t−tx)rp) dt
−t0
x−txrpP(tint > t0
x)(4.16)
=
et0
xµint et0
xµint −etxµint (Cpµint −rp)
µint
(4.17)
−→t0
x→∞ C−rp
µint
(4.18)
with rpbe the
price rate
that ahas to pay and Cpis the amount of the interruption
compensation payment.
So ahas an expected win from choosing t0
x> txif and only if µintCp> rp.
How can aget an estimate of µint?
Case 1.
We assume that the network attempts to optimize welfare and
drops least
valuable calls first
. In this case, some information is required on the distribution of
utility rates and interruption costs. We don’t consider this case here.
Case 2.
We follow Greenberg et al. and let the network
interrupt younger calls
first
. Under this assumption, acan compute µemp
int from the empirical interruption
probability pemp
Iand the parameter µIof the (exponentially distributed)
call duration
distribution
:
pemp
I=
∞
Z
0
P(tint < tdur)f(tdur)dtdur (4.19)
=
∞
Z
01−e−µinttdur µIe−µItdurdtdur (4.20)
=µI1
µI−1
µint +µI(4.21)
= 1 −µI
µint +µI
(4.22)
and therefore
µint =µI
pemp
I
1−pemp
I
.(4.23)
Note that for a given pair (rp, Cp), both aand the network can compute µint, and
therefore know whether “speculating” on Cpis profitable and also the amount of
the expected profit.
67
4.3.2.1 Non-existence of efficient two-dimensional mechanisms.
Definition 55.
A
two-dimensional access control mechanism
takes as input bids of
the form
(ba=ra, Ca)
and computes a decision function
χ
with
χ(ba)∈ {0,1}
, and a
rate-compensation vector (rp, Cp)
such that
rp
is the rate that
a
pays per time unit
until the reservation is released by
a
or cancelled by the network, and
Cp
is the
compensation that
a
receives if the reservation is interrupted by the network.
We say that a mechanism satisfies
rate-compensation voluntary participation
if
always
rp≤ra
and
Cp≥Ca
.
Corollary 56.
If the interruption probability
p
emp
I
is publicly known, there is no
efficient two-dimensional access control mechanism.
Proof.
Suppose there is only one bid (ra, Ca)with µintCa> pa.
If the mechanism is efficient, it must accept the single bid. Let (rm, Cm)be the
rate-compensation vector returned by the mechanism.
Case 1:
rm≤ra
and
Cm≥Ca
.
Then speculating on Cmis profitable for a. But
then the mechanism can’t be efficient.
Case 2:
rm> ra
or
Cm< Ca
.
Without loss of generality we can assume that a
has revealed his true type. But then it would be profitable for release the reserva-
tion right away. But this contradicts efficiency, because the request is lost even if
capacity is not used up.
4.3.2.2 Mapping two-dimensional types to one-dimensional ones.
In order to apply standard VGC mechanisms, we have to project the two-dimensional
types and bids (r, C)to one-dimensional ones. Here a one-dimensional bid is a per-
time price r, and no compensation being paid for service interrupts. The projection
πhas to satisfy that a risk-neutral user ais indifferent between the choices of either
being offered rate rand a compensation Cif service is interrupted, and a (“dis-
counted”) rate π(r, C)and no interrupt compensation. This is the case when the
expected profit from (r, C)and from π(r, C)are equal. The fact that the only differ-
ence between the two options is in payment implies that expected payments must
be equal.
While the
empirical
interrupt probability pemp
I( and the distribution femp
int and the
parameter µemp
int of the corresponding exponential distribution) is public informa-
tion (see table 4.2), the network additionally knows at any given time the currently
present BA reservations and can use this additional information to compute the in-
terrupt distribution function. Note that even if the expected profit computation is
based on the currently present BA reservations, it is obvious that there always
is
some projection πsuch that both expected profits are equal.
68
The use of the approximated distribution function fint yields
E(payment(r, C)) =
∞
Z
0
µIe−µItx"
tx
Z
0
femp
int (t0
x)(−rt0
x+C)dt0
x
−P(tint > tx)rtx#dtx(4.24)
=
∞
Z
0
µIe−µItx"
tx
Z
0
µemp
int e−µemp
int t0
x(−rt0
x+C)dt0
x
−e−µemp
int txrtx#dtx(4.25)
=−r+Cµemp
int
µI+µemp
int
(4.26)
and
E(payment(π(r, C))) =
∞
Z
0
µIe−µItx"
tx
Z
0−femp
int (t0
x)t0
xπ(r, C)dt0
x
−P(tint > tx)π(r, C)tx#dtx(4.27)
=
∞
Z
0
µIe−µItx"
tx
Z
0−µemp
int e−µemp
int t0
xt0
xπ(r, C)dt0
x
−e−µemp
int txπ(r, C)tx#dtx(4.28)
=−π(r, C)
µI+µemp
int
(4.29)
Simplifying yields
π(r, C) = r−Cµemp
int (4.30)
4.3.2.3 The empirical interrupt probability.
The above assumed that users have access to an empirical interrupt probability pemp
I.
This probability is public information, and is equal for all users. It is not necessary
that pemp
Ibe a constant over time, that is, it can be time-dependent. For instance, it
is conceivable that pemp
Iis drawn from previous days and depending on the time of
the day.
69
US SA NW
send IR request
request reservation certificate (AcceptedIR)
send reservation certificate
register reservation certificate
(a) Verified counting of reservation requests
US SA NW
request interrupt certificate (reservation id)
send interrupt certificate
send interrupt (interrupt certificate)
(b) Verified counting of service interrupts
Figure 4.2: Verified interrupt statistics
An important point is that, using standard cryptographic infrastructure, pemp
Ican
be
independently verified
to guarantee its accuracy even if mutual trust between
users and the network is absent. The verification algorithm uses that
• it is in the interest of the
network
to have a low published interruption proba-
bility (because then, users will bid higher according to equation (4.30)), while
• the
users
want certainty that pemp
Iis not to optimistic, because they incur
losses with every interruption.
The verification assumes that there is a trusted by all sides
statistics authority
SA
that counts admitted reservation requests and interrupts, and publishes pemp
I. The
data collection used by SA is built into the protocols for IR reservation requests and
IR interrupts. Let NW denote the network, and US the user. NW maintains a counter
AcceptedIR. If NW accepts an IR request, it increments AcceptedIR and sends its
value as a challenge to US.US replies with a
reservation certificate
that contains the
signed value. NW registers the reservation certificate at SA.
In case of a service interruption, NW requests from SA a
interrupt certificate
con-
taining some identification of the IR to be interrupted. NW sends the certificate to
the affected US.SA counts every reservation certificate as an admitted reservation
(not accepting duplicates with identical counter AcceptedIR), and every interrupt
certificate as a service interrupt. NW won’t serve IR reservations without the user is-
suing a proper reservation certificate. Users complain if service interruption occurs
without NW presenting a corresponding interrupt certificate.
Figure 4.2 shows an overview of the verified counting protocol.
4.4 Is there an advantage in auctioning bandwidth ?
We have above demonstrated how auction solutions can be used for bandwidth al-
location. So far, we have not stated how such a “market solution” performs in com-
parison with the classical
first come first served
allocation with a fixed rate.
70
For the comparison, we assume that there is a single link of fixed capacity cwhich
is allocated to requests issued by users in a random (Poisson) process with fixed
parameter λ. Granted requests are served until they are terminated after an expo-
nentially with parameter ddistributed time t, and users are charged rt where ris a
rate
determined by the allocation mechanism. While in the fixed price scenario, the
rate is a constant at all times, the auction mechanism recomputes the rate periodi-
cally on the base of the currently issued requests.
Requests have an associated
maximum rate
the issuer is willing to pay, and it
is guaranteed that a request is never charged more than this maximum rate. We
assume that the maximum rate of any request is drawn from a normal distribution
with constant parameters µand σ. The fixed price mechanism always denies all
requests with a maximum rate lower than the fixed rate. The auctioning mechanism
computes a
current rate
and accepts all requests with maximum rate at least the
current rate, and denies all other requests. The mechanism guarantees the current
rate for the complete time until the request is terminated by the issuer, no matter
how future current rates develop.
We simplify our scenario by assuming that there are no BA calls, and therefore,
there is no need of cancelling requests from the side of the mechanism.
In order to perform an auction, the mechanism needs to collect requests over a
certain time span which without loss of generality be of length 1.
4.4.1 Fixed price mechanism
Let us analyze the mechanism that offers a fixed rate rf. Requests are generated as
a Poisson process with parameter λ, and the associated maximum rates are normally
distributed with parameters µand σ. As described above, requests with associated
rate less than rare discarded. Thus, the sequence of non-discarded requests is
generated by a Poisson process with parameters λ∗(rf) = λP(r > rf)where r∼
N(µ, σ). Write f(r)and F(r)for the probability density function and cumulative
probability function of N(µ, σ). So
λ∗(rf) = λ1−1
21 + Erf rf−µ
√2σ (4.31)
with Erf being the well-known
error function
Erf(z) = 2
√πRz
0e−z2dz.
Since the requests of the modified process are served on first-come first-served
base, the reservation state for the fixed price scenario can be modelled as a queue
with Poisson arrival, exponential living time, cservers and no additional waiting
room. It follows (see e.g. [60, p.65]) that the state probability distribution is
pc(k) = (λ∗
d)k
k!1 + Pc
l=1
(λ∗
d)l
l!(4.32)
71
and the mean generated revenue per step can be computed by
meanrevenue(c, rf) =
c
X
k=1
(rfkpc(k)) (4.33)
Miller [51] considers M/M/c/c queues with a discrete set of customer classes. They
give an algorithm to compute the optimal admission policy if decision is immediate,
that is, the decision depends on the number of customers currently in the queue.
They introduce "shadow costs" ∇yi=yi+1 −yiof serving a customer if the system
is in state ithat reflect the expected revenue lost from the fact that now one more
server is busy. They show that than the following holds:
λ(b−∇y0) = A
···
λ(b−∇y1) + iµ∇yi−1=A
··· cµ∇yc−1=A
(4.34)
where Ais the per-time generated revenue (∇yiand Adepend on the admission
policy.)
Miller and Buckman [52] compare revenues under optimal state-dependent ad-
mission policies with the ones with the optimally chosen fixed price. They assume
that customer utilities are exponentially distributed. They conclude that
in a more realistic setting where economic environment is uncertain,
calculations suggest that there is a greater incentive to use an optimal
transfer pricing policy.
Furthermore, Miller and Buckman compute the
optimal value
T∗
of the fixed price
T, by maximizing A. Their theorem 2 says that for the optimal value T∗, the follow-
ing holds:
T∗=
c−1
X
i=0
qi∇yi(c, T∗)(4.35)
with
qi=pi(c)
Pc−1
j=0 pj(c)(4.36)
are the steady state probabilities of the queue conditioned on not all servers being
busy.
Low [45] computes optimal service price in a M/M/s/c queue if service prices
are computed in advanced after a new service has been accepted into the queue,
or a service was completed. Low assumes that at any such instance, the price
for the next arriving customer is chosen from a set Pof possible prices with P
being finite or a bounded closed subinterval of R. Low proves the existence of a
72
stationary strategy maximizing average per-time revenue, and gives an algorithm
for its computation.
Ziya et al. [85] compute the
revenue-maximizing rate
ropt
f. They prove that (propo-
sition 6.1)
ropt
f(c) = inf{r:e(r)∇c(r)≥1}(4.37)
where
e(r) = rf(r)
1−F(r)is the
price elasticity, and
(4.38)
∇c(r) = 1 + λ∗
d(pc(c)−pc−1(c−1)) (4.39)
4.4.2 Vickrey price mechanism
For a fair comparison of the revenue, we assume that the reservation requests are
generated exactly as above. However, resource allocation takes place at the end of
each time interval of length 1.6Let tk= (k−1, k]be the kth interval. Let {rk
1,...,rk
nk}
with rk
1≤. . . rk
nkbe the requests submitted during tk. (So nkhas Poisson distribution
with parameter λ.) Let lkbe the number of living requests at time k. Note that lk
is distributed according to the state distribution of a queue with Poisson(λ)arrival
and exponential(d)departure with cservers and no waiting room.
The requests rk
iare treated as bids for an auction of a good that is available in
c−lkcopies. So all requests rk
iwith i≥nk−c+lk+ 1 are accepted and pay the rate
rk=(rnk−c+lkif nk−c+lk≥1
0otherwise. (4.40)
The mean revenue per step then is
meanrevenue =cE(rk)(4.41)
4.4.3 Comparing the revenue
In the following, we give a comparison of the revenues of Vickrey pricing and pricing
with an optimally chosen fixed price. It will be shown that in many cases, Vickrey
pricing generates a higher revenue than optimal fixed pricing. We remark that to
compute the optimal fixed price, it is necessary to have a priori assumptions on the
distribution of requests. Vickrey pricing, however, generates a high revenue even if
there is no information on the distribution parameters of the incoming requests.
6This means that clients have to accept a delay <1until their reservations are accepted or rejected.
73
Figure 4.3: Revenue ratio Vickrey vs. fixed pricing with λ= 100, d = 0.1, µ = 10, σ ∈
[0,20], c ∈[1,150]
4.4.3.1 No global inequality.
While we intend to demonstrate that Vickrey pricing generates in some cases more
revenue than fixed rate pricing even with the optimally chosen fixed price, there is
no global inequality: Indeed, for λ
dcand small σ, the Vickrey price will converge
to 0for c→ ∞ (since the probability that less than crequests are in the system
converges to 1) while the number of accepted bids is bounded by the number of
submitted bids, and consequently the Vickrey revenue converges to 0if the capacity
grows beyond all limits, but the fixed rate revenue is still significantly positive. To
be more precise, we get from (4.32) and (4.33) for any fixed rate r,
lim
c→∞meanrevenue(c, r) = r∞
X
k=1
(kp∞(k))
=r∞
X
k=1 k(λ∗
d)k
k!eλ∗
d!
=rλ∗
d>0(4.42)
4.4.3.2 Simulation results.
Figure 4.3 shows the ratio of the revenues generated by Vickrey pricing and fixed
pricing with the optimally chosen fixed price. Note that in the chosen parameter
74
domain, Vickrey pricing generates a slightly higher revenue compared with optimal
fixed pricing. The advantage of Vickrey pricing here grows for small capacities and
larger σ.
4.5 Summary
In this chapter, we applied the theory of double-sided combinatorial auctions to
advanced reservations in networks. In particular, we used extensions of SBNL that
allows multiple item and combinatorial auctions. After describing a mechanism that
allows fixed length reservations, we presented various results on the case where
reservations are open-ended:
• Efficient mechanisms do not exist if the mechanism pays a compensation for
service interrupts.
• We showed how to map bids with per-time rate and penalty for service inter-
rupts, to bids only with per-time rate.
With this mapping, it is possible to apply mechanisms for combinatorial exchanges,
in particular, the SBNL pricing and commit window clearing as presented in the pre-
vious sections.
Finally, we presented simulation results that support that Vickrey pricing gener-
ates, in some cases, a higher revenue than fixed pricing with an optimally chosen
price, while not requiring information on the distribution of the requests.
A general characterization of the relationship between Vickrey revenue and op-
timal fixed price revenue would be highly desirable. We, however, leave this point
open for future research.
75
5 Indirect mechanisms for multicast
pricing
The previous chapter presented pricing for unicast streams based on the VGC mech-
anism. We considered
direct
mechanisms where users would reveal their utilities
to the network manager who would compute a resource allocation which maximizes
total utility.
Another line of research [41, 42, 40] works with
indirect mechanisms
, describ-
ing network flows as Walrasian tatonnement with elastic price and demand. Here,
network users adopt a control parameter that controls bandwidth allocation (in our
case, this parameter can be interpreted as payment either in monetary terms, or in
terms of an accepted delay). We adopt the interpretation that users control band-
width by monetary payment. In the tatonnement process, the auctioneer splits
bandwidth in proportion with the submitted payments. The adoption takes place
continuously.
Given a set of resources J, a
route
is a subset r⊆J. Fix set Rof possible routes
and define Aj,r to be the matrix defined by Aj,r = 1 if j∈r, and 0otherwise. Suppose
that every resource jhas a
capacity
cj≥0. For a route r, let xrbe the
flow through
r. The vector x= (xr:r∈R)is called the
total flow
.xis
feasible
if for all resources
j∈J, we have Pr:j∈rxr≤cj. Let us furthermore assume that to every route r,
there is an associated user that has utility ur(xr)from rwhich depends on xr.
Kelly considers three interconnected optimization problems1:
• the
system
tries to maximize aggregated utilities:
SYSTEM(u, A, c)
max X
r∈R
ur(xr)!over (xr:r∈R)(5.2)
1The setting described here is known as
inelastic supply
setting. This refers to the fact that every
link has a fixed capacity that is split among users.
Elastic supply
settings, see [40] assume that
supply can vary but that there is a cost associated with it. The corresponding SYSTEM problem
then has the form
max
X
r∈R
ur(xr)−C
X
r
xr
!!
over (xr:r∈R)(5.1)
where C(x)is the
cost
associated with a supply of capacity x.
76
subject to
X
{r∈R:Aj,r=1}
xr≤cjfor all j∈J(5.3)
xr≥0for all r∈R(5.4)
• the
users
maximize their own profit (that is, utility minus costs) while varying
the size of the flow he acquires for a given per-unit price λ:
USERr(ur, λ)
max (ur(xr)−wr)over xr(5.5)
subject to
xr≥0(5.6)
wr=xrλr.(5.7)
• Finally, the
network
maximizes revenue by varying the flow sizes:
NETWORK(A, λ, c)
max X
r∈R
λrxrover (xr:r∈R)(5.8)
subject to
X
{r∈R:j∈r}
xr≤cjfor all j∈J(5.9)
xr≥0for all r∈R. (5.10)
Theorem 1 of [40] interconnects these three optimization problems: If the urare dif-
ferentiable, strictly concave functions, then there is a price-per-unit vector λ= (λr:
r∈R)such that the unique solution vector (x=xr:r∈R)of the USERrproblems
simultaneously solves NETWORK(A, λ, c), and this vector also solves SYSTEM(u, A, c).
If we see users and network as self-interested agents (users maximizing their
private surplus, while the network maximizes revenue), we are tempted understand
this theorem as the guarantee that there is an equilibrium in the associated game,
and that at this equilibrium, the
social surplus
as given by the SYSTEM problem
(5.2) is also maximized. Note, however, that λdepends on the user’s input. If there
is a large number of users, and none of their utility functions is dominating, we can
77
assume, for approximation, that the price vector λdoes not depend on the input of
a fixed user r. Only in this case, the theorem implies that there is an equilibrium
with optimal social surplus.
Note that NETWORK(A, λ, c)is the relaxation of the combinatorial auction prob-
lem
AUCTION(A, λ, c)
max X
r∈R
λrxrover xr(5.11)
subject to
X
{r∈R:j∈r}
xr≤cjfor all j∈J(5.12)
xr∈ {0,1}for all r∈R. (5.13)
where cj(1 ≤j≤J) are
goods
and λ= (λr:r∈R)is the
bid vector
of the auction.
In contrast with the work of the mechanism design school, there are no
costs
considered to be incurred by the transmission. Rather, the price is computed such
that
• certain
fairness
conditions are honoured, and
• a balance between supply (available capacity of the required resources) and
demand is achieved.
5.1 Linear utilities
In [29, par. 6.2], an example is considered that illustrates how the Nash equilibrium
is computed in the case that users
are
aware of the effect of their input on the price
vector λ:
Assume that nusers have linear utility functions ur(xr) = αrxrwith αr>0. Fur-
thermore, assume that the network assigns rates to the users in proportion of their
willingness to pay wr. For convenience, write Wr=Pr06=rwr0and S=Prwr=
wr+Wrfor all r. Then the maximization problem presented to the user ris
USERr(ur)
max urwr
wr+Wr−wrover wr(5.14)
78
subject to
wr≥0(5.15)
Now
urwr
wr+Wr−wr=αr
wr
wr+Wr−wr(5.16)
and thus
d
dwrurwr
wr+Wr−wr=αr
wr+Wr1−wr
wr+Wr−1(5.17)
Therefore, for the solutions of (5.14) we have
either
wr= 0 and d
dwrurwr
wr+Wr−wr<0,(5.18)
or
d
dwrurwr
wr+Wr−wr= 0,(5.19)
or equivalently,
wr=S1−S
αr+
.(5.20)
Summing up (5.20) for all r, we get
S=SX
r1−S
αr+
(5.21)
and consequently,
1 = X
r1−S
αr+
.(5.22)
Fact 57.
a) There is a unique vector
(wr)
such that equations (5.20) hold for all
r
, and
S=Prwr
.
b) For
n= 2
, we have
wr>0
for all
r
.
Proof.
Note first that there is a unique Ssuch that
1 = X
r1−S
αr(5.23)
holds for all r, namely
S=n−1
Pr1
αr
.(5.24)
79
Define
vr0=n−1
Pr1
αr2 X
r
1
αr−n−1
αr0!(5.25)
which is equivalent to
vr0=S1−S
αr0.(5.26)
Consequently, if vr≥0holds for all r, then with wr=vr, equations (5.20) and (5.22)
hold for all r. Otherwise, remove all rwith vr<0, and apply (5.24-5.25) iteratively.
Note that for the case n= 2, (5.25) implies that vr0>0and thus iteration terminates.
This proves existence of S, and also part b of the claim.
To prove uniqueness, assume that there are S6=S0and (wr),(w0
r)such that (5.20)
holds for all r. Clearly if wr>0and w0
r>0, then wr=w0
r. Let r0be such that without
loss of generality, wr0< w0
r0. Then wr0= 0, w0
r0>0and thus S0< αr0< S. It follows
that for
all
users r, we have wr≤w0
r. But this implies S≤S0, a contradiction.
Those users rwith αr> S set wr=S1−S
αrwith Saccording to (5.22), the
remaining ones set wr= 0.
5.1.1 Comparison with VGC mechanisms
Note that the equilibrium bid wrdepends on the bids of the other players, and
so there is no
dominant
strategy for any user with positive utility. Also, at the
equilibrium, the social surplus is
not
maximized. Maximizing social surplus in the
case of linear utility functions would mean to allocate
all
capacity to the user r
with the highest αr. This, however, seems absurd: the assumption of linear utility
functions is reasonable only as an approximation for small ranges. The tatonnement
works independently from the shape of the utility functions, and the results apply
when utilities are linear for bandwidth range below the equilibrium allocation.
A dominant strategy mechanism would maximize surplus in respect to
all
possible
allocations and would therefore need the complete utility functions (for the band-
width ranges below the
total capacity
). The applicable VGC mechanism would then
be the auction of a divisible good, see the background chapter at 2.4. A dominant
strategy mechanism will split resources discontinuously in respect to the input from
the clients. This, of course, could impose problems for applications.
5.1.2 Approximativity of the Nash equilibrium
As noted above, the resource allocation at the Nash equilibrium is suboptimal. In
this paragraph, we give a bound for the quotient of the utilities of the Nash and
optimal allocations.
80
Note first that the optimal allocation assigns all utility to the users with the high-
est αr(being indifferent of how these users share the resource among each other).
Utility is then
uopt = max
rαr(5.27)
For the utility at the Nash equilibrium, we get from (5.24) and (5.25) and with n=
|{r:wr>0}|,
uNash =X
r:wr>0
αr
wr
S(5.28)
=X
r:wr>0
αr−n(n−1)
Pr:wr>01
αr
(5.29)
and
uNash
uopt = max
r0Pr:wr>0αr−n(n−1)
P
r:wr>0
1
αr
αr0
(5.30)
Let rmax = arg maxrαrand define
f(hαr:wr>0i) = Pr:wr>0αr−n(n−1)
P
r:wr>0
1
αr
αrmax
(5.31)
This function is symmetric in all αrexcept for r=rmax. Therefore, at its local
minima, αr=αholds for some αand for all r6=rmax. Now substitute αfor αrwith
r6=rmax to receive
f(hα, . . . , α, αr, α, . . .i) = 1 + (n−1)α1
αmax −n
(n−1)αmax +α(5.32)
and for the derivative, we get
d
dαmax f() = (n−1)α−1
αmax2+n(n−1)
((n−1)αmax +α)2(5.33)
The derivative has a positive root at
α=αmax 1−n+pn2−n(5.34)
Substituting this back into the definition of fyields that fis independent of αmax at
that location:
fn:= f() = n(3 −2n) + 2(n−1)pn(n−1) (5.35)
81
Now (fn)is monotonously decreasing, and
lim
n→∞fn=3
4.(5.36)
We conclude that 2
Fact 58.
If users have linear utility functions, the total utility at the Nash equilib-
rium is at least three quarter of the total utility at the optimal resource allocation.
5.1.3 Multicast with linear utilities
Let us now generalize this example to a setting that considers multicast. In the
simplest model inspired by the one of Feigenbaum et al [26], we assume that there
are users sharing a transmission, and that the sharing does not imply any extra cost.
To model this, we just have to allow that xr=xr0for distinct users r, r0. Then the
user problem (5.14) turns into
MULTICAST_USERr(ur)
max αr Pr0:xr=xr0wr0
wr+Wr!−wr!over wr(5.37)
subject to
wr≥0.(5.38)
For the derivative, we get
d
dwr
(ur() −wr) = αr
wr+Wr 1−Pr0:xr=xr0wr0
wr+Wr!−1(5.39)
Now
d
dwr
(ur() −wr)<0(5.40)
if and only if
wr> S −S2
αr−X
r06=r:xr0=xr
wr0(5.41)
2Added in proof: This is a special case of Theorem 3 of [38] which is scheduled for publication. The
proof for linear utility functions is considerably simpler and since given here. For the case of elastic
supply, see [37].
82
(and similarly for equality). Therefore, at the equilibrium, we must have wr≥S−
S2
αr−Pr06=r:xr0=xrwr0for all r, and equality for all rwith wr>0. However,if rand r0
are in one group, equality can hold for both only if αr=αr0. Write αg
r= maxr0∈Grαr0.
Then from (5.14), we get gr=S1−S
αg
r+.
This means that the resource is split between those multicast groups for which αg
is large enough in proportion with the
maximal
utility gradients of each group, that
the users with maximal utility gradient in each group pay and the other users enjoy
free service on the level that their group leaders are willing to pay.
5.1.3.1 Example with 3 users in 2 groups.
Let us look at a simple example with two groups: g1consisting of users 11 and 12
with α11 < α12, and group g2with one user 2 with α2. With S=w12 +w2, we get
from (5.20) and claim b of fact 57 for r= 12 and r= 2
w12 =α2
12α2
(α12 +α2)2(5.42)
w2=α12α2
2
(α12 +α2)2(5.43)
and for the utilities
u11 =α11α12
α12 +α2
(5.44)
u12 =α2
12
α12 +α2−w12 (5.45)
=α3
12
(α12 +α2)2(5.46)
u11 +u12 =α12 α2
12 +α11(α12 +α2)
(α12 +α2)2(5.47)
5.1.3.1.1 Comparison with group agent. Suppose that the first group from the
example above employs a group agent that adjust a weight w1used jointly by users
11 and 12. This means that the multicast stream is treated exactly like a unicast
stream. We get
w1=(α11 +α12)2α2
(α11 +α12 +α2)2(5.48)
w2=(α11 +α12)α2
2
α11 +α12 +α2
(5.49)
u1= (α11 +α12)w1
w1+w2−w1(5.50)
=−(α11 +α12)3
(α11 +α12 +α2)2(5.51)
83
0
5
10
15
20
a11
0
5
10
15
20
a12
0
10
20
utility
0
5
10
15
20
a11
Figure 5.1: Utility without (green) versus with (blue) group agent, a2=10
From straightforward calculation, we get that the group utility with group agent
is larger than group utility without group agent, if and only if
(α11, α12, α2)∈R3
+and (5.52)
α2<α2
11 +α11α12
2α12
+1
2sα4
11 + 2α3
11α12 + 5α2
11α2
12 + 8α11α3
12 + 4α4
12
α2
12
(5.53)
=
(α11 +α12)α11 +pα2
11 + 4α2
12
2α12
(5.54)
Figure 5.1 compares u11 +u12 from (5.47) (blue surface) and u1from (5.51)
(green surface) for the case a2= 10. Figure 5.2 shows the bounds of the polytope
{(α11, α12, α2)∈R3
+:u11 +u12 < u1}.
5.1.3.1.2 Remark. One can easily construct an example such that the first group
is not served at all even though its total utility is larger than that of both other
groups: let the first group consist of three users with α11 =α12 =α13 =25
3(write
α1=α11 +α12 +α13), let α2= 10 and introduce a third group with one member with
84
0
2.5
5
7.5
10
a11
0
2.5
5
7.5
10
a12
0
2.5
5
7.5
10
a2
0
2.5
5
7.5
10
0
2.5
5
Figure 5.2: Polytope of points where utility with group agent is larger than without
α3= 20. We get from (5.25) with a=α1α2α3
(α1α2+α1α3+α2α3)2
v11 +v12 +v13 =a(α1α2+α1α3−α2α3) = −200
361 (5.55)
v2=a(α1α2−α1α3+α2α3) = 1800
361 (5.56)
v3=a(−α1α2+α1α3+α2α3) = 2200
361 (5.57)
It follows that w11 =w12 =w13 = 0 and after another iteration, we compute w2=
400
81 , w3=500
81 .
5.1.3.2 Conclusion.
From the examples above, it follows that allocation at the Nash equilibrium for
multicast with individual weighs is arbitrarily inefficient in comparison with the
optimal allocation if multicast groups grow large. This contrasts the approximativity
of the Nash equilibrium for unicast (fact 58).
5.2 Logarithmic utilities
Suppose now that, as in the original model of Kelly, users have logarithmic utilities:
ur=αrlog(xr)−wr(5.58)
85
If resource allocation is in proportion with the wr’s, then the user problem is
LOGUSERr(ur)
max αrlog wr
wr+Wr−wrover wr(5.59)
subject to
wr≥0(5.60)
Note that limwr→0ur=−∞and thus at the equilibrium, the derivative of urmust be
zero for every r. In this example, voluntary participation is not satisfied in general
in the sense that if a user refuses to pay anything, his resource share will be zero
and his utility −∞.
Now with S=Prwr,
d
dwr
ur=αr
wr1−wr
S−1(5.61)
and at the equilibrium,
wr=αrS
αr+S.(5.62)
Summing (5.62) up for all rand dividing by S6= 0, we get
1 = X
r
αr
αr+S(5.63)
which determines S > 0uniquely.
Note that Sis the root of a polynomial of degree n+ 1, where nis the number of
users.
5.2.1 Numerical simulation for unicast
Let us assume there are 3 users a, b and cand fix αa= 1 for user a. How does a’s
optimal weight, resource share and surplus (utility minus costs) vary with b’s and
c’s weight?
Figures 5.3, 5.4 and 5.5 show a’s optimal weight , resource share and surplus for
band cvarying between 0 and 2.
86
00.5 11.5 20
0.5
1
1.5
2
0.4
0.5
0.6
0.7
00.5 11.5
Figure 5.3: Equilibrium weight for user adepending on αband αc
00.5 11.5 20
0.5
1
1.5
2
0.3
0.4
0.5
0.6
00.5 11.5
Figure 5.4: Equilibrium resource share for user adepending on αband αc
00.5 1
1.5
20
0.5
1
1.5
2
-2
-1.5
-1
00.5 1
1.5
Figure 5.5: Equilibrium surplus for user adepending on αband αc
87
5.2.2 Approximativity of the Nash equilibrium
Logarithmic utility functions as in (5.58) are unbounded from below. Therefore,
theorem 3 of [38] does not apply. Anyway, since user’s utility is negative, a
lower
bound of the coordination ratio is of interest.
Let T=Prαr. First note
Fact 59.
u
opt
(α1,...,αn) = X
1≤r≤n
αrlog αr
T.(5.64)
Proof.
Consider the function fαfor α= (α1,...,αn−1)defined by
fα:{(x1,...,xn−1) : xr>0,X
r
xr≤1} 7→ R(5.65)
fα(x1,...,xn−1) = X
1≤r<n
αrlog xr+αnlog(1 −X
1≤r<n
xr).(5.66)
For the partial derivatives of f, we have for 1≤r < n
∂fα
∂xr
(x1,...,xn−1) = αr
xr−αn
1−P1≤r<n xr
(5.67)
= 0
if
xr
1−P1≤r<n xr
=αr
αn
.(5.68)
There is exactly one point xwhere
all
partial derivatives vanish, namely at
x= (x1,...,xn−1)(5.69)
with
xr=αr
T.(5.70)
Now at f’s domain boundary
{(x1,...,xn−1) : xr= 0 for some ror X
r
xr= 1},(5.71)
fhas value −∞. It follows that xis a global maximum.
In contract to the case with linear utilities, there is no bound for the coordination
ratio depending only on n:
88
Fact 60.
For any
B > 0
and any
n≥2
, there are
α1,...,αn
such that if for
r=
1,...,n
, utility functions are defined by (5.58),
u
nash
(α1,...,αn)
u
opt
(α1,...,αn)> B. (5.72)
Proof.
Consider first the case n= 2. Then (5.63) turns into
α1
α1+S+α2
α2+S= 1,(5.73)
or
S=√α1α2.(5.74)
Then
wr=αrS
αr+S(5.75)
and
unash(α1, α2) = α1log α1
α1+S+α2log α2
α2+S(5.76)
and consequently
unash
uopt =α1log α1
α1+√α1α2+α2log α2
α2+√α1α2
α1log α1
α1+α2+α2log α2
α1+α2
,(5.77)
and this is unbounded for α1= 1 and α2grows large. This concludes the case n= 2.
For the general case, simply add users rfor r > 2with αr= 0. The optimal utility
does not change by introducing these additional users, and equation (5.62) implies
that it doesn’t change the Nash utility either. This finishes the proof.
The coordination ratio can be bounded depending on L=maxrαr
T:
Fact 61.
With
L=maxrαr
T
, the following holds:
u
nash
(α1,...,αn)
u
opt
(α1,...,αn)≤1−1
Llog L+ (1 −L) log(1 −L).(5.78)
Proof.
Let Sbe satisfying (5.63). Now
X
r
αr
αr+T<1(5.79)
and consequently
S < T. (5.80)
89
It follows
unash(α1,...,αn) = X
r
αrlog αr
αr+S(5.81)
>X
r
αrlog αr
αr+T(5.82)
=X
r
αrlog αr−X
r
αrlog(T+αr)(5.83)
>X
r
αrlog αr−X
r
αrlog T+αr
T(5.84)
using that log(x+y)< logx +y
xfor positive xand y, and thus
unash(α1,...,αn)>X
r
αrlog αr
T−X
r
αr2
T.(5.85)
The coordination ratio can then be bound by
unash(α1,...,αn)
uopt(α1,...,αn)<1 + Prαr2
TPrαrlog( T
αr)(5.86)
≤1 + T
Prαrlog T
αr(5.87)
using that Prαr2≤T2for the last inequality.
Now consider the function f
f(α1,...,αn−1) = X
1≤r<n
αrlog αr+ (T−X
1≤r<n
αr) log(T−X
1≤r<n
αr)(5.88)
defined on the polyhedron Pwith bounds
αr
T≤L
α1≥α2
α2≥α3
...
αn−2≥αn−1≥T−X
1≤r<n
αr>0.
We have that for 1≤r < n,
∂f
∂αr
(α1,...,αn−1, T) = log αr−log(T−X
1≤r<n
αr)>0(5.89)
90
for all points in P:fassumes its maximum at the bounds of the polyhedron
α1=TL
α2=T(1 −L)
α3=α4=...=αn−1= 0
T−X
r
αr= 0.
It follows that
f(α1,...,αn−1, T)< T L log(TL) + T(1 −L) log(T(1 −L)).(5.90)
Continuing from (5.87), we conclude
unash(α1,...,αn)
uopt(α1,...,αn)<1 + T
Tlog T−(TL log TL +T(1 −L) log(T(1 −L))) (5.91)
= 1 −1
Llog L+ (1 −L) log(1 −L).(5.92)
5.2.3 Multicast with logarithmic utilities
Let us now apply our model of multicast for the case of user utilities being loga-
rithmic. Let us write Gr={r0:xr0=xr}for the multicast group of user r, and
gr=Pr0∈Grwr0for the total weight of that group, and S=Prwrfor the total
weight. The user problem then is
MULTICAST_LOGUSERr(ur)
max αrlog gr
S−wrover wr(5.93)
subject to
wr≥0.(5.94)
For the derivative, we get
d
dwr
(ur() −wr) = αrS
gr1
S−gr
S2−1(5.95)
=αr
gr1−gr
S−1(5.96)
91
Thus the derivative is nonnegative as long as
gr≤Sαr
αr+S,(5.97)
and zero if equality holds. Similarly as in the case for linear utilities, the latter
is the case only for those users rfor which αris maximal within their group, and
consequently, for the remaining users r0, we have wr0= 0.
Fact 62.
The coordination ratio for multicast users with logarithmic utilities can
become arbitrarily bad.
Proof.
Let there be two multicast groups: one with nmembers and one with only 1
member. Suppose for all users rwe have αr= 1. According to fact 59, the optimal
utility is
uopt =nlog n
n+ 1 + log 1
n+ 1 (5.98)
=n(log n−log(n+ 1)) −log(n+ 1).(5.99)
The nash utility is
unash =nlog 1
2+ log 1
2(5.100)
=−(n+ 1) log 2.(5.101)
This implies
lim
n→∞
unash
uopt =−(n+ 1) log 2
n(log n−log(n+ 1)) −log(n+ 1) (5.102)
=∞.
5.3 General case for multicast
From the formulation of the multicast user problem for general utility functions
(5.14) we get
d
dwrurgr
wr+Wr−wr=u0
rgr
SS−gr
S2−1(5.103)
This is positive if and only if
u0
rgr
S>S2
S−gr
(5.104)
The right-hand side of (5.104) is identical for all users in a group. At the equilibrium,
only those users rfor which u0
rgr
Sis maximal among r0∈Grhave positive weight
while the others prefer to benefit from free service.
92
This means that if multicast users submit individual weights to the mechanism,
the resource share they are assigned does not in general increase with the total
utility of the multicast group, but rather with the
maximal individual utility
. Thus,
the equilibrium solution of the resource share problem is far from efficient.
5.4 Summary
In this chapter, we showed that the classical indirect bandwidth allocation mecha-
nism introduced by Kelly cannot easily be applied to multicast settings without loss
of much of its efficiency at equilibrium. If utilities are linear, Kelly’s unicast mech-
anism has coordination ratio of at most 4
3while if applied to multicast settings, the
coordination ratio is unbounded. In the general case and even in the case of log-
arithmic utilities, neither the unicast nor the multicast mechanisms have bounded
coordination ratio, however, the multicast coordination ratio can’t be bound even in
terms of the logarithmic unicast coordination ratio.
93
6 Publish/subscribe systems
6.1 Publish/Subscribe Systems
6.1.1 Introduction
Part of the work presented in this chapter were published in [77] and presented as
brief announcement at DISC 2004, and in [75].
In many applications today, conglomerates of independently created components
have to be integrated into increasingly complex information systems. It is becom-
ing more and more obvious that for large-scale distributed applications a loosely-
coupled event-based style of communication has many advantages: it facilitates the
clear separation of communication from computation and eases the integration of
autonomous, heterogeneous components into complex systems.
Publish/subscribe systems implement the event-based style: individual process-
ing entities, which we call
clients
, can
publish
information without specifying a
particular destination. Similarly, clients express their interest in certain types of
information by
subscribing
, so clients can be
producers
and
consumers
at the same
time. Information is encapsulated in
notifications
and the
notification service
is re-
sponsible for notifying each consumer about all occurrences of notifications which
match one of its subscriptions.
6.1.2 Importance for mobile applications
In comparison to classical client/server systems, the publish/subscribe paradigm
offers serious advantages in information-driven applications. Here, a client is not
obliged to poll a data source for updates – she just subscribes for information she
is interested in and gets informed whenever new data is available that fits his sub-
scription. In consequence, a loose coupling is achieved and lots of network traffic
can be economized. Applying pub/sub in commercial applications the bandwidth
savings can become a substantial argument, especially when clients need to get
informed in realtime about updates with bandwidth being expensive and scarce.
Consider for example a wireless network of battery-driven info-nodes with clients
connected locally to the nodes by wire. Obviously, the bandwidth between the nodes
is restricted and data transmission comes at the cost of valuable battery lifetime. In
this scenario, to decide if a client, subscribing to some information, will finally be
served, depends on its “utility” from the data. For example, a subscriber employed
94
in a research institute, may have a high utility of news from the scientific community,
published by newstickers from different news agencies. Thus, his subscription may
get served by the network while another subscription for less important news about
sports would not. Obviously, for the network operator in this scenario, finding out
over which links a message should be sent is a very expensive task regarding the
message and network complexity. Additionally, for encouraging the clients not to
lie about their utility, a price for the subscription has to be calculated and charged.
This price depends on the costs for the transmission and the utility of other clients
served on the same network-path. Of course calculation has to be redone every
time some change occurs in the network (e.g. a node (un)subscribes or a publisher
(un)advertises).
6.1.3 Why formalization?
There is a considerable amount of work on notification services, and many concrete
systems have been designed and implemented (e.g., Siena [14], JEDI [16], etc.).
Unfortunately, understanding and comparing these systems is difficult because of
differing and informal semantics. Research in the area of publish/subscribe has
concentrated on informal analyses and systems offering best-effort functionality.
Eugster et al. [22] give an overview about publish/subscribe systems and their rel-
atives. With the increasing popularity of publish/subscribe, however, the need for
a formal treatment and for systems guaranteeing more stringent properties is aris-
ing. A clear and detailed formalisation allows the behaviour of the system to be
described unambiguously and provides a basis for further reasoning, e.g. about the
correctness of the system. Formalisations have been proved useful in many areas
of distributed computing. However, the specification and verification of distributed
systems is a complex task. A variety of techniques (e.g. petri nets, temporal logic,
automata) have been proposed, each having its own set of strengths and weak-
nesses.
Propositional linear temporal logic (PTL) [59, 46] has proved to be a powerful
tool to characterise and verify the behaviour of concurrent distributed systems [28].
Fiege, Mühl, and Gärtner [27, 55] introduced a formal specification of publish/sub-
scribe systems using linear temporal logic. In their work, a requirement specifi-
cation for publish/subscribe systems consisting of safety and liveness properties is
introduced. To the authors best knowledge no other formalisation for publish/sub-
scribe systems has been proposed yet. Datta et al. [18] informally state liveness
and safety conditions, however, only for static subscriptions and not paying respect
to the distributed nature of publish/subscribe systems by implicitly assuming global
time. Courtenage [15] offers a description of event types using the λ-calculus, al-
lowing a formal specification of filters. However, system states and correct system
behaviour are not addressed in this work.
In this paper, we rewrite the formalism presented in [27, 55] such that it is
95
strictly propositional and extend it to provide message completeness guarantees.
In a
message-complete
publish/subscribe system, the system eventually acknowl-
edges every subscription and guarantees the delivery of notifications matching an
acknowledged subscription from this time on. In a system without message com-
pleteness, the delivery of all notifications matching a subscription is also eventually
guaranteed, but the consumer is not aware of the time from which on completeness
is guaranteed.
The remainder of this paper is structured as follows: Sect. 6.2 introduces a formal
specification for message-complete publish/subscribe systems. Then, we present an
implementation framework in Sect. 6.3 that realizes message completeness on top
of a system without this guarantee. The approach of separating the development of
an axiomatic formalism from the description of a possible implementation enables
precise formulation of axioms on the distributed state of publish/subscribe systems,
and provable statements on the implementation’s properties regarding these ax-
ioms.
6.2 Formal specification
6.2.1 Propositional temporal logic and traces
Propositional linear temporal logic (PTL) uses formulas recursively built from atomic
propositions, the
elementary state predicates
, which are predicates on the finite
set Sof
states
, propositional logical connectors ∨,∧,¬,⇒and temporal quantifiers
U,,♦and e.
For our purpose, we are a little more precise about the structure of S: The
state
s∈Sof a system is an assignment s=s:V 3 v7→ s(v)of the state variables v∈ V
to some value s(v)∈
range
(v). Both domain and range of sare assumed to be finite.
The semantics of PTL is defined by the notion of traces. A
trace
σis a sequence
of finitely many states
σ=sσ
0, sσ
1,...,sσ
n(6.1)
An ω
-trace
is an infinite sequence
σ=sσ
0, sσ
1,... (6.2)
of states.
Let Σbe the set of all traces and Σ∗the set of all ω-traces. For σ∈Σ, σ0∈Σ∪Σ∗,
we say that σ0
extends
σif σ=sσ0
0, sσ0
1,...,sσ0
nfor some n≥0. For σ∈Σ, define
σ∗={σ0∈Σ∗:σ0extends σ}. The collection {σ∗:σ∈Σ}of base-open sets induces
a topology for the space Σ∗.
Proposition 63.
Let
Σ0⊆Σ
. Then
Σ∗
0={σ∗∈Σ∗:
if
σ∈Σ
such that
σ∗
extends
σ
,then
σ∈Σ0}(6.3)
96
is a closed subspace of
Σ∗
.
Proof.
Let σbe in the closure of Σ∗
0, that is, all initial segments of σcan be extended
so that the extension is in Σ∗
0. But then, all initial segments of these extensions are
in Σ0. Therefore all initial segments of σare in Σ0.
Definition 64.
Let
Σ0⊆Σ
be a set of traces. We say that
Σ0
is
•
closed under initial segments
, if
sσ
0,...,sσ
i, sσ
i+1,...,sσ
n∈Σ0
implies that
sσ
0,...,sσ
i∈
Σ0
for arbitrary
0≤i≤n
,
•
closed under suffixes
, if
sσ
0,...,sσ
i, sσ
i+1,...,sσ
n∈Σ0
implies that
sσ
i, sσ
i+1,... ∈
Σ0
for arbitrary
0≤i≤n
„
•
closed under stuttering
, if
sσ
0,...,sσ
n∈Σ0
, implies that
sσ
0,...,sσ
i, sσ
i,...,sσ
i, sσ
i+1,...,sσ
n∈Σ0(6.4)
for arbitrary
0≤i≤n
, and
•
closed under skipping states
, if
sσ
0, sσ
1,...,sσ
n∈Σ0
implies that
sσ
0,...,sσ
i−1, sσ
i+1,...,sσ
n∈Σ0(6.5)
for arbitrary
0≤i≤n
.
By definition, an elementary state predicate applied to a trace σ=sσ
0, sσ
1,...,sσ
n
always refers to state s0. For instance, the predicate “v=v0” for some state variable
v∈ V and some v0∈
range
(v)is true for trace σiff s0(v) = v0.
Temporal logic allows us to state properties for a trace by introduction of the
additional quantifiers U,,♦, and e. For some formulas φ, φ0and σ=sσ
0, sσ
1,...,sσ
n,
1. φUφ0(σ)holds if either for all i,φholds for the trace sσ
i, sσ
i+1,..., or there is k
such that φ0holds for sσ
k, sσ
k+1,...and φholds for sσ
i, sσ
i+1,...for i < k1,
2. ♦φ(σ)holds iff there exists isuch that φholds for the trace sσ
i, sσ
i+1,...,
3. φ(σ)holds iff for all i,φholds for the trace sσ
i, sσ
i+1,...,
4. eφ(σ)holds iff φholds for the trace sσ
1, sσ
2,....
Alpern and Schneider [3, 4] give a definition of safety and liveness conditions in
this context, and a topological characterisation of them:
Definition 65.
A predicate
P
is a
safety
predicate if the following holds for
σ∈Σ∗
0
:
If for any
i≥0
, there is
σ0∈Σ∗
0
such that
σ0
extends
sσ
0,...,sσ
i
and
P
satisfies
σ0
,
then
P
satisfies
σ
. A predicate
Q
is a
liveness
predicate if for any
σ∈Σ0
, there is
an extension
σ0∈Σ∗
0
of
σ
satisfying
Q
.
1Note that our Uis written as W(
waiting for
) in [46].
97
Definition 66.
Let
Σ0
be closed under final segments.
Q
is
absolute liveness
pred-
icate in
Σ∗
0
if for any
ω
-trace
σ=s0, s1,... ∈Σ∗
0
, if there is an
i≥0
such that
Q
satisfies
si, si+1,...
, then
Q
satisfies
σ
.
With this definition, it is easy to see that Pis a safety predicate exactly if the set
of ω-traces satisfying Pis closed in Σ∗, and that Qis a liveness predicate, if and only
if the set of ω-traces satisfying Qis dense in Σ∗. [73] gives a sufficient syntactical
condition of safety predicates:
Theorem 67 (Sistla).
Every elementary state predicate is a safety predicate, and if
P
and
Q
are safety predicates, so are
P∧Q
,
P∨Q
,
eP
,
P
and
PUQ
.
Sistla gives the following strengthening of safety:
Definition 68 (Sistla).P
is a
strong safety
predicate, if
P
is a safety predicate and
closed under stuttering and skipping states.
Sistla also defines
Definition 69 (Sistla).P
is an
L-safety
predicate, iff for any
σ=sσ
0, sσ
1,...
,
P
sat-
isfies
σ
if and only if for all
i≥0
, the trace
σ0=sσ
0,...,sσ
i, sσ
i, sσ
i,...
is satisfied by
P
.
Proposition 70 (Alpern and Schneider[2]).
If
P
is closed under stuttering, then
P
is a safety predicate if and only if
P
is an
L
-safety predicate.
6.2.2 Formalising publish/subscribe systems
In [55], a formal specification of publish/subscribe systems has been given by defin-
ing axioms about the admissible sequences (traces) of interface operations and
client states. We will present a formalism that differs from that one by
a) being strictly propositional, using only predicates on states rather than on
state transitions, and
b) giving message completeness guarantee.
6.2.2.1 State variables and Interface
We now define the state variables of message complete publish/subscribe systems.
State transitions are triggered by
interface operations op
:S7→ S.
Definition 71.
The
state
of a client
c
of a publish/subscribe system with message
completeness guarantee is determined by the following variables:
• the input variable for the publisher’s role
Pc
, the set of notifications
n
pub-
lished by
c
,
98
• the variables for the subscriber’s role,
–
output
Dc
, the set of notifications that
c
received,
–
output
D
dup
c
, the set of notifications that
c
received at least twice,
–
input
Sc
, the set of active subscriptions of
c
.
–
output
S
ack
c
, the set of acknowledged subscriptions of
c
.
The
input state
of the system is defined to be the state restricted to the input vari-
ables, and similarly, the
output state
is defined.
Next we define the operations that trigger state transitions. We write the oper-
ations as op :v7→ v0, to be understood as operation op transforming state v∈Sto
v0∈S.
Definition 72.
The
interface of a publish/subscribe system with message complete-
ness guarantee
contains the following operations:
• operations called from the environment:
–
pub
(c, n) : Pc7→ Pc∪{n}
, client
c
publishes notification
n
–
sub
(c, F) : Sc7→ Sc∪{F}
, client
c
subscribes to filter
F
–
unsub
(c, F) : Sc7→ Sc\{F}
, client
c
unsubscribes from filter
F
• operations called by the system:
–
notify
(c, n, p) : D
dup
c7→ D
dup
c∪(Dc∩{n}), Dc7→ Dc∪{n},
, client
c
is notified
about
n
coming from publisher
p
–
ack
(c, F) : S
ack
c7→ S
ack
∪{F}
, client
c
is notified that from now on, notifi-
cations matching
F
will eventually be delivered to
c
The
initial state
of the system is defined to be the state
s
init with
Pc=Dc=D
dup
c=
Sc=S
ack
c=∅
for all clients
c
.
Definition 73.
For a trace
σ=sσ
0, sσ
1,...,sσ
n
, let the
input-restriction of σ
, denoted
by
σ
input , be the sequence of the input states
σ
input
=s
input
0, s
input
1, . . . , s
input
n
. Similarly,
we define the notion of
output-restriction
.
Definition 74.
Let
σ=sσ
0, sσ
1,...,sσ
n
be a trace. The
reduction
of
σ
is defined to be
the largest subsequence2
σ0=sσ
k0, sσ
k1, sσ
k2,...
of
σ
such that for all
i≥0
,
sσ
ki+1 6=sσ
ki
.3
We say that a trace
σ=sσ
0, sσ
1,...,sσ
n
is
input-admissible
, if there is a sequence
op
0,
op
1,...,
op
m
of interface operations such that the input-restriction of the reduc-
tion of
σ
is a subsequence of the input-restriction of
s
init
,
op
0(s
init
),
op
1(
op
0(s
init
)),...
.
Similarly, we define the notion of
output-admissibility
.
2Remember that a sequence hsi:i∈Niis a
subsequence
of htj:j∈Niif there is a strictly
monotonous sequence hli:i∈Niof natural numbers such that for all i, we have si=tli.
3Note that although hki:i∈Niis not uniquely determined, σ0is.
99
Note the following facts:
Fact 75.
• The operations pub, sub, and ack are idempotent for publish/subscribe systems
with message completeness guarantee.
•
σ=sσ
0, sσ
1,...,sσ
n
is input-admissible if and only if the sequence of sets
hPc(sσ
i) :
0≤i≤ni
is monotonously increasing for all clients
c
.
•
σ=sσ
0, sσ
1,...,sσ
n
is output-admissible if and only if the sequences of sets
hDc(sσ
i) : o≤i≤ni
and
hD
dup
c(sσ
i) : o≤i≤ni
are monotonously increas-
ing for all clients
c
.
• The set of input admissible traces is closed under initial segments, suffixes,
stuttering and skipping states, and so is the set of output admissible traces.
6.2.2.2 Axioms of liveness and safety.
We now present the axioms of message complete liveness and safety.4
Definition 76.
We say that a publish/subscribe system satisfies
message complete
liveness
, if
[F∈SY⇒♦F∈S
ack
Y](6.6)
[(F∈S
ack
Y)∧(n /∈PX)⇒(♦(n∈PX∧n∈F)⇒♦n∈DY)] (6.7)
Condition (6.6) guarantees that subscriptions which are not subsequently can-
celled will eventually be acknowledged. Condition (6.7) says that once a subscrip-
tion was acknowledged, matching notifications published thereafter will eventually
be delivered to the subscriber.
Proposition 77.
Conditions (6.6) and (6.7) are absolute liveness predicates in the
sense of definition 66.
Proof.
Let σ=sσ
0, sσ
1,... be an ω-trace such that for some suffix sσ
i, sσ
i+1,... of σ,
condition (6.6) holds. We have to prove that F∈SY⇒(♦F∈Sack
Y)holds for
all sσ
j, sσ
j+1,.... This is clear for j≥i, so let now j < i and suppose that sσ
j, sσ
j+1,...
satisfies F∈SY. Then also sσ
i, sσ
i+1,... satisfies F∈SYand consequently ♦F∈
Sack
Y, which thus is also satisfied by sσ
j, sσ
j+1,.... The proof for condition (6.7) is
similar.
4Strictly spoken, these are axiom schemata, as they are supposed to hold for any clients X, Y , no-
tifications n, and filter F. Also note that we silently use operations on sets and integers in our
formulas. This does not alter expressibility since there are only finitely many states.
100
Definition 78.
We say that a publish/subscribe system satisfies
message complete
safety
, if
D
dup
Y=∅(6.8)
n∈DY⇒n∈[
Y
PY(6.9)
n /∈DY∧en∈DY⇒en∈[
Y
SY(6.10)
Message complete safety means that clients will be only notified about notifica-
tions that were published by someone and are matching some subscription of that
client, and that there are no duplicate notifications.
As a direct consequence of Sistla’s theorem, we have
Proposition 79.
The conditions of definition 78 are safety predicates in the sense
of definition 65. They also satisfy strong safety and
L
-safety.
Now we can define message complete correct publish/subscribe systems.
Definition 80.
We say that a publish/subscribe system is
message complete cor-
rect
, if for all traces
σ
of states of the system that are input-admissible,
σ
is output
admissible and satisfies safety and liveness.
6.3 Implementation
In the last section, we gave an axiomatic description of the desired behaviour of a
message complete publish/subscribe system. This section, being titled
implementa-
tion
, has to start questioning what implementation of a system does actually mean in
this context. Practically, a system is implementable if it can be programmed on some
hardware using some programming language. From a theoretical point of view, the
implementation of some systems are described via
system specification
as opposed
to the
requirement specification
we have given above. There are many techniques
usable for system specification. However, one that is closely related with temporal
logic is based on
fair transition systems
[46, 47]. Fair transition systems have an
intrinsic temporal semantic and therefore can be used to derive requirements (our
axioms of liveness and safety) from the system specification.
Moreover, Manna and Pnueli introduce a
simple command-style programming lan-
guage
(SPL) that, additionally to the standard set of assignment, conditional and
loop statements, provides for semaphores and commands for channel-oriented, first-
in-first-out asynchronous and synchronous message passing. They give a semantic
interpretation of their language by defining an equivalent fair transition system.
101
6.3.1 Specifying module interfaces
The interaction of a system with its environment is described by
module specifica-
tions
. The interface of a module to its environment is defined by the declaration of
in,out, and external variables. Additional, a module can declare local variables.
A module can read and write to local variables. Local variables cannot be seen
by other modules. in variables are read-only for the module, out variables write-
only. Variables declared external can be written to by other modules (if properly
declared there).
The
body
of a module contains its system specification, written in SPL. For details,
we refer to [46, 47].
So one approach of defining an implementation of a correct publish/subscribe
system would be to define a module with the interface specification
module
2external in Sc
for every client
c
out Sack
c
for every client
c
external in Pc
for every client
c
out Dc
for every client
c
[
body
]
This listing reflects that the module watches the externally manipulated variables
Sc, Pcof subscriptions and notifications and computes from this the states of the
subscriptions, that is, Sack
c, and writes out notifications to Dc. Suppose that the
body of the module is such that it can be shown that correctness in the sense of
definition 80 is always satisfied, is this an implementation of a publish/subscribe
system that could be used as a model for a real-life implementation?
We suggest that the answer is no. Indeed, the module specification does not at
all reflect the fact that communication between the clients is asynchronous. If sub-
scriptions, notifications and notifications are performed synchronously, the whole
implementation gets quite trivially – in particular, there is no need for a requirement
specification using temporal logic with its ♦modifier at all, since subscriptions and
notifications can be propagated immediately.
This is why we explicitly model the network topology of our implementation. So
let there be given finite sets of clients c∈ C and notifications n∈ N. For every filter
F⊆ N, let there be a constant symbol F.
Nodes in our communication network are called
brokers
b∈ B. For every client
c, we assume there is a
local broker
bc∈ B that has bidirectional synchronous
communication with c. For a given broker b, let Lbbe the set of b’s
local client
,
that is, the set of clients cfor which bis the local broker. Assume that Bis a finite
set, and that the set of asynchronous communication channels between the brokers
forms an acyclic undirected graph G. Let Nbthe set of
neighbour brokers
of b, that
is, the set of brokers with whom bhas a shared edge in G.
The system specification of our composed module has the form
102
M=[module
// for every client
c
external in subc→
4external in pubc→
out ack→c
out notify→c;
kb∈B Mb
]
where Mbis the module specifying the behaviour of broker b.
We assume that the client state variables of definition 71 behave as given in defi-
nition 72.
To reflect the fact that the brokers communicate per asynchronous messaging, we
specify two asynchronous channels- one for every direction of message passing- for
every edge in G. So for b0∈Nb, let
channel
b→b0be the asynchronous communication
channel from bto b0, and
channel
b0→bthe channel from b0to b. Now we can specify
the interface of the modules Mbfor brokers b∈ B:
Mb=[module
2
// for every local client
c∈Lb
external in subc→b
external in pubc→b
out ackb→c
out notifyb→c
7
// for every neighbour broker
b0∈Nb
external in channelb0→bchannel
external out channelb→b0channel;
[body]]
Note that the interface of the module Mbis split into one part (the intersection
of Mb’s interface with M’s) that is visible from outside of the composed module M,
and another part that is used only by the other submodules Mb0.
Our road map is to specify the bodies of the modules Mbsuch that for the com-
posed module M, the axioms of safety and liveness are modularly valid.
We have not yet defined the types of our variables. We will formally let them have
integer type and informally assume a bijections between the “real” ranges of our
variables (filters for the
sub
variables, etc) and finite subsets of the integers. This
allows us to write in our specification statements like
l0:channelb0→b⇒m;
l1:if m=sub(F)
...
where l1stands for m=ifor some integer i.
Informally, the variables are of the following types:
subc→bof type
set of filters
2ackb→cof type
set of filters
pubc→bof type
notification
103
notifyb→cof type
notification
channelb→b0of type
channel of messages from alphabet
Σb→b0
Let us now define the message alphabets Σb→b0for neighboured brokers band b0.
While for the communication between clients and their local brokers the interface
operations
sub
,
pub
,
unsub
,
ack
,
notify
are used, brokers among themselves use
operations that are hidden from the local clients. The following message types are
used for inter-broker communication between neighboured brokers band b0:
Definition 81.
The message alphabet
Σb→b0
consists of the following messages:
• forward
(n, p)
for notification
n
and client
p
,
• admin
(S,U)
, and
• admin_ack
(S,U)
where
S
and
U
are sets of filters.
Informally,
channel
b→b0⇐
forward
(n, p)means that broker bforwards to neigh-
bour broker b0the notification nthat was published by client p.
channel
b→b0⇐
admin_ack
(S,U)means that broker brequests neighbour broker b0to forward noti-
fications matching some filter in S, but not to forward notifications matching some
filter in U.
channel
b→b0⇐
admin_ack
(S,U)means that broker bconfirms that he is
forwarding notifications matching a filter in Fbut not those matching a filter in U.
6.3.2 State variables
We will now informally introduce the local state of the brokers. Since (as we will
see) the set of possible states is finite, we can add a single local integer variable vto
the module specification, assume a 1-1 mapping between states and some integers,
and thus are allowed to write statements of the form
if (informally described state predicate) then
change state
endif
which can be translated into a statement of the form
if (v=v1∨v=v2∨...∨v=vn)then
2v=v0
endif
Brokers bmaintain
• a private
routing table
Tbcontaining pairs (F, d)where Fis a filter and dis a
destination
, i.e. a local client or a neighbour broker. For a destination dof b,
we write T|d
bfor {F|(F, d)∈Tb}.
• a private
pending acknowledgements table
Pbcontaining an entry for every
admin
message that the broker still needs to acknowledge, and a list of de-
pendent outstanding acknowledgements. Note that for every possible filter
104
set pair (S,U), there is maximally one entry in Pb, and the number of possible
dependencies is finite. Thus, there are only finitely many possibilities for Pb.
•
working copies
of the externally written variables
sub
c→band
pub
c→b, named
sub
work
c→band
pub
work
c→b.
Under the assumption that there are only finitely many filters, it is guaranteed that
there are only finitely many possible states for every broker.
6.3.3 The Framework Algorithms
Now, we give a description of the bodies of the submodules Mb. We will do that in
an informal way, which is justified since there are finitely many modules and every
module can assume only finitely many states. Therefore, we can freely use loops and
iterators, and can write statements like
send message
m
to all neighbour brokers
.
Fig. 6.1 gives the framework of the body of the module Mb. The state transitions
are performed in the subprocedures
processAdminMessage
,
processAdminAckMessage
and
processNotification
. Furthermore,
forward
and
pub
messages are processed by
the
processNotification
procedure,
sub
,
unsub
and
admin
messages are processed
by
processAdminMessage
procedure, and
admin_ack
messages are processed by
processAdminAck
procedure. These procedures we will describe informally. Trans-
lation into the module body is straightforward.
6.3.3.1 The procedure
processNotification
The procedure
processNotification
(d, n)takes a destination dand a notification nas
parameters and does the following:
• It sends a
forward
(n)message to all
channel
b→b0variables with b06=dfor
which there is an entry (F, b0)∈Tbsuch that n∈Fand
• adds nto all
notify
b→cvariables for which there is F∈
sub
c→bmatching n.
6.3.3.2 The procedure
processAdminMessage
This procedure takes a destination and two filter sets Sand Uas parameters. This
procedure is called when
admin
messages from neighbour brokers are received
and when subscriptions and unsubscriptions are issued by local clients: If broker
b1receives
admin
(S,U)from neighbour b2,
processAdminMessage
(b2,S,U)is called
(line 30). If a new subscription Fis issued by a local client c,
administer
(c, {F},∅)
is called (line 10), and respectively
processAdminMessage
(c, ∅,{F})for an unsub-
scription (line 15).
processAdminMessage
calls the
administer
procedure with the
same parameters.
administer
encapsulates the applied routing algorithm and trig-
gers changes in the routing configuration. These changes are performed at b1in
two ways:
105
1. by transforming his own routing table Tb1, and
2. sending out new
admin
messages to some subset of his neighbours except b2.
We say (cf.[55]) that the local transformation algorithm satisfies the
restricted change
condition, if b36=b2implies that (T0
b1)|b3=T|b3
b1, that is, b1does not change his routing
behaviour for destinations different from b2. Furthermore, we say that the algorithm
satisfies the
restricted impact
condition if the result of the transformation depends
only on the value T|b2
b1.
Let us call Sthe
positive part
of the message, and Uthe
negative part
. We require
the following condition: if
administer
(d, S,U)is called at broker bwith S=∅, then
S(T0
b)|d⊆ST|d
b. This condition ensures that only the positive part of an
admin
message can cause ST|d
bto increase.
administer
returns a pair (MS,MU)where
MSand MUassign filter sets MS(b3)and MU(b3)to each neighbour broker b3of
b1. Broker b1sends
admin
(MS(b3),MU(b3)) to b3if one of these sets are nonempty.
In order to acknowledge subscriptions, brokers will reply to
admin
messages with
admin_ack
messages by the following rule:
• If the incoming
admin
message triggers only
admin
messages with empty pos-
itive part, and there are no entries in the pending list, it is immediately replied
by
admin_ack
.
• Otherwise, the
admin
messages that are sent out are added to the pending list
and dependencies are marked. The reply will be sent as soon as bhas received
admin_ack
replies for all marked entries in the pending list.
The case for subscriptions and unsubscriptions of local clients is similar.
There is one point in this algorithm that we have to pay attention to: Suppose
b0sends three
admin
messages to b: the first one subscribes b0to F, the second
one unsubscribes F, and the third one subscribes Fagain. Now bsends out
admin
messages accordingly, and waits for acknowledgements in order to acknowledge to
b0. But how can bdistinguish incoming
admin_ack
messages referring to the first of
b0’s message, from the ones referring to the third? Note that bcan do this distinction,
even if there are only finitely many states. Let us explain how this can be done:
Two nodes, front (
f
) and back (
b
), are bidirectionally connected via asynchronous
communication. Both have the states
up
and
down
, and have to obey to the follow-
ing rules:
• never may
f
be up when
b
is down,
• if
f
is down, eventually
b
will be.
Now
f
receives synchronous signals
go up
and
go down
. Upon receiving
go down
,
f
must do so immediately and signal acknowledgement. Upon receiving
go up
,
f
106
must eventually go up and then signal acknowledgement.
f
can assume only finitely
many states.
How to achieve this?
f
maintains the three Booleans is_hot, last_sent, channel_free.
Upon receiving
go up
or
go down
,
f
sets is_hot accordingly to
true
or
false
. In case
of
go down
,
f
changes state and acknowledges. If channel_free, it forwards the sig-
nal to
b
and sets last_sent accordingly.
b
changes state according to the messages
received from
b
and sends acknowledgement. When
f
receives acknowledgement
for
go up
from
b
, it checks is_hot and if this is true, assumes state
up
and signals ac-
knowledgement. Otherwise, it sends
go down
to
b
. If
f
receives acknowledgement
for
go down
, and is_hot is true, it sends
go up
to
b
. If
f
has sent no message upon
receiving acknowledgement from
b
, it sets channel_free to true.
Now bmaintains the three flags for every pair (S,U)(of the finitely many pairs
that exist), thus guaranteeing that the
admin_ack
it sends to its predecessor b0are
never out of date.
6.3.4 Valid routing algorithms
The routing framework described above depends on the implementation of the
administer
procedures and on the initial states for Tb. [55] give classes of
administer
procedures that (with proper initial values for Tb) lead to systems that satisfy the
safety and liveness axioms defined there. One can prove that these classes do in
fact yield systems which satisfy the stronger axioms given here.
The most trivial example of an implementation of the
administer
procedure is the
one that leads to routing by
flooding
: suppose in initial state, brokers forward ev-
ery notification to all neighbour brokers (except the one that sent it). Suppose the
administer
procedure does nothing, that is, returns (∅,∅)for all inputs. We claim
that then, the system is correct in the sense of definition 80. Indeed, it is obvious
that our system produces admissible output. Furthermore, since never
admin
mes-
sages with nonempty positive part will be triggered, any incoming subscription will
be acknowledge at once. Anyway all brokers see all messages, so the second step of
processNotification
ascertains that subscribed notifications will be duly delivered.
Another example of routing is
simple routing
. Here, the
administer
procedures
work the following way:
administer
(b0,S,U)returns (MS,Mu), where
MS(b00) = S(6.11)
MU(b00) = U(6.12)
for all neighbour brokers b00 6=b0of b. Here,
admin_ack
s will be sent first by the
leaves of the network topology, that is by the brokers that have only one neighbour
broker. A subscription is answered by an acknowledgement similar to the echo
algorithm for message broadcast.
107
Other implementations of
administer
yield more efficient routing algorithms which
avoid flooding notifications or filters into the broker network. Covering-based rout-
ing, for example, assumes that it can be detected whether a filter matches a super-
set of notifications of another filter. The covering test is then used to restrict the
forwarding of new and cancelled subscriptions. This effects also acknowledging of
subscriptions. In Fig. 6.2, client c1had issued subscription Fwhich was already
acknowledged by the system. Then, client c2issues a subscription Gwhich is cov-
ered by F. In this case, b3only forwards Gto broker b1and therefore only waits
for b1to acknowledge G. Hence, after b3received the acknowledgement from b1it
acknowledges Gto b2which finally, acknowledges Gto c2.
6.3.4.1 Correctness proofs by decomposition
We claim that with suitable implementation of
administer
, safety and liveness for-
mulas are modularly valid for the composed module M. To prove such a claim for
formula φ, one has to decompose φinto φbformulas such that for every submodule
Mb, the formula φbis modularly valid for Mband the validity of all φb’s implies that
φis valid. Manna and Pnueli [46, Proposition 4] prove that this is a correct rule for
composing modules, and that such a decomposition does always exist for modularly
valid formulas.
Let φsafety be an instance of one of the three safety conditions from definition 78.
For a submodule b, let φts
bbe the formula that expresses the temporal semantics of
our system specification. It is quite straightforward to see that the conjunction of
the φts
b’s implies φsafety.
The decomposition of liveness properties depends on the implementation of the
administer
procedure. Note that changes in the broker’s routing tables Tbdepend
exclusively on the values that the
administer
procedures return. Mühl gives in [55,
Definition 3.4] a sufficient condition for
administer
procedures that lead to correct
publish/subscribe systems. The decomposition of the liveness properties are based
on Mühl’s condition. We omit the details here.
108
body of Mb
2Tb=∅;
Pb=∅;
subwork
b0→b=∅
pubwork
b0→b=∅
while (true) do
7forall (c∈Lb)do
forall (F∈subc→b\subwork
c→b)do
// new subscription
processAdminMessage
(c, {F},∅);
subwork
c→b=subwork
c→b∪ {F}
12 endforall
forall (F∈subwork
c→b\subc→b)do
// new unsubscription
processAdminMessage
(c, ∅,{F});
subwork
c→b=subwork
c→b\ {F}
17 endforall
forall (n∈pubc→b\pubwork
c→b)do
// new notification
processNotification
(c, n);
pubwork
c→b=pubwork
c→b∪ {n}
22 endforall
forall (b0∈Nb)
channelb0→b⇒m;
// non-blocking
[
// begin of atomic block
if
m is "
forward(n)
" message
then
27
processNotification
(b0, n);
endif
if
m is "
admin(S,U)
" message
then
processAdminMessage
(b0,S,U);
endif
32 i f
m is "
admin_ack(S,U)
" message
then
processAdminAckMessage
(b0,S,U);
endif
]
// end of atomic block
endforall
37 endwhile
endbody
Figure 6.1: Body of module Mb
109
b2
b4
b3
b1
c1
1. sub(c1, F)
c2
Broker
Client
(G, c2)
(G, b2)
(F, b1)
(F, b3)
2. ack(c1, F)
3. sub(c2, G)
(F, c1)
(G, b3)
4. ack(c2, G)
Figure 6.2: Acknowledging a subscription with covering-based routing (Fcovers G).
110
6.4 Pricing in publish/subscribe systems
6.4.1 Publish/Subscribe pricing as special multicast pricing
In recent years, lots of research has been conducted about pricing-mechanisms for
routing e.g. in ad hoc networks and multicast systems. The algorithms presented in
this paper are the first realizing pricing in publish/subscribe systems. We consider
scenarios with more than one publisher and a dynamic change at the publisher
and subscriber groups. When filters that clients subscribe for overlap, the saved
bandwidth is not credited to the clients. We leave this point open for future work.
Thus, for simplicity we assume a set of disjoint filters the clients may choose from.
In this scenario, publish/subscribe can be seen as a special type of multicast group
communication with two types of groups:
sender groups
, which publish notifications
matching certain filters, and
receiver groups
, which are subscribed to selected fil-
ters. Clients have “cheap” communication with their local brokers. In particular,
we assume that there are no costs for communication between a client and his lo-
cal broker. On the other hand, communication between brokers is assumed to be
“expensive”. The costs incurred by inter-broker communication can be modelled
in many ways. The simplest approach is to assume a fixed amount per link that is
charged whenever the link is used as part of the data transmission. This can be gen-
eralized to allow different service levels, or
transmission rates
, with distinct prices
for every level. We will go into this point when talking about extensions to multiple
rates.
The results in this chapter build on pricing mechanism for multicast groups with
one sender and many receivers. Feigenbaum et al. [26] consider marginal cost pric-
ing and Shapley value pricing for mechanisms that compute the optimal receiver
subtree of a multicast stream, and the payments of every receiver. Their results
were extended by Bläser [7, 8] and Adler and Rubinstein [1] who extended the
all-or-nothing
approach of Feigenbaum et al. and considered the possibility that
receivers are served with different service levels, and that there are costs incurred
by “enabling” a node to multicast.
Naturally, in the enterprise one has to consider more costs than just the ones
caused by the technical infrastructure. For instance, the publishers may charge
for the actual contents they transmit to the subscribers. As this paper takes the
computer science perspective on business, we do not consider other costs than the
ones of data transmission. Also, we assume that the complete broker network is
under one administrative domain and payment goes to the network. We do not
provide a mechanism how to split the revenue between the network links. On the
other hand, every client is seen as an independent agent. It can play both, the role
of publisher, and the role of subscriber.
The rest of the paper is structured as follows: Section 6.4.2 introduces the used
notation and basic facts. In Section 6.4.3 we present a pricing algorithm for the case
111
where the structure of the network is stable. We extend this algorithm in Section
6.4.4 to cope with changes in the utility of clients and new (un)advertisements.
Finally, Section 6.4.6 provides an extensions for multiple rates.
6.4.2 Notation and General Facts
A publish/subscribe systems consists of a set of
clients
which are connected by a
network of
brokers
. Every client cis connected to exactly one broker bc, the
local
broker
of c. Let Cbe the set of all clients, and Bbe the set of all brokers. For
a broker b, let Lbbe the set of local clients of b. The network is assumed to be
undirected and acyclic such that for any two nodes, there is a unique path between
them. Communication between clients and their local brokers, and inter-broker
communication is based on messages. We assume that message transmission is
reliable first-in-first-out.
For communication with the broker network, clients use outbound messages of
the types
publish, subscribe, unsubscribe, advertise
and
unadvertise
and inbound
notify
messages. For receiving messages, the client is interested in, she formulates
her interest as a filter which she sends in form of a
subscribe
message to its local
broker. In our model, a
filter
is some predicate on an attribute of a notification. The
filters diffuse through the broker network after a client subscription has been issued
based on the routing algorithm. They are used to build up the routing table at each
broker. A filter assigns Boolean true to a notification if this notifications
matches
the
filter (i.e. if the predicate of the filter is true for all considered attributes), or false
otherwise.
Notifications
are published by clients. A client announces her intention
of publishing notifications matching a filter Fby sending an
advertise
message, and
revokes this announcement with an
unadvertise
message. If a client csubscribes
to a filter F, then (after possibly some delay, as formalized by Mühl and Tanner
[55, 77]), all notifications that match F, no matter who published them, must be
delivered to cvia
notify
messages, until the client unsubscribes to this filter.
Let us now fix some filter F. Let P(F)denote the set of clients that have ad-
vertised for F. We consider the set S(F)of clients that are subscribed to Fas a
user group that jointly uses, and shares the costs of, the tree spanned by P(F). We
assume that for any link between two brokers, there is a fixed cost of using this link.
Rather than unconditionally subscribing to a filter, our clients send
valuations
for a subscription to some filter F. Client c’s valuation for a subscription to Fis
expressed via its
utility
, a nonnegative real.5
Costs, utility and advertisements are defined via
profiles
for a fixed broker topol-
ogy Tand a fixed filter F. A profile for Tis a triple P= (ξ, u, pub), where
•ξis a function that assigns to every inter-broker link la nonnegative real ξ(l),
the
cost
of l,
5We assume a quasilinear setting.
112
5
2
3
4
23
1
2
1 1
1 0P
10
2
2
1
5P
2
5 5
Figure 6.3: Example publish/subscribe network
•uis a function that assigns to every client ca nonnegative real u(c), the
utility
of cfrom a subscription for F,
•pub is a function that assigns to every client ca Boolean pub(c), true exactly if
chas advertised for F.
For a given profile P= (ξ, u, pub), and a client c, define P|u(c)=0 be the profile that
results from Pby changing client c’s utility to 0.
Every client chas free connection to its
local broker
bc. For a set of brokers B, let
T(B)be the minimal spanning tree connecting all brokers in B6, and ξ(B)be cost
of that tree, that is,
ξ(B) = X
l∈T(B)
ξ(l)(6.13)
For a set of clients C, define T(C) = T({bc:c∈C})the spanning tree connecting
all local brokers of clients in C.
Now assume that there is a special
master broker
bmaster. We view the broker
network as a tree rooted at bmaster. Let ch(b)be the children of band let par(b)
be the parent of bin this tree. Let Suc(b)be the
successor tree
of b, that is, the
transitive closure of {b}under the ch operation.
6Note that since the topology is acyclic, this is well-defined.
113
Figure 6.3 shows a possible network. Brokers are represented as circles, clients
as rounded boxes. The cost of an inter-broker link is printed next to the link. Inside
the boxes representing the clients, their utility (for a subscription for a fixed filter)
is printed, followed by a “P” if the client has advertised for this filter. The minimal
tree connecting all brokers with publishers as local clients is marked by a fat line.
The broker presented by the shaded circle functions as master broker.
An
admissible multicast receiver tree
for Tis a connected subtree of Tthat con-
tains T({c:pub(c) = true}).
A
mechanism
Mfor Tis a function that takes a profile Pas argument, and delivers
a pair (σP, πP)where σPassigns a Boolean7σP(c)to every client csuch that T(σP) =
{bc:σP(c) = true}is an admissible multicast receiver tree, and πPassigns a real
πP(c), the
payment
of c, to every client c.8
A mechanism Msatisfies the
no positive transfer
condition, if π(c)≥0for all
clients cand all profiles. Msatisfies
voluntary participation
, if always π(c)≤
σ(c)u(c).Mis
budget-balanced
, if always ξ(T(σ)) ≤Pcπ(c).Mis
strategyproof
if for all P, for all clients c, and for all x
σP(c)u(c)−πP(c)≥σPx(c)u(c)−πPx(c)(6.14)
where Px=P|u(c)=xis the profile used as input by Mif cpretends to have utility x.
The
social surplus
generated by σfor the profile P= (u, ξ, pub)is
Surplus(σ, P) = X
c
σ(c)u(c)−ξ(T(σ)) (6.15)
Note that the social surplus has nothing to do with the payment function πof the
mechanism.
Mis a
marginal cost mechanism
(
MC
)[54] if σmaximizes the social surplus, and
the payment function πis
π(c) = u(c)−Surplus(σ, P)−Surplus(σ, P|u(c)=0).(6.16)
It is well-known that this mechanism belongs to the family of Vickrey-Groves-
Clarke mechanism and thus is strategyproof. On the other hand, it can easily be
seen that it is in general not budget-balanced: if there are at least two local clients
connected to every broker and the receiver tree does not change when any one local
client changes its utility to zero, then no client will pay anything for transmission.
6.4.3 Marginal Cost Mechanism for Publish/Subscribe Setting:
The Static Case
Assume that there is a master broker bmaster among whose local clients include at
least one publisher for F.
7Sometimes we will silently cast the Boolean to zero or one by the obvious mapping.
8We omit the superscriptPif there is no ambiguity.
114
Then the algorithm presented in Figures 6.5 and 6.6 shows the marginal cost
algorithm for filter F. Note first that the algorithm is a generalization of the one
from Theorem 3.1 of [26]: if there is only one publisher, then this publisher plays
the role of bmaster and is the root of the tree, and the flags fαare not set for all
brokers different from bmaster. It is easy to see that in this case, the algorithm is
exactly the one presented by Feigenbaum et al.
Theorem 82.
1. The algorithm shown in Figures 6.5 and 6.6 computes a subtree
of the broker network that maximizes the social surplus, that is, the sum of the
utilities minus costs, and that is maximal among all trees with this property.
2. The payments computed in the algorithm are the ones defined by the marginal
cost mechanism.
Proof.
1. We prove this by induction on the number of nodes in the tree of all
brokers. The claim is trivial if there is only one node. So suppose the claim is
proven for trees with less than nnodes. Let Tbe the computed subtree of a
broker tree with less than nnodes, and T∗be an optimal subtree. We have to
prove that Surplus(T)≥Surplus(T∗), and that T∗⊆T.
Case
T
is empty, but
T∗
is not.
Since Tis empty, we have Pbβ∈ch(bmaster)Wβ<0.
Now for every bβ, the induction hypothesis implies that Wβ≥Surplus(T∗∩
Suc(bβ)). But then, Pβ∈ch(bmaster)Wβ≥Surplus(T∗)and consequently, Twouldn’t
be empty, a contradiction.
T
is nonempty.
This is similar: By induction hypothesis, for every child bβof
bmaster, the computed subtree must be optimal. Therefore, the total surplus
of Tmust be maximal. The maximality of the tree follows from the fact that
subtrees with zero utility are included in T.
2. Now we have to prove that the computed payments are the ones from the MC
mechanism. Let bαbe some broker in T, and let Abe the message bαsends
to its children in Figure 6.6. Then the social surplus of Tis decreased by Aif
we cut from Tthe subtree rooted at bα. Now let cbe some local client of bα.
If u(c)≤A, then A−u(c)≥0and bαwould still be in the tree if cwouldn’t
participate. Thus cpays nothing in the MC mechanism, and neither does it in
our algorithm. Similarly, if u(c)> A, then bαwould be cut from the tree (or no
multicast would take place at all, if there was a publisher behind bα), and the
marginal costs caused by care exactly u(c)−A.
Note that the algorithm requires that the master broker has a publishing client:
otherwise, the computed multicast tree may be not optimal. To see this, assume a
broker topology as shown in Figure 6.4.3. Here, the optimal tree would contain only
b2and b3. The algorithm fails to cut b1, since the master broker is always served if
115
2 5
b1b2b3
pub
u(c1) = 1 u(c2) = 6 u(c3) = 4
Figure 6.4: Master broker without publishing clients
the receiver tree is nonempty. On the other hand, it is easy to see that if
all
subtrees
rooted at the master broker’s children contain publishing clients, the computed tree
is correct even if the master broker itself doesn’t have publishing local clients.
Note also that there are no additional costs for the multi-publisher setting com-
pared to the multicast scenario of Feigenbaum et al.
Corollary 83.
Receiver tree and payments of the marginal cost mechanism can be
computed with no more than two messages per link.
6.4.4 Dynamic Aspects: Changing Utilities and Publishers in the
Tree
We are interested in the re-computation of the multicast tree after clients change
utility, or advertise or unadvertise a filter. Let us first assume that the change does
not concern the property of the master broker being a publisher for the filter. It is
easy to see that in the worst case, utility changes or advertisements and unadver-
tisements have to be propagated through the complete tree. There is, however, an
obvious restricted-impact property of the tree:
Fact 84.
Let
T
be a publish/subscribe network and let
P= (ξ, u, pub)
and
P0=
(ξ0, u0, pub0)
be two cost-utility-publisher profiles for
T
. Suppose that
b
master is a
broker with
pub(b
master
) = pub0(b
master
) =
true. Let
bα
be a broker such that
T({c:
pub(c) = true})∩Suc(bα) = T({c:pub0(c) = true})∩Suc(bα)
. Further suppose that
the
D
sent to the children of
bα
is the same for both profiles. Then receiver tree and
payments, restricted to
Suc(bα)
, are the same for both profiles.
If all publishing local clients of the master broker unadvertise and there is a sub-
tree rooted at one of its children that contains no publishers, a new master has to be
found. The algorithm in Figure 6.7 gives a distributed, self-stabilizing computation
of the marginal cost tree and payments.
116
At all brokers bα
After bαhas received message Aβ= (Wβ, fβ)from all
children β∈ch(bα)
/∗
The utility of
bα
is the sum of the utility of the
∗/
/∗
children
∗/
l1:uα⇐Pc∈Lbαu(c)
l2:Wα⇐uα+Pβ∈ch(bα),fβ=1 or Wβ>0Wβ−cα
/∗
Add the node to the receiver set if it has a
∗/
/∗
publishing local client or if one of the
∗/
/∗
descendants has one
∗/
fα⇐Wc∈Lbα{cis publisher for F}∨Wβ∈ch(bα)fβ
/∗
Send an upward message with the computed
∗/
/∗
values for
Wα
and
fα
to the parent-node
∗/
U= (Wα, fα)
send Uto par(bα)
Figure 6.5: The MC algorithm: Computing the receiver set
Every broker bαmaintains the following state information:
• a variable par(bα)that contains the current parent node of bαwhich is null if
bαis master (any neighbour broker different from par(bα)is a child),
• for every child bβ, the values of Wβand fβlast sent by them,
• the own values of σα, W αand fα.
A
system state
Sconsists of the collection of the current profile, the states of all
brokers, and the set of messages currently on the network. Let us call a system
state S
correct
, if
• there is exactly one master broker bmaster whose parent variable par(bmaster)
has value null,
• the network, together with the par relation, forms a tree rooted at bmaster,
• the set of brokers bαwith σα= 1 is a maximal surplus-maximizing subtree of
T, and
• the prices computed based on Wαare the prices defined by the MC mecha-
nism.
During initialization, an election is performed to choose a master broker. This can
be done by an election procedure. Mattern [49] gives (Theorem 2.7 on page 71) an
117
Initialize
/∗
Send
D
downward the tree with
∗/
/∗Dmaster =Wmaster ∗/
send Dto all children
At all brokers bα
After bαhas received message Dfrom par(α)
If (fα== false)
/∗bα
is not already in the receiver set
∗/
l3:D⇐min(D, W α)
Endif
If (D < 0)
/∗
The local clients are not part of the
∗/
/∗
receiver tree
∗/
send σ= 0 to all local clients
Else
For every local client c
/∗
Calculate the price for every local client
∗/
l4:If (u(c)> D)
π(c) = u(c)−D
Else
π(c) = 0
Endif
send σ= 1 and π(c)to c
Endif
For every child bβ∈ch(bα)
send Dto bβ
Figure 6.6: The MC algorithm: Propagating receiver set and payment
118
Initialize
Election of new master broker and computation of
initial tree
At every broker bαdo forever
/∗
Has some requirement changed for the
∗/
/∗
master-broker?
∗/
If (par(bα) == null /∗bα
is master
∗/
/∗
and
bα
has no publishing local client
∗/
and {c∈Lbα|pub(c) = true}== ∅
/∗
and there is a subtree rooted in a the master’s
∗/
/∗
broker that has no publishing client
∗/
and there is bβ∈ch(bα)such that fβ== false)
/∗
Then: Find another master
∗/
If (∃bβ∈ch(bα)with fβ== true)
/∗
Choose a child which itself or its subtree has
∗/
/∗
a publishing local client
∗/
l1:par(bα)⇐bβ
send U= (Wα, fα)to bβ
Else
/∗
There is no publisher in the tree anymore
∗/
go to Initialize
Endif
Endif
/∗
Has an update message arrived from the child?
∗/
If (receiving U= (Wβ, fβ)from child bβ∈ch(bα))
/∗
A state change is reported from a child
∗/
recompute fαand Wα
If (par(bα) == null)
/∗
The change-information has reached the root
∗/
send D= (Wα, fα)to children
Elseif (fαor Wαchanged)
send U= (Wα, fα)to parent
Endif
Endif
/∗
Has an update message arrived from the parent?
∗/
If (receiving U= (Wpar, fpar)from parent par(bα))
/∗
A new master is wanted
∗/
If (bαhas publishing local client)
/∗bα
becomes master
∗/
l2:par(bα)⇐null
Wα⇐Wα+Wpar
send D= (Wα, fα)to children
Else
/∗
look for another master
∗/
If (∃bβ∈ch(bα)with fβ== true)
l3:par(bα)⇐bβ
send U= (Wα, fα)to bβ
Else
/∗
There is no publisher in the tree anymore
∗/
go to Initialize
Endif
Endif
Endif
Figure 6.7: Self-stabilizing computation of MC
119
election algorithm for tree topologies that requires no more than three messages per
link. For our purpose, we assume that brokers have a unique, positive ID. Brokers
without publishing local clients participate in the election with a zero ID so that it
is guaranteed that they won’t be elected.
Thereafter, a node changes his parent node in two cases: either the node serves
as master but ceases to be eligible, or a node receives a message Afrom his parent.
We claim that the algorithm has the following property of self-stabilization:
Fact 85.
1. For any publish/subscribe network
T
and any profile
(ξ, u, pub)
, the
algorithm lets converge the system state to a state which is correct in the
sense defined above,
2. After initialization is completed and after a change of the profile, the system
state converges again to a correct state.
Proof.
Theorem 82 implies the first claim. Now suppose that the system is in a
correct state S, and the profile changes. Let us call a broker bαa
de-facto-master
if
for any neighbour bβof bα, we have par(bβ) = bα. Then in state S, the master broker
is also de-facto master, and is the only one. Now we claim that there is always
exactly one de-facto-master. To see this, note that only at l1, l2and l3, the de-facto
master can change. At l1and l3, the de-facto master just moves to some neighbour.
So let us look at l2. We have to prove that when l2is executed, bαis the unique
de-facto master. Now before the execution of l2, there is a unique de-facto master.
Since bparent sent message Uto bα, the de-facto master must be at or behind bα(seen
from bparent). Since par(bα) == bpar before execution of l2, the de-facto master must
be
at
bα. Thus, setting par(bα)to null preserves correctness of the state.
6.4.5 Shapley Value Mechanism
There are two issues about the MC mechanism:
• it is not budget-balanced, and
• although MC is strategyproof, it is not
group-strategyproof
, which means that
a group of colluding participants may manipulate pricing to its advantage.
It is well-known [53, 54] for sharing multicast costs with only one sender, that MC
is the only strategyproof and efficient mechanism satisfying
consumer sovereignty
(
CS
),
no positive transfers
9(
NPT
) and
voluntary participation
10 (
VP
). Groupwise
strategyproof mechanisms satisfying budget-balance and CS, NPT and VP can be
characterized as being induced by
cross-monotonic price functions
. Among all
9Users will not be paid for receiving a message.
10Every user can choose between receiving a message at a cost lower than the utility and not receiving
which results in a benefit of 0.
120
these, the
Shapley value
(
SH
) mechanism is the one that minimizes worst-case wel-
fare loss.
Definition 86.
A
price function
for client
c
is a function
πc:B7→ πc(C)∈R+
for sets of clients
C
. The price function
πc
is
cross-monotonic
if
C⊆C0
implies
πc(C)≥πc(C0)
. Let
F={πc:c∈ C}
be a family of cross-monotonic price functions.
The
mechanism induced by F
computes11 the receiver set as
C= lim
n→∞Cn(6.17)
where
C0=C
;
Cn+1 ={c∈ C :uc≥πc(Cn)}.(6.18)
The
Shapley value
mechanism is the mechanism induced by the family of price func-
tions
{πc:c∈ C}
defined as
πc(C) = X
C0⊆C\{c}|C0|!(|C|−|C0|−1)!
|C|!·
ξ(T(C0∪{c})) −ξ(T(C0))(6.19)
Note that for a fixed filter F,
c∈P(F)∧C6=∅ ⇒ ξ(T(C∪{c})) = ξ(T(C)) (6.20)
and thus the cost of the tree spanned by the publishers is shared between all sub-
scribers of F. The costs of the remaining links are shared by all subscribers that are
behind it (seen from T(P(F))).
Feigenbaum et al. [26] have shown that for a certain class of mechanisms, com-
puting SH requires Θ(np)messages total and at least pmessages over some links,
with pclients and nlinks in the network. This is essentially the complexity of the
brute-force mechanism which computes, for each n, the pc(Sn)in a separate round.
They conjecture that this is a lower bound in fact for all computations of SH.
6.4.6 Extension to Multiple Rates
Adler and Rubenstein [1] and Bläser [7, 8] generalize from the all-or-nothing sce-
nario considered so far and allow the multicast transmission to take place using
different service levels, or transmission rates. They distinguish between two tech-
niques for providing the transmission rates: the first one uses
layers
built on top of
each other. The more layers a transmission uses, the higher rate can be realized. If
a transmission uses a certain layer, then it uses also all layers beneath. This implies
that two transmissions sharing a link lshare the costs of lfor all layers that both
11Cross-monotonicity implies that the following is well-defined.
121
of them jointly use, that is, the receiver of the transmission with the higher rate
participates in the costs for the lower layers caused by the transmission with the
lower rate.
On the contrary, the second technique, called
split paradigm
, defines a new group
for every rate. With this technique, transmissions with different rates do not share
any resources, even if there is a link used by both of them.
Adler and Rubenstein present their
Max-Layered-Welfare
algorithm that com-
putes, for both layered and split paradigms, the optimal transmission tree. Their
algorithm communicates a total number of bits of order O(`hK), where `is the
number of available layers, his the height of the network tree and Kis the maximal
number of bits needed to code a bid. The additional factor hrequired by Adler and
Rubenstein’s algorithm is needed because they, in addition to introducing transmis-
sion with multiple rates, also introduce costs for
enabling
a node to transmitting an
incoming stream to various receivers. Our algorithms 6.5 and 6.6, without support-
ing layers, require only O(K)bits. We claim that we can modify our algorithm to
compute the transmission tree allowing different rates, using O(`K)bits.
So let clients submit, instead of a utility u(c), a utility vector ~u(c)where ~u(c)jis,
for 1≤j≤`,c’s utility from a subscription to filter Fserved on level j. Now in
Figure 6.5, replace uαby a vector ~uαand interpret the sum on the right-hand side
of l1as vector sum of the ~u(c). In l2, replace the computation of Wαby
~
Wα
j= max
~
Wα
j−1, ~uα
j+X
β∈ch(bα)
~
Wβ
j−~cα
j
(6.21)
In Figure 6.6, a broker bαreceives the multicast if the Dshe sends to his children
is nonnegative. We replace Dby ~
D. Broker bαreceives the broadcast on the level jα
that is the largest among those levels lthat maximize ~
Dj. The min function at line
l3is to be understood component-wise.
To compute the payment for client cα, let jαbe the maximum layer cαis receiving.
Write the utility vectors ~u(c)as ~udiff(c) = (u1, u2−u1,...,u`−u`−1)and compute the
payments separately for every layer jwith 1≤j≤jα, as done in Figure 6.6. Add up
all these payments. It is quite clear that this is the marginal cost payment for client
cα.
6.4.7 Summary and Outlook
We have demonstrated how to apply marginal cost mechanism to a (specialized)
publish/subscribe setting. Algorithms that were known for multicasts with a single
source where generalized to a setting with many message sources. A self-stabilizing
version of the algorithm was given.
It was shown by Feigenbaum et al. [26] that computing the Shapley value tree is
expensive even for multicasts with a single source. It would be nice to know whether
122
admitting multiple sources makes it even harder.
The publish/subscribe setting we considered in this paper is restricted in the
sense that we treat subscriptions separately for every filter F. In the case of over-
lapping filters, the costs for a new subscription may be lower if there are already
subscriptions for filters that overlap with the new one. In the current setting, these
saved costs are silently swallowed by the network provider. It would be interesting
to adopt our mechanisms to cope with overlapping filters.
123
7 Conclusion and outlook
Game theory is an efficient tool to use when it is necessary to coordinate behaviour
of self-interested actors. It finds meaningful applications in network management
for autonomous clients. Often the theory will predict that there is an unavoidable
loss of efficiency due to the egoistic behaviour of the clients, compared with a net-
work where it can be assumed that (surplus-maximizing) rules will be followed.
The aim of this thesis was application, and therefore, the establishment of negative
results was not in our focus. Rather, we concentrated on the adoption of known
mechanisms to application scenarios in resource management. In the introduction,
we stated the thesis that there are four points that make out a good protocol: ex-
istence of dominant strategies or equilibria, efficiency at the equilibria, robustness
against groupwise strategizing and manageable computational complexity.
We have developed mechanisms of two kinds:
• In chapter 3, we presented pricing schemes and clearing rules for a combina-
torial exchange. Continuing the line of research of [58], our pricing scheme
resulted from a modification of VGC pricing. Unfortunately, but similarly to
the modifications of Parkes et al., the most prominent feature of VGC pric-
ing – truthfulness being a dominant strategy – was lost with that modification.
However, a couple of other useful features were preserved, in particular, our
pricing rule guarantees that there is never a loss from the acceptance of com-
binatorial bids. This is a new feature compared to Parkes’ modifications. On
a broader context, it is an example of a property that – while not directly
contributing to global efficiency – is a highly desirable property from the per-
spective of
some
market participants – in our case, the sellers – which by
some reasons have to be honoured because otherwise, they could move to an-
other market that is more profitable for them. Our pricing scheme increases
efficiency in comparison to non-combinatorial markets, and it makes combina-
torial bids feasible by respecting the seller’s interests.
Also, it was shown that shill bidding always involves a risk of loosing trade.
This is one of the few result “against” the possibility of groupwise strategizing.
The combinatorial exchange setting is the most general exchange setting: ar-
bitrary
interdependencies
like preferred
bundles
can be stated by the users.
It is therefore not too surprising that an efficient and budget-balanced mecha-
nism does not exist in that setting.
124
• The publish/subscribe setting from chapter 6 proves that the situation is much
more hopeful if there is a narrower specification of the interdependencies that
may occur. In this setting, the
bundles
of goods that users may be interested
in are defined by the
filters
. Additionally, there is interdependency generated
by cost “savings” by multicast users due to them sharing links. It turns out
that in this setting, marginal cost pricing can be applied if budget-balance
is not required, and if it is, Shapley value pricing defines a budget-balanced
mechanisms that minimizes welfare loss. In this context, the questions of the
dominant strategy mechanisms as well as their efficiency therefore is settled.
While Shapley value mechanisms are even groupwise strategyproof, marginal
cost mechanisms are not. We do not know whether there are groupwise strat-
egyproof (of course,
not
budget balanced) mechanisms that are more efficient
than Shapley value.
We also showed that marginal cost prices can be computed with no more than
two messages per link (see corollary 83), and we presented a self-stabilizing
algorithm that efficiently computes marginal cost prices in dynamic networks
(see fact 85).
The issue of strategyproofness has seen a great deal of treatment in the literature
and also in this thesis. Much less has been said on the possibility of strategic
groupwise
behaviour. Neither Vickrey pricing, nor marginal cost pricing are ro-
bust against groupwise speculation. The negative results on the existence of strate-
gyproof mechanisms immediately show that the situation is hopeless if even group-
wise strategizing has to be taken into account. Therefore, the theory is unable to
deliver “safe” mechanism. On the other hand, groupwise strategizing requires coor-
dination between the participants, and will often fail due to lack of communication
and mutual trust. Participants of a groupwise speculation need a mechanism that
splits the benefits they gained between them, and thus encounter the same difficul-
ties as the system they speculate against. It seems that there is a need for
empiric
research on how a mechanism performs if groupwise strategizing is possible. This,
however, has completely been left out from this thesis.
While the general theory of mechanism design offers a couple of negative results
as well as a quite limited repertoire of standard mechanisms, the design of a mecha-
nism for a real-world application requires analysis of the interplay between resource
usage, user’s utility optimalization and their limited opportunities of coordination in
the situation of the specific application scenario.
125
Bibliography
[1] Micah Adler and Dan Rubenstein. Pricing multicasting in more practical net-
work models. In
Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algor. (SODA)
,
pages 981–990. ACM-SIAM, 2002.
[2] B. Alpern, A.J. Deemers, and F. Schneider. Safety without stuttering.
Informa-
tion Processing Letters
, 23(4):177–180, 1986.
[3] B. Alpern and F.B. Schneider. Defining liveness.
Information Processing Let-
ters
, 21(4):181–185, 1985.
[4] B. Alpern and F.B. Schneider. Recognizing safety and liveness.
Distributed
Computing
, 2(3):117–126, 1987.
[5] A. Archer and E. Tardos. Frugal path mechanisms. In
Proc. 13th Symp. on
Discrete Alg
, pages 991–999. ACM/SIAM, 2002.
[6] Aristotle.
Nicomachean Ethics
. Harvard University Press, 1982. ed. by H.
Rackham.
[7] Markus Bläser. Budget balanced mechanisms for the multicast pricing problem
with rates. In
Proc. 4th ACM Conf. on Electronic Commerce
, pages 194–195,
2002.
[8] Markus Bläser. Budget balanced mechanisms for the multicast pricing prob-
lem with rates. Technical report SIIM-TR-A-03-02, Institut für Informatik und
Mathematik, Universität Lübeck, 2003.
[9] A. Bonaccorsi, B. Codenotti, N. Dimitri, M. Leoncini, G. Resta, and P. Santi.
Realistic combinatorial auctions. In
Proc. IEEE Conference on Electronic Com-
merce (CEC)
, pages 331–338, Newport Beach, CA, June 2003.
[10] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin. Resource reserva-
tion protocol (rsvp) – version 1 functional specification. RFC 2205 (Proposed
Standard), September 1997.
[11] J. I. Bulow and P. D. Klemperer. Auctions vs. negotiations.
American Economic
Review
, 86:180–194, 1996.
126
[12] Lars-Olof Burchard.
Advance Reservations of Bandwidth in Computer Net-
works
. PhD thesis, Technische Universität Berlin, 2004.
[13] M. Burchardt.
Mikrotheorie. Kritische Einführung mit einem Kompendium
mikrotheoretischer Fachbegriffe
. Bund Verlag, Köln, 1986.
[14] Antonio Carzaniga, David S. Rosenblum, and Alexander L. Wolf. Design and
evaluation of a wide-area event notification service.
ACM Transactions on Com-
puter Systems
, 19(3):332–383, 2001.
[15] Simon Courtenage. Specifying and detecting composite events in content-
based publish/subscribe system. In
22nd International Conference on Dis-
tributed Computing Systems Workshops (ICDCSW ’02)
, 2002.
[16] G. Cugola, E. Di Nitto, and A. Fuggetta. The JEDI event-based infrastructure
and its application to the development of the OPSS WFMS.
IEEE Transactions
on Software Engineering
, 27(9):827–850, 2001.
[17] R.M. Cyert and J.G. March.
A behavioral theory of the firm
. Englewood Cliffs,
1963.
[18] A. K. Datta, M. Gradinariu, M. Raynal, and G. Simon. Anonymous publish/sub-
scribe in p2p networks. In
International Parallel and Distributed Processing
Symposium (IPDPS’03)
, 2003.
[19] Deutsche Börse Group.
Xetra Stock Market Model
, 2001. http://www.xetra.de.
[20] Deutsche Börse Group.
Xetra Warrant Market Model
, 2001.
http://www.xetra.de.
[21] S. DeVries and R. Vohra. Combinatorial auctions: A survey.
INFORMS Journal
on Computing
, 15, 2003.
[22] P.Th. Eugster, P. Felber, R. Guerraoui, and A.-M. Kermarrec. The many faces of
publish/subscribe.
ACM Computing Surveys
, 35(2):114–131, June 2003.
[23] J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker. A BGP-based mech-
anism for lowest-cost routing. In
Proceedings of the 2002 ACM Symposium on
Principles of Distributed Computing.
, 2002.
[24] J. Feigenbaum and S. Shenker. Distributed algorithmic mechanism design: Re-
cent results and future directions. In
6th International Workshop on Discrete
Algorithms and Methods for Mobile Computing and Communications
, 2002.
[25] Joan Feigenbaum, Arvind Krishnamurthy, and Rahul Sami. Approximation and
collusion in multicast cost sharing.
Games and Economic Behavior
, 47:36–71,
2004.
127
[26] Joan Feigenbaum, Christos H. Papadimitriou, and Scott Shenker. Sharing the
cost of multicast transmissions.
Journal of Computer and System Sciences
,
63(1):21–41, 2001.
[27] Ludger Fiege, Gero Mühl, and Felix C. Gärtner. A modular approach to build
structured event-based systems. In
Proceedings of the 2002 ACM Symposium
on Applied Computing (SAC’02)
, pages 385–392, Madrid, Spain, 2002. ACM
Press.
[28] A. Galton, editor.
Temporal Logics and Their Applications
. Academic Press,
1987.
[29] R. J. Gibbens and F. P. Kelly. Resource pricing and the evolution of congestion
control.
Automatica
, 35:1969–1985, 1999.
[30] J.R. Green and J.-J. Laffont.
Incentives in Public Decision Making
. North Hol-
land, 1979.
[31] Albert G. Greenberg, R. Srikant, and Ward Whitt. Resource sharing for book-
ahead and instantaneous-request calls.
IEEE/ACM Transactions on Network-
ing
, 7(1):10–22, 1999.
[32] John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What
is an edge worth? available at www.cs.ucsb.edu/ suri/psdir/vickrey.ps.
[33] John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What
is an edge worth? In
IEEE Symposium on Foundations of Computer Science
,
pages 252–259, 2001.
[34] John Hershberger and Subhash Suri. Erratum to “Vickrey pricing and short-
est paths: What is an edge worth?”. In
IEEE Symposium on Foundations of
Computer Science
, page 809, 2002.
[35] John E. Hershberger, Subhash Suri, and Amit M. Bhosle. On the difficulty
of some shortest path problems. In
Proc. 20th Symp. Theoretical Aspects of
Computer Science (STACS 2003)
, pages 343–354. Springer, 2003.
[36] John Paul II. Centesimus annus. Encyclical, 1991. English version at http:
//www.vatican.va/edocs/ENG0214/_INDEX.HTM.
[37] R. Johari, S. Mannor, and J. N. Tsitsiklis. Efficiency loss in a network resource
allocation game: the case of elastic supply. Technical Report 2605, MIT Labo-
ratory for Information and Decision Systems, 2004.
[38] R. Johari and J.N. Tsitsiklis. Efficiency loss in a network resource allocation
game.
Mathematics of Operations Research
, 2005. to appear.
128
[39] S. Kameshwaran and Y. Narahari. A new approach to the design of electronic
exchanges. In
EC-Web 2002
, pages 27–36. LNCS 2455, 2002.
[40] F. Kelly. Charging and rate control for elastic traffic.
European Transactions
on Telecommunications
, 8:33–37, 1997.
[41] F. Kelly. Fairness and stability of end-to-end congestion control.
European
Journal of Control
, 9:159–176, 2003.
[42] F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks:
shadow prices, proportional fairness and stability.
Journal of the Operational
Research Society
, 49, 1998.
[43] Paul Klemperer.
Auctions: Theory and Practice
. Princeton University Press,
2004.
[44] Pierre-Simon Laplace.
Essai philosophique sur les probabilités
. Courcier, Paris,
1814.
[45] D. W. Low. Optimal dynamic pricing policies for an m/m/s queue.
Operations
Research
, 22, 1974.
[46] Z. Manna and A. Pnueli.
The Temporal Logic of Reactive and Concurrent Sys-
tems: Specification
. Springer Verlag, 1992.
[47] Zohar Manna and Amir Pnueli. Temporal specification and verification of reac-
tive modules. Technical report, Weizmann Institute of Science, March 1992.
[48] A. Mas-Colell, W. Whinston, and J. Green.
Microeconomic theory
. Oxford uni-
versity press, 1995.
[49] Friedemann Mattern.
Verteilte Basisalgorithmen
. Springer, 1989.
[50] Paul Milgrom.
Putting Auction Theory to Work
. Cambridge University Press,
2004.
[51] Bruce L. Miller. Queueing reward system with several customer classes.
Man-
agement Science
, 16:234–245, 1969.
[52] Bruce L. Miller and A. G. Buckman. Cost allocation and opportunity costs.
Management Science
, 33(5):626–639, 1987.
[53] H. Moulin. Incremental cost sharing: characterization by strategyproofness.
Social Choice and Wellfare
, 16:279–320, 1999.
[54] H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: budget
balance versus efficiency.
Economic Theory
, 18:511–533, 2001.
129
[55] Gero Mühl.
Large-Scale Content-Based Publish/Subscribe Systems
. PhD the-
sis, Darmstadt University of Technology, September 2002.
[56] Robert B. Myerson and Mark A. Satterthwaite. Efficient mechanisms for bilat-
eral trading.
Journal of Economic Theory
, 28:265–281, 1983.
[57] Noam Nisan and Amir Ronen. Algorithmic mechanism design. In
Proceedings
of 31st Symposium on Theory of Computing
, pages 129–140. ACM, 1999.
[58] David C. Parkes, Jayant Kalagnanam, and Marta Eso. Achieving budget-balance
with vickrey-based payment schemes in exchanges. Technical report, IBM Re-
search Report, MAR 2002.
[59] A. Pnueli. The temporal logic of programs. In
Proceedings of the 18th IEEE
Symposium on the Foundations of Computer Science
, 1977.
[60] Thomas G. Robertazzi.
Computer Networks and Systems
. Springer, 2nd edi-
tion, 1994.
[61] Kevin Roberts. The characterization of implementable choice rules. In Jean-
Jacques Laffont, editor,
Aggregation and Revelation of Preferences
, pages 321–
348. North-Holland, 1979.
[62] Michael H. Rothkopf, Alexander Pekec, and Ronald M. Harstad. Computation-
ally managable combinatorial auctions.
Management Science
, 44:1131–1147,
1998.
[63] T. Roughgarden and E. Tardos. How bad is selfish routing?
Journal of the ACM
,
49(2):236–259, 2002.
[64] Y Sakurai, M. Yokoo, and S. Matsubara. A limitation of the generalized vickrey
auction in electronic commerce. In
Proc. AAAI-99
, pages 86–92, Orlando, FL,
1999.
[65] Paul A. Samuelson.
Economics
. McGraw-Hill, New York, 9th edition, 1973.
[66] T. Sandholm, S. Suri, A. Gilpin, and D. Levine. Winner determination in combi-
natorial auction generalizations, 2001.
[67] Tuomas Sandholm and Subhash Suri. Improved algorithms for optimal winner
determination in combinatorial auctions and generalizations. In
AAAI/IAAI
,
pages 90–97, 2000.
[68] O. Schelen and S. Pink. Sharing resources through advance reservation agents.
In
Proceedings of the IFIP International Workshop on Quality of Service
,
Columbia University, New York, May 1997. Chapman and Hall.
130
[69] A. Schill, F. Breiter, and S. Kühn. Design and evaluation of an advance reserva-
tion protocol on top of rsvp. In
IFIP 4th International Conference on Broadband
Communications
, pages 23–40, Stuttgart, 1998. Chapman & Hall.
[70] Jochen Schumann, Ulrich Meyer, and Wolfgang Ströbele.
Grundzüge der
mikroökonomischen Theorie
. Springer, 7th edition, 1999.
[71] Oz Shy.
The Economics of Network Industries
. Cambridge University Press,
2001.
[72] Herbert A. Simon. A behavioral model of rational choice.
The Quarterly Journal
of Economics
, 69:99–117, 1955.
[73] A. Prasad Sistla. Safety, liveness and fairness in temporal logic.
Formal Aspects
in Computing
, 6:495–511, 1994.
[74] Andreas Tanner. On the mean revenue of combinatorial exchanges under vari-
ation of clearing policies. In
Proceedings of the 7th International Conference
on Business Information Systems BIS
, Poznan, Poland, 2004.
[75] Andreas Tanner and Michael A. Jaeger. Pricing in publish/subscribe systems.
In
Proceedings of the 6th International Conference of E-Commerce (ICEC04)
.
ACM Press, 2004.
[76] Andreas Tanner and Gero Mühl. A combinatorial exchange for autonomous
traders. In
Proceedings of the 4th International Conference on Electronic Com-
merce and Web Technologies
, volume 2738 of
LNCS
, pages 26–36. Springer
Verlag, September 2003. ISBN 3-540-40808-8.
[77] Andreas Tanner and Gero Mühl. A formalisation of message-complete publish/-
subscribe systems. Technical Report Rote Reihe 2004/11, Technische Univer-
sität Berlin, October 2004.
[78] William Vickrey. Counterspeculations, auctions, and competetive sealed ten-
ders.
Journal of Finance
, 16:8–37, 1961.
[79] Zheng Wang.
Internet QoS: architectures and mechanisms for Quality of Ser-
vice
. Morgan Kaufmann, 2001.
[80] Lars C. Wolf, Luca Delgrossi, Ralf Steinmetz, Sibylle Schaller, and Hartmut
Wittig. Issues of reserving resources in advance. In
Fifth International Work-
shop on Network and Operating System Support for Digital Audio and Video
,
Durham, New Hampshire, USA, 1995.
[81] Elmar Wolfstetter.
Topics in Microeconomics
. Cambridge University Press,
1999.
131
[82] P. Wurman, W. Walsh, and M. Wellman. Flexible double auctions for electronic
commerce: Theory and implementation.
Decision Support Systems
, 24:17–27,
1998.
[83] M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false name declara-
tions in mechanism design: Towards collective decision making on the inter-
net. In
Proc. 20th International Conference on Distributed Computing Systems
(ICDCS-2000)
, pages 146–153, 2000.
[84] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. Robust combinatorial
auction protocol against false-name bids.
Artificial Intelligence
, 130:167–181,
2001.
[85] S. Ziya, H. Ayhan, and R. D. Foley. Optimal prices for finite capacity queueing
systems. Available at http://www.unc.edu/~ziya/papers.html.
[86] Gilead Zlotkin and Jeffrey S. Rosenschein.
Rules of Encounter
. MIT press,
1994.
[87] Edo Zurel and Noam Nisan. An efficient approximate allocation algorithm for
combinatorial auctions. In
Proceedings of the 3rd ACM conference on Elec-
tronic Commerce
, pages 125–136. ACM Press, 2001.
132
