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 ascendingbid auction mechanism was also considered. Finally, a firstprice sealedbid 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 ascendingbid auction. For the investigated firstprice sealedbid 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/valueadd: 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 ascendingbid auction; firstprice 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 leaderfollower 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 sigmaalgebra (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 ddimensional (d ≥ 1) standard Brownian motion W(.) with F = (F_{t})_{t≤T} being its natural filtration, augmented by all Pnull sets in F.
As said above, W(.) = (W_{t})_{t≥0} is the standard Brownian motion. At each time t, W_{t} is a random variable, that is, a function defined from Ω to the realline R such that, for each interval I in the realline 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 A_{i} and a function u_{i} such that for ∀t ∈ [1, T] we have and .
From this step, use simply A_{i} instead of for the bidder i’s action space and instead of u_{i} for the bidder i’s utility function.
Mathematical models and computational simulations in the open ascendingbid 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 B_{i}(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 p_{i} and q_{ii} 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 B_{i}(t) (asset bidding at the beginning of an open ascendingbid auction) t ∈[t_{0},t_{f}]. 


FIGURE 2: Plot of B_{i}(t) (asset bidding at the beginning of an open descendingbid reverse auction) t ∈[t_{0},t_{f}]. 

Mathematical models and computational simulations
This section develops mathematical models and computational simulations of the bidder valuation in an open ascendingbid in the firstprice auction. By reconsidering the open ascendingbid auction in Figure 1, we have the following reality: once bidder i gets involved in the auction, for example in an open ascendingbid auction or an open descendingbid 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 ascendingbid without loss of generality, the above equation can be rewritten as follows (based on the fact that he is in the open ascendingbid 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 W_{i} is a white noise such that is a Wiener stochastic process; p_{i}, q_{ii}, q_{ij}, α_{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 nonlinear system of 12 stochastic differential equations:
The above nonlinear 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 fourthorder 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 B_{1}(t) (asset bidding 1), t ∈ [t_{0},t_{f}]. 


FIGURE 4: Plot of B_{2}(t) (asset bidding 2), t ∈ [t_{0},t_{f}]. 


FIGURE 5: Plot of B_{3}(t) (asset bidding 3), t ∈ [t_{0},t_{f}]. 


FIGURE 6: Plot of B_{4}(t) (asset bidding 4), t ∈ [t_{0},t_{f}]. 


FIGURE 7: Plot of B_{5}(t) (asset bidding 5), t ∈ [t_{0},t_{f}]. 


FIGURE 8: Plot of B_{6}(t) (asset bidding 6), t ∈ [t_{0},t_{f}]. 

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 firstprice and secondprice 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 fourthorder 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 sealedbid 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 x_{ij} is the allocation of asset j to bidder i, which is a binary variable; B_{ij} is the amount of money bidder i intends to pay to be granted asset j; Q_{ij} 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); C_{ij} 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; T_{ij} 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 x_{ij}, 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 p_{i} is bidder i’s probability of winning the auction game and v_{i} the corresponding asset value. Also, let v_{0} 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 nonlinear system of stochastic differential equations) and computational simulations (where the nonlinear system of stochastic differential equations was coded into a Matlab function and a fourthorder 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 (AAAI2000), 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: Brainempowered 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, NewOrland, 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: Strategyproof 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.
