Abstract
Orientation: This article is related to Finances and Optimisation. The auctioneer designs every auction mechanism such that utility is maximised and cost is minimised.
Research purpose: This article proposes an optimal auction mechanism through which auctioneers can assign fairly and efficiently assets to the highest bidders and maximise utility and/or minimise cost.
Motivation for the study: One of the tasks of my PhD was about spectrum auction from which I got a vision to design mathematical models and related computational simulations for any asset underlying an auction.
Research approach/design and method: Firstly, a study was conducted to model the way auctioneers could analyse and estimate bidders’ (buyers’) valuations, and then, accordingly, set the prices of the underlying assets or services. An open ascending-bid auction mechanism was also considered. Finally, a first-price sealed-bid auction mechanism for utility maximisation and cost minimisation is investigated.
Main findings: The substantive contribution of this article is in the set of mathematical models and computational simulations designed and proposed for the bidders’ valuations and the considered open ascending-bid auction. For the investigated first-price sealed-bid auction mathematical models are developed in terms of a combinatorial optimisation problem. The formula computing the expected utility for the auctioneer was designed.
Practical/managerial implications: The research provides rigorous ways for optimal auction design to auctioneers and any financial operators or managers.
Contribution/value-add: The contributions are in the set of mathematical models and computational simulations. This article models the optimal auction design strategy mechanism as a combinatorial optimisation problem.
Keywords: auction design; bidding strategy; optimal auction; open ascending-bid auction; first-price bid auction; combinatorial auction; mathematical models; computational simulations.
Model
The interactions between the auctioneer (the seller) and the bidders (the buyers) are called a stochastic differential Stackelberg game or a stochastic differential leader-follower game. In this game, the auctioneer (the leader) moves first by setting rules and conventions that govern the auction. Every bidder (the followers) responds by submitting a bid based on the leader’s actions (the rules and conventions). The leader aims at maximising his payoff (utility), while every follower aims at maximising their individual utility. The game between the followers may be modelled as a stochastic competitive bidding game, where every follower is rational and aims at maximising their utility function by bidding accordingly.
If we define (Ω, A, F, P) as a complete filtered probability space, then Ω is a space; A is a family of subsets of Ω, and also a sigma-algebra (its elements are called measurable sets, random events) defined in Ω; (Ω, A) is a measurable space and P is probability measure defined in (Ω, A).
Given T > 0 (a finite time horizon for the game) and t ∈ [0, T], in the above probability space, define a d-dimensional (d ≥ 1) standard Brownian motion W(.) with F = (Ft)t≤T being its natural filtration, augmented by all P-null sets in F.
As said above, W(.) = (Wt)t≥0 is the standard Brownian motion. At each time t, Wt is a random variable, that is, a function defined from Ω to the real-line R such that, for each interval I in the real-line R, commonly called Borelian, we have  .
Define  , where I = {bidder 1, …, bidder N} is the set of bidders interacting at instant t. Later, for the sake of conciseness and simplicity, we shall define I = {1,…, N}. For an arbitrary i, player i is any bidder playing the auction game.
Every bidder i’s action space at time t is defined by  . It is the set of the amounts of money that bidder i may submit at time t to the auctioneer. It is the set of the probable bids for i at time t, and  is the Von Neumann–Morgenstern bidder i’s utility function at time t. In this case, it is the expected degree of satisfaction obtained after utilising the asset and is given by:
Consider that for ∀i ∈ I there exists a set Ai and a function ui such that for ∀t ∈ [1, T] we have  and  .
From this step, use simply Ai instead of  for the bidder i’s action space and  instead of ui for the bidder i’s utility function.
Mathematical models and computational simulations in the open ascending-bid auction
This subsection analyses and estimates bidder valuation before the auction game starts. This is done in the following way: for every bidder i, define Bi(t) to be the bid at time t. At the beginning of the game (the auction), before interacting with the other bidders, the model must satisfy the following differential equation:
This equation is a pure logistic equation where pi and qii are constants of proportionality. Eqn (2) was inspired by Morris, Stephen and Robert (2004) and developed by this article to finaly obtain Eqn (7). It shows that bidder i plans an increasing and bounded bid (from the beginning of the auction until the time at which the winner is found). His bidding profile increases, but not above a certain threshold.
Such a plan is based on the willingness to win subject to financial constraints, which is mathematically modelled by Eqn (2) and computationally simulated, as shown in Figure 1. For the reverse auction, bidder i (to win the game) plans a decreasing and bounded bid. His pricing profile is decreasing, but must not descend below a certain threshold. Such a situation is shown in Figure 2.
 |
FIGURE 1: Plot of Bi(t) (asset bidding at the beginning of an open ascending-bid auction) t ∈[t0,tf]. |
|
 |
FIGURE 2: Plot of Bi(t) (asset bidding at the beginning of an open descending-bid reverse auction) t ∈[t0,tf]. |
|
Mathematical models and computational simulations
This section develops mathematical models and computational simulations of the bidder valuation in an open ascending-bid in the first-price auction. By reconsidering the open ascending-bid auction in Figure 1, we have the following reality: once bidder i gets involved in the auction, for example in an open ascending-bid auction or an open descending-bid auction, his plan is influenced by the way the other N – 1 bidders emulate him to optimally value the considered asset and win, and by bidder i’s willingness to win. By considering the open ascending-bid without loss of generality, the above equation can be rewritten as follows (based on the fact that he is in the open ascending-bid auction):
where  is the combination of the interactions between bidder i and the other bidders j.
The more bidders in the auction, the greater is the constrained bid for every bidder desiring to win, and the greater is the final price for the auctioneer.
The bidding procedure of every bidder involves significant and considerable stochasticity because of the randomness existing in the auction environment. Because of this randomness associated with the asset’s price, the previous equation can be rewritten as follows:
where ξi is a coloured noise such that  is an Ornstein–Uhlenbeck stochastic process and is defined by
where Wi is a white noise such that  is a Wiener stochastic process; pi, qii, qij, αi, βi, γi are positive constant parameters of proportionality and N is the number of bidders. By letting N = 6 bidders in the auction and  , all the equations that precede yield a non-linear system of 12 stochastic differential equations:
The above non-linear system of 12 stochastic differential equations (defined by six equations of type (6) and six equations of type (7)) is coded into a Matlab function. A fourth-order Runge–Kutta method is also coded into a Matlab function. A script function is written to call the Runge–Kutta function, solve the system of equations and obtain the computational simulations for the bid functions (from Figures 3 to 8).
 |
FIGURE 3: Plot of B1(t) (asset bidding 1), t ∈ [t0,tf]. |
|
 |
FIGURE 4: Plot of B2(t) (asset bidding 2), t ∈ [t0,tf]. |
|
 |
FIGURE 5: Plot of B3(t) (asset bidding 3), t ∈ [t0,tf]. |
|
 |
FIGURE 6: Plot of B4(t) (asset bidding 4), t ∈ [t0,tf]. |
|
 |
FIGURE 7: Plot of B5(t) (asset bidding 5), t ∈ [t0,tf]. |
|
 |
FIGURE 8: Plot of B6(t) (asset bidding 6), t ∈ [t0,tf]. |
|
The first graph shows that asset valuation of an arbitrary bidder is planned to increase because of his willingness to win, and is bounded because of financial constraints. The following bidding functions increase as the auction continues until it closes because of the competition. One can notice that every bidder’s asset valuation is increasing because of the presence of the others competing against him. To find the definitions of the first-price and second-price auction, the reader may refer to David and Jon (2011). Auction Theory is a particular case of Game Theory. An auction is a double game opposing firstly the bidders (every bidder aims at winning the price) and secondly every bidder with the auctioneer (every bidder aims at winning the auction price and the auctioneer aims at maximising profit at a lowest cost of operation). To find applications of game theory the reader may refer to Samir, Samson, Merouane & Jean (2010), Haykin (2005), Hornby (2010), Juncheng, Qian and Mingyan (2009), Mo, Gaofei, Xinbing, and Qian (2012). To design and process auction data for winner determination and auction price allocation, most of time the auctioneer needs computer tools specially when dealing with huge quantity or complex structure of data. Combinatorial auctions are the one of the auctions requiring computer tools. For any infomation about papers dealing with such problems, the reader may refer to David and Lyle (2000) and Ayi and Arief (2011).
Consider the reverse auction where the auctioneer is the buyer and the bidders are the sellers. Before it starts, every bidder has a bounded decreasing pricing policy for the game. With such a pricing policy, there exists a price that each bidder (seller) must not go below because of financial constraints. The randomness in the market environment may influence the bidding profile. The price (the bid) profile of every bidder is the solution to a stochastic differential equation. It may be expressed as a negative deterministic exponential function, plus a random function that must not reach zero because the asset/service cannot be given for free. The system of equations can be approximated and solved by using a fourth-order Runge–Kutta method. The solutions (the bids) are plotted and interpreted.
After analysing the competing interactions between bidders, it is necessary to analyse the way the auctioneer manages the auction game to maximise revenue.
Mathematical models for the sealed-bid auctions
In designing the auction, the auctioneer willing to sell must take into account the following important issues (Shamik & Mainak 2008):
- build strategies to attract bidders by increasing their probability of winning
- construct mechanisms to prevent collusion from bidders willing to participate in the auction
- develop strategies to maximise revenue.
The auctioneer, in order to maximise the revenue, may adopt the following strategy:
Subject to:
where xij is the allocation of asset j to bidder i, which is a binary variable; Bij is the amount of money bidder i intends to pay to be granted asset j; Qij is the quantity associated with asset j as requested by bidder i; Q is the maximum total quantity of the available assets to sell; r is a real number such that 0 < r < 1 (a fraction of the available quantity of the asset to allow some remaining quantity for the auctioneer’s performance); Cij is the financial transaction cost (cost of operation) for granting asset j to bidder i; C is the maximum cost for granting all the assets to bidders that the auctioneer, according to the plan, must exceed; Tij is the time for granting asset j to bidder i and T is the maximum time for granting all the assets to bidders that the auctioneer has planned to not exceed. Sengupta and Chatterjee (2007) consider a similar model to deal with spectrum concurrent and sequential auction.
For this auction considered in general, we have N bidders requesting assets and only M assets can be allocated. Everything is given except xij, which are the unknowns.
In a case where the auctioneer wants to minimise total cost, he may proceed as follows:
Subject to:
where all the variables are defined as above.
The problem is carefully solved by applying simplex, integer programming, Hungarian algorithm and so on. From the conditions imposed on the unknowns, integer programming is the most suitable algorithm to apply.
Let N be the number of bidders at a given auction at a specified time, and consider that:
where pi is bidder i’s probability of winning the auction game and vi the corresponding asset value. Also, let v0 be the asset valuation for the auctioneer, who may decide to keep or sell the considered asset. The expected utility for the auctioneer is
For more infomation on spectrum auction the reader may refer to Juncheng, Qian and Mingyan (2009), Mo, Gaofei, Xinbing and Qian (2012), David and Jon (2011), Stephen, Vernon and Robert (1982), Tomasz and Michael (2017), Xia, Sorabh, Subhash and Haitao (2008).
Conclusion
The aim of this article was to investigate the way financial assets can be allocated to bidders to achieve and maximise utility for both the auctioneer and the bidders. Firstly, a study was conducted to estimate and analyse the way bidders value the considered assets, knowing that the bidders’ asset valuations enable the auctioneer to estimate and set the price. Bids’ mathematical models (in terms of a non-linear system of stochastic differential equations) and computational simulations (where the non-linear system of stochastic differential equations was coded into a Matlab function and a fourth-order Runge–Kutta was also coded into a Matlab function to solve the system) were provided to show the effectiveness of the approach. The open ascending auction is the type of auctions I needed to explore. Finally, an auction design was proposed for the assets to fairly allocate assets to bidders requesting such assets.
Acknowledgements
The authors thank the University of Johannesburg for funding this research.
Competing interests
The authors declare that they have no financial or personal relationships that may have inappropriately influenced them in writing this article.
Authors’ contributions
M.M was responsible for the development of mathematical models and computational simulations that are in the article. E.H. was responsible for the supervision of the work. T.M. was responsible for the supervision of the work.
Ethical considerations
This article followed all ethical standards for research without direct contact with human or animal subjects.
Funding
The research was funded by the University of Johannesburg.
Data availability statement
Data sharing is not applicable to this article.
Disclaimer
The views and opinions expressed in this article are those of the authors and do not necessarily reflect the official policy or position of any affiliated agency of the authors.
References
Ayi, P. & Arief, Z., 2011, ‘Optimization model for winner determination problem in combinatorial spectrum auction system’, in International conference on informatics for development, Philadelphia, PA, November 26, 2011.
David, C.P. & Lyle, H.U., 2000, ‘Iterative combinatorial auctions: Theory and practice’, in Proceedings of the 17th national conference on AI (AAAI-2000), American Association of Artificial Intelligence Press, Cambridge, October 17–20, 2000, pp. 74–81.
David, E. & Jon, K., 2011, ‘Networks, crowds, and markets: Reasoning about a highly connected world’, Technometrics 53(3), 329–330.
Haykin, S., 2005, ‘Cognitive radio: Brain-empowered wireless communications’, IEEE Journal of Communications 23(2), 201–220. https://doi.org/10.1109/JSAC.2004.839380
Hornby, A.S., 2010, ‘Auction’, in international student’s (8th edition), Advanced Learner’s Dictionary, p. 81, The Oxford University Press, Oxford.
Juncheng, J., Qian, Z. & Mingyan, L., 2009, ‘Revenue generation for truthful spectrum auction in dynamic spectrum access’, in Proceedings of the 10th Association for Computing Machinery (ACM) international symposium on mobile ad hoc networking and computing, Association for Computing Machinery, New-Orland, LA, May 18–21, 2009, pp. 3–12.
Mo, D., Gaofei, S., Xinbing, W. & Qian, Z., 2012, ‘Combinatorial auction with time frequency flexibility in cognitive radio networks’, in INFOCOM, 2012 Proceedings IEEE, IEEE, New Orlando, LA, March 25–30, 2012, pp. 2282–2290.
Morris, W.H., Stephen, S. & Robert, L.D., 2004, Differential equations, dynamical systems. An introduction to chaos, 2nd edn., vol. 60, pp. 139–158, Elsevier Academic Press, New York.
Samir, M.P., Samson, L., Merouane, D. & Jean, M.C., 2010, ‘Game theory for dynamic spectrum access’, in Cognitive radio networks: Architectures, protocols and standards, pp. 259–290, Paris, CRC Press.
Sengupta, S. & Chatterjee, M., 2007, ‘Sequential and concurrent auction mechanisms for dynamic spectrum acces’, in 2nd International conference on cognitive radio oriented wireless networks and communications (CROWNCOM), Institute of Information Technology, Kohat University of science and Technology, Talence (France), August 1–3, 2007, pp. 448–455.
Shamik, S. & Mainak, C., 2008, ‘Designing auction mechanisms for dynamic spectrum access’, Mobile Networks and Application 13(5), 498–515.
Stephen, J.R., Vernon, L.S. & Robert, L.B., 1982, ‘A combinatorial auction mechanism for airport time slot allocation’, The Bell Journal of Economics 13(2), 402–417. https://doi.org/10.2307/3003463
Tomasz, P.M. & Michael, W., 2017, ‘Artificial intelligence and economics’, IEEE Intelligent Systems Computer Society 2(1), 1–31.
Xia, Z., Sorabh, G., Subhash, S. & Haitao, Z., 2008, ‘eBay in sky: Strategy-proof wireless spectrum auctions’, in Proceedings of the 14th annual conference on mobile computers and networks, MOBICOM, Association for Computing Machinery (ACM), San Francisco, CA, September 14–19, 2008.
|
Hide
Show all
Email this article (Login required)
