Abstract
Suppose that a group of agents have demands for some good. Every agent owns a technology which allows them to produce the good, with these technologies varying in their effectiveness. If all technologies exhibit increasing returns to scale (IRS) then it is always efficient to centralize production of the good, whereas efficiency in the case of decreasing returns to scale (DRS) typically requires to spread production. We search for stable cost allocations while differentiating allocations with homogeneous prices, in which all units produced are traded at the same price, from allocations with heterogeneous prices. For the respective cases of IRS or DRS, it is shown that there always exist stable cost sharing rules with homogeneous prices. Finally, in the general framework (under which there may exist no stable allocation at all) we provide a sufficient condition for the existence of stable allocations with homogeneous prices. This condition is shown to be both necessary and sufficient in problems with unitary demands.
Similar content being viewed by others
Notes
Efficiency and individual rationality require that \(y_{i}^{pr}(x,C)=0\) whenever \(X=0\).
If many agents i have the lowest marginal cost, the algorithm may produce a different outcome depending on which one we pick; however, these outcomes all result in the same (minimum) cost and the same cost allocation—see Eq. (2).
Since \(\sum \nolimits _{i\in N}\bar{q}^X_i=\sum \nolimits _{i\in N}x_i=X\), note that we have: \({\mathcal {D}}\ne \emptyset \Leftrightarrow {\mathcal {P}}\ne \emptyset .\)
Such an agent always exists because N is a finite set. And even though we may have many such agents, our results apply regardless of which one is picked.
Note that \(y^{p}\) is a well-defined cost allocation. Indeed, since \( \sum \nolimits _{i\in N}y_{i}^{p}=C_{i^{*}}(X)\), it satisfies efficiency.
The cost function \(\hat{C}^x\) is optimistic in the sense that it implicitly assigns to a coalition the incremental cost of adding its demand to that of other players, when everybody has access to all technologies.
In case there are multiple efficient production plans, our results hold regardless of which one is picked.
References
Anderson RM (1992) The core in perfectly competitive economies. In: Aumann RJ, Hart S (eds) Handbook of game theory with economic applications, vol 1. Elsevier, New York, pp 413–457
Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J Comput 38:1602–1623
Bahel E, Trudeau C (2013) A discrete cost sharing model with technological cooperation. Int J Game Theory 42:439–460
Bahel E, Trudeau C (2014) Stable lexicographic rules for shortest path games. Econ Lett 125:266–269
Bergantinos G, Vidal-Puga J (2007) A fair rule in minimum cost spanning tree problems. J Econ Theory 137:326��352
Bird CJ (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6:335–350
Camiña E (2006) A generalized assignment game. Math Soc Sci 52:152–161
Crawford VP, Knoer EM (1981) Job matching with heterogeneous firms and workers. Econometrica 49:437–450
Gillies DB (1953) Some theorems on n-person games. Ph.D. Thesis, Department of Mathematics, Princeton University
Jaume D, Massó J, Neme A (2016) The multiple-partners assignment game with heterogeneous sells and multi-unit demands: competitive equilibria. Polar Biol 39:2189–2205
Kaneko M (1976) On the core and competitive equilibria of a market with indivisible goods. Naval Res Logist 21:321–337
Moulin H (2013) Cost sharing in networks: some open questions. Int Game Theory Rev 15:1340001
Moulin H, Sprumont Y (2007) Fair allocation of production externalities: recent results. Rev d’Econ Politique 117:7–36
Núñez M, Rafels C (2002) The assignment game: the \(\tau \)-value. Int J Game Theory 31:411–422
Núñez M, Rafels C (2017) A survey on assignment markets. J Dyn Games 2:227–256
Quant M, Borm P, Reijnierse H (2006) Congestion network problems and related games. Eur J Oper Res 172:919–930
Quinzii M (1984) Core and competitive equilibria with indivisibilities. Int J Game Theory 13:41–60
Rosenthal EC (2013) Shortest path games. Eur J Oper Res 224(1):132–140
Sanchez-Soriano J, Lopez MA, Garcia-Jurado I (2001) On the core of transportation games. Math Soc Sci 41:215–225
Shapley LS (1971) Cores of convex games. Int J Game Theory 1:11–26
Shapley LS, Shubik M (1971) The assignment game I: the core. Int J Game Theory 1:9–25
Sharkey WW (1995) Network models in economics. In: Ball MO, Magnanti TL, Nonma CL, Nemhauser GL (eds) Network routing. Handbooks in operation research and management science, vol 8. Elsevier, New York, pp 713–765
Sotomayor M (1992) The multiple partners game. In: Majumdar M (ed) Equilibrium and dynamics: essays in honor to David Gale. Springer, Berlin, pp 269–283
Sotomayor M (2002) A labor market with heterogeneous firms and workers. Int J Game Theory 31:269–283
Sotomayor M (2007) Connecting the cooperative and competitive structures of the multiplepartners assignment game. J Econ Theory 134:155–174
Sprumont Y (2005) On the discrete version of the Aumann–Shapley cost-sharing method. Econometrica 73:1693–1712
Thompson GL (1981) Auctions and market games. In: Aumann R (ed) Essays in game theory and mathematical economics in Honor of Oskar Morgenstern. Princeton University Press, Princeton
Trudeau C (2009a) Cost sharing with multiple technologies. Games Econ Behav 67:695–707
Trudeau C (2009b) Network flow problems and permutationally concave games. Math Soc Sci 58:121–131
Trudeau C (2012) A new stable and more responsive cost sharing solution for minimum cost spanning tree problems. Games Econ Behav 75:402–412
Yokote K (2016) Core and competitive equilibria: an approach from discrete convex analysis. J Math Econ 66:1–13
Author information
Authors and Affiliations
Corresponding author
Additional information
The authors would like to thank two anonymous reviewers and the Editor for their useful comments and suggestions, which have helped improve the paper. The second author thanks the Social Sciences and Humanities Research Council of Canada for financial support (Ref.: 435-2014-0140). The funding agency had no involvement in the study design, in the writing of the report or in the decision to submit the article for publication.
Appendices
Appendixes
A Interpretation of a PAG as a market with indivisible goods
We show how a PAG relates to a market with indivisible goods as modeled by Kaneko (1976). While Kaneko’s model can accommodate multiple goods, we consider here a version with a single, homogeneous good. Kaneko’s model includes a set of buyers (\(N^b)\) and a set of sellers (\(N^s)\). We have an endowment for the sellers, and each seller \(i\in N^s\) has a utility function \(u_i\) such that if \(k<k'\), \(u_i(k)=u_i(k')\) if \(k\ge e_i\) and \(u_i(k)<u_i(k')\) otherwise. We have a demand vector for buyers, and each buyer \(i\in N^b\) has a utility function \(v_i\) such that if \(k<k'\), \(v_i(k)=v_i(k')\) if \(k\ge d_i\) and \(v_i(k)<v_i(k')\) otherwise. Let u and v be the sets of these utility functions. Agents are also endowed with money and \(U_i(k,l)=u_i(k)+l\) and \(V_i(k,l)=v_i(k)+l\) are the corresponding quasi-linear utility functions. A market with indivisible goods is characterized by \((N^s, N^b, e,d,u,v)\).
A competitive equilibrium is \((p,\hat{z})\), with such that
In words, the first two conditions are utility maximizing conditions, while the third ensures that the quantity sold by sellers is equal to the quantity demanded by buyers. If \((p,\hat{z})\) is a competitive equilibrium, \((u^{p,\hat{z}},v^{p,\hat{z}})\) is a competitive imputation, where \(u^{p,\hat{z}}_i=u_i(\hat{z}_i)+p(e_i-\hat{z}_i)\) for all \(i\in N^s\) and \(v^{p,\hat{z}}_i=v_i(\hat{z}_i)-p\hat{z}_i\) for all \(i\in N^b\).
For each \(S\in N^s\cup N^d\), define W(S) as
subject to \(\sum _{i\in N^s\cap S}\hat{z}_i+\sum _{i\in N^d\cap S}\hat{z}_i=\sum _{i\in N^s\cap S}e_i\). An imputation (U, V) is a core allocation (for the market with indivisible goods) if
for all \(S\subseteq N^s\cup N^b\).
Lemma 2
(Kaneko 1976) For any problem \((N^s, N^b, e,d,u,v)\), if \((p,\hat{z})\) is a competitive equilibrium, then \((u^{p,\hat{z}},v^{p,\hat{z}})\) is a core allocation.
We show that any PAG can be written as a market with indivisible goods. Start with a PAG (x, C), with the set of agents N.
We then let
-
\(N^s=N\)
-
\(N^d=\left\{ i\in N | x_i>0 \right\} \)
-
\(e=X^{N}\)
-
\(d_i=x_i\text { for all }i\in N^d\)
-
\(u_i(k)=uX-C_i(k)\text { for all }i\in N^s\)
-
\(v_i(k)=uk\text { for all }i\in N^d\)
where \(u=\max _{i\in N}\max _{q=1,\ldots ,X}c_{i}(q).\)
Let \(P^{MIG}(x,C)\) be the market with indivisible goods built from the PAG (x, C).
For any imputation (U, V), let \(y^{U,V}\) be such that
In particular, for any competitive imputation \((u^{p,\hat{z}},v^{p,\hat{z}})\), let \(y^{p,\hat{z}}\) be such that
Lemma 3
If \((U,V)\in Core(P^{MIG}(x,C))\), then \(y^{U,V}\in Core(x,C)\).
The above lemma is obtained as there are less core constraints in a PAG than in the corresponding market with an indivisible good: we only consider the coalitions that include seller i if and only if it also includes buyer i. In particular, if there exists a competitive equilibrium, the corresponding competitive imputation generates a stable allocation with homogeneous price for the PAG. Typically, the core of the PAG problem will contain more allocations than the core of the market with indivisible goods built from it.
B Counterexample: monopsony with general cost functions
In the case of a single demander (monopsony), Theorems 4 and 7 respectively show that \(Core(x,C)={\mathcal {Y}}^{ms}(x,C)\) if we have IRS or DRS. This result is not true with general cost functions: in the following example, we show that \({\mathcal {Y}}^{ms}(x,C)\) is not a subset of the core.
Suppose that \(N=\left\{ 1,2,3\right\} \) and \(x=(4,0,0)\), with the cost functions given as follows.
One can see that \(\bar{q}^{X}=\left( 2,1,1\right) \). The coalitional costs are \(\tilde{C} ^{x}(N)=40,\) \(\tilde{C}^{x}(N\backslash 2)=55,\) \(\tilde{C}^{x}(N\backslash 3)=55\) and \(\tilde{C}^{x}(N\backslash \left\{ 2,3\right\} )=55.\) It hence follows that \(p^H_2=p^H_3=15\) and \(p^L_2=p^L_3=5\).
Therefore, taking \(\mathbf p =(15,15)\) in Eq. (3), we get \(^{ms}y^\mathbf{p }=(60,-10,-10)\in {\mathcal {Y}}^{ms}(x,C)\). However, it is not difficult to argue that \(^{ms}y^\mathbf{p }=(60,-10,-10)\notin Core(x,C)\), since agent 1’s share is higher than her stand-alone cost: \(^{ms}y^\mathbf{p }_1=60>55= C_1(4)\). This shows that \(Core(x,C)\ne {\mathcal {Y}}^{ms}(x,C)\).
Rights and permissions
About this article
Cite this article
Bahel, E., Trudeau, C. Stable cost sharing in production allocation games. Rev Econ Design 22, 25–53 (2018). https://doi.org/10.1007/s10058-018-0209-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10058-018-0209-0