Cost sharing on prices for games on graphs

Daniel Li Li () and Erfang Shan ()
Additional contact information
Daniel Li Li: Shanghai University
Erfang Shan: Shanghai University

Journal of Combinatorial Optimization, 2017, vol. 34, issue 3, No 2, 676-688

Abstract: Abstract Let $$N=\{1,\dots ,n\}$$ N = { 1 , ⋯ , n } be a set of customers who want to buy a single homogenous goods in market. Let $$q_i>0$$ q i > 0 be the quantity that $$i\in N$$ i ∈ N demands, $$q=(q_1,\dots ,q_n)$$ q = ( q 1 , ⋯ , q n ) and $$q_S=\sum _{i\in S}q_i$$ q S = ∑ i ∈ S q i for $$S\subseteq N$$ S ⊆ N . If f(s) is a (increasing and concave) cost function, then it yields a cooperative game (N, f, q) by defining characteristic function $$v(S)=f(q_S)$$ v ( S ) = f ( q S ) for $$S\subseteq N$$ S ⊆ N . We now consider the way of taking packages of goods by customers and define a communication graph L on N, in which i and j are linked if they can take packages for each other. So if i and j are connected, then a package can be delivered from i to j by some intermediators. We thus admit any connected subset as a feasible coalition, and obtain a game (N, f, q, L) by defining characteristic function $$v_L(S)=\sum _{R\in S/L}f(q_R)$$ v L ( S ) = ∑ R ∈ S / L f ( q R ) for $$S\subseteq N$$ S ⊆ N , where S / L is the family of induced components (maximal connected subset) in S. It is shown that there is an allocation (cost shares) $$x=(x_1,\dots ,x_n)$$ x = ( x 1 , ⋯ , x n ) from the core for the game ( $$x_S\le v_L(S)$$ x S ≤ v L ( S ) for any $$S\subseteq N$$ S ⊆ N ) such that x satisfies Component Efficiency and Ranking for Unit Prices. If f(s) and q satisfy some further condition, then there is an allocation x from the core such that x satisfies Component Efficiency, and $$x_i \le x_j$$ x i ≤ x j and $$\frac{x_i}{q_i} \ge \frac{x_j}{q_j}$$ x i q i ≥ x j q j if $$q_i \le q_j$$ q i ≤ q j for i and j in the same component of N.

Keywords: Cooperative game; Graph game; Cost sharing; Ranking; Unit price; 91A12; 91A43; 05C57 (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0099-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:3:d:10.1007_s10878-016-0099-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0099-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().