Discrete convex analysis for analysis of iterative auctions

May 24, 2016, Tokyo Institute of Technology
Discrete convex analysis for analysis of iterative auctions
Figure 1. Behavior of the iterative auction algorithm

Researchers are investigating auction models where there are many different indivisible goods such as houses and cars. Notably, algorithms known as iterative auctions are often used to compute equilibrium prices of goods.

However, the theoretical behavior of iterative auction algorithms is not fully understood. In particular, there are only a few scattered results of research on the theoretical analysis for time bounds of iterative auctions to-date, even though the theoretical bounds on the number of iterations are interesting as research topics in their own right and important for practical applications.

Here, Akiyoshi Shioura at Tokyo Tech and colleagues at Tokyo Metropolitan University, and University of York, UK, describe a unified method of analysis for iterative auctions based on discrete convex analysis—a theory of discrete optimization problems. A key tool in the analysis is the concept of the Lyapunov function in auction theory. The researchers show that the Lyapunov function has a useful property called discrete convexity. By making use of this property, the team derived exact bounds on the number of iterations in terms of the distance between the initial price vector and the resulting equilibrium.

The results of this research extend and unify the iterative auction algorithms for a variety of auction models, offering computational complexity results for these algorithms, and reinforcing the connection between auction theory and discrete convex .

Explore further: How to digitally stoke that old-time auction fever

More information: Kazuo Murota et al. Time bounds for iterative auctions: A unified approach by discrete convex analysis, Discrete Optimization (2016). DOI: 10.1016/j.disopt.2016.01.001

Related Stories

How to digitally stoke that old-time auction fever

July 28, 2015

Whether online auctions are selling rare Pokemon cards or fine art, the science behind inciting the highest bids gets a boost from a paper to be published in the September issue of the Journal of Retailing. Researchers from ...

Real competitors enhance thrill of auctions

September 4, 2015

The thrill is part of the game—whoever waits for his bid to be accepted on online auction platforms, feels the excitement in the bidding war for the object of desire. The heart beats faster, palms start to sweat. Physiological ...

Recommended for you

A decade on, smartphone-like software finally heads to space

March 20, 2019

Once a traditional satellite is launched into space, its physical hardware and computer software stay mostly immutable for the rest of its existence as it orbits the Earth, even as the technology it serves on the ground continues ...

Tiny 'water bears' can teach us about survival

March 20, 2019

Earth's ultimate survivors can weather extreme heat, cold, radiation and even the vacuum of space. Now the U.S. military hopes these tiny critters called tardigrades can teach us about true toughness.

Researchers find hidden proteins in bacteria

March 20, 2019

Scientists at the University of Illinois at Chicago have developed a way to identify the beginning of every gene—known as a translation start site or a start codon—in bacterial cell DNA with a single experiment and, through ...

Turn off a light, save a life, says new study

March 20, 2019

We all know that turning off lights and buying energy-efficient appliances affects our financial bottom line. Now, according to a new study by University of Wisconsin-Madison researchers, we know that saving energy also saves ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.