Multi-agent resource allocation

The multi-agent resource allocation or resource allocation in multi-agent systems (Multiagent Resource Allocation (MARA)) is about the distribution of resources among competing agents .

This article follows the assumption, as is common in the literature, that resources are indivisible. I.e. Resources are indivisible, so they cannot be broken down into smaller pieces and they cannot be used jointly.

Multi-agent resource allocation is a branch of the still young discipline Computational Social Choice, which primarily deals with the algorithmic aspects of game and social choice theory.

Allocation procedures

Allocation procedures can be divided into centralized and distributed. In a distributed allocation procedure resulting allocations from a number of local negotiating steps. An example of a distributed allocation procedure is the cake cutting protocol .

In the case of a centralized allocation procedure, the distribution of the goods takes place via a central entity, e.g. B. the auctioneer at an auction . The auctioneer can distribute the resources based on the preferences of the agents or their bids.

Division of individual goods

Divorce formula

One way to divide goods is the so-called discrimination formula (engl. Adjusted Winner Procedure ) by Steven Brams and Alan D. Taylor . The goods to be divided are evaluated by the parties concerned according to their subjective perception (a total of 100 points can be awarded) and distributed on the basis of this evaluation. In the event of an imbalance, the beneficiary must cede objects until compensation occurs. The order of the goods to be surrendered results from the relative valuations of the individual goods; these are sorted in ascending order with the condition that the ratio is at least 1. This means that first of all the objects are considered for which the profit / loss ratio is the smallest, i.e. the parties are most likely to agree.

The advantages of the divorce formula are that the result achieved is Pareto-optimal , evenly distributed and free of envy.

Single auctions

In the case of individual auctions, the objects are auctioned off individually to the bidders. From the auctioneer's point of view, the aim of an auction is to achieve the highest possible revenue for the object, whereas the agent (bidder) wants to pay the lowest possible price. Bidders are in competition with each other. There are a number of different auctions which, by their nature, allow different strategies for the bidders.

Of interest are e.g. B .:

• English auction
• Vickrey auction
• Dutch auction
• American auction

In most cases, determining the winner is very simple: only the highest bid has to be determined; if there is a tie, u. U. to apply a preferential rule.

Division of bundles of goods

In contrast to the individual auctions, whole bundles of goods are now offered.

Multi-agent resource allocation Starting position

A multi-agent resource allocation starting position denotes a triple , whereby ${\displaystyle \textstyle ({\mathcal {A}},{\mathcal {R}},{\mathcal {U}})}$

${\displaystyle \textstyle {\mathcal {A}}=\{1,2,...,n\}}$ is a lot of agents

${\displaystyle \textstyle {\mathcal {R}}=\{r_{1},r_{2},...,r_{m}\}}$ a lot of resources is and

${\displaystyle \textstyle {\mathcal {U}}=\{u_{1},u_{2},...,u_{n}\}}$is a set of utility functions, describes the utility function of the i-th agent, with . ${\displaystyle \textstyle u_{i}}$ ${\displaystyle \textstyle u_{i}:2^{\mathcal {R}}\rightarrow \mathbb {Q} }$

Bundle shape

In the case of the bundle form , each bundle other than zero is enumerated in the form of a tuple . There can be an exponential number of tuples. ${\displaystyle \textstyle B\subseteq {\mathcal {R}}}$ ${\displaystyle \textstyle (B,u_{i}(B))}$

k-additive form

With the k-additive form, it can be possible to achieve a more compact representation by utilizing regularities.

${\displaystyle \textstyle u_{i}(B)=\sum _{T\subseteq R}a_{i}^{T}}$

T is a bundle, it holds , d. H. the maximum bundle size is limited upwards by k . ${\displaystyle \textstyle \left\|T\right\|\leq k}$

The expressiveness of the bundle form and the k-additive form are not comparable; for both it can be shown that one form requires an exponential number of tuples or coefficients in extreme cases, while the other form only requires many. (see also ). ${\displaystyle \textstyle \left\|R\right\|}$

Social welfare

→ Main article : Welfare function

→ Main article : Bergson-Samuelson welfare function

The social welfare (ger .: social welfare) is an efficiency measure.

Utilitarian SWF

The utilitarian social welfare describes the summed up benefits of all agents. She is z. Of interest to determine the average utility of the agents or to determine the maximum return of the auctioneer.

${\displaystyle \textstyle sw_{u}(X)=\sum _{a_{j}\in A}u_{j}(X)}$

Egalitarian

In the case of egalitarian social welfare, the utility of the agent who "got away" worst is determined. This type of determination is e.g. B. interesting in the distribution of humanitarian goods.

${\displaystyle \textstyle sw_{e}(X)=\operatorname {min} \{u_{j}(X)|a_{j}\in A\}}$

Nash SWF

The Nash product represents a compromise between the two previous welfare benefits. The value is maximum when all agents have the same benefit. Only positive benefits are useful.

${\displaystyle \textstyle sw_{N}(X)=\prod _{a_{j}\in A}u_{j}(X)}$

Individual evidence

1. ↑ ^{a b} Y. Chevaleyre et al. Issues in Multiagent Resource Allocation. In: Informatica. Issue 1, Vol. 30 2006
2. ↑ Y. Chevaleyre et al. Multiagent resource allocation in k-additive domains: preference representation and complexity doi: 10.1007 / s10479-008-0335-0 , 2008

literature

• Jörg Rothe, Dorothea Baumeister, Claudia Lindner, Irene Rothe. Introduction to Computational Social Choice: Individual strategies and collective choices in playing, voting and sharing . Spectrum Academic Publishing House. ISBN 978-3-8274-2570-6
• Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution . Cambridge University Press. ISBN 0-521-55390-3