A simple algorithm for the nucleolus of airport profit games (Q2501071)

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.