Suppose that an @math -simplex is partitioned into @math convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance @math from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant @math uses @math queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant @math uses @math queries. We show via Kakutani's fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds for computing approximate well-supported equilibria in this setting.
Separately, we note that the present paper is possibly relevant to the search for a price equilibrium in certain markets. Baldwin and Klemperer study markets consisting of strong-substitutes demand functions for @math different goods available in multiple discrete units @cite_7 . These markets are a generalisation of the product-mix auction of @cite_4 ; a basic task is to identify prices at which some desired bundle of the goods is demanded. Consider the space @math of all price vectors. As analysed in @cite_7 , a strong-substitutes demand function partitions this price space into convex polytopes, each of which comprises the prices at which some particular bundle of goods is demanded. So, the present paper relates to a setting where price vectors may be queried, and responses consist of demand bundles. The connection is imperfect, since the main objective in the context of @cite_7 would be to learn a price at which some target bundle is demanded, rather than the entire demand function. The ideas here may be useful for learning the values that the market has for various bundles.
@cite_4 @cite_7
2121902457 2127265337
I describe a new static (sealed-bid) auction for differentiated goods - the "Product-Mix Auction". Bidders bid on multiple assets simultaneously, and bidtakers choose supply functions across assets. The auction yields greater efficiency, revenue, information, and trade than running multiple separate auctions. It is also often simpler to use and understand, and less vulnerable to collusion, than a simultaneous multiple round auction. I designed it after the 2007 Northern Rock bank-run to help the Bank of England fight the credit crunch; in 2008 the U.S. Treasury planned using a related design to buy "toxic assets"; it may be used to purchase electricity. We propose new techniques for understanding agents' valuations. Our classification into types", incorporates existing definitions (substitutes, complements, substitutes", etc.) and permits new ones. Our Unimodularity Theorem generalises previous results about when competitive equilibrium exists for any set of agents whose valuations are all of a type" for indivisible goods. Contrary to popular belief, equilibrium is guaranteed for more classes of purely-complements, than of purely-substitutes, preferences. Our Intersection Count Theorem checks equilibrium existence for combinations of agents with specific valuations by counting the intersection points of geometric objects. Applications include matching and coalition-formation; and the Product-Mix Auction, introduced by the Bank of England in response to the financial crisis.