Incentive compatibility constraints

[samwycherley]

Say I have a (mechanism design) problem where there are two agents $1,2$. Agent 1 has a type $v_1\in V$ and a utility function $u(x(v_1,v_2),t(v_1,v_2),v_1)=v_1 x(v_1,v_2)-t(v_1,v_2)$. I want to encode incentive compatibility constraints of the form $u(x(v_1,v_2),t(v_1,v_2),v_1)\geq u(x(v_1',v_2),t(v_1',v_2),v_1)$ for each $v_1'\in V$. Agent 2's type is $v_2\in V$ and their utility function and incentive compatibility constraints are similar.

Is there a way to encode these kinds of constraint in InfiniteOpt.jl? Here is an MWE for two agents with iid uniformly distributed types:

using Distributions, Ipopt

model = InfiniteModel(Ipopt.optimizer)

N = 1:2
@infinite_parameter(model, v[i in N] ~ Uniform(0,1), independent = true)

@infinite_parameter(model, v′ ~ Uniform(0,1))
@variables(model, begin
    0 ≤ x[N] ≤ 1, Infinite(v)
    t[N], Infinite(v)
end)

u(v,q,t) = v*q - t
@constraint(model, u(v[1], x[1], t[1]) ≥ 0)  # Participation constraint for agent 1
@constraint(model, u(v[1], x[1](v[1],v′), t[1](v[1], v′)) ≥ 0)  # Incentive compatibility constraint for agent 1

@constraint(model, u(v[2], x[2], t[2]) ≥ 0)  # Participation constraint for agent 2
@constraint(model, u(v[2], x[2](v[2],v′), t[2](v[2], v′)) ≥ 0)  # Incentive compatibility constraint for agent 2

The incentive compatibility constraints here don't work in this form.

[pulsipher]

Could you better clarify your notation? Given a function $x(v)$ where $v \in \mathbb{R}^{|N|}\sim \mathcal{U}(0, 1)$, I am not sure what it means to write $x(v_i,v_{-i})$. This goes from a function that takes a vector of arguments to one that takes two scalars. Also, what does the negative indexing denote? Is there an objective function? Overall, it is not clear to me exactly what this formulation is trying to model, granted I am not well-versed with mechanism design.

[samwycherley]

Sorry, the $v_{-i}$ notation denotes the profile of types of the other agents but I have updated the question to make the notation clearer.

[pulsipher]

Is $v'_1$ some external random parameter that is not indexed by type? Would I use the same one for each agent or do I need to generate a different one?

[samwycherley]

$v_1'$ is another type that agent 1 could declare to the designer. To give some intuition: say there is an object and agent 1 values the object with value $v_1$ (this is her type). The designer has some objective (for example, maximizing revenue) and will ultimately choose to allocate the object to agent 1 or to agent 2 and make payments to or from the agents. Each agent reports their value for the object to the designer. $x(v_1,v_2)$ gives the probabilities that agent 1 and agent 2 are allocated the object if agent 1 reported value $v_1$ and agent 2 reported value $v_2$. The transfer function $t(v_1,v_2)$ gives the net payments the agents make to the designer.

We need that the agents truthfully report their value for the object to the designer -- this is where the incentive compatibility constraint comes in. Suppose agent 1 deviates to reporting that their value $v_1'$ instead of $v_1$. Then it cannot be that the agent would be better off doing this than if they reported their true value $v_1$. The way I am encoding this in the MWE is by taking $v_1'$ to be a separate parameter on the same space as $v_1$ (the unit interval). I want the incentive compatibility constraint to hold for all $v_1'\in[0,1]$. I think it should be sufficient to use one $v'$ parameter for both agents.

[pulsipher]

Thanks for the clarifications. If I understand correctly, then we can try to express the 2 agent case:

using InfiniteOpt, Distributions, Ipopt

model = InfiniteModel(Ipopt.Optimizer)

N = 1:2
num_samples = 10 # adjust to desired amount

@infinite_parameter(model, v[i in N] ~ Uniform(0,1), independent = true, num_supports = num_samples)
vp_samples = rand(Uniform(0, 1), num_samples) # InfiniteOpt doesn't allow us to swap infinite parameter arguments directly

@variables(model, begin
    0 ≤ x[N] ≤ 1, Infinite(v[1], v[2])
    t[N], Infinite(v[1], v[2])
end)

u(v,q,t) = v*q - t

# Define the incentive compatibility constraints
@constraint(model, [vp ∈ vp_samples], u(x[1], t[1], v[1]) ≥ u(x[1](vp, v[2]), t[1](vp, v[2]), vp))
@constraint(model, [vp ∈ vp_samples], u(x[2], t[2], v[2]) ≥ u(x[2](v[1], vp), t[2](v[1], vp), vp))

A few things to note here are

• We cannot use the name v' since ' is an operator for the transpose.
• The discretized problem size will increase rapidly in proportion to num_samples^(num_agents+1) due to the combinatorics. If we instead sparsely sample dependent samples, we can reduce the factor to num_samples^2.
• I didn't declare $v'$ as an infinite parameter since InfiniteOpt doesn't allow mixing and matching of input parameters.
• Each realization/combination of v1,v2 will act as a variable index in the underlying sample average problem. Thus, in this case vp_samples are added as additional samples to each v[i] such that there are corresponding discretized variables that exist. This might cause unintended consequences in other constraints where you would expect v[i] not to include the samples from vp.

To alleviate the last point, there is a plan to allow arbitrary constraint domain restrictions which would allow us to ignore these additional support points in other constraints, but this isn't implemented yet.

[samwycherley]

Thanks!