Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Fast core pricing algorithms for path auction

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

Path auction is held in a graph, where each edge stands for a commodity and the weight of this edge represents the prime cost. Bidders own some edges and make bids for their edges. The auctioneer needs to purchase a sequence of edges to form a path between two specific vertices. Path auction can be considered as a kind of combinatorial reverse auctions. Core-selecting mechanism is a prevalent mechanism for combinatorial auction. However, pricing in core-selecting combinatorial auction is computationally expensive, one important reason is the exponential core constraints. The same is true of path auction. To solve this computation problem, we simplify the constraint set and get the optimal set with only polynomial constraints in this paper. Based on our constraint set, we put forward two fast core pricing algorithms for the computation of bidder-Pareto-optimal core outcome. Among all the algorithms, our new algorithms have remarkable runtime performance. Finally, we validate our algorithms on real-world datasets and obtain excellent results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. We use \(v_i \rightarrow v_j\) to represent the path from \(v_i\) to \(v_j\) in the preceding text.

  2. Notice that \(P_w(v_0,v_{s_1})\) may be a subpath from \(v_0\) to \(v_0\) when \(s_1 =0\), and so is \(P_w(v_{t_m},v_n)\).

  3. The algorithm is used by the package nexworkx 2.1, we didn’t use the multi-source shortest path algorithm because that actually networkx 2.1 achieves the multi-source algorithm by calling single-source algorithm many times.

  4. In the experiment, the algorithm we use is actually SPFA algorithm, it is an improved version of Bellman–Ford algorithm.

  5. http://www.weiboyi.com/.

  6. \(p_{e_i} \ge c_{e_i}\) according to CCG-SET.

References

  1. Archer, A., & Tardos, É. (2007). Frugal path mechanisms. ACM Transactions on Algorithms (TALG), 3(1), 3.

    Article  MathSciNet  MATH  Google Scholar 

  2. Ausubel, L. M., & Milgrom, P. R. (2002). Ascending auctions with package bidding. Advances in Theoretical Economics, 1(1), 1–42.

    Article  MathSciNet  Google Scholar 

  3. Ausubel, L. M., Milgrom, P., et al. (2006). The lovely but lonely Vickrey auction. Combinatorial Auctions, 17, 22–26.

    Google Scholar 

  4. Bünz, B., Seuken, S., & Lubin, B. (2015). A faster core constraint generation algorithm for combinatorial auctions. In Twenty-Ninth AAAI conference on artificial intelligence (pp. 827–834).

  5. Bünz, B., Lubin, B., & Seuken, S. (2018). Designing core-selecting payment rules: A computational search approach. In Proceedings of the 2018 ACM conference on economics and computation (pp. 109–109). ACM.

  6. Cheng, H., Zhang, L., Zhang, Y., Wu, J., & Wang, C. (2018). Optimal constraint collection for core-selecting path mechanism. In Proceedings of the 17th international conference on autonomous agents and multiagent systems (pp. 41–49).

  7. Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 11(1), 17–33.

    Article  Google Scholar 

  8. Cramton, P. (2013). Spectrum auction design. Review of Industrial Organization, 42(2), 161–190.

    Article  Google Scholar 

  9. Day, R., & Milgrom, P. (2013). Optimal incentives in core-selecting auctions. In The handbook of market design (Chap. 11, pp. 282–298). OUP Oxford.

  10. Day, R., & Milgrom, P. (2008). Core-selecting package auctions. International Journal of Game Theory, 36(3–4), 393–407.

    Article  MathSciNet  MATH  Google Scholar 

  11. Day, R. W., & Cramton, P. (2012). Quadratic core-selecting payment rules for combinatorial auctions. Operations Research, 60(3), 588–603.

    Article  MathSciNet  MATH  Google Scholar 

  12. Day, R. W., & Raghavan, S. (2007). Fair payments for efficient allocations in public sector combinatorial auctions. Management Science, 53(9), 1389–1406.

    Article  MATH  Google Scholar 

  13. Du, Y., Sami, R., & Shi, Y. (2010). Path auctions with multiple edge ownership. Theoretical Computer Science, 411(1), 293–300.

    Article  MathSciNet  MATH  Google Scholar 

  14. Elkind, E., Sahai, A., & Steiglitz, K. (2004). Frugality in path auctions. In Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms (pp. 701–709). Society for Industrial and Applied Mathematics

  15. Erdil, A., & Klemperer, P. (2010). A new payment rule for core-selecting package auctions. Journal of the European Economic Association, 8(2–3), 537–547.

    Article  Google Scholar 

  16. Feigenbaum, J., Papadimitriou, C., Sami, R., & Shenker, S. (2005). A BGP-based mechanism for lowest-cost routing. Distributed Computing, 18(1), 61–72.

    Article  MATH  Google Scholar 

  17. Grötschel, M., Lovász, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2), 169–197.

    Article  MathSciNet  MATH  Google Scholar 

  18. Groves, T., et al. (1973). Incentives in teams. Econometrica, 41(4), 617–631.

    Article  MathSciNet  MATH  Google Scholar 

  19. Hartline, J., Immorlica, N., Khani, M.R., Lucier, B., & Niazadeh, R. (2018). Fast core pricing for rich advertising auctions. In Proceedings of the 2018 ACM conference on economics and computation (pp. 111–112). ACM.

  20. Hershberger, J., & Suri, S. (2001). Vickrey prices and shortest paths: What is an edge worth? In Proceedings 42nd IEEE symposium on foundations of computer science (pp. 252–259). IEEE.

  21. Karger, D., & Nikolova, E. (2006). On the expected VCG overpayment in large networks. In Proceedings of the 45th IEEE conference on decision and control (pp. 2831–2836).

  22. Karlin, A.R., Kempe, D., & Tamir, T. (2005). Beyond VCG: Frugality of truthful mechanisms. In 46th annual IEEE symposium on foundations of computer science (FOCS’05) (pp. 615–626). IEEE.

  23. Lee, Y. T., Sidford, A., & Wong, S. C. W. (2015). A faster cutting plane method and its implications for combinatorial and convex optimization. In 56th annual symposium on foundations of computer science (pp. 1049–1065). IEEE.

  24. Lehmann, D., Oćallaghan, L. I., & Shoham, Y. (2002). Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM (JACM), 49(5), 577–602.

    Article  MathSciNet  MATH  Google Scholar 

  25. Leskovec, J., & Krevl, A. (2014, June). SNAP datasets: Stanford large network dataset collection. http://snap.stanford.edu/data/.

  26. Nisan, N., & Ronen, A. (1999). Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on theory of computing (pp. 129–140). ACM.

  27. Polymenakos, L., & Bertsekas, D. P. (1994). Parallel shortest path auction algorithms. Parallel Computing, 20(9), 1221–1247.

    Article  MathSciNet  MATH  Google Scholar 

  28. Rothkopf, M. H., Pekeč, A., & Harstad, R. M. (1998). Computationally manageable combinational auctions. Management science, 44(8), 1131–1147.

    Article  MATH  Google Scholar 

  29. Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1), 8–37.

    Article  MathSciNet  Google Scholar 

  30. Yokoo, M., Sakurai, Y., & Matsubara, S. (2004). The effect of false-name bids in combinatorial auctions: New fraud in internet auctions. Games and Economic Behavior, 46(1), 174–188.

    Article  MathSciNet  MATH  Google Scholar 

  31. Zhang, L., Chen, H., Wu, J., Wang, C. J., & Xie, J. (2016). False-name-proof mechanisms for path auctions in social networks. In ECAI (pp. 1485–1492).

  32. Zhu, Y., Li, B., Fu, H., & Li, Z. (2014). Core-selecting secondary spectrum auctions. IEEE Journal on Selected Areas in Communications, 32(11), 2268–2279.

    Article  Google Scholar 

Download references

Acknowledgements

This paper is supported by the National Key Research and Development Program of China (Grant No. 2018YFB1403400), the National Natural Science Foundation of China (Grant No. 61876080), the Collaborative Innovation Center of Novel Software Technology and Industrialization at Nanjing University.

Author information

Authors and Affiliations

  1. National Key Laboratory for Novel Software Technology, Department of Computer Science and Technology, Nanjing University, Nanjing, China

    Hao Cheng, Wentao Zhang, Yi Zhang, Lei Zhang, Jun Wu & Chongjun Wang

Authors
  1. Hao Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wentao Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yi Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lei Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jun Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Chongjun Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hao Cheng.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Part of the contents in this paper were published in AAMAS ’18 [6].

Appendices

Appendix A: Summary of main notation

\(G=(V,E)\) :

A directed graph that consists of a edge set E and a vertex set V

\(v_0\) :

The starting vertex

\(v_n\) :

The ending vertex

\(e_i= (v_{i-1},v_i)\) :

The edge that starts in the vertex \(v_{i-1}\) and ends in \(v_{i}\), also represents a bidder owning edge \(e_i\)

\(c_{e_i}\) :

The cost of the edge \(e_i\)

\(\pi _{e_i}\) :

The utility of the bidder \(e_i\)

\(\Pi\) :

Social welfare of the auction

0:

The auctioneer

N :

The total set of players, including the bidders and auctioneer

W(L):

The social welfare of the subset L of N

P :

The payment set of the auction

\(p_{e_i}\) :

The payment to the bidder \(e_i\)

\(\text {core}\) :

The total set of core outcomes

\(W_G(v_i,v_j)\) :

A walk from \(v_i\) to \(v_j\) in graph G

\(P_G(v_i,v_j)\) :

The shortest path from \(v_i\) to \(v_j\) in graph G

\(V_G(v_i,v_j)\) :

The vertex set of \(P_G(v_i,v_j)\)

\(E_G(v_i,v_j)\) :

The edge set of \(P_G(v_i,v_j)\)

\(P_w(v_0,v_n)\) :

The path that is selected as the winner path in the auction

\(E_w(v_0,v_n)\; or\; E_w\) :

The edge set of \(P_w(v_0,v_n)\)

\(V_w(v_0,v_n)\; or\; V_w\) :

The vertex set of \(P_w(v_0,v_n)\)

\(P_w(v_i,v_j)\) :

A subpath of \(P_w(v_0,v_n)\) that is from \(v_i\) to \(v_j\)

\(E_w(v_i,v_j)\) :

The edge set of \(P_w(v_i,v_j)\)

\(V_w(v_i,v_j)\) :

The vertex set of \(P_w(v_i,v_j)\)

\(d_G(v_i,v_j)\) :

The cost of the shortest path from \(v_i\) to \(v_j\) in graph G

Appendix B: Proof of the correctness of CCG-VCG algorithm for path auction

Theorem 15

The outcome of CCG-VCG algorithm is a bidder-Pareto-optimal core outcome.

Proof

Consider the constraint added into CCG-SET

$$\begin{aligned} \sum _{e_i \in E_w \backslash z}p_{e_i} \le \sum _{e_i \in E_{w'} \backslash z}c_{e_i} \end{aligned}$$
(65)

\(E_{w'}\) is the new winner set in a new graph where we change the cost of each edge in \(E_w\) from \(p^{t-1}_{e_i}\) to \(p^{t}_{e_i}\) in G. Denote by \(G_1\) this graph and \(P_{w'}\) the path corresponding to the edge set \(E_{w'}\). \(P_{w'}\) is the shortest path in \(G_1\). We first prove that the constraint (65) is a standard constraint of (C1).

In \(G_1\), we remove the edges in \(E_w \backslash z\) and change the costs of the edges in z from \(p^{t}_{e_i}\) to \(c_{e_i}\). Denote by \(G_2\) this graph. \(P_{w'}\) also exists in \(G_2\) because it doesn’t include any edge in \(E_w \backslash z\). Compared with \(G_1\), the cost of \(P_{w'}\) reduces by \(\sum _{e_i\in z}p^t_{e_i} - c_{e_i}\)Footnote 6 in \(G_2\). As to other paths in \(G_2\), their costs reduce by \(\sum _{e_i\in z}p^t_{e_i} - c_{e_i}\) at most, so \(P_{w'}\) is also the shortest path in \(G_2\). Note that \(G_2\) is just the graph \(G\backslash (E_w \backslash z)\), from the constraint (65), we have

$$\begin{aligned} \sum _{e_i \in E_w \backslash z}p_{e_i}&\le \sum _{e_i \in E_{w'} \backslash z}c_{e_i}\\&= d_{G_2}(v_0,v_n) - \sum _{e_i\in z}c_{e_i}\\&= d_{G\backslash (E_w\backslash z)}(v_0,v_n)- \sum _{e_i\in z}c_{e_i} \end{aligned}$$
(66)

Recall the constraint in (C1) as

$$\begin{aligned} (C1):\sum _{e_i \in x}p_{e_i} \le d_{G\backslash x}(v_0,v_n) - (d_G(v_0,v_n) -\sum _{e_i\in x}c_{e_i}),\forall x\in E_w \end{aligned}$$
(67)

Let \(x= E_w\backslash z\), we have

$$\begin{aligned} \sum _{e_i \in E_w\backslash z}p_{e_i}&\le d_{G\backslash (E_w\backslash z)}(v_0,v_n) - \left(d_G(v_0,v_n) -\sum _{e_i\in (E_w\backslash z)}c_{e_i}\right)\\&= d_{G\backslash (E_w\backslash z)}(v_0,v_n) - \sum _{e_i\in z}c_{e_i} \end{aligned}$$
(68)

The constraint (68) is (C1) is just the same as the constraint (66), so the constraint we add into CCG-SET during each iteration is a standard constraint of (C1). Then the constraint set CCG-SET is a subset of the constraint set (C1). In each iteration, CCG-VCG algorithm adds a constraint of (C1). The number of constraints in (C1) is limited so that this algorithm must stop in a limited number of steps.

To prove the theorem, we just need to prove that the outcome of CCG-VCG algorithm is in the core. Assuming that the outcome of CCG-VCG algorithm isn’t in the core. Thus, there is at least one constraint in (C1) which is not satisfied by this result. Without loss of generality, let \(x=E_w\backslash z'\) is the corresponding set, then the constraint becomes

$$\begin{aligned} \sum _{e_i \in E_w\backslash z'}p_{e_i}&> d_{G\backslash (E_w\backslash z')}(v_0,v_n) - \left(d_G(v_0,v_n) -\sum _{e_i\in (E_w\backslash z')}c_{e_i}\right)\\&= d_{G\backslash (E_w\backslash z)}(v_0,v_n) - \sum _{e_i\in z}c_{e_i} \end{aligned}$$
(69)

Then we have

$$\begin{aligned} \sum _{e_i \in E_w}p_{e_i}&= \sum _{e_i \in E_w\backslash z'}p_{e_i} +\sum _{e_i \in z'}p_{e_i}\\&> d_{G\backslash (E_w\backslash z)}(v_0,v_n)+\sum _{e_i \in z'}p_{e_i}-\sum _{e_i \in z'}c_{e_i} \end{aligned}$$
(70)

where \(d_{G\backslash (E_w\backslash z)}(v_0,v_n)\) is the cost of the shortest path from \(v_0\) to \(v_n\) in graph \(G\backslash (E_w\backslash z)\). This path still exists in graph which changes the cost of edges in \(E_w\) from \(c_{e_i}\) to \(p_{e_i}\). This change makes the cost of this path increase by \(\sum _{e_i \in z'}p_{e_i}-\sum _{e_i \in z'}c_{e_i}\) at most. So the cost of this path is no more than \(d_{G\backslash (E_w\backslash z)}(v_0,v_n)+\sum _{e_i \in z'}p_{e_i}-\sum _{e_i \in z'}c_{e_i}\), which means it is shorter than the sum of outcome in CCG-VCG algorithm. This produces a contradiction with terminal condition in CCG-VCG algorithm, so this theorem is established. \(\square\)

Appendix C: Proof of Theorem 9

Proof

In \(G'\), the edge in \(E_w\) is converted into a reverse edge with negative original cost. As we know, each edge is not cut edge for the connectivity from \(v_0\) to \(v_n\), that is, there exist a path from \(v_0\) to \(v_n\) after removing this edge in graph G. We use the mathematical induction by proving the following two propositions.

  1. 1.

    There exist a path from \(v_0\) to \(v_1\) in \(G'\).

  2. 2.

    If there exists a path from \(v_0\) to \(v_i\) in \(G'\), then there exists a path from \(v_0\) to \(v_{i+1}\) in \(G'\) (\(0< i < n\)).

It is obvious that Theorem 9 is established if these two propositions is correct. Note that \(V_w(v_1,v_n)\) is the vertex set including \(v_1, v_2,\dots , v_n\). In proposition 1, since \((v_0,v_1)\) is not a cut edge, there must exist a path from \(v_0\) to any vertex of \(V_w(v_1,v_n)\) in the graph \(G\backslash E_w\). Otherwise, there will not exist a path from \(v_0\) to any vertex of \(V_w(v_1,v_n)\) in graph \(G\backslash (v_0,v_1)\), this is because compared with \(G\backslash E_w\), the extra edges in \(G\backslash (v_0,v_1)\) is useless for the connectivity between \(\{v_0 \}\) and \(V_w(v_1,v_n)\). This means \((v_0,v_1)\) is a cut edge, which is contradictory. Therefore, there exists a path from \(v_0\) to any vertex of \(V_w(v_1,v_n)\) in \(G\backslash E_w\). This path also exists in \(G'\) and once this path could arrive at any vertex of \(V_w(v_1,v_n)\) from \(v_0\), it could arrive at \(v_1\) along the negative edges in \(G'\). Thus, proposition 1 is true.

In proposition 2, since there exists a path from \(v_0\) to \(v_i\) in \(G'\), we can arrive at any vertex of \(V_w(v_0,v_i)\) by just lengthening this path along the negative edges. Based on that \((v_i,v_{i+1})\) is not a cut edge, similarly, we can draw a conclusion that there exists a path from any vertex of \(V_w(v_0,v_i)\) to any vertex of \(V_w(v_{i+1},v_n)\). Then there also exists a path from any vertex of \(V_w(v_0,v_i)\) to any vertex of \(V_w(v_{i+1},v_n)\) in \(G'\). Denote these two vertices by \(v_a,v_b\) and we have a path from \(v_0\) to \(v_{i+1}\) as \(v_0 \rightarrow v_i \rightarrow v_a \rightarrow v_b \rightarrow v_{i+1}\), like Fig. 12. Therefore, proposition 2 is proved.

Fig. 12
figure 12

Path \(v_0 \rightarrow v_i \rightarrow v_a \rightarrow v_b \rightarrow v_{i+1}\)

Full size image

Above all, Theorem 9 is established. \(\square\)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cheng, H., Zhang, W., Zhang, Y. et al. Fast core pricing algorithms for path auction. Auton Agent Multi-Agent Syst 34, 18 (2020). https://doi.org/10.1007/s10458-019-09440-y

Download citation

  • Published:

  • DOI: https://doi.org/10.1007/s10458-019-09440-y

Keywords

Search

Navigation