This papers discusses the scientific and practical perspectives of using general game playing in business-to-business price negotiations as a part of Procurement 4.0 revolution. The status quo of digital price negotiations software, which emerged from intuitive solutions to business goals and refereed to as electronic auctions in industry, is summarized in scientific context. Description of such aspects as auctioneers' interventions, asymmetry among players and timedepended features reveals the nature of nowadays electronic auctions to be rather termed as price games. This paper strongly suggests general game playing as the crucial technology for automation of human rule setting in those games. Game theory, genetic programming, experimental economics and AI human player simulation are also discussed as satellite topics. SIDL-type game descriptions languages and their formal game theoretic foundations are presented.
The ever quest of cost reduction leads nowadays to application of many AI related
technologies in manufacturing. Since 2011 [
The buyer side of the process does less progress in this development [
Procurement can be subdivided into following fields: 1) Demand Analysis This is the decision process before the procurement. The company decides concerning a certain item, whether to buy it or to self-manufacture it or not to buy it. 2) Supplier Selection a) Supplier Recruitment Suppliers are found and surveyed. The replied surveys include major characteristics of suppliers essential for their recruitment. b) B-to-B Price Negotiations After the supplier recruitment step, the price negotiations start to determine the contract partners. Those are referred to as eAuctions. 3) Contract Management Contracts are signed and systematically retained. 4) Order Management Placed orders are systematically recorded. Ordered items are tracked during delivery and in the buyer’s storage. 5) Supplier Failure Recovery In case of accidental supplier failure, certain emergent steps are made.
This paper concentrates on 2b – the B-to-B price negotiations. The state of the art of those negotiations shows features beyond the common usage and scientific notion of an auction, as the following Section 2 summarizes. These features or rather rule settings originate from intuitive solutions to business goals. The arising challenges fit into the subject matter of mechanism design (Section 3). The primary goal of the buyers is to improve the offer – reduce price and risk. One of the subordinate goals is to shift the common price expectations on the market by transparency in the bidding process or in opposite to reduce transparency to keep the prices secret. Also measuring the price distribution among suppliers might be a subordinate goal. More subordinate goals can be pursued.
Since the intuitive solutions are done manually and are neither driven by formal methods nor by data-driven methods, there is huge space for optimization and automation. This paper proposes a set of technologies to fill this empty space.
The summarized state of the art of e-auctions in 2 does not refer intentionally to any available commercial systems in order to keep neutrality and avoid distorting the competition between such systems. Section 3 describes the key concepts of application of general game playing technology in e-auctions. Section 4 describes the main patterns of languages for configuration of e-auctions. 2
e-Auctions’ State of the Art
Sellers offer goods or services. Buyers buy them for certain amounts in a chosen
currency. Depending on how many buyers and how many sellers participate in a B-to-B
negotiation, we categorize it according to Tab. 1. If there is more than one seller, it
is a buyer auction. If there is more than one buyer, it is a seller auction. A unique
seller and a unique buyer are called auctioneers in these two categories. If there are
several sellers and several buyers, it is a double auction. A negotiation without
buyers is a barter exchange. There are many internet platforms offering electronic sellers
auctions and buyers auctions, while barter double auction is a promising technology
transfer opportunity [
Table 2 shows different types of e-Auctions used in nowadays procurement. Both the auctioneer and the bidders might wish to know the market price distribution for the auctioned goods and services. Every auction type provides at least the auctioneer with the knowledge of the best price and all bidders with the knowledge of their price threshold being best or inferior. Beyond that both the auctioneer and bidders can get also the full market price distribution of all bidders. Knowing the competitors’ price might have a long-term impact on the bidders and therefore on the market. The auction types are grouped into rows according to the transparency for the bidders and marked by text style according to the auctioneer’s reception of the market price distribution.
During an action run, the price develops either in the direction of auctioneer’s preference or inverse to it. If the price grows, it is a forward auction and reverse otherwise. Sealed-Bid auction has no price development and offers no sight of market prices to the bidders. In Seal-Bid auction, all bids are final and the auctioneer receives therefore the market price distribution. The columns of Table 2 group auction types according to the availability and the type of price development. An available price development can be driven by the bids or by the system, which runs the auction. In Dutch and Japanese auctions, the system clock steps the price either forward or reverse. Dutch buyer auction steps the price forward and inverse to auctioneer’s preference, until one of the bidders stops it by bidding. All bidders and the auctioneer only see the best price on the market through a Dutch auction. Japanese buyer auction steps reverse and in auctioneer’s preference. The bidders have either to confirm the price every step until only one bidder remains or to drop out of bidding. This makes the final bid threshold and therefore the market price distribution visible to the auctioneer and to the bidders.
A bidder driven price development is available in English auction. The last bids are not the final ones, since bidders are not rationally incentivised to bid final prices like in Japanese auction. The bidders see the best price and a blurred version of the market price distribution. For some subordinate goals, the auctioneer might wish to blur the transparency for the bidders even more like in Rank and Traffic Light auctions. Rank auction shows the bidder only the current rank of his last bid among other bidders. If the bidder can not estimate the best price from his/er current rank development, s/he is rationally incentivised to bid until his/her final price threshold. Traffic Light auction is like Rank auction, where the ranks are grouped into colors like green, yellow and red. This color is then shown to the bidder. This color grouping can also be defined according to some thresholds. Best/No-Best auction are like Sealed-Bid auctions, in which the bidders get a binary feedback and can provide subsequent bids. Further, new and hybrid auctions can fit into the empty spaces of Tab 2.
In addition to the diverse auction types, there are also some special features used by procurement: Auctioneer’s Intervention In the buyer auction, the auctioneer can stop intervene into the auction at a certain moment, purchase or break it up. The bid price is binding for the suppliers, but a winning bid is not binding the buyer for a contract. The auctioneer also can add more bidders during an auction run or change the duration of the auction.
Second-Price Almost all auction types can be set to provide the second best bid price plus small margin as the contract price. Second-Price Sealed-Bid auction is known as Vickrey auction. This feature assumes the existence of a second bid, which is not applicable to Dutch auctions.
Multi-Item The total bid price is not given by supplier directly, but consists out of multiple parts. Buyers apply this feature to acquire information about the partial costs of a purchase, although there is no rational incentive for the bidders to show their true cost structure.
Multi-Attribute The bidders submit not only their prices like with multi-item, but also some additional input. In a Brazilian buyer auction, bidders don’t bid prices at all, but bid amounts of identical items for a constant total price. The additional input might consist of attributes of diverse types. For instance, the attribute ’country of supplier’ might add bonuses or penalties on the total price.
Multi-Lot Multi-Lot auction allows additionally bidding on subsets of items. For instance, Yankee auction is a combination of Dutch auction with multi-lot feature. A bid in Yankee buyer auction does not stop the auction, if it does not encompass all the items. The rest will be bidden on at a higher price.
Reserve Prices For buyer auction types, which are not driven by system, maximal bid
prices can be defined and for seller auctions minimal ones. These prices are called
reserve prices. In seller auctions of Internet advertising for instance [
Asymmetry of Bidders From auctioneer’s point of view, a certain asymmetry between bidders has to mirrored in prices and price calculation. The asymmetry applies to reserve prices as well as to Multi-Attribute calculations.
Cascading Auctions Sometimes auctions run as multiple winner auctions and serve as supplier filters for subsequent auctions.
Variable Ticking The ticking price development in the system driven auctions can be set to be non-linear and depend on players’ behavior. 3
The features described in the previous section reveal e-auctions as rather general games.
In game-theoretic terms, e-auctions are a subset of n-person games with imperfect
information. While artificial intelligence research advanced in providing ever improving
algorithms for players in games, game theory seeks to find the final solution instead [
Mechanism design is inverse to solving games – there is a desired solution, from which the appropriate game rules have to be derived. In procurement, we still deal with human players. Therefore, formal mechanism design would help as less as formal game-theoretic solution. This constitutes a kind of chicken-and-egg problem – you need human behavior data to determine appropriate game rules, but human behavior data is gathered after the game rules are determined. Obviously, one has to start with some standard or experimental game rules.
Once the game rules are determined, the game has to be realised by software. This
is called game implementation. Current industry practice of e-auctions’
implementation is the subsequent addition of any new feature and rule by hard-coding development
sprints. Every new feature has to fit well with the previously implemented features.
This approach does not only produce growing maintenance issues, it also poses a clear
set-back for Procurement 4.0:
1. Since the appropriate rule settings depends on yet unknown and future data of
human behavior, one would need a flexible soft-codable e-auctions engine for fast
game implementation. Nowadays hard-code development needs scheduling sprints
and extensive testing.
2. Once an auction is completed, the bidders’ and auctioneer’s behavior data can be
analysed. Analysing data presumes a clear game rule definition, which should be
better written in some soft-code. Game rules can be even processed to automatically
derive game-theoretic solutions [
Modeling of human bidders for prediction of outcomes requires data sources. Unfortunately, commercial data of procurement e-auctions is not public. The are no nonprofit organisations running platforms for procurement e-auctions. The only data source available for public research is the data from experimental economics.
SIDL-type languages are based on Prolog syntax. Game description are written using five main sets of language elements: 1) Definition of roles Game description should be independent of concrete players.
The slots for the players are the roles. Let us consider an example with two bidders and an auctioneer: role([bidder,1]) role([bidder,2]) role([auctioneer]) 2) Definition of database The state of a game is defined as a set of predicate tuples also called facts. This is the database. The database definition also includes the starting state definition. Let us consider an example of an auction’s starting state: fact([auctioncurrency, usd]) fact([rate, usd, usd, 1.0]) fact([rate, eur, usd, 1.1]) fact([biddercurrency, 1, eur]) fact([biddercurrency, 2, usd]) fact([reserve, 1, 10.00]) fact([reserve, 2, 20.00]) fact([starttime, "20.10.2019 12:32:00"]) fact([bestbid, null, 100000, "20.10.2019 12:32:00"]) 3) Database update rules The rules of database update will retract and/or assert predicate tuples, if certain conditions apply. The conditions include either system-driven events or submitted players’ commands. An example rule for reverse price English auction: rule([bidding, B]) <fact([reserve, B, Y]), command([bidding, bidder, B, X]), X < Y, // lower than the reserve price fact([bestbid, _, Z]), fact([auctioncurrency, C]), fact([biddercurrency, B, CC]), fact([rate, CC, C, R]), XX is X * R, // currency rate calculation XX < Z, // lower than the last bid retract([lastbid, B, _]), // remove any own last bid retract([bestbid, _, _]) // remove the best bid assert([bestbid, B, XX]), // add the new best bid assert([lastbid, B, X, ctime]).// add new own last bid 4) Database visibility definition There are rules which define visibility of the database to the players. An example for a Best/Not-Best-Auction:
hidden([bestbid, B, _],[bidder,BB]) <- not(B = BB). 5) Update rules’ availability Rules become available and therefore the commands become available under certain conditions. An example for the starting and ending states of an auction: available([bidding, _]) <fact([starttime, T]), ctime > T, fact([lastbid, _, _, TT]), ctime < T + "5m". // stop 5 minutes after the last bid Once a description of an auction is written in SIDL, one needs a piece of software called game management. Game management is separately maintained to the bidders, the auctioneer and especially the human computer interface. Game management is typically implemented as a server, which runs on a description of an auction. Time is a very important aspect in game management. There are basically two ways to introduce time into generic game management. These are Alg. 1 and Alg. 2.
Alg. 1 is based on a chronon, which is waited to receive multiple commands from the players. A chronon is a computer science analogue of a time quantum. All commands received during a chronon are considered to be simultaneous. Alg.2 is based on interrupts. No commands are considered to be simultaneous. There is succession between the commands. Obviously, a real world application requires a combination of both approaches in order to reduce the disadvantages.
Time aspects have also major impact on imperfect information. The game-theoretic notion of perfect recall from Def. 1 has to be extended for timed aspects. Different time spans between game events can make hidden information deducible. Def. 2 introduces Algorithm 1: Chronon-based game management algorithm. Algorithm 2: Interrupt-based game management algorithm. 1 send_game_rules; 2 prepare_database; 3 while any_available_update_rules_exist do 4 if interrupt_caused then 5 update_the_database; 6 record_database_changes; 7 send_visible_changes_to_players; 8 send_available_commands_to_players; the notion of perfect timed recall as the reference to this problem.
Definition 1 (Perfect recall). In a game tree of multiple paths, where junctions are caused by system events and player turns, perfect recall refers to the assumption that every player remembers all previous visible game states and never confuses different paths.
Definition 2 (Perfect timed recall). In a game tree of multiple paths, perfect timed recall refers to the assumption of perfect recall together with the assumption that every player remembers time spans between all previously visible game states and never confuses paths of different time duration. [13, p.76] One should note that the database of a running auction does not include information about its previous state. Alg. 1 (line 9) and Alg.2 (line 6) cover this aspect. The purpose of game database is to ensure a correct game state, while the external auction recording database gather data, for example, for subsequent contract management. 5
This paper presented the future innovation trajectory for e-auctions development in Procurement 4.0 revolution. The key technology for flexible e-auctions configuration already exists as general game playing. Unfortunately, field data is unavailable for public research. While it is clear that public research in this domain has to rely on laboratory data collection technologies.
Acknowledgement The study was implemented in the framework of the Basic Research Program at the National Research University Higher School of Economics (Sections 2, 3 and 5), and funded by the Russian Academic Excellence Project ’5-100’. The second author was also supported by Russian Science Foundation (Sections 1 and 4) under grant 17-11-01276 at St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, Russia.