In the following subsectionssections, we show the performance of our agent, HerbT+, compared to the performance of the chosen top agents. Furthermore, we provide an extensive analysis that sheds light on the contribution of several important design choices made and their contribution for the agent's success.  We will start by providing the overall performance of our agent and then proceeds to discuss the observations and insights we have made about our agent from the results of the evaluation.

Agent Performance

In the following paragraphs, we compare how well each agent manages to make the tradeoff between social welfare and individual utility. To do so, we define $beta\ score$ to be the score of an agreement given the tradeoff coefficient $\beta$ between social welfare and individual utility:
$beta\_score(bid)$ is calculated using the following equation:

\[
\begin{adjustbox}{max width=\columnwidth}{
$\beta*social\_welfare(bid) + (1-\beta)*individual\_utility(bid)$
\end{adjustbox}
\]

$beta\_score(bid)=\beta*social\_welfare(bid) + (1-\beta)*individual\_utility(bid)$.

$\beta$ of 1 means we look only at the social welfare of a bid, and $\beta$ of 0 means we look only at the individual utility of a bid.
The graphs in Figure <ref> show the beta score of the top 11 agentseach agent for each beta with jumps of 0.1 in domain A and domain E[For space considerations, we provide the results of additional domains in the Appendix.], i.e., a small sized domain and a high sized domain.

Beta score of the top agent for each beta

Beta score of the top agent for each beta

Beta score of the top agents for each beta

According to our results, except for domain D, where the discount factor is 1, our agent managed to outperform most of the agents. The lower the discount factor in the domain, the higher the beta score obtained by our agent.
In fact, in domain A in which the discount factor is 0.2, our agent was able to achieve the highest beta score for almost every $\beta$ (every $\beta$ above 0.1). In addition, as can be seen, the closer the beta is to 1, i.e., the higher the weight of social welfare, the better the performance of our agent relative to the other agents. Yet, even when $\beta$ is equal to 0, i.e., when our agent's goal is to maximize its individual utility, in most domains, our agent manages to outperform most of the agents and in domain B our agent managed to achieve the highest individual welfare among the agents. In most values of $\beta$ in the graphs, Atlas3 <cit.> had the closest beta score to our agent, and in most domains, he was able to achieve a higher beta score than our agent did when $\beta$ was close to 0. Atlas3's beta score can be explained by the fact that Atlas3 was proven effective for both social welfare and individual utility maximization (as he won both categories in ANAC 2015 <cit.>), unlike the other agents who were found effective for at most one of them.
In order to further verify the performance of our agent, we ran a dependent t-test <cit.>
on the results of the two agents whose sum of the beta scores over all the negotiations is the highest. The first agent is our agent, HerbT+, and the second is Atlas3. Using t-test, we found the difference between the two agents' performance to be statistically significant ($p<0.0001$).
Table <ref> summarizes the social welfare score of all thethe top 4 agents in all of the domains when $\beta$ equals 1, i.e., when the goal is to maximize the social welfare.empty_values

Social welfare results

As can be seen from the table, the strategy described in this research was able to achieve the highest social welfare among the agents in all domains except for domain D (where the discount factor is 1) in which AgentH <cit.> achieved the highest social welfare.

Even though our evaluation is based on limiting the number of rounds rather than the number of seconds allotted, we provide a comparison based on the latter measure (180 seconds) for domain B. Domain B was chosen because most of its characteristics are average compared to the rest of the domains. Here, again, the performance of our agent is best among all the agents tested, resulting in social welfare of 0.3221, compared to 0.3142 (JonnyBlack), 0.2926 (AgentX) and 0.2921 (Atlas3), which are the best agents in this category (see complete table in the Appendix).

From those results, we made several conclusions about the scenarios we mentioned in section <ref>:

* From the results in domain A and domain E, we conclude that a low number of possible outcomes (in our evaluation, 25 possible outcomes) and a high number of possible outcomes (in our evaluation, 65,536 possible outcomes) does not have a negative effect on our agent's performance.

* From the results of domain F, i.e., the domain with the integer issues type, and the results of domains A, B, C, E, and G, i.e., the domains with the discrete issues type, we can see that our agent manages to handle both domains with discrete issues and domains with integer issues.

* From the results of domains A, C, and F, i.e., the domains with a low reservation value (reservation value of 0), and the results of domain G, i.e., the domain with high reservation value (reservation value of 0.7), we can see that both low reservation values and high reservation values do not have a negative effect on the agent's performance, as in both scenarios, our agent was able to achieve the best results.

* From the results in domain B, we can see that although naturally, our agent's performance is lower on domains with low preference homogeneity than the other domains, it is still high relative to the other agents.

* From the results of domain B with time limit, we can see that the difference between time limit and rounds limit does not have a negative effect on our agent's performance.

* From the results of domain D, we conclude that our agent is sensitive to high discount values, and specifically, our agent's performance is lower on domains with a discount factor of 1, i.e., domains without discounting. More about that will be covered in the following sections.

Overall, we observe that the performance of HerbT+ are robust cross domains and setting parameters.  The only domain parameter which seems to have a significant influence on the agent's performance is the discount factor of the domain. The effect of the discount factor will be covered in the following paragraphs.

Discount Factor Implications

Since in domain D, which was the only one where HerbT+ was not ranked first, the discount factor is 1, we extended the evaluation to verify that indeed the discount factor fully accounts to the difference.  Specifically, we  used domains A - D with $\beta=1$ and $\beta=0.5$ for all discount factors with jumps of 0.2. The results are presented in Table <ref> and Table <ref>.
The average beta score in these settings are given in Table <ref>.[The agents presented in this table, as well as the agents in the rest of the tables in this section, are the agents who achieved top results according to $\beta$.]

max width=

Domain A

max width=

Domain B

Beta score by discount factor for $\beta=1$

max width=

Domain C

max width=

Domain D

Beta score by discount factor for $\beta=1$

max width=

Domain A

max width=

Domain B

Beta score by discount factor for $\beta=0.5$

max width=

Domain C

max width=

Domain D

Beta score by discount factor for $\beta=0.5$

max width=

max width=

Beta score by discount factor

Indeed, according to our results, a discount factor of 1 decreases the performance of our agent relative to other agents.

In addition, the results emphasize the stability of our agent. Our agent's achievements seem to be only influenced by the discount factor, unlike other agents whose results are harder to predict and seem to be influenced by many parameters since in each domain we see that another agent got the highest beta score.

The difference between the performance in discounted and undiscounted domains indicates that our agent manages to keep its utility from being substantially reduced by the discount factor and therefore increases the social welfare it achieves at the end of the negotiation.
Table <ref> shows the undiscounted social welfare of all the agentsthe top 5 agents in all the domains when our agent only tries to maximize social welfare.[Some agents do not support integer issues, hence the N/A values in domain F.]

Undiscounted social welfare results

From the table, we can see that when removing the effect of the discount factor on the results, our agent's score is still among the top agents, but not the top one in some domains, as with the discounted results.. However, for example, in domain A, domain C, domain E, and domain G, we can see that there are agents with higher undiscounted social welfare than our agent.
This difference strengthens our agent's capability of avoiding a significant discount factor reduction, relative to other agents, and explains a significant part in its success in maximizing the beta score.
To understand the difference between our agent's discounted social welfare and undiscounted social welfare, first, we look at the average negotiation length of each agent, as provided in Table <ref>. and Table <ref>.empty_values The lower the average length is, the smaller the effect of the discount factor.

max width=

All domains

max width=

Domain A

Average agreement round by discount factor for $\beta=1$

max width=

Domain B

max width=

Domain C

Average agreement round by discount factor for $\beta=1$

max width=

Domain D

Average agreement round by discount factor for $\beta=1$

max width=

Domain A

Average agreement round by discount factor for $\beta=0.5$

max width=

Domain B

max width=

Domain C

Average agreement round by discount factor  for $\beta=0.5$

max width=

Domain D

Average agreement round by discount factor  for $\beta=0.5$

max width=

max width=

Average agreement round by discount factor

According to our results, all of the agents who achieved good results in terms of social welfare also have a relatively low agreement round, e.g., AgentX, AgentH, Atlas3.
These results genuinely emphasize the importance of finding agreement fast and finishing the negotiation early in order to maximize social welfare. Furthermore, in most domains, our agent has the lowest average agreement round, and when $\beta=1$, it has the lowest one in all of the domains. Our agent's ability to quickly find agreements with a high beta score, with a low number of rounds, is one of the key aspects for its success in maximizing the beta score in domains with discount factors that are different than one. To understand the reasons for our agent's low agreement round, we collected statistics from the negotiation process of the agents about the agents' behaviors.
The decline rate of an agent is the rate at which the agent rejects a received bid and proposes a counteroffer, i.e., the number of declines an agent made out of the total number of its actions.

It is calculated using the following equation:

\[decline\_rate(agent)=\frac{number\_of\_declines(agent)}{number\_of\_actions(agent)}\]

$number\_of\_declines(agent)$ and $number\_of\_actions(agent)$ are the number of time $agent$ rejected an offer and all the number of times $agent$ had to make a decision on accepting or rejecting  of an agreement, respectively, in all the negotiations we ran on a domain.

Table <ref> and Table <ref> describe each agent's decline rate by discount factordescribes the average decline rate of each agent for different discount factor values.

max width=

Domain A

Decline rate by discount factor for $\beta=1$

max width=

Domain B

max width=

Domain C

Decline rate by discount factor for $\beta=1$

max width=

Domain D

Decline rate by discount factor for $\beta=1$.

max width=

Domain A

Decline rate by discount factor for $\beta=0.5$

max width=

Domain B

max width=

Domain C

Decline rate by discount factor for $\beta=0.5$.

max width=

Domain D

Decline rate by discount factor for $\beta=0.5$

max width=0.9

Decline rate by discount factor for $\beta=1$

Further analysis of the results reveals that HerbT+ has the lowest decline rate among the agents in most of the domains and discount factors. In domains with a discount factor of 0.2, it even seems that our agent almost always accepts. Our agent's low decline rate relative to that of other agents explains our agent's low agreement round. As with average agreement rounds, the agents who achieved good social welfare among the top agents have a relatively low decline rate, which indicates that a low decline rate plays a substantial role for agents who want to maximize social welfare.
In Table <ref> and Table <ref>, we can see that even when the discount factor equals 1, our agent's average agreement round is low relative to other agents. However, since there is no discount factor reduction, an early agreement does not improve the negotiation's outcome, which causes our agent to lose that advantage over the other agents. In addition, when there is no discount factor reduction at all, agents have no incentive to make concessions and change their original offer until the late rounds in the negotiation, which makes our attempt to model the agent's utility function more difficult. These two reasons explain the lower results of our agent with a discount factor of 1. With that being said, while in ANAC all agents have the same discount factor, the situation might be different in other settings. In settings where each agent has its own discount factor, one that is not known to the other agents, there is an advantage for maximizing social welfare in early agreements, even if our agent's discount factor is 1, as we do not know how much the social welfare is reduced due to other agents' discount factors.

Always Accept Policy

Our agent's low decline rate, which is a key factor in its success, raises an important question regarding the need in efficient opponent modeling and bidding strategy—if the bids our agent rejects and the offers our agent makes are negligible for the performance of the agent, any agent who agrees on everything could achieve the same results. To verify the contribution encapsulated in our agent's opponent modeling and bidding strategy, we created a new agent to compare our agent against. Our new agent will have the same opponent model and bidding strategy, but its acceptance strategy will be to always accept, and therefore the new agent opponent model and bidding strategy will be used only when the new agent has to make an offer, i.e., when the new agent is the first to make an action in the negotiation. By comparing the new agent performance against the other top agents, we will be able to see the contribution of a low decline rate to the social welfare, as our new agent will have the lowest possible rate.
To evaluate the agent we created, we added it to both the evaluation pool and comparison pool, as mentioned in section <ref>to the evaluation under the name $AlwaysAcceptAgent$.we created a new agent that always accepts offered bids and added it to the evaluation under the name $AlwaysAcceptAgent$. We ran the evaluation with all of the top agents, including our agent, HerbT+, and the new agent on domains A-D, with $beta=1$ (where the decline rate of our agent is the lowest), and with all of the discount factors with jumps of 0.2. The results are described in Table <ref>.
The average results of each agent are given in Table <ref>.

Domain A

Social welfare with AlwaysAcceptAgent by discount factor

Domain B

Domain C

Social welfare with AlwaysAcceptAgent by discount factor

Domain D

Social welfare with AlwaysAcceptAgent by discount factor

max width=0.9

Social welfare with AlwaysAcceptAgent by discount factor

According to our results, AlwaysAcceptAgent managed to outperform most of the agents in terms of social welfare, especially in domains with a low discount factor. From these results, we learn that in some scenarios, in order to maximize social welfare in multilateral negotiation, a strategy to consider, which is simple and achieves reasonably good results, is to agree on everything, i.e., taking yourself out of the picture and thus making it easier for the other agents to find an agreement.These results verify the effectiveness of a low decline rate for social welfare maximization in multilateral negotiation settings (such as the settings in ANAC).
In addition, the results above demonstrate the effectiveness of the opponent model and the bidding strategy of our agent, HerbT+. Our agent was able to surpass AlwaysAcceptAgent's performance in all domains and discount factors. except for a discount factor of 0.2, where they achieved similar results.
To further explore the differences between the two agents, we provide the average social welfare and the average individual utility of the offers that "AlwaysAcceptAgent" and "HerbT+" accepted, over all the negotiations we ran on the domains (denoted acceptance social welfare and accepted individual utility, respectively). The average acceptance social welfare and average acceptance individual utility are calculated using the following equations:

\[
\begin{adjustbox}{max width=\columnwidth}
$acceptance\_social\_welfare(agent) = \frac{\sum_{bid \in accepted\_bids(agent)}social\_welfare(bid)}{|accepted\_bids(agent)|}$
\end{adjustbox}
\]

\[
\begin{adjustbox}{max width=\columnwidth}
$acceptance\_individual\_utility(agent) = \frac{\sum_{bid \in accepted\_bids(agent)}individual\_utility(bid)}{|accepted\_bids(agent)|}$
\end{adjustbox}
\]

$accepted\_bids(agent)$ is a group of all the bids $agent$ has accepted throughout the negotiations. The values of $individual\_utility(bid)$ and $social\_welfare(bid)$ are according to the negotiations the bid was offered in.

The results are described in Table <ref>.

The average cross-domain results  are given in Table <ref>.

max width=

Domain A - social welfare

max width=

Domain A - individual utility

Domain B - social welfare

Domain B - individual utility

Acceptance social welfare and individual utility by discount factor

Domain C - social welfare

Domain C - individual utility

Domain D - social welfare

Domain D - individual utility

Acceptance social welfare and individual utility by discount factor

max width=

social welfare

max width=

individual utility

Acceptance social welfare and individual utility by discount factor

According to our results, with most discount factors, our agent, HerbT+, does manage to accept bids with a higher social welfare than AlwaysAcceptAgent. Interestingly, the individual utility of the bids that HerbT+ accepts, in most discount factors, is much higher than the individual utility of the bids AlwaysAcceptAgent accepts even though HerbT+ is tuned to maximizing only social welfare ($\beta=1$). This actually makes sense as our agent's individual utility is part of the overall social welfare, so, in order to maximize social welfare, one of our agent's interests is also to have a high individual utility for itself. From those results we learn that one reason for the difference between our agent's performance and that of AlwaysAcceptAgent is that, unlike AlwaysAcceptAgent, our agent also tries to achieve a high individual utility for itself, as doing so helps it to increase the overall social welfare.

Offers/Accepts Comparison

To understand the contribution of the offers our agent makes compared to the offers our agent accepts, we first provide the $negotiation\ agreement\ rate$ of the agent. The negotiation agreement rate of an agent is defined as the likelihood of a negotiation to end with an agreement of the agent given the agent participated in the negotiation. We calculate it as the number of negotiations that ended with an agreement offered by the agent divided by the number of negotiation sessions in which the agent participated. The results are described in Table <ref>.
The average negotiation agreement rate of the domains is described in Table <ref>.

Domain A

Negotiation agreement rate per $\beta$

Domain B

Domain C

Domain D

Negotiation agreement rate per $\beta$

max width=

Negotiation agreement rate per $\beta$

From the results, we can see that, especially when $\beta$ is closer to 1, the chances of a negotiation ending with an agreement that was offered by our agent are relatively low. Therefore, our agent's performance is more influenced by the offers it accepts rather than the offers it makes. In addition, from the results of other agents, we learn that an agent's negotiation agreement rate is not strongly related to its performance.
Both an aggressive agent, i.e., an agent that tends to end a negotiation with an offer it proposed, and a non-aggressive one that tends to accept other agents' offers can achieve good results.
For example, while $Sontag$ has a relatively low negotiation agreement rate and $Agent33$ has a relatively high negotiation agreement rate, both achieve relatively good results.
To further investigate the contribution of the bids our agent accepts, we measured the acceptance beta score (i.e., the average beta score of the accepted bids of an agent) of all of the agents. The results are shown in Table <ref> and Table <ref>
The average results are shown in Table <ref>.

max width=

Domain A

Acceptance beta score by discount factor for $\beta=1$

max width=

Domain B

max width=

Domain C

Acceptance beta score by discount factor for $\beta=1$

max width=

Domain D

Acceptance beta score by discount factor for $\beta=1$

max width=

Domain A

Acceptance beta score by discount factor for $\beta=0.5$

max width=

Domain B

max width=

Domain C

Acceptance beta score by discount factor for $\beta=0.5$

max width=

Domain D

Acceptance beta score by discount factor for $\beta=0.5$

max width=0.9

Acceptance beta score by discount factor for $\beta=1$

According to our results, in most scenarios, our agent, HerbT+, accepts bids with a relatively high beta score but usually not the highest. However, in Table <ref>, we saw that our agent's performance is more affected by the bids it accepts, i.e., its acceptance beta score, than the bids it offers. Therefore, a good acceptance beta score will increase its overall performance more than it would increase other agents' performance. From this result, we learn that a significant reason for our agent's success is a combination of a low decline rate and a low negotiation agreement rate while still maintaining a high acceptance beta score, especially when $\beta=1$. In other words, our agent manages to achieve good results by accepting many bids relative to other agents and still manages to keep a high average of the beta score of the bids it accepts.
With that being said, it would also be interesting to see the results of negotiations that do end with an agreement that was proposed by our agent. We measured for each agent the average beta score of the negotiations that ended with an offer of the agent. The results are shown in Table <ref> and Table <ref>
The average results are shown in Table <ref>.

max width=

Domain A

max width=

Domain B

Beta score of the negotiations that ended with an offer of a specific agent for $\beta=1$

max width=

Domain C

max width=

Domain D

Beta score of the negotiations that ended with an offer of a specific agent for $\beta=1$

max width=

Domain A

max width=

Domain B

Beta score of the negotiations that ended with an offer of a specific agent for $\beta=0.5$

max width=

Domain C

max width=

Domain D

Beta score of the negotiations that ended with an offer of a specific agent for $\beta=0.5$

max width=0.9

Beta score of the negotiations that ended with an offer of a specific agent for $\beta=1$

According to our results, although not many negotiations end with an agreement that was offered by our agent, the ones that do end with a relatively high beta score, especially when $\beta=1$.

Unique Populations

In the following section, we provide an analysis of our agent's evaluation in different and unique agent populations.

Only Social
First, we used only the agents who try to maximize social welfare (i.e., the agents who had an achievement in the social welfare category according to Table <ref>) as our population. Using only negotiations with the agents in this population, we compared our agent's social welfare with $\beta=1$ to the social welfare achieved by each of those agents. The results are provided in Table <ref>.

max width=0.9

Social welfare in the only social populationempty_values

According to Table <ref>, when the entire population tries to maximize social welfare, our agent managed to achieve the highest social welfare than all the other agents in all the domains (including domain D, in which our agent did not achieve the highest social welfare with the original population,  as shown in Table <ref>). In addition, every agent achieved higher social welfare in this population than it achieved in the original population in most domains. This makes sense since when all the agents in the negotiation want to maximize the social welfare, the social welfare will naturally be higher than the opposite case.

Self Negotiation
Next, we evaluated how well our agent does in a negotiation against itself, relative to other agents, i.e., negotiation when all the negotiators are instances of the same agent (each such instance still has different preferences, but the strategy is the same). For this evaluation, we used only the negotiations who contain 3 instances of the same agents. The beta score of each agent is provided in Table <ref>.

max width=

Domain A

max width=

Domain B

Beta score of each agent against only instances of itself

max width=

Domain C

max width=

Domain D

Beta score of each agent against only instances of itself

max width=

Domain E

max width=

Domain F

max width=

Domain G

Beta score of each agent against only instances of itself

According to Table <ref>, when competing against itself and when $\beta=1$, our agent achieved the highest beta score in all domains (including domain D). Furthermore, when only negotiations of three instances of the same agent are considered, an agent's average beta score is equal to the average individual utility and the average social welfare of the agent. This means that when $\beta=1$, in this kind of population, our agent outperforms all the other agents in all of the domains, both in its individual utility and social welfare. In addition, as can be seen in the table, unlike our agent, a lot of agents do not reach an agreement with themselves in some of the domains (when the beta score is the discounted reservation value of the domain).

Correlation Assumption

In our strategy, we assume that there is a strong correlation between an agent's utility function and the actions it takes, i.e., choosing a bid to offer and deciding whether to accept or reject another agent's offer. We test this assumption by comparing the output of the model we trained for each agent on each possible bid with the output of the real utility function of the agent. We compare the outputs using two measures: mean absolute error <cit.> and Pearson's correlation coefficient <cit.>. From the mean absolute error of the output of our model and the real utility function, we will be able to tell how close our model is to the real utility function and from the correlation between the output of our model and the output of the real utility function we will be able to verify the correlation assumption we use in our strategy. In addition, using these measures we compare our logistic regression model to other machine learning models: SVM <cit.>, Decision tree <cit.>, and Random forests <cit.>. We made the comparison using all of the negotiations in domain B. We chose domain B since it has the most samples of negotiations which proceeded to late rounds.
The results are provided in Figure <ref> and Figure <ref>:

Pearson's correlation coefficient on each round in the negotiation

Mean absolute error on each round in the negotiation

Pearson's correlation on each round in the negotiation

Mean absolute error on each round in the negotiation

According to Figure <ref>, by training a logistic regression model with an agent's actions, we managed to build a model where the Pearson correlation coefficient of its output with the output of the real utility function is above 0.5. This indeed verifies the correlation assumption we use in our strategy. As expected, since the correlation is high, our model manages to achieve a relatively low mean absolute error with the real utility function. In addition, as can be seen in Figure <ref>, a logistic regression model does manage to achieve the lowest mean absolute error between the compared methods.

Random Initialization

In order to measure the effectiveness of re-initializing the logistic regression model with random weights in each turn, we compared our model with random initialization against our model which uses the same logistic regression model in all the negotiation's rounds and updates the model with each new observation. Table <ref> provides the average agreement round and the achieved social welfare of each one of the models.

Comparison of random initialization and continuous training approaches on domain C

From Table <ref>, we can see that when using the random initialization for the logistic regression model, our agent does manage to reach agreements faster, and therefore its achieved social welfare is higher.


# Characterization of Incentive Compatible Single-parameter Mechanisms
Revisited

###### Abstract

We reexamine the characterization of incentive compatible single-parameter
mechanisms introduced in Archer Tardos (2001). We argue that the claimed
uniqueness result, called ‘Myerson’s Lemma’ was not well established. We
provide an elementary proof of uniqueness that unifies the presentation for
two classes of allocation functions used in the literature and show that the
general case is a consequence of a little known result from the theory of real
functions. We also clarify that our proof of uniqueness is more elementary
than the previous one. Finally, by generalizing our characterization result to
more dimensions, we provide alternative proofs of revenue equivalence results
for multiunit auctions and combinatorial auctions.

Keywords: incentive compatibility, single-parameter mechanisms, Myerson’s
lemma, auctions, revenue equivalence.

JEL Classification Numbers: D44, D82.

##  1 Introduction

W e are concerned here with a characterization result of a specific class of
incentive compatible direct selling mechanisms. For the sake of this article
such a _mechanism_ consists of an _allocation rule_ that assigns some good or
goods to the participants, called agents, and a _payment rule_ that determines
how much each agent needs to pay. Assuming that each agent has a _private
valuation_ of the good or goods, these decisions are taken in response to a
vector of _bids_ made by the agents. These bids may differ from agents’ true
valuations. Recall that a mechanism is (_dominant strategy_) _incentive
compatible_ (alternatively called _truthful_), if no agent is better off when
providing false information regardless of reports of the other agents or, more
precisely, when submitting a bid different from his/her valuation regardless
of reports of the other agents.

Given a class of mechanisms one of the main problems is to characterize their
incentive compatibility in terms of an appropriate payment rule. Several such
results were established in the literature, starting with the one in Green
Laffont (1977) concerning Groves mechanisms, originally proposed in Groves
(1973). One of the earliest characterization results was given in Myerson
(1981), who considered single object auctions in an imperfect information
setting. In Milgrom (2004) such characterizations are called ‘Myerson’s
Lemma’. This terminology was adopted in Roughgarden (2016), Chapter 3 of
which, titled ‘Myerson’s Lemma’, is concerned with a characterization of
incentive compatible single-parameter mechanisms which were introduced and
studied in Archer Tardos (2001).

As we explain below, both in this article and in Roughgarden’s book such a
characterization result is actually not proved. Most (but not all) of the
claims are rigorously established in Nisan (2007) in the context of randomized
single-parameter mechanisms.

Given that this purported characterization of incentive compatible single-
parameter mechanisms is frequently referred to in the literature (see e.g.
Hartline Karlin (2007) or in Babaioff (2016)) we find it justified to review
these claims. We will provide an elementary proof of the characterization
result for two classes of allocation functions considered in Roughgarden
(2016) and subsequently provide a proof of the original claim of Archer Tardos
(2001) by appealing to more advanced results from the theory of real
functions. We conclude by comparing our proof to the one given in Krishna
(2002) and Börgers (2015).

##  2 Preliminaries

We follow here the terminology of Roughgarden (2016) that is slightly
different than the one originally used in Archer Tardos (2001). In particular
Roughgarden (2016) refers to a single-parameter mechanism and an allocation
rule, while Archer Tardos (2001) refer to a one-parameter mechanism and load.

Each _single-parameter mechanism_ concerns sale of some ‘stuff’ to bidders and
assumes

  * •

a set of agents $\\{1,\mbox{$\ldots$},n\\}$,

  * •

for every agent $i$, a value $v_{i}\geq 0$ which specifies $i$’s _private
valuation_ “per unit of stuff” that he or she acquires.

In the auction the agents submit simultaneously their _bids_ , which are their
reported valuations “per unit of stuff”. The auctioneer receives the bids and
determines how much ‘stuff’ each agent receives and against which price. So in
contrast to the single-item auctions each agent $i$ receives a possibly
fractional amount $a_{i}\geq 0$ of an object (here ‘a stuff’) he or she is
interested in.

An _allocation_ is a vector $\mathbf{a}=(a_{1},\dots,a_{n})$, where each
$a_{i}\geq 0$ specifies the amount allocated to agent $i$. A _payment_ is a
vector $\mathbf{p}=(p_{1},\mbox{$\ldots$},p_{n})$, where each $p_{i}\geq 0$
specifies the amount agent $i$ has to pay.

Each single parameter mechanism consists of an _allocation rule_

$\mathbf{a}:\mathbb{R}_{\geq 0}^{n}\to\mathbb{R}_{\geq 0}^{n}$

and a _payment rule_

$\mathbf{p}:\mathbb{R}_{\geq 0}^{n}\to\mathbb{R}_{\geq 0}^{n}.$

Given a vector of bids $\mathbf{b}=(b_{1},\dots,b_{n})$ such a mechanism
selects an allocation
$\mathbf{a}(\mathbf{b})=(a_{1}(\mathbf{b}),\dots,a_{n}(\mathbf{b}))$ and a
vector of payments
$\mathbf{p}(\mathbf{b})=(p_{1}(\mathbf{b}),\dots,p_{n}(\mathbf{b}))$.

We assume that the _utility_ of agent $i$ is defined by

$u_{i}(\mathbf{b})=v_{i}a_{i}(\mathbf{b})-p_{i}(\mathbf{b}).$

We then say that a single-parameter mechanism is _incentive compatible_ if for
each agent $i$ truthful bidding, i.e., bidding $v_{i}$, yields the best
outcome regardless of bids of the other agents. More formally, it means that
for all agents $i$

$u_{i}(v_{i},\mathbf{b}_{-i})\geq u_{i}(b_{i},\mathbf{b}_{-i}),$

for all bids $b_{i}$ of agent $i$ and all vectors of bids $\mathbf{b}_{-i}$ of
other agents, or equivalently—ignoring the parameters $\mathbf{b}_{-i}$—that
for all $y\geq 0$

$v_{i}a_{i}(v_{i})-p_{i}(v_{i})\geq v_{i}a_{i}(y)-p_{i}(y).$

##  3 A characterization result

We say that a function $f:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ is
_monotonically non-decreasing_ , in short _monotone_ , if

$0\leq x\leq y\rightarrow f(x)\leq f(y).$

We say that an allocation rule $\mathbf{a}$ is _monotone_ if for every agent
$i$ and every vector of bids $\mathbf{b}_{-i}$ of other agents the function
$a_{i}(\cdot,\mathbf{b}_{-i})$ is monotone.

The following result is stated in Archer Tardos (2001), Nisan (2007), and
Roughgarden (2016). (In Nisan (2007) it is formulated as a result about
randomized single-parameter mechanisms but the proofs are the same for the
deterministic mechanisms considered here.)

######  Theorem 1.

  1. (i)

If a mechanism $(\mathbf{a},\mathbf{p})$ is incentive compatible then the
allocation rule $\mathbf{a}$ is monotone.

  2. (ii)

If the allocation rule $\mathbf{a}$ is monotone then for some payment rule
$\mathbf{p}$ the mechanism $(\mathbf{a},\mathbf{p})$ is incentive compatible.

  3. (iii)

If the allocation rule $\mathbf{a}$ is monotone, then all payment rules
$\mathbf{p}$ for which the mechanism $(\mathbf{a},\mathbf{p})$ is incentive
compatible differ by a constant.

There are some technically irrelevant differences between these three
references. In Archer Tardos (2001) instead of allocations loads are
considered, with the consequence that the loads are monotonically non-
increasing, though the authors also state that the results equally apply to
the setup that uses allocations. In what follows, following Nisan (2007) and
Roughgarden (2016), we use allocations. It leads to an analysis of
monotonically non-decreasing functions. Further, in the last two references it
is assumed that the payment rule yields 0 payment when bids are equal to 0,
which makes it possible to drop in $(iii)$ the qualification ‘up to a
constant’. To make the discussion applicable to arbitrary payment rules we do
not adopt this assumption.

Item $(i)$ is established in Archer Tardos (2001) by appealing to the first
derivative, so under some assumptions about the load function. However, a
short argument given in Nisan (2007) and reproduced in Roughgarden (2016)
shows that no assumptions are needed.

In turn, item $(ii)$ is proved in Archer Tardos (2001) ‘by picture’. A
rigorous proof is given in Nisan (2007), while in Roughgarden (2016) only a
‘proof by picture’ is provided for piecewise constant allocation rule and it
is mentioned that “the same argument works more generally for monotone
allocation rules that are not piecewise constant”.

Finally, in Archer Tardos (2001) item $(iii)$ is claimed for arbitrary
monotone loads and allocation rules. But in the paper only a short proof
sketch is given that ends with a claim that “To prove that all truthful
payment schemes take form (2), even when $\omega_{i}$ [the load rule] is not
smooth, we follow essentially the same reasoning as in the [earlier given]
calculus derivation.” However, this derivation refers to load rules that are
assumed to be smooth (actually only twice differentiable, so that integration
by parts can be applied), while the characterization result is claimed for all
monotone allocation functions.

In Nisan (2007) item $(iii)$ is established by reducing in the last step the
expression $\int_{0}^{x}zf’(z)dz$ to $xf(x)-\int_{0}^{x}f(z)dz$. We quote
(adjusting the notation): “[…] we have that $p(x)=\int_{0}^{x}zf’(z)dz$, and
integrating by parts completes the proof. (This seems to require the
differentiability of $f$, but as $f$ is monotone this holds almost everywhere,
which suffices since we immediately integrate.)” (Recall that a property holds
_almost everywhere_ if it holds everywhere except at a set of measure 0, i.e.,
a set that can be covered by a countable union of intervals the total length
of which is arbitrarily small.) A minor point is that the initial part of the
proof is incomplete as it only deals with the right-hand derivative instead of
the derivative.

Finally, in Roughgarden (2016) about item $(iii)$ it is only stated without
proof “We reiterate that these payments formulas [for the above two classes of
allocation functions] give _the only possible_ payment rule that has a chance
of extending the given allocation rule x into a DSIC [i.e., incentive
compatible] mechanism.” Also here the formula (in the adjusted notation)
$p(x)=\int_{0}^{x}zf’(z)dz$ is derived by discussing only the right-hand
derivative.

In our view these arguments are incomplete as they do not take into account
some restrictions that need to be imposed on the use of integrals and
application of integration by parts. Note that, except in the final
discussion, Riemann integration is assumed throughout.

######  Remark 2.

To start with, integration by parts can fail for simple monotone functions,
for example those considered in Roughgarden (2016). Indeed, let for $q>0$

$H_{q}(x):=\begin{cases}0&\text{ if $0\leq x\leq q$ }\\\ 1&\text{ if $x>q$
}\end{cases}$

be an elementary step function with a single step at $x=q$.

Take now $f=H_{q}$ with $q=1/2$. Then $f’=0$ for $x\neq 1/2$ and $f’$ is
undefined for $x=1/2$. Consequently (defining $f’(1/2)$ arbitrarily)

$\int_{0}^{1}zf’(z)dz=0\neq 1/2=xf(x)\big{|}_{0}^{1}-\int_{0}^{1}f(z)dz.$ (1)

Further, integration by parts can fail even if we insist on continuity.
Indeed, take for $f$ the Cantor function, see, e.g., (Tao, 2011, pages
170-171). It is monotone, continuous and almost everywhere differentiable on
$[0,1]$, with $f(0)=0$, $f(1)=1$ and $f’$ equal to 0 whenever defined.
Additionally, (1) holds for $f$, as well.

Finally, there exists a monotone and everywhere differentiable function $f$
for which the above integral $\int_{0}^{1}zf’(z)dz$ does not exist. Indeed, as
observed in Goffman (1977), there exists a monotone and everywhere
differentiable function $f:[0,1]\rightarrow\mathbb{R}_{\geq 0}$ such that the
integral $\int_{0}^{1}f’(z)dz$ does not exist. By a result of Lebesgue (see,
e.g., Bressoud (2008)) a bounded function defined on a bounded and closed
interval is Riemann integrable iff it is continuous almost everywhere. But
$f’$ is continuous almost everywhere on $[0,1]$ iff the function
$g(x):=xf’(x)$ is, so the claim follows. $\Box$

These points of concern motivate our subsequent considerations. To keep the
paper self-contained we reprove items $(i)$ and $(ii)$, given that the proofs
are very short.

##  4 An analysis

Our analysis can be carried out without any reference to mechanisms by
reasoning about functions on reals. We first rewrite the incentive
compatibility condition as

$p_{i}(y)-p_{i}(v_{i})\geq v_{i}(a_{i}(y)-a_{i}(v_{i})),$

which from now on we analyze as the following condition on two functions
$f:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ and $g:\mathbb{R}_{\geq
0}\to\mathbb{R}_{\geq 0}$:

$\mbox{$\forall$}x,y:g(y)-g(x)\geq x(f(y)-f(x)).$ (2)

We are interested in solutions in $g$ given $f$. We begin with the following
obvious observation.

######  Note 3.

The inequality (2) is equivalent to

$\mbox{$\forall$}x,y:y(f(y)-f(x))\geq g(y)-g(x)\geq x(f(y)-f(x)).$ (3)

###### Proof.

By interchanging in (2) $x$ and $y$ we get the additional inequality
$y(f(y)-f(x))\geq g(y)-g(x)$. ∎

######  Corollary 4 (Nisan (2007); Roughgarden (2016)).

Suppose (2) holds. Then the function $f$ is monotone.

###### Proof.

Assume $0\leq x<y$. By Note 3 (3) holds. The inequalities in (3) imply
$(y-x)(f(y)-f(x))\geq 0$, so $f(x)\leq f(y)$. ∎

This establishes item $(i)$ of Theorem 1. To investigate items $(ii)$ and
$(iii)$ we study existence and uniqueness of solutions of (2) in $g$. The
following result establishes item $(ii)$. The proof is from Nisan (2007).

######  Lemma 5.

Suppose $f$ is monotone. Then (2) holds for

$g(x)=C+xf(x)-\int_{0}^{x}f(z)dz,$ (4)

where $C$ is some constant.

Because $f$ is monotone $g$ is well defined (see, e.g., Rudin (1976)).

###### Proof.

By plugging the definition of $g$ in (2) we get after some simplifications

$\int_{0}^{x}f(z)dz-\int_{0}^{y}f(z)dz\geq(x-y)f(y),$ (5)

which needs to be proved. Two cases arise.

Case 1. $x\geq y$.

Then

$\int_{0}^{x}f(z)dz-\int_{0}^{y}f(z)dz=\int_{y}^{x}f(z)dz\geq(x-y)f(y),$

where the last step follows by bounding the integral from below, since by the
monotonicity of $f$, we have $f(y)\leq f(z)$ for $z\in[y,x]$.

Case 2. $y>x$.

Then

$\int_{0}^{x}f(z)dz-\int_{0}^{y}f(z)dz=-\int_{x}^{y}f(z)dz\geq(x-y)f(y),$

where the last step follows by bounding the integral from above, since by the
monotonicity of $f$, we have $f(z)\leq f(y)$ for $z\in[x,y]$.

So (5) holds, which concludes the proof. ∎

To deal with uniqueness let us first consider the case for which the argument
given in Nisan (2007) can be justified.

######  Lemma 6.

Suppose $f$ is everywhere differentiable. Then any two solutions $g$ of (2)
differ by a constant.

###### Proof.

Suppose that (2) holds. By Note 3 (3) holds. Given an arbitrary $x\geq 0$ we
first use it with $y=x+h$, where $h>0$. Dividing by $h$ we then obtain

$\frac{(x+h)(f(x+h)-f(x))}{h}\geq\frac{g(x+h)-g(x)}{h}\geq\frac{x(f(x+h)-f(x))}{h}.$

By the assumption about $f$

$\lim_{h\to 0^{+}}\frac{(x+h)(f(x+h)-f(x))}{h}=\lim_{h\to
0^{+}}\frac{x(f(x+h)-f(x))}{h}=xf^{\prime}(x),$

so

$\lim_{h\to 0^{+}}\frac{g(x+h)-g(x)}{h}=xf^{\prime}(x).$ (6)

Next, we use (3) with $x=y+h$, where $h<0$. Dividing by $h$ we then obtain

$\frac{y(f(y)-f(y+h))}{h}\leq\frac{g(y)-g(y+h)}{h}\leq\frac{(y+h)(f(y)-f(y+h))}{h},$

so replacing $y$ by $x$ and multiplying by $-1$ we get

$\frac{x(f(x+h)-f(x))}{h}\geq\frac{g(x+h)-g(x)}{h}\geq\frac{(x+h)(f(x+h)-f(x))}{h}.$

By the assumption about $f$ and $x$

$\lim_{h\to 0^{-}}\frac{(x+h)(f(x+h)-f(x))}{h}=\lim_{h\to
0^{-}}\frac{x(f(x+h)-f(x))}{h}=xf^{\prime}(x),$

so

$\lim_{h\to 0^{-}}\frac{g(x+h)-g(x)}{h}=xf^{\prime}(x).$ (7)

We conclude from (6) and (7) that $g^{\prime}(x)$ exists and

$g^{\prime}(x)=xf^{\prime}(x).$ (8)

Hence all solutions $g$ to (2) have the same derivative and consequently
differ by a constant. ∎

######  Remark 7.

The above proof coincides with the one given in Nisan (2007), except on two
points. First, only (6) is established there. This allows one only to conclude
that the right derivative of $g$ in $x$ exists; to establish that $g’(x)$
exists also (7) is needed. More importantly, Nisan argued that all solutions
$g$ to (2) are of the form (4) given in Lemma 5. Under the assumption that $f$
is everywhere differentiable this additional claim is a direct consequence of
Lemmas 5 and 6.

Nisan’s argument for this point involved integration and integration by parts.
To justify it we need to assume that $f’$ is continuous. Then by (8) also $g’$
is continuous, which allows us to use the Fundamental Theorem of Calculus. It
yields that for some constant $C$

$g(x)=C+\int_{0}^{x}g’(z)dz.$

Further, integration by parts of $\int_{0}^{x}zf’(z)dz$ is then also justified
since $f$ is everywhere differentiable and $f’$ is integrable (see, e.g.,
Rudin (1976)). Then $\int_{0}^{x}zf’(z)dz$ exists and by integration by parts

$\int_{0}^{x}zf’(z)dz=xf(x)-\int_{0}^{x}f(z)dz,$

so (8) and the last two equalities imply that $g$ is indeed of the form (4)
given in Lemma 5. $\Box$

In the remainder of this section we do not use integration or the existence of
solutions in the form (4), but proceed directly from (2). This allows us to
sidestep the associated complications and show that the requirement of $f$
being everywhere differentiable of Lemma 6 can be substantially weakened and,
appealing to strong results from the theory of real functions, can even be
removed altogether.

For $x=0$ continuity (differentiability) means right continuity
(differentiability), which we will not mention or treat separately.

We first need an auxiliary result.

######  Lemma 8.

Let $g_{1}$ and $g_{2}$ be two solutions of (2) and let $G=g_{1}-g_{2}$.

  1. (i)

$G$ is continuous.

  2. (ii)

If $f$ is continuous at $x$, then $G$ is differentiable at $x$ and $G’(x)=0$.

###### Proof.

$(i)$ By Note 3 (3) holds for $g_{1}$ and $g_{2}$. By using it with $y=x+h$
for $g_{1}$ and for $g_{2}$ we obtain

$0\leq|G(x+h)-G(x)|\leq h(f(x+h)-f(x)).$ (9)

We have $h(f(x+h)-f(x))\leq hf(x+h)$ for $h>0$ and $\leq-hf(x)$ for $h<0$. But
by Corollary 4 $f$ is monotone, hence $\lim_{h\to 0}|G(x+h)-G(x)|=0$, which
establishes the claim.

$(ii)$ Take some $x\geq 0$. By (9) for $h\neq 0$

$0\leq\Big{|}\frac{G(x+h)-G(x)}{h}\Big{|}\leq|f(x+h)-f(x)|,$

which implies the claim. ∎

Note that the continuity of $G$ holds for any $f$.

The following result with an elementary proof covers in a unified way item
$(iii)$ of Theorem 1 for two classes of allocation functions considered in
Roughgarden (2016), piecewise constant and differentiable ones.

A function $f:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ is called _piecewise
continuous_ if it has at most a finite number of discontinuities in every
bounded interval. Thus discontinuities can occur only at isolated points
separated by open intervals of continuity. Piecewise constant and step
functions are special cases. This definition is a straightforward
generalization to $\mathbb{R}_{\geq 0}$ of the usual one for functions with a
bounded domain.

######  Theorem 9.

Suppose $f$ is piecewise continuous. Then any two solutions $g$ of (2) differ
by a constant.

###### Proof.

Let $g_{1}$ and $g_{2}$ be two solutions of (2) and let $G=g_{1}-g_{2}$.

Let $f$ be piecewise continuous with discontinuities $q_{1}<q_{2}<\ldots$ and
consider the intervals $I_{0}=[0,q_{1})$ ($\emptyset$ if $q_{1}=0$),
$I_{i}=(q_{i},q_{i+1})$ ($i\geq 1$), with $I_{N}=(q_{N},\infty)$ if $f$ has a
finite number $N>0$ of discontinuities and $I_{0}=[0,\infty)=\mathbb{R}_{\geq
0}$ if $N=0$.

If $f$ has an infinite number of discontinuities,
$\lim_{i\to\infty}q_{i}=\infty$ since there can be only finitely many of them
in any bounded interval. Hence, the $I_{i}$ and $q_{i}$ together cover the
whole of $\mathbb{R}_{\geq 0}$.

$f$ is continuous on each $I_{i}$, so by Lemma 8$(ii)$ $G$ is constant on
$I_{i}$, say $G=C_{i}$ on $I_{i}$. Since $G$ is continuous everywhere by Lemma
8$(i)$, $C_{0}=G(q_{1})=C_{1}=G(q_{2})=\ldots$, so for some constant $C$,
$G=g_{1}-g_{2}=C$. ∎

Theorem 9 can be generalized to a wider class of functions whose discontinuity
sets may have limit points (accumulation points), at least to some degree. We
give a simple example of a monotone function $f$, for which Theorem 9 does not
apply but the stronger result presented below does.

Let

$f(x)=\sum_{n=1}^{\infty}{2^{-n}}H_{1-{2^{-n}}}(x),$

where $H_{q}$ is defined in Remark 2. It is not piecewise continuous, but has
an infinite set of discontinuities $\\{1/2,3/4,\ldots\\}$ with a single limit
point $1$. Note that $f$ happens to be continuous at $x=1$, but this might
also have been otherwise.

Functions like $f$ and more complicated ones having discontinuity sets with
limit points of limit points, etc. can, to some extent, be dealt with by
adapting the proof of Theorem 9 and appealing to the well-known Bolzano-
Weierstrass theorem (BW for short, see, e.g., Bressoud (2008)).

Given a set $S\subseteq\mathbb{R}_{\geq 0}$, we denote by $S^{(1)}$ the set of
its limit points (which need not be in $S$) and define
$S^{(n+1)}=(S^{(n)})^{(1)}$ for $n\geq 1$. A set $S$ is called _first species_
of type $n-1$ if $S^{(n)}=\emptyset$ and $S^{(m)}\neq\emptyset$ for $m<n$
(Bressoud, 2008). Such a set has limit points, limit points of limit points,
etc., up to level $n-1$. A first species set of type $0$ has no limit points.

######  Theorem 10.

Suppose the discontinuity set of $f$ is first species of type $n\geq 0$. Then
any two solutions $g$ of (2) differ by a constant.

###### Proof.

Let $g_{1}$ and $g_{2}$ be two solutions of (2) and let $G=g_{1}-g_{2}$. Let
the discontinuity set of $f$ be $S$ and use induction with respect to the type
of $S$.

If $n=0$, $S^{(1)}=\emptyset$, so $f$ can have only finitely many
discontinuities in every bounded interval. Otherwise, there would be a limit
point in some bounded and closed interval by BW. Hence, $f$ is piecewise
continuous and the case $n=0$ corresponds to Theorem 9.

Assume the theorem holds for all $n\leq k$ for some $k>0$ and consider $S$ of
type $k+1$. The elements of $S^{(k+1)}$ are the limit points of level $k+1$.
Recall that these need not be elements of $S$. Since $S^{(k+2)}=\emptyset$,
$S^{(k+1)}$ does not have limit points, so there can be only finitely many
elements of $S^{(k+1)}$ in every bounded interval by BW as before.

Now let the elements of $S^{(k+1)}$ be $q_{1}<q_{2}<\ldots$ and consider the
intervals $I_{i}$ ($i\geq 0$) as in the proof of Theorem 9. Together with the
$q_{i}$, they cover the whole of $\mathbb{R}_{\geq 0}$ as in the previous
proof.

However, the $S\cap I_{i}$ may still have $q_{i}$ and/or $q_{i+1}$ as limit
points, which means the $S\cap I_{i}$ need not be of type $\leq k$ but can
still be of type $k+1$, so the induction hypothesis cannot be applied to the
$I_{i}$. Therefore, for fixed $i$ and sufficiently small $\delta>0$ consider a
non-empty bounded and closed subinterval
$J_{i}=J_{i}(\delta)=[q_{i}+\delta,q_{i+1}-\delta]$ of $I_{i}$ (or, if the
number of limit points is a finite number $N$,
$J_{N}=J_{N}(\delta)=[q_{N}+\delta,\infty)$).

Now $S\cap J_{i}$ can no longer have $q_{i}$ and/or $q_{i+1}$ as limit points.
Hence, it is of type $\leq k$ and the induction hypothesis applies to $J_{i}$,
so $G$ is constant on $J_{i}$, say $G=C_{i}$ on $J_{i}$. Since $G$ is
continuous everywhere by Lemma 8$(i)$ and $\lim_{\delta\to
0}J_{i}=[q_{i},q_{i+1}]$ (or, if the number of limits points is $N$,
$\lim_{\delta\to 0}J_{N}=[q_{N},\infty)$), we get $G(q_{i})=C_{i}=G(q_{i+1})$.
The final step of the proof is the same as in the proof of Theorem 9. ∎

Unfortunately, the above result does not cover all monotone functions
$f:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$. Indeed, a monotone function may
be discontinuous on the set $\mathbb{Q}_{\geq 0}$ of non-negative rational
numbers, see, e.g., Rudin (1976), and $\mathbb{Q}_{\geq 0}$ is not first
species, since $\mathbb{Q}_{\geq 0}^{(1)}=\mathbb{R}_{\geq 0}$ and
$\mathbb{R}_{\geq 0}^{(1)}=\mathbb{R}_{\geq 0}$.

This limitation can be circumvented by appealing to a strong result of
Goldowski and Tonelli. Recall first that a function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ is differentiable _nearly everywhere_ if it
is differentiable except at a countable number of points. Note that _nearly
everywhere_ implies _almost everywhere_. We need

######  Theorem 11 (Goldowski (1928); Tonelli (1930-31); Saks (1937)).

Let $G:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ be a function such that

  * •

$G$ is continuous,

  * •

$G$ is differentiable nearly everywhere,

  * •

$G’\geq 0$ almost everywhere.

Then $G$ is monotone.

This leads directly from Lemma 8 to the desired conclusion.

######  Theorem 12.

Any two solutions $g$ of (2) differ by a constant.

###### Proof.

Let $g_{1}$ and $g_{2}$ be two solutions of (2) and let $G=g_{1}-g_{2}$. By
Lemma 8$(i)$ $G$ is continuous.

A monotone function is continuous nearly everywhere (see, e.g., Rudin (1976)).
So by Lemma 8$(ii)$ $G$ is differentiable nearly everywhere and $G’=0$ nearly
everywhere. Hence by Theorem 11 both $G$ and $-G$ are monotone, i.e., $G$ is
constant. ∎

The above theorem justifies item $(iii)$ of Theorem 1. The following result
summarizes the results of this section.

######  Theorem 13.

Inequality (2) holds iff $f$ is monotone and for some constant $C$

$g(x)=C+xf(x)-\int_{0}^{x}f(z)\>dz.$

###### Proof.

By Corollary 4, Lemma 5, and Theorem 12. ∎

##  5 Discussion

Results closely corresponding to our uniqueness result (Theorem 12) were also
presented in Krishna (2002) (and its second edition Krishna (2009)) and
Börgers (2015). (The customary name of these results is Revenue Equivalence.)
Krishna considers in Chapter 5 a setup with a seller that has one indivisible
object to sell and $n$ potential buyers, while Börgers considers in Chapter 2
a setup in which there is just one potential buyer. In Krishna (2009) the
equivalent of our function $f$ is defined as an integral representing the
probability that a buyer gets the object, while in Börgers (2015) $f$
corresponds to the probability of selling the object to the buyer. However, a
close inspection of the proofs of these Revenue Equivalence results reveals
that they do not depend on the actual form of $f$.

Further, ignoring the differences in the setup, the corresponding proofs in
both books are from the mathematical point of view essentially the same. As
the arguments in the latter one are more detailed, we discuss them here, but
using our notation.

The proof of the corresponding result (Proposition 2.2) in Börgers (2015) is
not based on the equivalent of our function $f$ but instead deals, in Lemma
2.2, with the function $u$ (representing utility) defined by

$u(x):=xf(x)-g(x),$

and states that for all $x$ for which $u$ is differentiable,

$u’(x)=f(x).$

Lemma 2.2 also establishes that the function $u$ is monotone and convex. Then
in Lemma 2.3 it is shown that

$u(x)=u(0)+\int_{0}^{x}f(z)dz,$

which is equivalent to (4) by taking $C=u(0)$, so the uniqueness result (Lemma
2.4 (Revenue Equivalence)) corresponding to our Theorem 12, follows.

Lemma 2.3 is a direct consequence of two results from Royden Fitzpatrick
(2010), namely, that convexity implies absolute continuity (a notion we leave
undefined here) and that every absolutely continuous function is equal to the
integral of its derivative.

Note, however, that the latter result (Theorem 10 of Royden Fitzpatrick
(2010)) is the Fundamental Theorem of Calculus (FTC) for the Lebesgue
integral, a fact not mentioned in Krishna (2002) and in Börgers (2015)
deducible only indirectly from footnote 2 in Chapter 2. So the proofs of the
uniqueness result (the Revenue Equivalence) presented in Krishna (2002) and
Börgers (2015) _crucially_ rely on the Lebesgue theory of integration. In
contrast, our proof is much more elementary: it does not rely on _any_ form of
integration and appeals only to the notion of derivative. Only the existence
result (Lemma 5) relies on the Riemann integral. Having said this, apart from
its complications, use of the Lebesgue integral yields a very efficient proof.

Both Krishna and Börgers establish in their books appropriate Revenue
Equivalence results for other mechanisms. In particular, Börgers considers in
Chapters 3 and 4 of Börgers (2015) Bayesian mechanisms and dominant
mechanisms, each time for $n$ buyers. In both cases he establishes the
corresponding Revenue Equivalence result (Lemma 3.4 and Proposition 4.2) by
explaining that the reasoning provided in Chapter 2 can be repeated.

Given that in both setups the crucial inequalities are the counterparts of (2)
(considered separately for each buyer), it follows that both results can be
alternatively proved using our Theorem 12. We conclude that our more
elementary approach can be applied to other mechanisms than the single-
parameter mechanism considered in Section 2.

Finally, we show that a generalization of Theorem 13 allows one to provide
alternative, more elementary proofs of Revenue Equivalence for two other types
of auctions, considered in Krishna (2009) in Chapters 14 and 16. These
auctions are concerned with multiple objects, leading to functions $f$ and $g$
having to deal with vectors.

We use the following notation. For functions $f:\mathbb{R}^{n}_{\geq
0}\to\mathbb{R}^{n}_{\geq 0}$ and $g:\mathbb{R}^{n}_{\geq
0}\to\mathbb{R}_{\geq 0}$ and $\textbf{x}\in\mathbb{R}^{n}_{\geq 0}$ we
introduce the functions $f_{\textbf{x}}:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq
0}$ and $g_{\textbf{x}}:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ defined by

$f_{\textbf{x}}(t)=f(t\textbf{x})\cdot\textbf{x},$

where $\cdot$ is the inner product (dot product), and

$g_{\textbf{x}}(t)=g(t\textbf{x}).$

We then say that $f:\mathbb{R}^{n}_{\geq 0}\to\mathbb{R}^{n}_{\geq 0}$ is
_monotone_ if for each $\textbf{x}\in\mathbb{R}^{n}_{\geq 0}$ the function
$f_{\textbf{x}}$ is monotone.

We now establish the following result which generalizes Theorem 13 to
dimension $n>1$. (Note that using the substitution $u(z)=zx$ we have
$\int_{0}^{x}f(u)\>du=\int_{0}^{1}f(zx)x\>dz$.)

######  Theorem 14.

For two functions $f:\mathbb{R}^{n}_{\geq 0}\to\mathbb{R}^{n}_{\geq 0}$ and
$g:\mathbb{R}^{n}_{\geq 0}\to\mathbb{R}_{\geq 0}$ the inequality

$\mbox{$\forall$}\textbf{x},\textbf{y}:g(\textbf{y})-g(\textbf{x})\geq(f(\textbf{y})-f(\textbf{x}))\cdot\textbf{x}$
(10)

holds iff $f$ is monotone and for some constant $C$

$g(\textbf{x})=C+f(\textbf{x})\cdot\textbf{x}-\int_{0}^{1}f(z\textbf{x})\cdot\textbf{x}\>dz.$
(11)

###### Proof.

First note that (10) holds iff

$\mbox{$\forall$}\textbf{x},x,y:g_{\textbf{x}}(y)-g_{\textbf{x}}(x)\geq
x(f_{\textbf{x}}(y)-f_{\textbf{x}}(x)),$ (12)

since for each $\textbf{x}\in\mathbb{R}^{n}_{\geq 0}$

$\mbox{$\forall$}x,y:g_{\textbf{x}}(y)-g_{\textbf{x}}(x)=g(y\textbf{x})-g(x\textbf{x})$

and by linearity of the inner product

$\mbox{$\forall$}x,y:x(f_{\textbf{x}}(y)-f_{\textbf{x}}(x))=(f(y\textbf{x})-f(x\textbf{x}))\cdot
x\textbf{x}.$

By Theorem 9 (12) holds iff for all x the function $f_{\textbf{x}}$ is
monotone and for some constant $C_{\textbf{x}}$

$g_{\textbf{x}}(x)=C_{\textbf{x}}+xf_{\textbf{x}}(x)-\int_{0}^{x}f_{\textbf{x}}(z)\>dz.$
(13)

But $C_{\textbf{x}}=g_{\textbf{x}}(0)=g(\mathbf{0})$, so the constant
$C_{\textbf{x}}$ does not depend on x. Further,
$g(\textbf{x})=g_{\textbf{x}}(1)$, and
$1f_{\textbf{x}}(1)=f(\textbf{x})\cdot\textbf{x}$, so by putting $x=1$ we see
that(13) implies (11).

But also (11) implies (13), which can be seen by using (11) with $x\textbf{x}$
instead of x.

∎

Let us return now to Krishna (2009). In Chapter 14 he studies multiunit
auctions in which multiple identical objects are available. The relevant
inequality (14.1) on page 204, capturing the expected payment in an
equilibrium for a player, corresponds to (10). Theorem 14 then provides an
alternative proof of his Proposition 14.1 stating that

> “The equilibrium payoff (and payment) functions of any bidder in any two
> multiunit auctions that have the same allocation rule differ at most by an
> additive constant.”

Krishna’s proof relies (implicitly) on the Lebesgue integral. We adopted from
his proof the idea of reasoning about the functions $f_{\textbf{x}}$ and
$g_{\textbf{x}}$. In Chapter 16 of his book he studies auctions in which one
can bid for a set of nonidentical objects. (They are called in the computer
science literature combinatorial auctions.) Krishna explains that “The proof
is _identical_ to that of Proposition 14.1.” (italic used by the author).
Consequently, our approach also yields an alternative proof of Revenue
Equivalence for combinatorial auctions.

## References

  * Archer Tardos (2001) AT01Archer, A. Tardos, É.  2001\.  Truthful Mechanisms for One-Parameter Agents Truthful mechanisms for one-parameter agents.  IEEE Symposium on Foundations of Computer Science (FOCS) IEEE Symposium on Foundations of Computer Science (FOCS) ( 482–491).  IEEE Computer Society.
  * Babaioff (2016) Bab16Babaioff, M.  2016\.  Truthful Mechanisms for One-Parameter Agents Truthful mechanisms for one-parameter agents.  Encyclopedia of Algorithms Encyclopedia of Algorithms ( 2267–2271).  Springer.
  * Börgers (2015) Bor15Börgers, T.  2015\.  An Introduction to the Theory of Mechanism Design An Introduction to the Theory of Mechanism Design.  Oxford University Press.
  * Bressoud (2008) Bre08Bressoud, D.  2008\.  A Radical Approach to Lebesgue’s Theory of Integration A Radical Approach to Lebesgue’s Theory of Integration.  Cambridge University Press.
  * Goffman (1977) Gof77Goffman, C.  1977\.  Bounded Derivative Which is Not Riemann Integrable Bounded derivative which is not Riemann integrable.  The American Mathematical Monthly843205-206.
  * Goldowski (1928) Gol28Goldowski, G.  1928\.  Note sur les dérivées exactes Note sur les dérivées exactes.  Rec. Math. Soc. Math. Moscou (Mat. Sbornik)3535-36.
  * Green Laffont (1977) GL77aGreen, JR. Laffont, JJ.  1977\.  Characterization of satisfactory mechanism for the revelation of preferences for public goods Characterization of satisfactory mechanism for the revelation of preferences for public goods.  Econometrica45427-438.
  * Groves (1973) Gro73Groves, T.  1973\.  Incentives in Teams Incentives in teams.  Econometrica41617–631.
  * Hartline Karlin (2007) HK07Hartline, JD. Karlin, AR.  2007\.  Profit Maximization in Mechanism Design Profit maximization in mechanism design.  N. Nisan, T. Roughgarden, É. Tardos VJ. Vazirani (), Algorithmic Game Theory Algorithmic Game Theory ( 331-361).  Cambridge University Press.
  * Krishna (2002) Kri02Krishna, V.  2002\.  Auction Theory Auction Theory.  Academic Press.
  * Krishna (2009) Kri09Krishna, V.  2009\.  Auction Theory Auction Theory (second ).  Academic Press.
  * Milgrom (2004) Mil04Milgrom, P.  2004\.  Putting Auction Theory to Work Putting Auction Theory to Work.  Cambridge University Press.
  * Myerson (1981) Mye81Myerson, R.  1981\.  Optimal Auction Design Optimal auction design.  Mathematics of Operations Research61.
  * Nisan (2007) Nis07Nisan, N.  2007\.  Introduction to Mechanism Design (for Computer Scientists) Introduction to mechanism design (for computer scientists).  N. Nisan, T. Roughgarden, É. Tardos VJ. Vazirani (), Algorithmic Game Theory Algorithmic Game Theory ( 209-241).  Cambridge University Press.
  * Roughgarden (2016) Rou16Roughgarden, T.  2016\.  Twenty Lectures on Algorithmic Game Theory Twenty Lectures on Algorithmic Game Theory.  Cambridge University Press.
  * Royden Fitzpatrick (2010) RF10Royden, H. Fitzpatrick, P.  2010\.  Real Analysis Real Analysis (fourth ).  Pearson.
  * Rudin (1976) Rud76Rudin, W.  1976\.  Principles of Mathematical Analysis Principles of Mathematical Analysis (third ).  McGraw-Hill.
  * Saks (1937) Sak37Saks, S.  1937\.  Theory of the Integral Theory of the Integral (second revised ).  New YorkHafner Publishing Company.  Reprinted by Hassell Street Press in 2021. Available at https://archive.org/details/theoryoftheinteg032192mbp/page/n7/mode/2up
  * Tao (2011) Tao11Tao, T.  2011\.  An Introduction to Measure Theory An Introduction to Measure Theory.  American Mathematical Society.
  * Tonelli (1930-31) Ton30Tonelli, L.  1930-31.  Sulle derivative esatte Sulle derivative esatte.  Mem. Istit. Bologna813-15.