Loading...

Multiple Criteria Decision Making in Application Layer Networks

Diploma Thesis 2008 138 Pages

Computer Science - Commercial Information Technology

Excerpt

Contents

List of Figures

List of Tables

List of Abbreviations

List of Symbols

1 Introduction
1.1 Starting Position: Trust in eCommerce
1.2 Objectives of this Study
1.3 Conduct of this Study

2 Interactions in Application Layer Networks
2.1 Depicting the Environment
2.2 Coordination in Application Layer Networks
2.2.1 Application Layer Networks
2.2.2 Catallactic Information Systems
2.3 Software Agents in Multi Agent Systems
2.3.1 Software Agents
2.3.2 Multi Agent Systems
2.3.3 Disseminating and Gathering Information
2.4 The Object of Interaction: Trading Goods
2.4.1 Homogeneous and Heterogeneous Goods and Services
2.4.2 Price Formation Mechanisms
2.5 Differentiation through Reputation
2.5.1 Reputation and Image
2.5.2 Reputation Systems
2.6 Decision Making
2.6.1 Theory of Decision
2.6.2 The Classical Model for Decision Making
2.6.3 Multiple Criteria Decision Making
2.6.4 Preference Modeling through Utility and Values

3 Multiple Criteria Decision Making
3.1 Classification of MCDM Methods
3.2 On Data and Weights
3.2.1 Scales of Data
3.2.2 Normalization Techniques for Equalizing Diverse Scales
3.2.3 Weights as Means for Relative Importance of Criteria
3.3 Multiple Attribute Decision Making
3.3.1 A Taxonomy of MADM Methods
3.3.2 Deciding without Preference Information
3.3.3 Satisficing (Conjunctive and Disjunctive Approaches)
3.3.4 Sequential Elimination
3.3.5 Value Function Methods
3.4 Multiple Objective Decision Making
3.4.1 Overview of MODM Methods
3.4.2 Goal Programming
3.5 Decision Aids
3.5.1 Outranking Relations
3.5.2 The ELECTRE Approach

4 Application of the Extended TOPSIS to the Scenario
4.1 Structure
4.2 A Synthesis of ALN and MCDM
4.2.1 Summary of Environment Characteristics
4.2.2 Comparison of MCDM Methods
4.2.3 Conclusion for Method Application
4.3 Scenario Specifications
4.3.1 Environment and Actors
4.3.2 Interaction between Actors
4.3.3 Offer Attributes
4.3.4 Principal’s Preference Information
4.4 The Extended TOPSIS
4.4.1 Description of the Technique
4.4.2 Application of the xTOPSIS: A Numerical Example
4.5 Findings from the Scenario Application
4.5.1 Intertemporal Comparison of Reached Agreements
4.5.2 Seller Evaluation
4.5.3 Summary

5 Conclusion

5.1 Results

5.2 Suggestions for Research and some Critical Annotations

References

Appendix

Appendix A

Appendix B: Case Study

List of Figures

Figure 1: Percentage of EU enterprises' total turnover from eCommerce via Internet

Figure 2: General approach of this work

Figure 3: Outline of the 2nd Section

Figure 4: The ALN as a virtual hard disk

Figure 5: The Procedural Reasoning System

Figure 6: Typology of goods

Figure 7: Price formation mechanisms

Figure 8: Well-known auction types

Figure 9: Building blocks of reputation

Figure 10: Calculation of trust in ReGreT

Figure 11: Decision-making process

Figure 12: Non-sequential decision-making process

Figure 13: Subprocess of defining a decision matrix

Figure 14: Classical model of decision-making

Figure 15: MCDM methodology

Figure 16: Outline of the 3rd Section

Figure 17: Relative and cumulative weights in value trees

Figure 18: The subprocess of defining weights

Figure 19: Overview of MADM methods

Figure 20: Efficient frontier

Figure 21: Process of the Simple Additive Weighting method

Figure 22: Process of the Weighted Product Method

Figure 23: Generic four- and five-level hierarchies

Figure 24: Simplified process of the Analytic Hierarchy Process

Figure 25: A three-level hierarchy for means of travel

Figure 26: Euclidean distances to the ideal solutions in two-dimensional space

Figure 27: Process of the Technique for Order Preference by Similarity to Ideal Solution .

Figure 28: A taxonomy of methods for Multiple Objective Decision Making

Figure 29: Portray of feasible solutions in a GP example

Figure 30: Process of the ELECTRE method

Figure 31: Outline of the 4th Section

Figure 32: The main process of buying storage capacity and the MCDM blackbox ...

Figure 33: Prerequisites for the appropriate MCDM method

Figure 34: Classification of MCDM methods in the light of the scenario

Figure 35: Scheme of the scenario

Figure 36: Interaction within the ALN

Figure 37: Process of the extended TOPSIS

List of Tables

Table 1: Standard cases for the employment of DBAs

Table 2: Distinction between DPS and MAS

Table 3: Example of a decision matrix

Table 4: Terminology in decision-making

Table 5: Example of a multiple criteria decision problem

Table 6: Scale levels and their properties

Table 7: Normalization with linear scale transformation

Table 8: Vector normalization

Table 9: Maximin and Maximax decision rules

Table 10: Satisficing approaches

Table 11: Additive and multiplicative weighting approaches

Table 12: Assembling positive and negative ideal solutions

Table 13: Outranking relations

Table 14: Summary of scenario characteristics

Table 15: Dimensions of the comparison table

Table 16: Comparison of MCDM methods

Table 17: Offer attributes

Table 18: Weight vector

Table 19: Decision matrix of the 1st round

Table 20: Weighted normalized decision matrix of the 1st round

Table 21: Closeness values and ranking for the 1st round

Table 22: Decision matrix of the 2nd round

Table 23: Weighted normalized matrix, closeness values and ranks of the 2nd round

Table 24: Weighted normalized matrix, closeness values and ranks of the 3rd round

List of Abbreviations

illustration not visible in this excerpt

1 Introduction

1.1 Starting Position: Trust in eCommerce

The rise of the Internet economy can be attributed to the worldwide spread of Internet access points and the rapid pace of ICT development (information and communication technology), which together induced cross-border networking between private households, enterprises and entire markets [Wirt01, 23-25]. The Internet economy paved the way for electronic Commerce (eCommerce) and enabled traditional enterprises to move parts of their value chain online [Wirt01, 40]:

According to Eurostat, the Statistical Office of the European Communities, the turn- over share from eCommerce has soared by a compound annual growth rate of 26 per- cent during the past three years (Figure 1) [Euro08a]. For the next three years, mar- ket analysts of Forrester Research as well as eMarketer even predict a vigorous an- nual growth of 21 to 25 percent for the European business-to-customer market [Forr08], [Emar08].

illustration not visible in this excerpt

Figure 1: Percentage of EU enterprises' total turnover from eCommerce via Internet [Euro08a]

But the increasing number of customers and suppliers also bears risks:

Since Internet traders are dispersed worldwide and may remain anonymous, it is dif- ficult to estimate the trustworthiness of a potential partner upon the first encounter [BoOc06, 1], [RZSL06, 80]. In consequence of doubts and mistrust, honest partners refrain from trading while fraudulent ones continue, which eventually leads to de- struction of markets for high quality goods [Aker70]. Currently, one of eight Europe- ans shies away from shopping online due to lack of trust in digital stores [Eur08b, 1]. On their search for cure, electronic institutions (e.g. the popular electronic markets Amazon Marketplace, eBay, and Yahoo!Shopping) discovered reputation systems (also called online feedback mechanisms). Their purpose: Building trust between strangers by disseminating ratings from past encounters [Amaz08], [Ebay08a], [Yaho08], [Erep05, 3-4], [Dell03, 1407].

But how can we explain online reputation systems in the light of social cognitive the- ory, i.e. how is reputation generated, spread and represented? Is there a standard mechanism, or how shall we engineer a reputation system to fulfill its purpose as good as possible? These questions are the core issues of the Social Knowledge for e- Governance (eRep) project sponsored by the EU’s Framework Programme f]or Re- search and Technological Development. After laying the theoretical foundations and developing a reputation mechanism, the project committee plans to implement this mechanism in an agent -based environment and test the impact of the reputation sys- tem [Erep05, 2-4], [Euro02a, 2].

The actors in the specified simulation scenario, multiple software agents trading with each other, consider the reputation of potential partners in their course of negotiations. The goal of this study is to determine an efficient method for programming this consideration step.

1.2 Objectives of this Study

In the simulation scenario of the eRep project, multiple agents contemplate reputation of potential partners before purchasing goods. The primary objective of this work is the elaboration of an appropriate procedure for decision-making, i.e. a method for preparing decisions by processing information (e.g. price, reputation) and providing a clear advice to the agent.

Aside from the distinct method, we keep the following secondary objectives in mind:

1. Trading services: The progress from trading plain digital goods (such as music files, Video-on-demand) to renting software applications leads to a multitude of distinguishing features [StEy07, 7], [Back03, 379], [MEKr03, 298-299], [ShVa99, 55-63]. Can the chosen decision-making method cope with all addi- tional requirements and enable the automated trade of complex goods?
2. Added benefit: Are there any added benefits that can be drawn from the appli- cation of the chosen method?
3. Restrictions: Modeling the scenario and implementing the decision-making method involves necessary concessions in terms of assumed underlying con- nections. Which assumptions inhibit the translation of the scenario results to human-based environments?

1.3 Conduct of this Study

Our search for an appropriate decision-making method is based on a scenario similar to the simulation testbed of the eRep project (Figure 2). Thus we explain underlying theories of this scenario and characterize the environment and its determinants.

The latter enables us to derive prerequisites for developing a framework of our decision-making problem. Where possible we will point out connections to developments of the eRep project to assure the outcome of this work can be finally transferred to the simulation testbed (Section 2).

Thereafter we conduct an analysis of eleven methods for multiple criteria decision problems and sort the results according to their requirements. In connection with the inspection, we examine fundamentals of modeling decision problems, namely data scaling and preference integration (Section 3).

Section 4 summarizes and synthesizes the results of the previous sections. The elabo- rated prerequisites enable us to detail the specifications of the simulation scenario, which in turn allow us to recommend a particular decision-making method. We mod- ify and demonstrate this technique using a numerical example and close with a sum- mary of our findings.

The work ends with a summary comprising of answers to the questions we have posed above. Moreover, we list potential opportunities of the chosen method and provide recommendations for further research on decision-making in the given con- text (Section 5).

illustration not visible in this excerpt

Figure 2: General approach of this work

The Appendix at the end includes the example of a multiple criteria decision problem concerning the purchase of a car. The case study complements the work in terms of illustrating the calculation steps for almost all presented decision-making methods.

2 Interactions in Application Layer Networks

2.1 Depicting the Environment

This Section clarifies the used terminology and describes the economic environment in which the decision-making scenario is located (Figure 3). To achieve that, we ex- plain the coordination principle (Subsection 2.2) and present the actors (Subsection 2.3). Thereafter, we clarify the rationale for and the conduct of interaction (Subsection 2.4) before we attend to the function of reputation in general and as an inherent institution of the environment (Subsection 2.5). Finally, we explicate decisionmaking and glance at preference modeling (Subsection 2.6).

illustration not visible in this excerpt

Figure 3: Outline of the 2nd Section

2.2 Coordination in Application Layer Networks

2.2.1 Application Layer Networks

An extensive computer network which provides services requiring a considerable amount of resources is called Application Layer Network (ALN). In order to acquire these resources, ALNs use communication infrastructures such as the Internet in order to interconnect numerous individual computers [ESR+05, 7].

Resource allocation by means of centralized mechanisms proves to be inefficient for two reasons: First, the coordinating institution is supposed to transfer instantly a huge number of requests from connected peers. Second, rapidly changing member structures in dynamic networks and multiple varying environmental states place great demand on the processing capacities of the coordinator. Especially large-scale networks call for coordination mechanisms which are capable of allocating resources and services in real time to fulfill specified service-levels [ERA+04, 10], [Eyma03, 53-54]. Hence, we explain a decentralized philosophy in the next Subsec- tion.

A prominent example for an ALN is the Peer-to-Peer system BitTorrent which enables members to share resources and transfer files to each other [SNV+07, 91-92], [Cohe03, 1]. For the application of ALNs in academics, prime examples are the Stanford University’s Folding@home project or the distributed search for extra-terrestrial intelligence, SETI@home, run by the Space Science Laboratory at the University of California, Berkeley [Pand08, 1-2], [Univ08].

In the scenario of this work, the ALN is a virtual hard disk composed of space provided by linked up computer systems (Figure 4).

illustration not visible in this excerpt

Figure 4: The ALN as a virtual hard disk

2.2.2 Catallactic Information Systems

With regard to the economic principles of Friedrich August von Hayek’s Catallaxy, the Catallactic Information System (CIS) proposes a decentralized coordination mechanism as a new paradigm for the design of information systems [EPSc00, 349- 350].

Hayek’s Catallaxy can be understood as a synonym for free-market economy, using prices as coordination mechanisms and, without knowledge of the individual actors’ behaviors, leading to a “spontaneous order” [Eyma03, 157]. The concept assumes members in the system are self-interested and strive to maximize their utility. As participants can neither foresee future market states nor predict other agents’ behaviors (constitutional ignorance), they are forced to make decisions under bounded ration ality [ESR+05, 13]. The CIS molds the concept of Catallaxy using the technology of Multi Agent Systems (MAS), which consist of software agents representing the actors in the Catallaxy (cf. Subsection 2.3.2).

The evaluation of a Catallaxy-based coordination mechanism has been subject to research in the CATNETS project. The authors deduced several fields for further research, including, but not limited to, the necessity to implement electronic institutions and social control mechanisms to cope with volatile service qualities and malevolent software agents [StEy07, 27-30]. With respect to these findings we implement a governance mechanism in our future scenario.

2.3 Software Agents in Multi Agent Systems

2.3.1 Software Agents

2.3.1.1 Agents in Computer Science

The Merriam-Webster explains the term agent as “one who is authorized to act for or in the place of another”, i.e. a representative of someone or something [Merr08a, § 4]. The translation of the traditional meaning in the context of computer science is called software agent or intelligent agent. Due to the versatility of agents in applica- tions, a definite and overarching explication is still open [Burk03, 1014-1015], [Nwan96, 208].

Referring to Wooldridge, we understand software agents as autonomous entities interacting with their environment in a bidirectional way: Agents receive input through sensors and use effectors to react with output actions [Wool00, 29].

In addition to autonomy, our agents are intelligent in the sense that they are flexible in conducting actions to achieve their goals. Flexibility in turn comprises the following three features:

ƒ- reactivity refers to immediate response to environmental changes,
pro-activeness is the ability to take the initiative, and
ƒ - social ability means interacting with other agents.

Each feature has implications for the remainder of this work: Social ability requires the presence of additional agents to cooperate with as well as the implementation of a common communication language. Pro-activeness and reactivity seem contradictory, and reactivity even puts autonomy into question - in order to balance these features, an internal model is required that allows elaborating and adjusting plans of action [Wool00, 32-33].

Supplementary to Wooldridge’s definition of reactivity, suggestions for further poten- tial dimensions are listed in [Burk03, 951-953]. Nwana takes up learning which evolves from past interactions with the environment, and argues for its explicit con- sideration [Nwan96, 210]. Learning is “any instance of improvement of behavior through increased information about the environment” [Kael93, 4]. Though learning seems implicit when attributing reactivity to agents, it can take various forms in MAS; a general characterization can be found in [SeWe00, 260-264].

In our context, the agent learns from encounters with others in the way that he adjusts his beliefs about the environment.

2.3.1.2 Practical Reasoning in the Internal Model

Between perception and action, the internal model provides the basis on which agents make decisions and fulfill their assigned function. Practical reasoning is the two-phase process of deliberation and means-end reasoning. At first, deliberation refers to deciding what state to achieve, whereas means-end reasoning afterwards refers to deciding how to achieve the particular state. States an agent has committed to are called intentions: they drive means-end reasoning, constrain future deliberation, and exert influence on beliefs [Wool05, 66-69].

Among the available models, we will outline the Procedural Reasoning System (PRS) in the following paragraphs, since it is an approved implementation for deliberate agents and embodies the Belief-Desire-Intention (BDI) paradigm [Wool05, 82]. Far- ther, the PRS corresponds to the framework used in the eRep project [SPV+07, 13].

In the PRS architecture, four attitudes determine the behavior of the agent, i.e. how practical reasoning is conducted. Our agent is in possession of the key data structures

beliefs, desires, intentions and plans (Figure 5) [Wool96, 663-664]:

ƒ- Belief: knowledge emerging from information about environmental states re- ceived and updated through the agent’s sensor. Belief is subjective and not necessarily correct or complete.
ƒ- Desire: objectives or tasks, the agent is supposed to accomplish, and priorities associated with them. Desire represents the motivational state of an agent.
ƒ- Intentions: deliberative state. Intentions are the currently chosen course of ac- tion, i.e. the objective the agent has committed to pursue at the moment.
Plans: particular patterns of instructions to achieve an objective. Plans are made up of a goal, a context (preconditions) and a body (the sequence of ac- tions to carry out).

illustration not visible in this excerpt

Figure 5: The Procedural Reasoning System [Wool05, 83]

The process of procedural reasoning works as follows: At the beginning, the inter- preter (planner) has beliefs about the world, a collection of plans and a top-level goal. He browses his library of plans to extract those ones that match both goal and pre- condition of the current state. Afterwards, in the process of deliberation the agent selects a plan from the resulting set of options. A practical means to allow rational justified selections is the implementation of a utility value for options: then the plan with the highest value is selected (for an explication of utility cf. Subsection 2.6.4). After execution of the chosen plan, new goals arise and require deliberation and so on. [Wool05, 83-84].

2.3.1.3 Digital Business Agents

Software agents acting on behalf of a legal entity in commercial environments are called digital business agents (DBA). They are obedient, utilitarian entities whose commercial function (goal) is defined by a principal (human being or organization). Obedience implies that the DBA’s paramount goal is always aligned with the princi- pal’s one: to act in the owner’s interest. This in turn justifies the utilitarian attitude of the agent, expressed by rational conduct in order to contribute to the principal’s util- ity [Eyma03, 24-26].

Roughly, one may distinguish between two different cases in which DBAs are used: the cooperative and the competitive environment (Table 1).

Table 1: Standard cases for the employment of DBAs (based on [Eyma03, 27])

illustration not visible in this excerpt

This work assumes a competitive environment, since this corresponds with the CIS underlying the ALN and the research subject of the eRep project. At present, possible purposes of DBAs include capacity management, supply chain coordination, product design, and trade on electronic marketplaces [Eyma03, 99-107]. This work will focus on the decision-making process of DBAs trading on an electronic marketplace.

2.3.2 Multi Agent Systems

Discussing how various agents interact with each other involves explaining how coor- dination is realized between them. On the one hand we have cooperation through Distributed Problem Solving (DPS), on the other hand competition is solved through negotiation processes (Table 2) [HuSt00, 83]. While in DPS a common goal is fractured top-down and solved bottom-up, MAS have the top goal emerging from the bottom as a result of the various agents’ competing goals [Eyma03, 49-51].

Table 2: Distinction between DPS and MAS [RoZl98, 15-16]

illustration not visible in this excerpt

In accordance with the concept of DBAs, participating agents in MAS are rational, self-interested and utility-maximizing; they strive to realize the interest of their respective owner [RoZl94, 31]. Thus, DBAs negotiate with each other in order to achieve their goals.

As mentioned before (cf. Section 2.2.2), the implementation of the CIS constitutes a price mechanism to encourage coordination between the rival agents. Assuming that we apply the MAS idea to an electronic marketplace, we predict the overarching goal is system efficiency in terms of a Pareto efficient allocation of traded goods with their respective utility (welfare maximization) [Vari06, 618-620], [RoZl94, 31].

2.3.3 Disseminating and Gathering Information

With the implementation of reputation (cf. Subsection 2.5.1.2), it becomes necessary to compute an aggregate which reflects the common image of the target agent. We assume agents disseminate their experiences on a voluntary basis, though this con- tradicts with the definition of the self-centered, utilitarian agent (cf. Subsection 2.3.1.3). Miller et al. suggest a complex reward system based on scoring rules to elicit honest feedback from other participants [MRZe05]. For the sake of simplicity, we suppose agents spread information on a voluntary basis.

In order to allow dissemination and accumulation of information in the ALN, a for- mal communication mechanism has to be implemented. Possible forms range from broadcasting mechanisms over blackboard systems to direct communication [Eyma03, 56-58]. Whereas broadcasting means transmitting information to all par- ticipants (“one-to-many”), direct communication relates to the opposite channel-wise messaging (“one-to-one”). Blackboard systems store news (feedback) in repositories and disseminate information upon request; well-known eCommerce examples in- clude online reputation systems such as the ones of Amazon Marketplace, Ebay, or Yahoo!Shopping [Amaz08], [Ebay08a], [Yaho08]. Researchers of the eRep project have also examined possible means of communication and their effects on reputation [CoPa07, 9-13]. Despite the high degree of decentralization of our reference system, we presume agents store data partially in public local repositories which are accessi- ble for all connected members when requesting information (Subsection 2.5.2.3).

2.4 The Object of Interaction: Trading Goods

2.4.1 Homogeneous and Heterogeneous Goods and Services

In ordinary language, goods are “something that has economic utility or satisfies an economic want“ [Merr08b]. Moreover, we need to differentiate goods with respect to their impact on marketing: While some goods do not allow differentiation and further market segmentation, some goods permit multi-dimensional customization. Thus, the following terminology is being used from now on: When we talk about goods, we mean goods and services. Very complex, multi-faceted goods which can hardly be compared are named heterogeneous goods (e.g. cars, advisory, holiday trips), while very simple goods, which only differ in their price, are called homogeneous goods (e.g. power, coal or storage capacity in megabytes) [WRSc05, 69], [GLFo04, 257].

These two types of goods can be understood as extreme values on a continuum - many goods are positioned in between. To determine the grade of complexity, we use the typology of Woratschek and classify goods on three dimensions: behavioral un- certainty associated with the transaction, the degree of customer integration and the degree of customization [WRSc05, 69], [Wora96, 69]. We can illustrate the contin- uum between homogeneity and heterogeneity using a sliced cube (Figure 6).

A distinction between homogeneous and heterogeneous goods is applicable in ALNs as well: the former are termed resources, the latter services. Moreover we assume application services (e.g. converting a Portable Document Format file [PDF]) can be broken down into resources needed to provide the service (like hard disk capacity and processing power) [StEy07, 7-8]. We hold on to a commodity or plain resource (such as a coal or wheat) and assume sellers cannot modify the good in a way that allows them to differentiate from com- peting suppliers. From a customer’s perspective, all offers are equal except for the price and the potential supplier (uncertainty about the suppliers’ trustworthiness is a distinguishing feature).

illustration not visible in this excerpt

Figure 6: Typology of goods (based on [Wora96, 69])

The particular object of trade in the scenario of this work is storage capacity in units of one gigabyte per month (GB/month).

2.4.2 Price Formation Mechanisms

2.4.2.1 How Prices Emerge

The price demanded by producers represents the evaluation of a product in monetary units. From a customer’s point of view, the price is a sacrifice made to benefit from the possession of something, i.e. his willingness-to-pay depends on his associated utility with the particular good [Simo92, 3-4]. From the producer’s position, the price has to compensate for costs incurred in the manufacturing process and has to yield profit for the company [Simo92, 25], [Vari06, 386-387]. Thus, the goals of customers and producers are rivaling.

Furthermore, the market structure influences price formation as well: on competitive markets with numerous customers and producers (polypolies) prices emerge from aggregate demand and supply [Simo92, 20-27]. This equilibrium principle relates back to the findings of Leon Walras, but is disputed when constraints such as infor- mational asymmetries persist [Vari06, 572], [McMc87, 700], [Aker70, 492].

Since utility is subject to individual preferences, customers’ willingness-to-pay varies as well: producers are keen to match these price limits in order to maximize turnover. If the price is set too low, demand exceeds the production plan, and if the price is too high, customers are deterred and supply exceeds demand. In both cases social welfare is forgone. Thus, for complex bundles, market research is conducted to measure the utility perceived by consumers and to derive the associated willingness-to-pay. But the aggregation of individual estimates is often problematic and seldom reduces information asymmetry sufficiently [Meff05, 542-548].

Price formation mechanisms describe how prices come into existence on markets. Mechanisms can be grouped in variable pricing, one-sided posted pricing and two sided posted pricing (Figure 7). In variable pricing, price and product details result from bargaining and negotiations between the respective parties. Since no formal rules are given, this mechanism is excluded in this work [WRSc05, 62]. Instead, we explain one-sided posted pricing and two-sided posted pricing.

illustration not visible in this excerpt

Figure 7: Price formation mechanisms [WRSc05, 62]

2.4.2.2 One-sided Posted Pricing

In one-sided posted pricing, either the seller or the buyer posts a fixed price and de- fines the characteristics of the product. Usually producers announce the price on the basis of incurred costs and market structure. Potential buyers then decide whether to accept or to reject the offer in conformance with their willingness-to-pay [WRSc05, 62-63]. This mechanism requires knowledge about the buyer’s preference structure in order to exploit the full potential benefit from the bargain [Meff05, 542].

2.4.2.3 Two-sided Posted Pricing: Auctions

Two-sided posted pricing involves both seller and buyer when it comes to defining product price and characteristics. If the seller designs the product in question, the buyer announces his price - and vice versa. The according mechanism for this way of price determination is the auction in one of its forms [WRSc05, 63]. Quoting McAfee and McMillan, “an auction is a market institution with an explicit set of rules deter- mining resource allocation and prices on the basis of bids from the market partici- pants” [McMc87, 701]. The design of auctions, the pros and cons of specific bidding rules, and the resulting bidding strategies are the subject of auction theory [McMc87, 700], [MiWe82, 1090-1093].

Auction types can be categorized by the number of sides submitting bids (auction / double auction) and by the market role of the auctioneer (buyer/ seller) (Figure 8). Auctions conducted by buyers are called reverse or procurement auctions [KaCa04, 15], and auctions in which both supplier and customer place bids are named double auctions [Klem04, 35].

The four fundamental auction forms are the Dutch auction, the English auction, the first-price sealed-bid ( FPSB ) auction and the second-price sealed-bid auction (also known as Vickrey auction). The Dutch auction (descending-bid auction) starts with a high price and decreases continuously until one bidder accepts the price and calls out. In the English auction (ascending-bid auction), the auctioneer commences with a low price and increments the price until one bidder remains (who wins the event). In FPSB and Vickrey auctions bidders cannot see their competitors’ bids, and the object is won by the bidder who submits the highest bid. The difference lies in the final price: whereas in the FPSB auction, the winner has to pay his full bid, the winner in Vickrey auctions pays the bid of the second- highest bidder [Klem04, 11-12].

On the basis of the Revenue Equivalence Theorem, we assume the seller’s expected revenue is the same in all four fundamental auction forms (to be precise, revenue is equal on average). In this case the winner is the participant with the highest willing- ness-to-pay, induced by the individually perceived utility [Klem04, 17-18], [McMc87, 710-711].

illustration not visible in this excerpt

Figure 8: Well-known auction types (based [WRSc05, 64])

Allowing for informational asymmetries, markets are less competitive on the suppliers’ side and rather constitute monopolistic situations [McMc87, 703]. This complies with our future scenario - every supplier and his offer are more or less unique and are requested by a group of interested buyers.

In a recent simulation in the eRep project the authors presumed a mechanism similar to the one implemented at the popular Internet auction platform eBay [BJTr08, 13]; we follow these developments and use an English auction to determine the price of the particular good.

2.5 Differentiation through Reputation

2.5.1 Reputation and Image

2.5.1.1 The Function of Reputation

In modern economies, companies build reputation to differentiate themselves from competitors and gain competitive advantage [Fomb96, 80]. A good reputation can stimulate product sales, increase the chance of hiring the best employees and attract potential investors [FoSh90, 233-234]. As an intangible asset, reputation is of para- mount importance for service providers and can be shaped through various practices such as conducting pro bono activities or by company advertising campaigns [Fomb96, 112-136].

The peculiar importance for service providers can be explained as follows:

In comparison to commodities, services are, among other things, characterized by a high degree of uncertainty. As a result of asymmetrical information between service providers and customers, potential buyers face high risks of being exploited after signing a contract (moral hazard) [MeBr06, 97], [Wora96, 62]. Taking those risks into account, consumers’ willingness-to-pay decreases and eventually leads to the destruction of markets for high-quality products [Aker70, 490-491].

Reputation is an effective panacea which indicates reliability and mitigates moral hazard [Wora98, 47]. Building a good record is expensive and time-consuming; and since reputation is sensitive to dishonesty, deceitfulness and fraudulence, a good name promotes self-commitment by encouraging the owner to continue fair business practices [MeBr06, 98]. In consequence, customers believe past behavior is a good predictor for future conduct [Roth01, 59]. This corresponds with Axelrod’s “shadow of the future”, a phenomenon describing why future interactions are constrained by behavior in the past [Axel88, 11].

2.5.1.2 Building Blocks of Reputation: Image and Social Reputation

The assessment of one partner’s reputation depends not only on a common agreed social estimate. Instead, we distinguish between an individual’s perception and the social opinion about an entity [BKOc04, 1588].

Through the evaluation of outcomes of past transactions individuals gain impressions and form an estimate of a partner: this is called image. Furthermore, the common belief about the image of a target spread in social communities is considered as an objective result of evaluations and complements the assessment of the target’s repu- tation. This component is termed social reputation [Erep06, 7-8]. As reputation again stipulates trust, a cycle of reputation building is formed (Figure 9).

illustration not visible in this excerpt

Figure 9: Building blocks of reputation

With respect for brevity, we omit a further explanation of reputation here; and for a deeper understanding in the context of the eRep project we refer to [CoPa07].

2.5.2 Reputation Systems

2.5.2.1 Reputation Systems and Feedback Mechanisms in ALN

A reputation system serves the purpose of providing information about the reputation of an individual: The system has to gather, extract and evaluate feedback from information and to assign it to the relevant entity [RZFK00, 46]. Results from experiments conducted in controlled environments emphasize the value of reputation systems and advocate their implementation; empirical studies support these findings [RZSL06, 26], [Ocke03, 310], [Kese02, 21], [ReZe01, 23].

The great importance of reputation in ALNs can be explained this way: Since an ex- tremely large number of participants offer and demand services, repeated encounters are very unlikely. This in turn inhibits building images from impressions. Resnick and Zeckhauser support this assumption: In their study of empirical data from eBay they discovered that 89 percent of the examined bargains were conducted by a unique seller-buyer pairing. The authors draw the conclusion that eBay’s reputation system rewards honest behavior, although the particular results of different studies on the system’s effects vary in detail [ReZe01, 9].

To summarize, effective reputation systems foster the trade among strangers and “help people decide whom to trust, encourage trustworthy behavior, and deter participation by those who are unskilled or dishonest” [RZFK00, 46].

Feedback mechanisms in ALNs can be distinguished from word-of-mouth networks of human beings in terms of three aspects [Dell03, 1410]:

First, the large scale of participants in the system requires that the number of col- lected feedbacks exceeds a certain threshold before it makes a difference. No entity pays attention to the social reputation if the number of underlying appraisals is too low.

Second, information technology allows the detailed design of feedback mechanisms and the formulation of algorithms for transforming feedback into aggregated values. For example, eBay displays the arithmetic mean of the sum of positive feedbacks collected by each member. The number of positive feedbacks exceeding negative ones is summarized and a colored star next to the sum signals the awarded reputation [Ebay08a], [Ebay08b]. The application of logical evaluations induces transparency and comparability of reputation values.

Third, ALNs are virtual constructs and prevent personal encounters. Prior to transactions, individuals cannot interpret signals from the surroundings (tangibles) or empathize with the potential partner. The degree of uncertainty exceeds the one of typical service providers’. For example, when seeking advice from a lawyer, people pay attention to the decoration of the waiting room, the district in which the office is located or the brand of the suit the lawyer is wearing (cf. [MeBr06, 294], [Bitn03], [Wora01, 273]). In ALNs, the agent has no such signals, since company websites or digital business cards will be of little help.

In Internet marketplaces, reputation systems are realized through central institutions collecting and evaluating feedback information [Dell03, 1408]. This does not apply to the individual image of a participant except for its contribution to social reputation.

As intuitively assumed and supported by the findings of a lab experiment in 2004, the gain from one’s own experience is likely to exceed a cumulative public reputation value [BKOc04, 1595]. These findings are underpinned by recent survey results showing 60 percent of private online shoppers remain loyal to vendors they had a positive shopping experience with [Niel08, 5].

Since the effects of locally managed reputation are investigated in the eRep project, the following paragraphs focus on such reputation systems.

2.5.2.2 A Panoramic View on Current Systems

It is beneficial for the development of an appropriate reputation framework to con- trast outcomes from empirical research with theoretical findings [Dell03]. A valuable roundup of reputation systems serves three purposes: it lists existent frameworks, describes the designs, and extracts particular contributions from each system.

Sabater and Sierra provide such a summary: they reviewed thirteen different con- cepts and classified them on seven dimensions (cf. Appendix A 2, p. 106, and for the abbreviations Appendix A 1, p. 105) [SaSi05, 55-56]. We explain two of these dimen- sions, since they exert direct influence on the selection of decision-making tools.

First, information sources comprise the types of sources taken into account when determining the reputation value of another entity. The perceived reputation of a trader depends on the subjective image of the customer built from impressions and the trader’s circulating social reputation. The subjective impressions stem from ex- periences made in direct interactions or observations with the trader. Following the narrow definition above, witnesses’ experiences are aggregated and result in social reputation. Beyond these experiences, information based on the trader’s societal af- filiations and social relations is likely to influence his picture. Hence, those potential sources are as well subsumed under social reputation [SaSi05, 35-37].

Second, an associated reliability measure helps to understand how stable each im- pression is. Thus, our customer can use the measure to weight the information value. In communities with a tremendous number of entities, the reliability measure serves as a threshold and filters less credible impressions. But even the subjective image a customer has is instable: Memories are fugacious, and in the course of time experi- ences blur or disappear completely. By assigning a reliability measure to each impres- sion, the individual computation of an aggregate reputation score becomes more precise and comprehensible [SaSi05, 40-41].

Our scenario with autonomous and deliberate agents encourages local decision- making. Hence, a reputation system that makes use of direct experience as well as witness information has to be implemented. Though not critical, a measure for reli- ability is useful when dealing with large-scale MAS. With the aid of Sabater and Si- erra’s comparison, two possible systems are identified: AFRAS and ReGreT.

Since ReGreT includes a comprehensive framework for evaluating sociological information, we prefer it to AFRAS and present it in the following chapter.

2.5.2.3 ReGreT

The ReGreT system consists of a direct trust and a reputation module to assess the trustworthiness (trust) of a prospective, so called target agent. Trust towards a target agent is the weighted sum of social reputation and direct trust (i.e. image). The computation of each component is determined by the system’s architecture: it distinguishes between three reputation dimensions, the individual dimension, the social dimension and the ontological dimension (Figure 2 1) [SaSi01, 194].

In the next paragraphs, each dimension with its components will be presented in a nutshell; for a detailed explication see [Saba03, 44-62].

On the individual level, outcomes of dialogues between agents are used to compute a direct trust value. An outcome is represented by a subjective rating and a tuple of in- formation; it is stored in the outcomes database (ODB). The tuple of information characterizes the outcome (e.g. price or expected quality) and the rating reflects the perceived evaluation. Direct trust is usually the most stable source to predict the sin- cereness of a partner; on the downside, it is unavailable for new entrants and expen- sive to build [Saba03, 44-46].

In the social dimension, the reputation measure is computed by the weighted results of three sources: witness, neighborhood, and system reputation. The weights are obtained from the credibility of each source, which is in turn calculated from the numbers of impressions and the standard deviations [SaSi01, 195].

We talk about witness reputation when information is collected from other agents who transmit their direct experiences or feedback obtained from peers. Evaluated impressions of witnessed outcomes are recorded in a second storage, the impression database (IDB). Neighborhood reputation is determined by the target’s social envi- ronment and the relations the target has established with his environment. It is com- parable to prejudice, but not necessarily discriminating. System reputation is based on the target’s role in a group. It assumes that roles adhere to certain observable fea- tures or behaviors which may be assigned to the target agent [Saba03, 47-48].

illustration not visible in this excerpt

Figure 10: Calculation of trust in ReGreT (based on [Saba03, 92])

The computation of neighborhood and system reputation depends on the group the individual belongs to; thus, both can be understood as group knowledge, and both are influenced by the social structures. Those structures, mapped as sociograms, are stored in a third container, the sociogram database (SDB). Though not fully specified yet, sociograms will support each estimate of credibility for all considered impres- sions by providing aid for proper weight assessment (e.g. witness reputation issued by a node related to the target agent may be biased and thus less valuable than others’ feedback) [Saba03, 51], [Saba03, 41].

Finally, the ontological dimension describes the context of information on which the target agent is rated. The ODB does not merely provide an aggregated value on each outcome but also detailed information on attributes such as price or delivery date; our subject can evaluate the overall impression by combining different aspects ac- cording to his preferential structure. This reflects different perceptions in real life, in which the seller’s reputation strongly depends on the rating customer [Saba03, 61].

König et al. propose a completely decentralized implementation of the ReGreT system using peer-to-peer technology for information exchange [KKWi07]. Due to its complexity, we reject their suggestion and presume the IDB is centrally implemented and social reputation of an agent is identically perceived by all participants. Of course, this does not affect the decentrally calculated image estimate.

We assume our participants will consider potential partners’ social reputation as well as direct trust from previous encounters. Consequently, social reputation and image are differentiating features for agents in MAS.

2.6 Decision Making

2.6.1 Theory of Decision

Decision theory is concerned with a decision-maker ’ s (DM) goal-directed rational behavior of coming to a decision in presence of possible options. Rationality implies deliberating about the action before and during decision-making, as well as commitment to the selection [SzWi74, 3-5]. In this work agents undertake decision-making and serve as proxies for their principal, the DM.

A distinction is made between normative and descriptive decision theory: Normative decision theory prescribes how problems can be solved. It provides advice on problem solving by formal means of depicting initial situations and solutions. In contrast, descriptive decision theory researches empirical findings and deals with the ex post analysis of decisions made [Laux07, 2], [SzWi74, 18-21].

Decision-making is a multi-stage process that “begins with the identification of a stimulus for action and ends with a specific commitment to action” [MRTh76, 246].

The famous economist and Nobel prize winner Herbert A. Simon (1960) proposed a sequential model with the three principal phases intelligence, design, and choice - similar in structure and content to the models later developed by Irle (1971) or Szyperski (1974) (Figure 11) [Simo77, 40], [SzWi74, 7-10].

The first phase, intelligence, covers the search for decision predicates in the environ- ment; Simon has baptized this phase in analogy to the military meaning. The follow- ing step, design, involves forging, developing, and studying possible conduct. Finally, the choice activity deals with selecting a particular conduct from the available ones [Simo77, 40-41].

illustration not visible in this excerpt

Figure 11: Decision-making process (cf. [SzWi74, 7-10], [Simo77, 40-41])

Later on, Mintzberg et al. (1976) recommend a non -sequential, iterative model with three intertwined phases comprising of seven central routines (Figure 12) [MRTh76, 252]. In contrast to the sequential models, their proposal assumes rather an iterative process of routines than the linear succession of actions. Iterations in- clude cycles between routines within a phase as well as cycles between phases.

The initial phase is termed identification and comprises two routines. The first, deci- sion recognition, is concerned with the identification of problems, crises, and oppor- tunities. The second routine, diagnosis, deals with accumulation and assessment of related information, and determination of cause-effect relationships [MRTh76, 253- 254].

The development stage is composed of the search and the design routine. While the search aims at finding existing solutions, design is about the development of custom- made solutions as well as the modification of ready-made ones. The purpose of both

illustration not visible in this excerpt

Figure 12: Non-sequential decision-making process [MRTh76, 266]

Finally, during the selection stage, three routines take place: The screen routine is concerned with the elimination of infeasible alternatives. In the evaluation-choice routine possible courses of action are evaluated and a choice is made. The last routine, authorization, deals with the submission of the decision to superior instances for approval [MRTh76, 257-260].

Depending on the model, the focus for this work lies on the choice stage (Figure 11) or the selection stage (Figure 12), both dealing with formal models for comparing and ranking considered alternatives.

2.6.2 The Classical Model for Decision Making

Whether we approve of Simon’s sequential decision process or the cycling phases of Mintzberg et al., decision-making is concerned with selecting one or more options from a number of alternatives. In order to support DMs, decision matrices are commonly used to visualize and formulate decision situations [Laux07, 36-37], [YoHw95, 3]: The columns in the matrix represent the criteria and the rows the al ternatives with their specific outcome vector.

We show an example situation below: A passenger who is requested to journey low- budget from Frankfurt to Munich is confronted with three travel options (Table 3).

Table 3: Example of a decision matrix

illustration not visible in this excerpt

A decision matrix is constructed by gathering and attributing information to alternatives and criteria (Figure 13; processes in this work are illustrated using activity dia grams of the UML notation, see [OMG08]).

illustration not visible in this excerpt

Figure 13: Subprocess of defining a decision matrix

A decision matrix is a particular decision model with some building blocks which are always apparent (Table 4) [Laux07, 19-26]. We denote by the decision matrix A on [Abbildung in dieser Leseprobe nicht enthalten] Upon deciding, our passenger picks A 1 and faces the safe out- come a11 = 70, i.e. paying 70 Euros for the train ticket.

Table 4: Terminology in decision-making [Laux07, 19-26]

illustration not visible in this excerpt

The relationship between these building blocks in the classical model of decisionmaking is depicted below (Figure 14): We see the outcome depends on the interplay of decision and current state.

With respect to brevity, we disregard uncertainty and environmental states here. This in turn leads to the following simplification:

[Abbildung in dieser Leseprobe nicht enthalten]

The calculated preference value Φ of an alternative Ai is equal to the utility ui of the outcome ai [Laux07, 27].

illustration not visible in this excerpt

Figure 14: Classical model of decision-making (based on [ZiGu91, 3])

Thus, when we know the preference value for all alternatives, an utility-maximizing decision can be made without explicitly deriving utility from each parameter value. The question is whether all alternatives with their respective outcomes are available or not. Returning to the example (cf. Table 3), we recommend taking the train, which dominates the other alternatives in minimizing costs.

2.6.3 Multiple Criteria Decision Making

Under certainty, classical models can cope with decision-making as long as the preference function draws a comparable value out of each alternative. Everyday problems are usually more demanding: A comprehensive judgment involves balancing multiple goal-related criteria which are often competing [BeSt02, 1]. This challenge is called aggregation problem [Roy05, 14]. The modified decision matrix (Table 5) from the previous Subsection adds the criterion “travel time” to the problem.

Table 5: Example of a multiple criteria decision problem

illustration not visible in this excerpt

Although this problem seems simple, the challenge lies in managing the trade-off be- tween travel time and costs (assuming less travel time is associated with a higher util- ity). Time and costs are incommensurable units (What is the value of an hour in Eu- ros? How much time can I buy for a certain amount of money?) and no alternative dominates the others on both dimension (the train is now less attractive due to the long travel time). We are concerned with Multiple Criteria Decision Making (MCDM) when we take account of multiple conflicting criteria which need to be balanced [BeSt02, 5].

In our later scenario, the buying agent is choosing between several sellers, which dif- fer in social reputation, image and the demanded price. While shoppers seek concur- rently a high reputation and a low price, well-reputed sellers will likely seize their good name and ask for a premium (cf. the results of the experiment in [RZSL06, 21]).

2.6.4 Preference Modeling through Utility and Values

The predictability of the environmental states influences the means of preference modeling and distinguishes between preference representations under certainty and under risk. When we deal with uncertainty or risk, we refer to a preference represen- tation function as a utility function, and when all states are certain, we refer to a pref- erence representation function as a value function [Dyer05, 267-268], [BeSt02, 95], [KeRa93, 15-16].

In sympathy with Dyer et al. we exclude the field of Multiattribute Utility Theory here and assume value functions are either implicit or no such function exists at all [DFS+92, 647]. And since we also omitted cases of uncertainty and risk, we do not need to pay attention to utility functions from now on (for details on utility see [Vari06, 54-56]). Instead, we define value as being proportional to utility, i.e. a higher value implies always a higher utility (i.e. monotonically increasing).

In case outcome and evaluation are positively correlated, we deal with a benefit at tribute (i.e. maximization goal), in case they correlate negatively, a cost attribute is considered (i.e. minimization goal) [YoHw95, 15].

At this point, we denote the dependency of the value vij of an attribute’s outcome aij

as a value function [Abbildung in dieser Leseprobe nicht enthalten] (techniques for the attribute-wise rating of outcomes are presented in Subsection 3.2.2). We assume furthermore the following two axioms among the preferences are satisfied, which are formulated for the case of benefit attributes1 [Vari06, 35], [Laux07, 31-32]:

1. Completeness: Any couple of alternatives A α, A β and their outcomes a α j, a β j in a set of n alternatives can be compared and valued, so that [Abbildung in dieser Leseprobe nicht enthalten]

2. Transitivity: Comparing and valuating three alternatives A, A, A α β γ) the following has to hold good:

a. If outcome a α is preferred to or equal to the outcome a β and the out- come a β is preferred to or equal to the outcome a γ, then a α is pre- ferredtoor equal to a γ. Formal: [Abbildung in dieser Leseprobe nicht enthalten]2
b. If outcome a α is equal to the outcome a β and the outcome a β is equal to the outcome a γ, then the outcome a α is equal to the outcome a γ. Formal: [Abbildung in dieser Leseprobe nicht enthalten]

The two axioms seem sound but are not unquestionable: especially transitivity is problematic, because human beings can hardly distinguish between complex options. In the light of procedural rationality, the ability of individuals to conduct rational behavior is determined by cognitive powers and limitations (bounded rationality) [Simo78, 67], [SzWi74, 29-31].

In our scenario, we assume our agents are capable of taking all aspects into account and their time to process information is sufficient, thus they do not suffer from an excessive supply of information (information overload) [FaDr02, 127].

3 Multiple Criteria Decision Making

3.1 Classification of MCDM Methods

A wide collection of approaches is available to support individuals or groups in deci- sion-making but none outperforms all other methods. The selection of an appropriate method depends on the environment and is influenced by several factors such as available information, desired type of outcome or number of alternatives [BMP+00, 150], [Tria00, xxvi]. In order to provide an overview of available MCDM methods, it is helpful to classify these methods. Beforehand, we summarize some general aspects of data measurement and introduce scale normalization and weight- ing methods.

First of all, MCDM methods can be grouped according to the certainty of information: data may be either deterministic, stochastic or fuzzy 3. This work focuses on deterministic cases, for approaches covering uncertainty see [Stew05] and for fuzzy MCDM methods see [GrLa05], [ZiGu91, 247-266].

Further, MCDM can be separated into Multiple Attribute Decision Making (MADM), Multiple Objective Decision Making (MODM) and Decision Aids (Figure 15) [ZiGu91, 25-28].

illustration not visible in this excerpt

Figure 15: MCDM methodology

MADM concentrates on situations with a predetermined set of alternatives, i.e. the selection of an alternative from a discrete decision space. In contrast to MADM, MODM covers problems in which alternatives are not explicitly defined a priori. However, constraints and objectives are given to design efficient solutions from the continuous decision space (these cases are often termed vector-maximum problems) [Tria00, 1], [ZiGu91, 25], [HwYo81, 2-4]. Following this classification, we present a MADM methodology and a classic MODM approach. Apart from MADM and MODM, Decision Aids facilitate decision-making and not necessarily produce an unambigu- ous solution. We briefly introduce the approved outranking technique along with a corresponding method; outranking approaches estimate efficient solutions on the grounds of pairwise comparing alternatives. [BeSt02, 233-234], [ZiGu91, 26-29].

The structure of this Section is as follows (Figure 16): We commence with a general introduction of different data types and weighting methods and their influence on decision-making (Subsection 3.2). Then we turn to MADM (Subsection 3.3) and ex- plain a MODM method (Subsection 3.4). The last Subsection (3.5) is concerned with Decision Aids.

illustration not visible in this excerpt

Figure 16: Outline of the 3rd Section

In order to facilitate the understanding, we provide an exemplary decision problem to illustrate the results for each method. This case study can be found in Appendix B.

3.2 On Data and Weights

3.2.1 Scales of Data

The information on a criterion, i.e. the raw data of the outcome, can be expressed in terms of numbers or characters which are subject to a specific scale. Levels of meas- urement distinguish between nominal, ordinal ( grouped as categorical scales) , in- terval and ratio scales (comprised as continuous, metric or cardinal scales) [BEPW06, 4]. The scale levels and their distinct properties are sorted according to the number of mathematical operations and listed together with an example in con-centration with a car purchase decision [Webe93, 10].

[...]


1 For cost attributes, the binary relations between two outcomes are inverse to the relations of their values.

2 In case of α = β the axiom of reflexivity is satisfied.

3 “Fuzzy” refers to information which is not represented by an exact value, but instead is subject to a membership function that assigns values on a gradual base (see [Zade65]).

Author

Share

Previous

Title: Multiple Criteria Decision Making in Application Layer Networks