SMAC · Smart Markets via Computation

Smart Markets via Computation

Markets are one of the primary mechanisms for determining who gets what in our society. Their combination with computation and the Internet has revolutionary potential – carefully designed, algorithmic markets can be facilitators of resource allocation that is unprecedentedly efficient, fair and profitable. This potential is already being realized in important applications such as efficient allocation of radio spectrum among telecommunication companies, monetization of online advertisements by companies like Google (funding free web search), and fair allocation of schools among students. However, there turn out to be several barriers that stand in the way of maximizing social welfare by combining market mechanisms and computation. One issue is that not all problems are computationally tractable; but computer scientists have developed techniques to deal with intractability. For example, it may be the case that maximizing welfare is computationally hard, but approximately maximizing it may be tractable. Often, the approximation algorithm performs surprisingly well in practice and is surprisingly simple – a typical example is “greedy” allocation of each resource in turn (independently of how the other remaining resources will be allocated). Another issue is that not all allocation problems can be solved by the invisible hand of the market. In fact, some of the fundamental theory underlying the idea of free markets relies on an assumption of “no complements”. This means that the goods on the market are assumed not to have synergies – owning one good cannot increase the value of owning another good (peanut butter and jelly are a classic example of complements, since having peanut butter can increase the desirability of jam). Complements greatly complicate the allocation of goods and may lead to market failures. However the assumption of no complements is grossly unrealistic. The main objective of this project is to apply the computer science approach for dealing with computational barriers to the realm of economic barriers, in particular, the existence of complements among goods. We aim to find whether wide-spread economic mechanisms (e.g., greedy allocation or standard ascending-price auctions) are robust to some degree of complementarity, and to design robust alternatives if not. Robustness is a key property in transferring theoretical insights to applicable and exploitable practices.

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз