Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency

Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency

A fundamental problem in building open distributed systems is to design mechanisms that compute optimal system-wide solutions despite the self-interest of individual users and computational agents. Classic game-theoretic solutions are often prohibitively expensive computationally. For example, the Generalized Vickrey Auction (GVA) is an efficient and strategy-proof solution to the combinatorial allocation problem (CAP), in which agents demand bundles of items, but every agent must reveal its value for all possible bundles and the auctioneer must solve a sequence of NP-hard optimization problems to compute the outcome. I propose iBundle, an iterative combinatorial auction in which agents can bid for combinations of items and adjust their bids in response to bids from other agents. iBundle computes the efficient allocation in the CAP when agents follow myopic best-response bidding strategies, bidding for the bundle(s) that maximize their surplus taking the current prices as fixed. iBundle solves problems without complete information revelation from agents and terminates in competitive equilibrium. Moreover, an agent can follow a myopic best-response strategy with approximate values on bundles, for example with lower- and upper- bounds. My approach to iterative mechanism design decomposes the problem into two parts. First, I use linear programming theory to develop an efficient iterative auction under the assumption that agents will follow a myopic best-response bidding strategy. Second, I extend the approach to also compute Vickrey payments at the end of the auction. This makes myopic best-response a sequentially-rational strategy for agents in equilibrium, inheriting many of the useful game-theoretic properties of the GVA. iBundle implements a primal-dual algorithm, CombAuction, for the CAP, computing a feasible primal (the provisional allocation) and a feasible dual (the ask prices) that satisfy complementary slackness conditions. An extended auction, iBundle Extend & Adjust, interprets a primal-dual algorithm, VickAuction, as an iterative auction. VickAuction computes the efficient allocation and Vickrey payments with only best-response information from agents. Experimental results demonstrate that iBundle Extend & Adjust, which keeps iBundle open for a second phase before adjusting prices towards Vickrey payments, computes Vickrey payments across a suite of problems.

Ideas

Goals
A truly strategic online multiplayer game

Means
Actively prosecute micromanagement
Provide advisors to implement strategic decisions, even in absence of the player
Protect playability by using reputation

Canvas
Supply chains of enormous complexity (orders of magnitude more complex than Settlers TM)

Tutorial
Players start as hired work force for other players/bots

Gameplay
Players engage in contracts with each other
There is always a risk of your partner failing - use insurance, redundancy, and reputation

Side effects
Social networking

References
Settlers
SimCity
x-battle
* Tycoon

Challenges
Language for contracts
Language for strategic plans

Miscellaneous
Transport topology - relevant or not? A spectrum from vital to relevant to cosmetic to non-existant.
Ownership of land lots. Parceling?
And other real estate.
Roads and tolls. Ports and airports. Railroads and stations.
Factories.
Carriers.
Financial: loans, deposits, transfers. Stocks? Derivatives?
Legal: contracts and lawsuits. Bankruptcy.
Insurance.
Market. Sales. Advertising. Media.
Warehouses.
Retailers.
Residentials. Rent.
Packaging.
Energy.
Communications.
Business processes as property.
Research.

Strategic map - towns (municipalities) as points with attached ports, industries, and population. Connected by roads, railroads, water and air transport.
Town map - grid (or polygonal map?) of land lots.

Industries
Aerospace, food, agri, auto, chem, energy, electronics, machinery, medicinal, metal, entertainment, textile, wood&paper

Pilot Scope
Only strategic map.
Simplified economy (only parts of raw resources and industries, some transportation - roads and water, maybe energy, no sales, no financials, no legal, no insurance). Basically Middle Ages, or even antiquity - except for workforce.
No military conflict.
A game is a set of towns, plus a connectivity matrix or two (roads/water).
Each town contains population, industries, materials; and has attached raw resources availability (lumbering/farming/fishing/mining for several minerals).
Towns/neighborhoods have limited capacity for industries, so that supply chains are forced to distribute across towns.

Maybe: using vector maps to bridge the gap between strategic/town maps - there are just various LODs.
Still need some atomic map unit for purposes of logistics (site?).
Maybe: each facility' design has some polygonal footprint plus rules for internal logistics. These footprints can be freely rotated, and can have requirements on their placement (water, resources, etc.).
Research GIS systems.

3D -> features (peak/pit/pass/ridge/valley) -> drainage network -> resource distribution

http://www.carto.net/papers/svg/samples
http://www.carto.net/papers/svg/mapbrowser/index.svgz