×

A simple algorithm for the nucleolus of airport profit games. (English) Zbl 1126.91004

This paper studies a cooperative game problem in the characteristic function form induced by a model described by \(\left( N,\preceq ,C,b\right) \) where \(N\) is a finite non-empty set, \(\preceq \) is a total order relation on \(N,\) \(C:N\rightarrow \mathbb R_{+}\) is non-decreasing, i.e., \(i\preceq j\) implies \( C\left( i\right) \leq C\left( j\right) ,\) and \(b\in \mathbb R_{++}^{N}.\) The problem could be interpreted as one of sharing the cost of construction of an airport landing strip. \(N\) is the set of agents. Every agent \(i\) wishes to implement a project (runway strip) whose cost of construction is \( C\left( i\right) \) with the understanding that if \(i\preceq j\) the project (runway strip) of agent \(j\) is an extension of the project of \(i\) and that is why \(C\left( i\right) \leq C\left( j\right) .\) If the project of \(i\) is carried out then that player receives a revenue \(b_{i}>0.\)
For a vector \(x\in \mathbb R^{N}\) and a coalition \(S\subset N,S\neq \emptyset ,\) write \(x^{S}\) for the restriction of \(x\) to \(R^{S}\) and \(x\left( S\right) =\sum_{i\in S}x_{i}.\) Similarly \(b\left( S\right) \) denotes the total revenue of the members of \(S\). Let \(C\left( S\right) \equiv \max \left\{ C\left( i\right) :i\in S\right\} ,\) with \(C\left( \emptyset \right) =0,\) which represents the cost of attending to the needs of the coalition \(S.\)
Define the transferable utility game \(\left( N,v^{\left( N,\preceq ,C,b\right) }\right) \) by defining the characteristic function \(v^{\left( N,\preceq ,C,b\right) }\) as follows. \[ v^{\left( N,\preceq ,C,b\right) }\left( S\right) \equiv \max \left\{ b\left( R\right) -C\left( R\right) :R\subset S\right\} ,\text{ for each }S \subset N \] The value of a coalition \(v^{\left( N,\preceq ,C,b\right) }\left( S\right) \) represents the profits obtained by coalition \(S\).
The paper determines an algorithm to calculate the nucleolus of such games based on maximal excesses of coalitions and a sequence airport problems each of which is a suitably restricted version of the previous problem.

MSC:

91A12 Cooperative games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arin J, Iñarra E (1998) On the nucleolus of convex games. Games Econ Behav 23:12–24 · Zbl 0911.90363 · doi:10.1006/game.1997.0601
[2] Davis M, Maschler M (1965) The kernel of a cooperative game. Naval Res Logist Q 12:223–259 · Zbl 0204.20202 · doi:10.1002/nav.3800120303
[3] Dubey P (1982) The Shapley value as aircraft landing fees-revisited. Manag Sci 28:869–874 · Zbl 0487.90093 · doi:10.1287/mnsc.28.8.869
[4] Littlechild SC (1974) A simple expression for the nucleolus in a special case. Int J Game Theory 3:21–29 · Zbl 0281.90108 · doi:10.1007/BF01766216
[5] Littlechild SC, Owen G (1973) A simple expression for the Shapley value in a special case. Manag Sci 20:370–372 · Zbl 0307.90095 · doi:10.1287/mnsc.20.3.370
[6] Littlechild SC, Owen G (1977) A further note on the nucleolus of the airport game. Int J Game Theory 5:91–95 · Zbl 0348.90191 · doi:10.1007/BF01753311
[7] Littlechild SC, Thompson GF (1977) Aircraft landing fees: a game theory approach. Bell J Econ 8:186–204 · doi:10.2307/3003493
[8] Potters J, Sudhölter P (1999) Airport problems and consistent allocation rules. Math Soc Sci 38:83–102 · Zbl 1111.91310 · doi:10.1016/S0165-4896(99)00004-9
[9] Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17:1163–1170 · Zbl 0191.49502 · doi:10.1137/0117107
[10] Shapley LS (1953). A value for n-person game. In: Kuhn HW, Tucker AW (eds). Contributions to the theory of games II in Annals of Mathematic Studies, vol 28. Princeton University Press, Princeton, pp. 307–317
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.