A relay device includes the following elements. A use request receiver receives a use request to use a service to be provided by a service providing device from a client device. An allocation request sender sends an allocation request to allocate a usage amount of the service based on a usage amount indicated by usage amount information specified by the use request received by the use request receiver to a different relay device. An allocated amount receiver receives allocated amount information indicating an allocated usage amount for the service sent from the different relay device in response to the allocation request. A return information generator generates return information from the allocated amount information received from the allocated amount receiver and a usage amount of the service. A return information sender sends the return information generated by the return information generator to the different relay device.