PaperlayerView exact revision on arXiv

Source-linked AI summary

Automated Mechanism Design via Neural Networks

Weiran Shen, Pingzhong Tang, Song Zuo

arXiv:1805.03382v2cs.AIcs.GT

TL;DR

Computational approaches to multidimensional revenue-optimal mechanism design may lack exact truthfulness or optimality. MenuNet uses separate mechanism and buyer networks to learn mechanisms, and the paper reports proving exact optimality for its first two studied problems. Its results include an exact mechanism for an additive uniform setting with a menu-size bound.

  • Problem

    Existing computational approaches to multidimensional mechanism design may fail to provide mechanisms that are both exactly truthful and exactly optimal.

    Source: §1 · p. 2

  • Method

    MenuNet uses a mechanism network to produce a mechanism from a training distribution and a separate buyer network to choose an action, modeling incentive compatibility through buyer behavior.

    Source: §1.1 · p. 2

  • Results

    The authors prove exact optimal mechanisms for the first two studied problems, including revenue 59/108 for an additive buyer with values uniform on [0, 1]^2 and menu size at most 3.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    MenuNet’s empirical findings guided proofs of exact optimal mechanisms for the first two studied problems.

    Source: §1.2 · p. 3

    Most sections assume additive valuation functions.

    Source: §2 · p. 4

Abstract

from arXiv · show

Using AI approaches to automatically design mechanisms has been a central research mission at the interface of AI and economics [Conitzer and Sandholm, 2002]. Previous approaches that attempt to design revenue optimal auctions for the multi-dimensional settings fall short in at least one of the three aspects: 1) representation -- search in a space that probably does not even contain the optimal mechanism; 2) exactness -- finding a mechanism that is either not truthful or far from optimal; 3) domain dependence -- need a different design for different environment settings. To resolve the three difficulties, in this paper, we put forward -- MenuNet -- a unified neural network based framework that automatically learns to design revenue optimal mechanisms. Our framework consists of a mechanism network that takes an input distribution for training and outputs a mechanism, as well as a buyer network that takes a mechanism as input and output an action. Such a separation in design mitigates the difficulty to impose incentive compatibility constraints on the mechanism, by making it a rational choice of the buyer. As a result, our framework easily overcomes the previously mentioned difficulty in incorporating IC constraints and always returns exactly incentive compatible mechanisms. We then apply our framework to a number of multi-item revenue optimal design settings, for a few of which the theoretically optimal mechanisms are unknown. We then go on to theoretically prove that the mechanisms found by our framework are indeed optimal. To the best of our knowledge, we are the first to apply neural networks to discover optimal auction mechanisms with provable optimality.

1 Introduction

Existing computational approaches often miss exact truthfulness or optimality, while MenuNet is designed to target both. The paper introduces separate mechanism and buyer networks and reports proofs of exact optimality for its first two investigated problems.

1 Introduction

  • Prior work studies optimal mechanisms through economic characterization, algorithm design, and AI-based search, but computational approaches often lack exact optimality or truthfulness.The paper identifies exact incentive compatibility and optimality as desired properties of constructive approaches.Source: §1 · pp. 1–2

1.1 Our methodology

  • MenuNet separates a mechanism network, which takes a training distribution, from a buyer network that takes the mechanism and outputs an action.The buyer network is not trained; its independent design is used to model exact incentive-compatibility constraints.Source: §1.1 · p. 2
  • In the single-buyer case, MenuNet represents mechanisms as menus and lets the buyer select an item, yielding incentive compatibility under the taxation principle.Menu size can also be restricted to measure mechanism complexity.Source: §1.1 · p. 2
  • Neural-network solutions can suggest an optimal solution’s structure, although the framework does not directly prove optimality.The authors say its high accuracy can reduce the effort needed to guess the solution.Source: §1.1 · p. 2

1.2 Our results

  • The paper investigates optimal mechanisms for constant menu size, triangular valuation domains, deterministic mechanisms, and buyers with combinatorial values.Source: §1.2 · p. 2
  • For additive values uniform on [0, 1]^2, the optimal mechanism with menu size at most 3 yields revenue 59/108.The paper reports proving exact optimal mechanisms for its first two investigated problems.Source: §1.2 · p. 3
  • The optimal mechanism can be asymmetric even when the distribution is symmetric.Source: §1.2 · p. 3
  • For the correlated triangular distribution, the stated optimal menu has two items for c∈[1, 4/3] and three items for c>4/3.The supplied menu-item expressions are incomplete, so only the item counts and parameter ranges are reported.Source: §1.2 · p. 3

2 Preliminaries

The paper considers a single buyer with private values for heterogeneous items and studies mechanisms that allocate items and collect payments. It defines buyer choice, the designer’s objective, and assumptions used in most sections, while also noting a correlated-values case.

2 Preliminaries

  • The seller offers m heterogeneous items, and each outcome specifies an allocation vector and a payment from the buyer.Each allocation coordinate gives the probability of allocating that item.Source: §2 · p. 3
  • A naïve mechanism maps buyer actions to outcomes, and a rational buyer chooses an action maximizing utility; letting the buyer select from the offered outcomes yields incentive compatibility.The action set includes an exit action.Source: §2 · pp. 3–4
  • A direct mechanism uses the valuation set as its action set and requires truthful reporting to maximize utility, expressed through incentive compatibility and individual rationality.The paper relates these constraints to rational choice and the option to exit.Source: §2 · p. 4
  • The designer maximizes expected objective value over the buyer’s valuation distribution; this paper focuses on seller revenue, though the methodology is not restricted to that objective.Source: §2 · p. 4
  • Most sections assume additive valuations and independent item values, while Section 5 also verifies an optimal solution for an additive buyer with correlated values.The correlated-values verification uses characterization results by Daskalakis et al..Source: §2 · pp. 4–5

3 Problem Analysis

Directly encoding incentive and rationality constraints in neural networks is difficult, and characterization-based designs can depend on restrictive assumptions and domain knowledge. The paper instead models buyer choice among offered options, using that choice in a network framework that produces exactly incentive compatible and individually rational mechanisms.

3 Problem Analysis

  • Directly encoding incentive compatibility and individual rationality in a revelation-principle network is unclear, while characterization-based structures can be restricted to additive valuations and domain knowledge.Source: §3 · p. 5
  • These domain-specific approaches may be difficult to generalize to risk-sensitive or partially rational buyers, whose behavior may instead be learned from real data.Source: §3 · p. 5
  • MenuNet starts from a naïve mechanism in which the buyer chooses her favorite option, producing exactly incentive compatible and individually rational mechanisms.The authors describe this as the first neural-network approach to output mechanisms with both properties exactly in multidimensional settings.Source: §3 · p. 5

3.1 Revisiting the Na¨ıve Mechanism

  • The buyer network models choice as a utility argmax over menu items, using a neural network for utility when available or a supplied or learned behavior model otherwise.Source: §3.1 · p. 5
  • The mechanism network outputs allocation-payment pairs, and buyer networks for different valuations choose among them to estimate the probability-weighted expected objective.Training loss is the negative expected objective; Figure 1 provides a high-level abstraction of the networks.Source: §3.1 · p. 5, Figure 1 · p. 6
  • Because buyer preferences feed into the designer’s objective, the naïve-mechanism network needs no separate incentive-compatibility or individual-rationality constraints and can use standard neural-network training methods.Source: §3.1 · p. 6

4 Network Structure of MenuNet

MenuNet represents a mechanism and buyer behavior with separate networks: one produces a menu, and the other returns the buyer’s choice. Its buyer network can be adapted to known utilities or trained from interaction data, while the objective minimizes negative expected revenue without assuming independent values.

4 Network Structure of MenuNet

  • MenuNet separates mechanism generation from buyer choice: one network produces a menu, and the other outputs the buyer’s selection.The mechanism network’s output is the mechanism’s set of menu items; the buyer network takes that menu as input.Source: §4 · p. 6

4.1 Mechanism Network

  • The mechanism network emits allocation and payment vectors, including a zero-priced, zero-allocation exit option that guarantees individual rationality.It uses a constant input to produce the menu; the exit option is the final column and payment entry.Source: §4.1 · p. 6

4.2 Buyer Network

  • The buyer network need not assume a particular utility function, and the framework can also accommodate buyer valuations that make its strategy inconsistent with any utility function.The network’s input-output format can be retained while adapting it to known utility functions or interaction data.Source: §4.2 · p. 7
  • For each discretized value profile, the buyer network outputs a distribution over menu choices, with the highest-utility menu item assigned the highest probability.When utility is known, the buyer network can be designed around it; when it is unknown, interaction data can be used to train the network.Source: §4.2 · pp. 7–8

4.3 Loss Function

  • The loss minimizes negative expected revenue, using value-profile probabilities from the joint distribution without restricting that distribution to be independent.The framework can handle joint distributions, including correlated ones.Source: §4.3 · p. 8

5 Experiments and Analysis

The experiments and analysis examine neural-network-guided discovery and optimality proofs for mechanisms across several settings, including correlated triangle distributions, restricted-menu uniform-square settings, unit-demand, combinatorial-value, and deterministic mechanisms. For mechanisms with at most three menus, the section identifies an optimal way to sell either the first item or the two-item bundle, yielding revenue 59/108.

5.1.1 Uniform [0, 𝑐] × [0, 1]

  • The computed mechanism is almost identical to the known optimum, with a slight difference in Figure 3(c).The figure compares the network's color-coded menu regions with the known optimal mechanism.Source: §5.1.1 · p. 8, Figure 3 · p. 9

5.1.2 Correlated Distribution: Uniform Triangle

  • For uniform triangle values, the optimal menu has three items when c>4/3 and two items—a bundle posted price—when c≤4/3.The framework uses the joint distribution to compute its objective and can handle arbitrary value distributions.Source: §5.1.2 · pp. 8–9

5.1.3 Restricted Menu Size

  • By symmetry, an at-most-three-menu mechanism selling the second item at price 2/3 or the bundle of two items at 5/6 is not outperformed by any other such mechanism.Source: §5.1.3 · p. 10

5.1.4 Unit-Demand Buyer

  • For unit-demand buyers, the allocation network uses a softmax with a dummy element to enforce x1+x2≤1, and experiments are shown in Figure 6(a).The dummy element allows the softmax output to represent allocations whose sum is less than one.Source: §5.1.4 · p. 10

5.1.6 Deterministic Mechanisms

  • 0.14%: at c=2, restricting the triangle-distribution mechanism to deterministic allocations decreases revenue, although the optimal mechanism is not deterministic.For two items, the deterministic mechanism network has only four possible menu allocations, so its parameters are the corresponding prices.Source: Figure 6 · p. 10, §5.1.6 · p. 11

5.1.5 Combinatorial Value

  • For combinatorial values with utility x1v1+x2v2+x1v1x2v2−p, the framework adds the product term to the buyer network.The network's mechanism for this setting is shown in Figure 6(b).Source: §5.1.5 · p. 11

5.2.1 Optimal mechanisms for selling two items with correlated distributions

  • For the correlated-triangle mechanism, the dual objective equals its actual revenue, certifying that the proposed menu is optimal.The proof uses duality and a transport construction to establish the certificate.Source: §5.2.1 · pp. 11, 13

5.2.2 Optimal mechanisms under limited menu size constraints

  • The asymmetric at-most-three-menu optimum sells the first item at 2/3 or the bundle at 5/6, yielding revenue 59/108 ≈0.546296; by symmetry, the second item may be sold instead.The analysis treats the symmetric at-most-three-menu mechanism separately; its proof assumes a zero menu and uses a bundling result to reduce the cases.Source: §5.2.2 · p. 14
  • For p≥1>q, the optimal mechanism yields revenue 14/27; for p>q>1, its revenue is at most 1/2.Source: §5.2.2 · p. 16
  • With at most 3 menus, the optimal mechanism sells the first item at 2/3 or the two-item bundle at 5/6, yielding revenue 59/108.Conditional on p≤1, the asymmetric three-menu mechanism has A: [(1, 1), 5/6], B: [(1, 0), 2/3], and Z: [(0, 0), 0].Source: §5.2.2 · pp. 15–16

6 Performance

The evaluation compares MenuNet with linear programs on discretized value distributions and reports faster scaling, convergence, and accuracy. The setup uses a default discretization of N=100.

6 Performance

  • The evaluation discretizes the continuous value space into N intervals per unit length, using N=100 by default.This creates N^2 squares in a unit square, each of size 1/N by 1/N.Source: §6 · p. 16

6.1 Efficiency and Accuracy: Compared with Linear Programs

  • 51 mins for the linear program at N=30, while MenuNet trains in less than 5 mins at N=200; the linear program is not applicable at N≥40.Figure 9 compares runtime and convergence; MenuNet’s problem size grows as O(N^2), versus O(N^4) for the linear program.Source: Figure 9 · p. 16, §6.1 · p. 17
  • MenuNet converges quickly toward the optimum, but its revenue gap does not reach zero because revenue is evaluated on the original continuous distribution after discretization.The paper also reports that its method dominates the linear-program approach in accuracy in Appendix B.Source: §6.1 · p. 17

A.1 Proof of Lemma 5.6

The proof constructs a mass-balancing line for each value profile and uses the resulting slices to establish properties of mass transport within region R3.

A.1 Proof of Lemma 5.6

  • For each value profile, the proof finds a nonnegative-slope line whose upper and lower regions satisfy opposite mass inequalities.These inequalities yield a balancing line l*_v.Source: §A.1 · p. 19
  • The proof rules out an intersection of two balancing lines inside R3 by assuming one exists and deriving a contradiction.Figure 10 depicts the intersection point considered in the argument.Source: §A.1 · p. 19, Figure 10 · p. 19
  • The balancing lines partition R3 into slices with equal positive and negative mass, allowing mass to be redistributed uniformly within each slice.The proof then uses the nonnegative slope of l*_v to infer an ordering of transported values.Source: §A.1 · p. 20

A.2 Proof of Teorem 5.8

The proof reduces the symmetric three-menu mechanism to two priced menus and the zero menu, then analyzes when the buyer chooses zero and the resulting revenue cases.

A.2 Proof of Teorem 5.8

  • By symmetry, the two nonzero menus have allocations (α, β) and (β, α) at price p, alongside the zero menu.The proof assumes α≥β and α>0 without loss of generality.Source: §A.2 · p. 20
  • The buyer chooses the zero menu when both priced allocations yield value below p; the proof expresses this probability using symmetry across v1≥v2.The probability expression is given for the event that both αv1+βv2 and βv1+αv2 are below p.Source: §A.2 · p. 20
  • For the branch p≥α, the proof finds a local maximum at x=2/3, then states the maximum revenue occurs at p=α=β=1 with Rev=1/2.The proof also identifies equality conditions for its preceding inequalities.Source: §A.2 · pp. 20–21

A.3.1 Proof of Lemma 5.12

For p≤1, the proof establishes conditions for reaching the revenue upper bound and gives the resulting menus.

A.3.1 Proof of Lemma 5.12

  • Since p≠q, the upper bound is reached if and only if 1−δ=2(p−q)/(2p+q−2); the revenue expression is 2Rev=2p−p^3+(p−q)(p+q/2−1)^2.Source: §A.3.1 · p. 21
  • The second equality condition is p−q = p+q/2−1, equivalently q=2/3.Source: §A.3.1 · p. 22
  • The resulting menus are A: [(1, 1), 5/6], B: [(1, 0), 2/3], and Z: [(0, 0), 0].Source: §A.3.1 · p. 22

A.3.2 Proof of Lemma 5.13

For p>1≥q, the proof identifies equality conditions and shows the maximum revenue on the stated interval occurs at p=1.

A.3.2 Proof of Lemma 5.13

  • The two inequalities reach equality only when 1−δ = 2(p−q)/(2p+q−2) and q=2/3.Source: §A.3.2 · p. 22
  • On p∈[1,5/3], revenue decreases in p, so its maximum is reached at p=1.The proof considers the maximum of (27p^3−108p^2+117p−8)/54 on this interval.Source: §A.3.2 · p. 22
  • At p=1, Rev=14/27, below 59/108.Source: §A.3.2 · p. 22

A.3.3 Proof of Lemma 5.14

The proof bounds revenue below 59/108 for p>q>1; the accuracy figures show the uniform [0,1]^2 setting at three discretizations.

A.3.3 Proof of Lemma 5.14

  • In the proof of Lemma 5.14 for p>q>1, the excerpt states that the supremum over q∈(1,2] is reached at q=1 and over p∈(1,2] at p=1.Source: §A.3.3 · pp. 22–23
  • The proof states that the supremum over q∈(1,2] is reached at q=1 and over p∈(1,2] at p=1.Source: §A.3.3 · p. 23

B Comparison of Accuracy

Loading 1805.03382v2…