Browsing by Subject "Allokation"

Now showing 1 - 3 of 3

Electronic service allocation with private quality information
(2017) Widmer, Tobias; Kirn, Stefan
The efficient allocation of electronic services is a complex business problem. Customers demand electronic services from service providers who supply these services at a specified quality of service (QoS). Electronic marketplaces provide a platform on which multiple customers and multiple providers negotiate the allocation of electronic services. Such marketplaces might be administrated by government authorities or large corporations who aim at a socially optimal allocation. This research addresses the allocation problem for electronic services with private quality information from a mechanism design perspective. By assigning specific reservation functions, multiple customers and multiple providers enunciate their preferences for these services. Once all demands and offers for electronic services are submitted, the mechanism determines an allocation that maximizes the sum of the aggregated preferences. However, the design of such mechanisms is difficult because of the following requirements: (1) Double-sided competition: Multiple competitive customers and multiple competitive providers must be matched together appropriately to generate maximal surplus, (2) QoS-awareness: The QoS desired by customers and the QoS offered by service providers must be internalized in the allocation mechanism, (3) private information: The mechanism must facilitate the allocation of electronic services for which any QoS information is unknown, (4) incentive compatibility: The mechanism has to provide adequate incentives to strategic individuals in order to ensure truthful bidding, (5) individual rationality: The participation decision in the mechanism must be voluntarily to all bidders, (6) budget balance: The mechanism must omit any independent intermediary in order to facilitate distributed decision-making among the participants, (7) optimality: The ultimate objective of the mechanism is to achieve an outcome that is optimal from a social welfare perspective. Standard impossibility theorems from mechanism design theory assert that meeting these requirements simultaneously is not attainable. In particular, ex post optimality cannot be attained when incentive compatibility, individual rationality, and budget balance are required as well. Therefore, the mechanism designer must decide about a viable tradeoff of these requirements. One possible compromise in the presence of privately known QoS is to derive a second-best mechanism that satisfies incentive compatibility, individual rationality, and budget balance. The outcome of such second-best mechanisms can be used to estimate the efficiency loss that must be tolerated in comparison to the first-best outcome. The objectives of this research are to (1) develop a second-best mechanism for allocating electronic services with private quality information and (2) study its efficiency properties in a set of simulation experiments to demonstrate its usefulness. All experiments imply that the asymptotic efficiency of the second-best mechanism is bounded away from 100% even for large markets. This finding is related to the economic concept of informational smallness, which is defined as the incremental impact of an participants QoS on the demand of an electronic service. In the proposed model, each provider offers a service of distinct QoS, and each customer demands a service of distinct QoS. It is this feature of differentiated service quality that prevents the participants from becoming informationally small as the market becomes large. If each participant’s private information about QoS follows the uniform distribution, the mechanism must tolerate an efficiency loss of more than 31% for an increasing number of customers and providers. In contrast, if private quality information is normally distributed among participants, this research finds that the mechanisms asymptotic inefficiency can be reduced to about 7% as the market size increases on both sides. With asymmetric, beta-distributed QoS, the mechanism arrives at an asymptotic efficiency of more than 91%. These findings are crucial to social planners because in designing service allocation with double-sided competition, they can obtain an accurate estimation of potential efficiency losses that arise from asymmetric information about QoS. On the other hand, the social planner can ensure that every allocation decision is made by the participants only. Hence, the emerging mechanism implementation eludes the need for an external, independent decision maker.
Multiagent resource allocation in service networks
(2014) Karänke, Paul; Kirn, Stefan
The term service network (SN) denotes a network of software services in which complex software applications are provided to customers by aggregating multiple elementary services. These networks are based on the service-oriented computing (SOC) paradigm, which defines the fundamental technical concepts for software services over electronic networks, e.g., Web services and, most recently, Cloud services. For the provision of software services to customers, software service providers (SPs) have to allocate their scarce computational resources (i.e., hardware and software) of a certain quality to customer requests. The SOC paradigm facilitates interoperability over organizational boundaries by representing business relationships on the software system level. Composite software services aggregate multiple software services into software applications. This aggregation is denoted as service composition. The loose coupling of services leads to SNs as dynamic entities with changing interdependencies between services. For composite software services, these dependencies exist across SN tiers; they result from the procurement of services, which are themselves utilized to produce additional services, and constitute a major problem for resource allocation in SNs. If these dependencies are not considered, the fulfillment of agreements may become unaccomplishable (overcommitment). Hence, the consideration of service dependencies is crucial for the allocation of service providers resources to fulfill customer requests in SNs. However, existing resource allocation methods, which could consider these dependencies -- such as combinatorial auctions with a central auctioneer for the whole SN -- are not applicable, since there are no central coordinating entities in SNs. The application of an allocation mechanism that does not consider these dependencies might negatively affect the actual service delivery; results are penalty payments as well as a damage to the reputation of the providers. This research is conducted in accordance to the design science paradigm in information system research. It is a problem-solving paradigm, which targets the construction and evaluation of IT artifacts. The objectives of this research are to develop and evaluate an allocation protocol, which can consider multi-tier service dependencies without the existence of central coordinating entities. Therefore, an interaction protocol engineering (IPE) perspective is applied to solve the problem of multi-tier dependencies in resource allocation. This approach provides a procedure model for designing interaction protocols for multiagent systems, and is closely related to the well-established area of communication protocol engineering. Automated resource allocation in SNs is analyzed in this research by representing the actors as autonomous software agents in the software system. The actors delegate their objectives to their software agents, which conduct the negotiations for service provision on their behalf. Thus, these agents communicate concerning the resource allocation; in this process, the sequence of communication interactions is crucial to the problem addressed. Interaction protocols define a structured exchange of defined messages between agents; they facilitate agent conversations. When multiple agents have to reach agreements by negotiation and bargaining, such as in case with allocating scarce resources, game theory provides means to formalize and analyze the most rational choice of actions for the interacting agents. Based on a formal framework for resource allocation in SNs, this research first performs a game-theoretic problem analysis; it is concerned with the existence, as well as the complexity of computing optimal allocations. In addition, Nash equilibria are analyzed for optimal allocations. Second, a distributed, auction-based allocation protocol, which prevents overcommitments and guarantees socially optimal allocations for single customer requests under certain assumptions, is proposed. Therefore, a game-theoretic model and an operationizable specification of the protocol are presented. Third, it is formally verified that the protocol enables multi-tier resource allocation and avoids overcommitments by proofs for the game-theoretic model and by model checking for the interaction protocol specification; using the model checker Spin, safety properties like the absence of deadlock are as well formally verified as the protocol enabling multi-tier resource allocation. Fourth, the efficacy and the benefits of the proposed protocol are demonstrated by multiagent simulation for concurrent customers. The experimental evaluation provides evidence of the protocols efficiency compared to the socially optimal allocation as a centralized benchmark in different settings, e.g., network topologies and different bidding policies.
Smarte Städtebauliche Objekte für eine adaptive Stadt : ein Verfahren der Künstlichen Intelligenz zur Erhöhung der Wohlfahrt
(2021) Hubl, Marvin; Kirn, Stefan
The objective of the thesis is the advancement of urban areas with intelligent information technology to enhance urban life. In doing so, social inclusion of people with motor impairments is of particular interest. At this, an important group is the set of older adults. The aspired advancement aims at enabling self-determined participation in urban life, and hence in social life, up until old age: Participation in social life essentially depends on the opportunities for self-determined exertion of outdoor activities. Motor impairments in old age lead to a perceived significant reduction of safety in urban areas and hence concerned people are worried of using the urban area. To counteract the resulting avoidance of outdoor activities the thesis pursues the approach to transform urban objects by means of technologies of the Internet of Things into novel so-called Smart Urban Objects that actively provide support in outdoor activities. Smart Urban Objects are equipped with sensors, actuators and information processing capabilities and can adapt to individual requirements of pedestrians. Due to age-correlated motor impairments, there are for example special requirements for seating. Besides the information technological transformation of single urban objects, there are furthermore important requirements for networked Smart Urban Objects. By means of intelligently coordinated, goal-oriented availability of the supportive functionalities of single Smart Urban Objects, the urban area as overall system is enabled for adaptivity with respect to pedestrians requirements. The thesis studies the conception for an adaptive city with a safety-engineering approach at the example of smart seating and develops a method for an intelligent coordination of the networked Smart Urban Objects. For an accurate allocation of single smart seats as public objects with respect to individual requirements a welfare criterion is applied which shall avoid unfairness. Using methods of Artificial Intelligence the thesis develops a heuristic procedure for finding a solution according to the welfare criterion. This implements aspects of the theory of justice by John Rawls that underlie the welfare criterion for the example of the urban area. A scenario-based simulation substantiates that the developed solution approach can effectively enhance the safety-oriented welfare in the urban area.