This chapter presents a game theory based routing algorithm that defines the best route based on the power consumption that each intermediate node will suffer to forward a packet, the price the destination will pay to the source, and the amount of compensation the source will pay to each intermediate node. The chapter also presents a polynomial time algorithm that can give a Nash Equilibrium path and use it to evaluate the performance of the game. The key features of the introduced mechanism are: it uses the first and second price auctions; the auction mechanism insures a fare allocation of the data to the user who values it the most; the second-price sealed-bid auction gives better revenue to the source when compared to the random allocation scheme and the first-price sealed-bid mechanism; the game mechanism combines both source compensation to the intermediate nodes and the power consumption to improve the path reliability between the source and the destination (i.e. the winning bidder); the source payoff will increase once the network density increases; and, finally, the simulation results prove that the introduced auction mechanism dramatically increases the destination’s revenue whether the first or second-price auction is chosen.
TopAuction Theory: A Brief History
Economists consider auctions as one of oldest surviving classes of economic institutions (Milgrom, 1985). One of the earliest reports of an auction was from interpreting the biblical account of the sale of Joseph (the great son of Abraham) into slavery as being an auction sale (Cassady, 1967). Another report was by the Greek historian Herodotus, who described the sale of women to be wives in Babylonia around the fifth century B.C. (Shubik, 2004; Krishna, 2002) these auctions use to begin with the woman the auctioneer considered the most beautiful and progressed to the least. In fact, at that time, it was considered illegal to allow a daughter to be sold outside of the auction method. During the closing years of the Roman Empire; the auction of plundered booty was common, following military victory, Roman soldiers would often drive a spear into the ground around which the spoils of war were left, to be auctioned off. Later slaves, often captured as the “spoils of war,” were auctioned in the forum under the sign of the spear, with the proceeds of sale going towards the war effort (Shubik, 2004).
Moreover, the personal belongings of deceased Buddhist monks were sold at auction as early as the seventh century A.D. in China. In some parts of England during the seventeenth and eighteenth centuries auction by candle was used for the sale of goods and leaseholds. This auction began by lighting a candle after which bids were offered in ascending order until the candle spluttered out. The high bid at the time the candle extinguished itself won the auction (Patten, 1970). During the end of the 18th century, French started auctioning art, soon after the French Revolution, daily in taverns (which was used to be considered as a place of business and social activities) and coffeehouses, during these auctions, catalogues used to be printed to show available items. Which lead us to mention the oldest auction house in the world, known as “Stockholm Auction House,” it was established in Sweden in 1674 (Varoli, 2010; Stockholm Auction House, 2010).